1

I am trying to make a circular linked list in C, but i'm having some trouble. I'm pretty sure it's a pointer issue (I am learning C and pointers are a weakness). here is the code:

#include <stdio.h>
#include <stdlib.h>
#include "cl.h"

nodeptr add_to_end(nodeptr head, int val)
{
    if (head == NULL)
    {
        nodeptr new_node = (nodeptr)malloc(sizeof(node));
        new_node->data = val;
        new_node->next = NULL;
        return new_node;
    } else {
        head->next = add_to_end(head->next,val);
        return head;
    }
}


void print_piles(nodeptr nodeHead)
{
    if (nodeHead == NULL)
        return;
    printf("%d\n ",nodeHead->data);
    print_piles(nodeHead->next);
}



int main(int argc, char *argv[])
{
    nodeptr head = NULL;
    nodeptr tail = NULL;
    int i = 0;

    head = add_to_end(head,i);
    i++;
    tail = add_to_end(tail,i);
    head->next = tail;
    i++;
    tail = add_to_end(tail,i);
    tail->next = head;

    printf("%d\n ",head->data);
    printf("%d\n ",tail->data);
    tail = tail->next;
    printf("%d\n ",tail->data);
    return 0;
}

and from cl.h:

// create struct for cards in piles
;typedef struct node
{
    int data;
    struct node *next;
}node, *nodeptr;

the output is: 

0
1
0

What I expect to get is:

0
1
2

What do I need to change?

4

4 回答 4

5

不是指针问题！您正在获得定义的行为。但是您循环链接的步骤是错误的。阅读下面我解释了你的main()功能步骤：

步骤1： 

i = 0;
head = add_to_end(head,i);

于是创建了一个head节点（假设节点地址为201）：

head: 201
[ 0, NULL]

第2步： 

i++;
tail = add_to_end(tail,i);

于是创建了一个tail节点（假设节点地址为304）：

tail: 304
[ 1, NULL]

步骤3：
分配后 head->next = tail;：：链表类似于：

head: 201     tail: 304 
[ 0, 304] --► [1, NULL]

Step-4： 在以下两个代码序列之后：

i++;
tail = add_to_end(tail,i);

您已经在链表中创建了一个新节点并附加了带有值的节点2（假设是地址 349），列表是这样的：

head: 201     tail: 304         : 349
[ 0, 304] --► [ 1, 349] --► [ 2, NULL]

第5步：
现在错误：tail值仍然是304根据您的添加功能，所以在最后一次分配后，tail->next = head;您得到如下内容：

head: 201     tail: 304         : 349
[ 0, 304] --► [ 1, 349]    [ 2, NULL]
   ▲             |
   +-------------+

所以next of tail is head这就是为什么你得到0, 1, 0输出。

还要注意你有内存泄漏！

为什么会这样？add 函数最后附加一个节点并返回head传递给您正在传递的函数tail（我正在评论）。

nodeptr add_to_end(nodeptr head, int val)
{                     //    ^ is tail at third call
    if (head == NULL)// if first node is NULL
    {
        nodeptr new_node = (nodeptr)malloc(sizeof(node));
        new_node->data = val;
        new_node->next = NULL;
        return new_node; <-- "return only if new node is first node"
    } else {
        head->next = add_to_end(head->next,val);
        return head; <--- "Return `head` that is passed to function at calling"
    }
}

因此，当您调用tail = add_to_end(tail, i);where tailis not NULL 时，函数 add_to_end 返回较旧的tail（在我的示例中地址为 304）。

你应该更正tail->next = head;，tail->next->next = head;你会得到例外的结果。

于 2013-09-20T04:44:10.907 回答
0

如果你打算学习 C，通过实现一个循环链表，你应该尝试正确实现它，而不是通过 tail->next = header 将非循环列表强制转换为循环列表，因为如果你尝试添加一个之后将项目添加到列表中，您将获得无限递归挂起，有点无限循环，因为您的算法检查 NULL 作为终止条件。

一个循环列表，有一个指向头部和尾部的指针，当你到达最后一个节点时，你通过比较当前节点和尾部来结束。

于 2013-09-20T04:47:12.727 回答
0 
int main(int argc, char *argv[])
{
    nodeptr head = NULL;
    nodeptr tail = NULL;
      nodeptr tail1 = NULL;

    int i = 0;

    head = add_to_end(head,i);
    i++;
    tail = add_to_end(tail,i);
    head->next = tail;
    i++;
    tail1 = add_to_end(tail1,i);
    tail->next = tail1;
    tail1->next= head;

    printf("%d\n ",head->data);
    printf("%d\n ",tail->data);
    tail = tail->next;
    printf("%d\n ",tail->data); 

    return 0;
}
于 2013-09-20T04:55:33.527 回答
0

您需要
tail = tail->next在这两行之间添加：

tail = add_to_end(tail,i);
tail->next = head;

并使用 tail->next 获取新节点。

因此，将主代码更新为 -

int main(int argc, char *argv[])
{
    nodeptr head = NULL;
    nodeptr tail = NULL;
    int i = 0;

    head = add_to_end(head,i);
    i++;
    tail = add_to_end(tail,i);
    head->next = tail;
    i++;

    // Add new node to current tail's next
    tail->next = add_to_end(tail,i);
    // Change tail to point to latest added node
    tail = tail->next
    tail->next = head;

    printf("%d\n ",head->data);
    printf("%d\n ",tail->data);
    tail = tail->next;
    printf("%d\n ",tail->data);
    return 0;
}
于 2013-09-20T04:37:31.633 回答