Бинарный поиск, strcmp два динамических массива строк в C - PullRequest
Новая
       14

Бинарный поиск, strcmp два динамических массива строк в C

0 голосов
/ 01 апреля 2012

Я довольно новичок в программировании на С, но стараюсь изо всех сил понять это. У меня есть две динамические строки, которые заполняются из двух текстовых файлов. Один из них является формой словаря, а другой - просто пользовательский ввод. То, что я хочу получить, - это двоичный поиск по каждому вводимому пользователем слову в словаре и выяснение, присутствует ли оно (вроде как проверка орфографии).

Я застрял в своей функции двоичного поиска: 

char **dictElem;
int dictSize;
char **inputElem;

int binsearch(const char *val){
  int pos;
  int beg=0;
  int end=dictSize-1;
  int cond=0;

  while (beg<=end){
    pos=(beg+end)/2; //Jump in the middle
    if ((cond=strcmp(dictElem[pos],val)) == 0)
      return pos;
    else if (cond<0)
      beg=pos+1;
    else
      end=pos-1;
  }
  return 0;
}

Оба dictElem и inputElem уже были прочитаны другими методами, и (скажем) оба элемента [0] являются одинаковыми строками "aa".

Однако после запуска binsearch(inputElem[0] всегда возвращается 0. Я попробовал просто strcmp(dictElem[0],inputElem[0]), и он возвращает 1.

Куда я иду не так? Это сравнивает char ** и char *?

UPD: Функция, которая загружает dictElem

void readd(FILE *file){
  int i=0,size=0; /* local size */
  char line[1024]; /* Local array for a single word read */
  printf("Loadingn dict...\n");
  while ((fgets(line,sizeof(line),file))!=NULL){
    dictElem=(char**)realloc(dictElem,(size+1)*sizeof(char *));
    dictElem[size++]=strdup(line);
  }
  printf("Total elements loaded: %d\n",size);
}

Функция, которая читает пользовательский файл, очень похожа, только немного в другом формате.

Ответы [ 2 ]

2 голосов
/ 01 апреля 2012

Проблема с вашим кодом в этой строке if ((cond=strcmp(dictElem[pos],val) == 0)).Эта строка кода присваивает результат выражения strcmp(dictElem[pos], val) == 0 переменной cond, а затем проверяет, равен ли cond нулю или нет.Я предполагаю, что ваше первоначальное намерение состояло в том, чтобы сохранить в cond результат strcmp, поэтому вы должны переместить закрывающую скобку перед ==.Правильная строка: if ((cond = strcmp(dictElem[pos], val) == 0).

Есть и другие проблемы с вашим кодом:

  1. 0 используется в качестве специального не найденного значения, но в то же время 0 может бытьвозвращается, когда элемент найден с индексом 0.
  2. Использование char *val, когда лучше использовать const char *val, потому что содержимое этой строки не будет изменено.Всегда лучше написать правильный код.
1 голос
/ 01 апреля 2012

Ваша проблема в этой строке: 

if ((cond=strcmp(dictElem[pos],val) == 0))

В скобках указан неверный порядок вычисления, и cond всегда будет 0 или 1 (потому что вы присваиваете результаты сравнения strcmp () == 0 к нему).Попробуйте вместо этого: 

if ((cond=strcmp(dictElem[pos],val)) == 0)
...