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

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

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;          
        }
    }
}

c loops infinite swap
person cmsl    schedule 09.01.2012    source источник
comment
Вы пытались выполнить код в отладчике?   -  person Oliver Charlesworth    schedule 09.01.2012

Ответы (4)


arrow_upward
1
arrow_downward

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

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

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

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

person Sangeeth Saravanaraj    schedule 09.01.2012
comment
пошаговое выполнение кода, чтобы увидеть, что ptr становится после каждого цикла, очень полезно - person tehdoommarine; 09.01.2012

arrow_upward
0
arrow_downward

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

person craig1231    schedule 09.01.2012

arrow_upward
0
arrow_downward

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

    pptr=ptr->next;

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

    pptr->next = ptr->next;

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

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

person ruakh    schedule 09.01.2012

arrow_upward
0
arrow_downward

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

Как указал ruakh, проблема в том, что вы путаете свой список, возясь со всем следующим указателем, вы слишком усложняете вещи! Я бы не стал трогать структуру самого списка, перемещая целые узлы, а использовал бы 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));
}

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

person BlackBear    schedule 09.01.2012