Бесконечный цикл с указателями — почему?

Я относительно новичок в C и указателях. Я пытаюсь отсортировать, а затем распечатать связанный список структур. Либо я пропускаю логическую ошибку, либо я не совсем понимаю указатели. Может кто-нибудь объяснить мне, что мне не хватает в этом коде? Заранее благодарю!

// *** Sort Linked List ( Merge Sort ) ***

struct address_node *newRoot;

// ptr, rearPtr, and tempRoot are also struct Pointers
newRoot = root;
root = root->next;

while (root != NULL)
{
    tempRoot = root;
    ptr = newRoot;
    rearPtr = newRoot;

    while (ptr != NULL)
    {
        printf("here");
        if ((root->frequency) == (ptr->frequency))
        {                       // SPECIAL CASE: To determine read hierarchy for repeated
                                // Entries
            if ((root->read_order) < (ptr->read_order))
            {
                if (ptr == newRoot)
                {
                    root = root->next;
                    tempRoot->next = newRoot;
                    newRoot = tempRoot;
                    ptr = NULL;
                }
                else
                {
                    root = root->next;
                    tempRoot->next = ptr;
                    rearPtr->next = tempRoot;
                    ptr = NULL;
                }
            }
        }
        else if ((root->frequency) > ptr->frequency)
        {                       // To ADD BEFORE an ENTRY
            if (ptr == newRoot)
            {
                root = root->next;
                tempRoot->next = newRoot;
                newRoot = tempRoot;
                ptr = NULL;
            }
            else
            {
                root = root->next;
                tempRoot->next = ptr;
                rearPtr->next = tempRoot;
                ptr = NULL;
            }
        }
        else if (ptr->next == NULL)
        {                       // if END OF LIST
            root = root->next;
            ptr->next = tempRoot;
            ptr = NULL;
        }
        else
        {                       // SPOT NOT FOUND YET< MOVE FORWARD THROUGH LIST
            rearPtr = ptr;
            ptr = ptr->next;
        }
    }
}

// *** PRINT ***
ptr = newRoot;
if (numOut == 0)
{
    while (ptr != NULL)
    {
        printf("0x%zx :%d\n", ptr->address, ptr->frequency);
        ptr = ptr->next;
    }
}
else
{
    while (ptr != NULL && numOut > 0)
    {
        printf("0x%zx :%d\n", ptr->address, ptr->frequency);
        numOut--;
        ptr = ptr->next;
    }
}

c infinite-loop pointers
person Molly Lingham    schedule 07.10.2013    source источник
comment
В настоящее время цикл никогда не выходит?   -  person canhazbits    schedule 07.10.2013
comment
Первое, что нужно сделать, это написать две отдельные функции (как минимум): одну для сортировки слиянием связанного списка и одну для печати связанного списка. Вы будете использовать функцию печати для печати связанных списков на различных этапах при отладке кода сортировки. Функции должны принимать список (и, в случае функции печати, я рекомендую «тег» — строку символов, которая будет напечатана перед содержимым списка — и, возможно, также файловый поток: void print_list(const char *tag, struct address_node const *list) или void print_list(FILE *fp, const char *tag, struct address_node const *list)).   -  person Jonathan Leffler    schedule 07.10.2013
comment
Классический алгоритм сортировки слиянием для списка разбивает заданный список на два отдельных списка, сортирует слиянием каждый из отдельных списков (рекурсия), а затем объединяет полученные отсортированные отдельные списки в выходной список. Ваш код не соответствует этой модели. Найдите [c] merge sort list в поле поиска SO. Это может привести к использованию сортировки слиянием для сортировки связанных списков и, возможно, к другие вопросы тоже.   -  person Jonathan Leffler    schedule 07.10.2013
comment
@JonathanLeffler Спасибо за ответ и совет! Я знаю, что алгоритм сортировки не следует сортировке слиянием. Я забыл стереть эту закомментированную строку. Для логики, которую я пытался использовать для сортировки: я намеревался вытащить узлы из исходного связанного списка и отсортировать их 1 на 1 в связанный список newRoot. Как вы понимаете, где-то по пути не совсем получилось. Мне придется перечитать вашу ссылку и посмотреть, смогу ли я ее четко понять (ты за ее публикацию).   -  person Molly Lingham    schedule 07.10.2013

Ответы (2)


arrow_upward
1
arrow_downward

Все ваши указатели, похоже, указывают на одно и то же, root. Таким образом, в одном случае root перемещается вперед, но затем вы указываете root-> next указывает на то, что находится за корнем. поэтому представьте, что root указывает на bob, а root->next указывает на bill, предположим, что ваше первое гнездо ifs все оказывается истинным, root = bill, но root->next = bob. Никакого движения вперед не происходит.

