Infinite Loop with Pointers - Why?

Question

I am relatively new to C & pointers. I am trying to sort and then print a linked list of structs. Either I am missing a logical error or I am not fully understanding pointers. Can someone please explain to me what I am missing in this code? Thank you kindly in advance!

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

The first thing to do is to write two separate functions (at minimum), one to merge sort a linked list, and one to print a linked list. You'll use the print function to print linked lists at various stages while debugging your sorting code. The functions should take a list (and, in the case of the printing function, I recommend a 'tag' — a character string that will be printed out before the list contents — and perhaps the file stream too: void print_list(const char *tag, struct address_node const *list) or void print_list(FILE *fp, const char *tag, struct address_node const *list)). — Jonathan Leffler
– Jonathan Leffler, Commented Oct 7, 2013 at 0:31
The classic merge sorting algorithm for a list splits the given list into two separate lists, merge sorts each of the separate lists (recursion), and then merges the resulting sorted separate lists into the output list. Your code does not seem to follow that model. Please look up [c] merge sort list in the SO search box. It might lead you to Using mergesort to sort linked lists, and possibly to other questions too. — Jonathan Leffler
– Jonathan Leffler, Commented Oct 7, 2013 at 0:35
@JonathanLeffler Thank you for replying and the advice! I know the sorting algorithm doesn't follow merge sort. I had forgotten to erase that commented line. For the logic I was trying to use to sort: I was intending to pull nodes off the original linked list, and sort them 1 by 1 into a newRoot linked list. As you know, it didn't quite work out somewhere along the way. I'll have to re-read your link and see if I can understand it clearly (ty for posting it). — Molly Lingham
– Molly Lingham, Commented Oct 7, 2013 at 0:49

czifro · Accepted Answer · 2013-10-07 01:10:56Z

1

All your pointers seem to be pointing to the same thing, root. So in one instance root gets moved forward, but then you point root->next points to whats behind root. so imagine that root points to bob and root->next points to bill, assume your first nest of ifs all turn up true, root = bill but root->next = bob. No forward movement is being made.

answered Oct 7, 2013 at 1:10

czifro

7847 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jonathan Leffler · Accepted Answer · 2013-10-07 01:26:25Z

You are not ensuring that root is updated on every iteration of the inner loop. For example, given this instrumented variation on your code:

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

The output I get starts:

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

It doesn't get any more exciting after this. You need the inner loop to progress forward on every iteration, I believe, so you need to ensure that root is updated each time around. The else clause (5) does not alter root at all; neither does the (2C) clause. So, you need to go back and ensure that root is updated appropriately on every iteration. If the change is always root = root->next;, you should investigate whether a for loop with root = root->next as the reinitialization condition is appropriate.

Collectives™ on Stack Overflow

Infinite Loop with Pointers - Why?

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related