Почему этот кусок кода C оказывается в бесконечном цикле?

Question

Я пытался исправить бесконечный цикл в этом коде.Однако я не мог понять, почему возникает бесконечный цикл.Этот код пытается отсортировать задания от наименьшего к наивысшему перед обработкой.

SortJobs()
{
    linked_list ptr, h, temp, pptr;
    int i, j;

    pptr = ready_queue;
    ptr = ready_queue->next;
    h= ready_queue;

    while(ptr != NULL) {    
        if ((ready_queue->pcb.job_length - ready_queue->pcb.run_time) > (ptr->pcb.job_length - ptr->pcb.run_time)) {
            ready_queue = ptr;
            pptr->next = ptr->next;
            ptr->next = h->next;                
            h->next = pptr->next;
            pptr->next = h;
            ptr=h->next;
            h=ready_queue;
            pptr=ptr->next;
        } else {
            pptr = ptr;
            ptr=ptr->next;          
        }
    }
}

Answer 1

gdb ваш друг для устранения таких проблем. Пожалуйста, начните использовать отладчики!

OTOH, это circular-(linked)-list ?!

СОВЕТ: перед запуском SortJobs(), не могли бы вы пройти через ваш ready_queue и распечатать все элементы и посмотреть, идет ли он в бесконечном цикле ?!

Причиной бесконечного цикла может быть то, что вы не установили последний узел в вашем связанном списке на NULL. Вы можете проверить свою функцию addNode().

Answer 2

Я нахожу ваш алгоритм очень запутанным, и я думаю, что он также неверен.Предположим, что цикл как-то заканчивается, и вы все сделали правильно, в результате вы получите первый элемент с минимальным значением job_length - run_time, но остальная часть списка не будет упорядочена.

Как указал Руах, проблема в том, что вы запутываете свой список, перебирая весь следующий указатель, вы слишком усложняете вещи!Я бы не стал касаться структуры самого списка, перемещая целые узлы, а использовал memcpy и перемещал только данные, переносимые узлами.Вот примерная функция:

// I assume your linked list is made of nodes such as this
typedef struct {
    struct Node next;
    struct Node prev;     // optional
    struct Somewhat pcb;
} Node;

void swapData(Node *n1, Node *n2)
{
    struct pcb temp;

    memcpy(&temp, n1->pcb, sizeof(struct Somewhat));
    memcpy(n1->pcb, n2->pcb, sizeof(struct Somewhat));
    memcpy(n2->pcb, &temp, sizeof(struct Somewhat));
}

Теперь, когда мы можем правильно поменять узлы, я бы использовал некоторый хорошо проверенный / хорошо известный алгоритм сортировки, так что вы найдете помощь проще иследующий, кто будет смотреть на твой код, не будет искушать себя убить (не в обиду, я просто шучу;)).Позвольте мне предложить несколько простых алгоритмов, таких как Выбор сортировки или Пузырьковая сортировка .Не очень быстро, но легко реализуемо:)

Answer 3

Проблема, которая выделяется, заключается в том, что за этой строкой:

    pptr=ptr->next;

иногда может следовать эта строка:

    pptr->next = ptr->next;

без изменений на pptr или ptrмежду.Это приведет к маленькому круговому связанному списку с одним узлом, с ptr->next->next == ptr->next.Так что вы никогда не сможете выйти из связанного списка.

В целом, я нахожу ваш алгоритм очень запутанным.Вам действительно нужно определиться с одним логическим значением для каждой переменной и придумать соответствующие инварианты цикла.Например, в конце итерации цикла у вас иногда будет ptr == pptr->next (что, я думаю, правильно), но иногда pptr == ptr->next (что, я уверен, неправильно, по причине, указанной выше).

Answer 4

Потому что ptr всегда не равно нулю ??