person czifro    schedule 07.10.2013

arrow_upward
0
arrow_downward

Вы не гарантируете, что root обновляется на каждой итерации внутреннего цикла. Например, учитывая этот инструментальный вариант вашего кода:

#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>

struct address_node
{
    struct address_node *next;
    int frequency;
    int read_order;
};
static void sort_list(struct address_node * *root);
static void print_list(char const *tag, struct address_node const *root);

int main(void)
{
    struct address_node data[] =
    {
        { &data[1], 43, 0 },
        { &data[2], 23, 1 },
        { &data[3], 13, 2 },
        { &data[4], 27, 3 },
        { &data[5], 57, 4 },
        { &data[6], 17, 5 },
        { &data[7], 27, 6 },
        { &data[8], 20, 7 },
        { &data[9], 30, 8 },
        {     NULL, 50, 9 },
    };
    struct address_node *root = &data[0];

    print_list("Before", root);
    sort_list(&root);
    print_list("After", root);
}

static void sort_list(struct address_node **proot)
{
    struct address_node *root = *proot;
    struct address_node *newRoot;
    struct address_node *ptr;
    struct address_node *rearPtr;
    struct address_node *tempRoot;

    printf("-->> %s: root 0x%.12" PRIXPTR "\n", __func__, (uintptr_t)root);
    newRoot = root;
    root = root->next;


    while (root != NULL)
    {
        tempRoot = root;
        ptr = newRoot;
        rearPtr = newRoot;

        while (ptr != NULL)
        {
            printf("here  1: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
            if (root->frequency == ptr->frequency)
            {
                printf("here  2: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                if (root->read_order < ptr->read_order)
                {
                    if (ptr == newRoot)
                    {
                        root = root->next;
                        tempRoot->next = newRoot;
                        newRoot = tempRoot;
                        ptr = NULL;
                        printf("here 2A: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                    }
                    else
                    {
                        root = root->next;
                        tempRoot->next = ptr;
                        rearPtr->next = tempRoot;
                        ptr = NULL;
                        printf("here 2B: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                    }
                }
                else
                    printf("here 2C: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
            }
            else if (root->frequency > ptr->frequency)
            {
                printf("here  3: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                if (ptr == newRoot)
                {
                    root = root->next;
                    tempRoot->next = newRoot;
                    newRoot = tempRoot;
                    ptr = NULL;
                    printf("here 3A: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                }
                else
                {
                    root = root->next;
                    tempRoot->next = ptr;
                    rearPtr->next = tempRoot;
                    ptr = NULL;
                printf("here 3B: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                }
            }
            else if (ptr->next == NULL)
            {
                printf("here  4: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                root = root->next;
                ptr->next = tempRoot;
                ptr = NULL;
            }
            else
            {
                printf("here  5: root 0x%.12" PRIXPTR "\n", (uintptr_t)root);
                rearPtr = ptr;
                ptr = ptr->next;
            }
        }
    }
    *proot = root;
    printf("<<-- %s: root 0x%.12" PRIXPTR "\n", __func__, (uintptr_t)root);
}

static void print_list(char const *tag, struct address_node const *root)
{
    printf("%s: 0x%.12" PRIXPTR "\n", tag, (uintptr_t)root);
    while (root != NULL)
    {
        printf("0x%.12" PRIXPTR " : %2d %2d\n",
              (uintptr_t)root, root->frequency, root->read_order);
        root = root->next;
    }
}

Вывод, который я получаю, начинается:

Before: 0x7FFF5382D440
0x7FFF5382D440 : 43  0
0x7FFF5382D450 : 23  1
0x7FFF5382D460 : 13  2
0x7FFF5382D470 : 27  3
0x7FFF5382D480 : 57  4
0x7FFF5382D490 : 17  5
0x7FFF5382D4A0 : 27  6
0x7FFF5382D4B0 : 20  7
0x7FFF5382D4C0 : 30  8
0x7FFF5382D4D0 : 50  9
-->> sort_list: root 0x7FFF5382D440
here  1: root 0x7FFF5382D450
here  5: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450
here  1: root 0x7FFF5382D450
here  2: root 0x7FFF5382D450
here 2C: root 0x7FFF5382D450

После этого интереснее не становится. Я считаю, что вам нужен внутренний цикл для продвижения вперед на каждой итерации, поэтому вам нужно убедиться, что root обновляется каждый раз. Пункт else (5) вообще не меняет root; то же самое относится и к пункту (2C). Итак, вам нужно вернуться и убедиться, что root обновляется соответствующим образом на каждой итерации. Если изменение всегда root = root->next;, следует проверить, подходит ли цикл for с root = root->next в качестве условия повторной инициализации.

person Jonathan Leffler    schedule 07.10.2013