Сортировка Вставка в связный список

Question

ССХ,

Я пытаюсь отладить проблему в моем круговом связанный списке для 12hrs в настоящее время. Функция принимает ADT, у которого есть начало и поле курсора. Начальная фиктивная ячейка указывает на себя. Вставить элементы. Элементы повторения не допускаются.

int setInsertElementSorted(setADT buffer, setElementT E) 
    { 
     bool isUnique = true; 
     cellT *previous; 

     previous = buffer->start; 
     buffer->cursor = buffer->start->next; 

     while(buffer->cursor != buffer->start){ 
      if(buffer->cursor->value == E){ 
       isUnique = false; 
      } else if(E < buffer->cursor->value) 
       break; 
       else { 
       previous = buffer->cursor; 
       buffer->cursor = buffer->cursor->next; 
      } 
     } 

     if(isUnique != false){ 
      cellT *newNode = malloc(sizeof(cellT)); 
      newNode->value = E; 
      previous->next = newNode; 
      newNode->next = buffer->cursor; 

      buffer->count++; 
      return (buffer->count); 
      } 
    } 

Код принимает целую серию и затем сортирует их в параметр LL. Предполагается, что он будет использоваться для набора (следовательно, почему нет повторных записей).

Выход для: 9, 8, 7, 6, 5, 4, 3, 2, 1

есть .. 3, 4, 5, 6, 7, 8, 9 (что случилось с первые два значения)

При вводе что-то вроде: 7, 3, 5, 1, 9, 2

из всего 7, 9 (так что он не может обрабатывать значения, разделенные более чем один .. оо)

Дополнительная информация:

typedef struct cellT { 
    int value; 
    struct cellT *next; 
} cellT; 

struct setCDT{ 
    int count; 
    cellT *start; 
    cellT *cursor; 
}; 

setADT setNew() 
{ 
    setADT newNode = malloc(sizeof(struct setCDT)); 
    newNode->start = newNode->cursor = malloc(sizeof(cellT)); 
    newNode->start->next = newNode->cursor->next = newNode->start; 
    newNode->count = 0; 
    return (newNode); 
} 

setADT - указательный тип для установкиCDT. setElementT, однако, является простым и простым int. Извините за двусмысленность.

Answer 1

Некоторые наблюдения:

while(buffer->cursor != buffer->start && buffer->cursor->value < E){ 
    if(buffer->cursor->value == E) // never true 

value == E внутри первого цикла никогда не верно, так как условие цикла имеет value < E, следовательно, встречая значение, равное E бы остановить итерации. Измените условие цикла на <= E и просто return, если найден дубликат вместо flag.

Путь, где flag == false также не возвращает значение (хотя из-за указанной выше ошибки он не доступен в данный момент), а также памяти, выделенной для newNode утечек, если ошибка с flag является фиксированной и E существует в список уже.

Следующая if кажется бессмысленным, и из-за не { после else отступы не вводить в заблуждение:

if(buffer->cursor != buffer->start){ 
    newNode->next = buffer->cursor; // would be harmless in both branches 
    previous->next = newNode;  // done in both branches 
} else        // always using { } would make this clear 
    previous->next = newNode; 
    buffer->count++; 
    return (buffer->count); 

Кроме того, не определение типа во setADT как тип указателя, это просто заблуждение, и в сочетании с конструкциями, такими как New(setADT) почти наверняка вызывает ошибки.

Между тем в setNew, так как существует только один узел, замените newNode->start->next = newNode->cursor->next = newNode->start; на newNode->start->next = newNode->start;

Сводка изменений:

int setInsertElementSorted(struct setCDT * const buffer, const int E) { 
    cellT *newNode; 
    cellT *previous = buffer->start; 
    buffer->cursor = previous->next; 

    while (buffer->cursor != buffer->start && buffer->cursor->value <= E) { 
     if (buffer->cursor->value == E) { 
      return buffer->count; // duplicate value 
     } 
     previous = buffer->cursor; 
     buffer->cursor = buffer->cursor->next; 
    } 
    if ((newNode = malloc(sizeof(*newNode)))) { 
     newNode->value = E; 
     newNode->next = buffer->cursor; 
     previous->next = newNode; 
     buffer->count++; 
    } 
    return buffer->count; 
} 

Если ошибка не устранена, то ошибка может быть в другом месте.

код для проверки:

int main (int argc, char **argv) { 
    struct setCDT *list = setNew(); 
    for (int i = 1; i < argc; ++i) { 
     setInsertElementSorted(list, atoi(argv[i])); 
    } 
    list->cursor = list->start; 
    while ((list->cursor = list->cursor->next) != list->start) { 
     (void) printf("%d\n", list->cursor->value); 
    } 
    return EXIT_SUCCESS; 
}