1

I am creating a simple linklist of integers and then reversing it. While reversing, last integer in original list is not getting printed. Instead a garbage value is printed. Here is the code:

#include<stdio.h>
#include<stdlib.h>
struct list
{
    int node;
    struct list *next; 
};

void insert(struct list **, int);
void print(struct list *);

int main()
{
    struct list *mylist= NULL, *tmp = NULL;

    insert(&mylist, 10);

    tmp = mylist;
    insert(&mylist, 20);
    insert(&mylist, 30);
    insert(&mylist, 40);
    insert(&mylist, 50);
    insert(&mylist, 60);
    insert(&mylist, 70);
    mylist=tmp;
    reverse(&mylist);
    printf("hello  ");
    print(mylist);

    return 0;
}

void reverse(struct list **temp)
{
    struct list **pre, **aft, **head;
    *pre = NULL;
    *head = *temp;
    if(*head == NULL )
        {
        return;
        }
    else
    {
        while((*head)!= NULL)
        {

        *aft =(*head)->next;

        (*head)->next = *pre;
        *pre = *head;
        *head = (*aft);
         printf("%d\t",(*pre)->node);
        }

    *temp = *pre;         
    }           
    }

void print(struct list *head)
{
    if(head==NULL)
        return;
    else
    {
            while(head!=NULL)
            {
             printf("%d\t",head->node);
             head=head->next;       
        }
    }
}


void insert(struct list **head, int value)
{   
    struct list *new_node;
    new_node = (struct list *)malloc(sizeof(struct list));

//node Creation
    new_node->node=value;
    new_node->next=NULL;

//Adding Node to list
    if(*head==NULL)
    {
        *head=new_node;  

    }
    else
    {
        while((*head)->next!=NULL)
        {   
            *head=(*head)->next;

        }
        (*head)->next=new_node;

    }

}

Output: 10 20 30 40 50 60 6532425 hello 6532425 60 50 40 30 20 10

Why?

4

2 回答 2

2

首先，通过执行以下操作取消引用并写入不确定的位置：

struct list **pre, **aft, **head;
*pre = NULL;    // <=== HERE
*head = *temp;  // <=== HERE

这些指针都没有初始化为任何东西，因此是不确定的。取消引用它们以读取、写入甚至评估指针值本身是未定义的行为。

解决这个问题很容易，因为这个函数不需要任何指针到指针的变量，除了传入的头指针（它必须具有按地址来重置新的列表头，一旦它被反转）。

void reverse(struct list **head)
{
    struct list *back = NULL, *cur = *head, *fwd = NULL;
    while (cur && cur->next)
    {
        fwd = cur->next;
        cur->next = back;
        back = cur;
        cur = fwd;
    }

    if (cur)
        cur->next = back;

    *head = cur;
}

也就是说，有证据表明您使用指针对指针的工作需要更多练习。还有其他错误，如下所示

内存泄漏insert()

在您的insert()功能中：

while((*head)->next!=NULL)
{
    *head=(*head)->next;

}
(*head)->next=new_node;

此代码盲目地按地址覆盖传入的头指针，并在此过程中泄漏任何先前分配的节点，除了最后一个添加的节点。如果您要接收双指针并使用它遍历列表以找到新插入的位置，请正确执行。tmp在 in中玩的指针游戏main()应该是不必要的，并且通过以下实现，它不是：

void insert(struct list **head, int value)
{
    // find the address of the last `next` pointer in
    // the list. note: it may be the head pointer itself
    while (*head)
        head = &(*head)->next; 

    *head = malloc(sizeof(**head));
    (*head)->node = value;
    (*head)->next = NULL;
}

简化print()

print()您的代码中也存在一些小不便。不需要对传入的指针作为 NULL 进行初始检查。只需使用 while 循环的中断条件：

void print(struct list *head)
{
    while(head)
    {
        printf("%d ",head->node);
        head=head->next;
    }
    printf("\n");
}

把它们放在一起

使用上述实现，以及以下main()：

int main()
{
    struct list *mylist = NULL;

    insert(&mylist, 10);
    insert(&mylist, 20);
    insert(&mylist, 30);
    insert(&mylist, 40);
    insert(&mylist, 50);
    insert(&mylist, 60);
    insert(&mylist, 70);

    print(mylist);
    reverse(&mylist);
    print(mylist);

    return 0;
}

输出

10 20 30 40 50 60 70 
70 60 50 40 30 20 10
于 2013-10-26T01:31:35.133 回答
2

问题出在这个声明中：

struct list **pre, **aft, **head;

因此，它们是指向列表指针的指针，然后，您可以执行以下操作：

*pre = NULL;

问题是pre尚未初始化，因此此时它包含垃圾。您基本上是将内存中的随机地址设置为 NULL。您有两个选择：为它们分配空间（之后使用 malloc 和 free），或者将它们更改为如下所示：

struct list *pre, *aft, *head;

这样，就可以安全地分配它们。您的功能将被修改如下：

void reverse(struct list **temp) {
    struct list *pre, *aft, *head;
    pre = NULL;
    head = *temp;
    if(head == NULL ) {
        return;
    } else {
        while(head!= NULL) {
            aft =head->next;
            head->next = pre;
            pre = head;
            head = aft;
            printf("%d\t",pre->node);
        }
        *temp = pre;
    }
}

这样做，我得到以下输出：

10      20      30      40      50      60      70      hello  70       60
50      40      30      20      10

编辑：

我还注意到您正在更改head函数内部的值insert和print. 我建议使用时间变量来迭代列表。这也使您摆脱了在mainwith中使用的技巧tmp。

反正修改后的完整代码可以看这里。如果您的仍然给您带来麻烦，请发布更新或 Ideone 链接，其中包含仍然失败的修改代码。

于 2013-10-26T00:46:46.017 回答