Бинарный поиск со строками


Я написал быстрый и грязный программу, которая выполняет бинарный поиск с упорядоченный массив (список) из строки c стиль. Например:

{"1", "12", "23", "124"} и т. д. (Хотя мой входной набор является на самом деле очень разные)

Примечание:

  1. Извиняюсь за непонятные названия - строка не является строкой, строку->идентификатор является. (Как я уже сказал, Я починил очень быстро, так как я писала в более крупную программу). Предположим, что все переменные были объявлены.

  2. Меня интересует только программа (кусок) правильность и эффективность алгоритма (например - игнорировать множественные возвраты и т. д.) На данный момент.

  3. Не беспокойтесь о вызовах функций, как log() или макросы, которые я использовал. Низ и верх рассчитываются с stringEntries.

  4. Подумайте, как это будет перерыв. Не беспокойтесь об остальном программа - просто сосредоточиться на этот кусок!

  5. пид - это ваш входной строки. Мы ищем через "строку"с атрибута "идентификатор" (который является строкой). Предположим, что "струна" на самом деле нечто иное, как указатель на структуру struct или что-то с членом "ID", который представляет собой строку в стиле C (оканчивающуюся нулем и все).

  6. лен на самом деле функция strlen(пид).

    while (TRUE)
            {                   

      *string = &stringEntries[mid = (bottom + top) / 2];

       if (*string == NULL) {
              Log(DEBUG, _ERROR,”*string is NULL\n”);
              return ERROR;                   
       }
       else if ((*string)->ID == NULL) {
              Log(DEBUG, _ERROR,”(*string)->ID is NULL\n”);
              return ERROR;
       }                                          

       if (!(diff = strcmp(pID, (*string)->ID)))                           
               diff = len - strlen((*string)->ID);                                          

       if (!diff) return PRESENT;                                        

       if (bottom == top) {
              if (diff > 0) 
                     (*string)++;  //ignore this bit - i need it later on                         
                     return NOT_PRESENT;                   
       }                   

       if (diff > 0){                           
              if (bottom == mid) bottom++;                           
              else  bottom = mid;                   
       }
       else        top = mid;           
    }


2093
3
задан 18 октября 2011 в 03:10 Источник Поделиться
Комментарии
1 ответ

Существует недостаточно информации, чтобы дать реальный отзыв.
Если вы заполните всю информацию, тип и сделать его функция компилируется рассмотрим ваш алгоритм, но опираться на имеющийся код единственное, что я могу рассмотреть-это стиль.


  • C и C++ - два совершенно разных языков.


    • Выбрать одну и изучить ее.
      Синтаксис может быть внешне одинаковыми, но как вы используете его не будет.
      Я сделаю мои комментарии предполагая, что вы пытаетесь писать на C++, а не С.


  • Ваш макет настолько ужасное, что его практически нечитаемым.


    • Выбрать один из общих отступов стиль
      Если это проблема с вырезать и вставить затем узнать, как использовать ваш редактор, так что вы можете вырезать/вставить без вкладок на сайте.


Комментарий

while (TRUE)

C++ имеет свои собственные логические типы. истина/ложь

        {                  

Ужасное форматирование. Выше '{' изрезана способ далеко, особенно по отношению к линии, это инкапсуляция.

  *string = &stringEntries[mid = (bottom + top) / 2];

Задание внутри [] разрешено, но делает код трудно читать.
Предпочитаю не делать что-то гораздо более читабельным, чтобы разделить его на две линии.
Вы не платят, чтобы написать компактный код вам платят, чтобы написать простой в обслуживании код.

   if (!(diff = strcmp(pID, (*string)->ID)))                           
diff = len - strlen((*string)->ID);

Ваш именования переменных здесь делает этот код нечитаемым.
Сделайте ваши имена переменных очевидна.
Не повторно использовать переменные. В приведенном выше коде это выглядит как разница используется для двух различных целей (или нет?). Позволить компилятору оптимизировать дополнительные места нужно будет сделать код понятным.

   if (bottom == top) {
if (diff > 0)
(*string)++; //ignore this bit - i need it later on
return NOT_PRESENT;

Абсолютный провал.
Этот абзац говорит о том, что мы вернемся, когда (разн > 0), но код не собирается это сделать, как только первый оператор после если заявление относится к блок if. Всегда предпочитаю использовать блоки операторов после структур управления. Даже если они одна вкладыши (некоторые люди до сих пор использовать многострочный макрос, который будет сломать ваш код, если вы не поместите его в '{' '}'

   if (diff > 0){                           
if (bottom == mid) bottom++;
else bottom = mid;
}
else top = mid;

Более едва читаемый код.
Хороший расклад будет хорошо. Есть и другие конструкции, которые помогут:

  if (diff > 0)
{
bottom = ( bottom == mid) ? bottom + 1 : mid;
}
else
{
top = mid;
}

2
ответ дан 18 октября 2011 в 03:10 Источник Поделиться