不使用函数的单链列表创建问题

Question

//linked_list_1

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

struct list
{
    int data;
    struct list *link;
};

int main()
{
    struct list *ll=NULL, *tp=NULL;
    int n=3, i;

    ll=(struct list *)malloc(sizeof(struct list));

    scanf("%d",&ll->data);

    for(i=1; i<n; i++)
    {
        tp=(struct list *)malloc(sizeof(struct list));
        scanf("%d",&tp->data);
        ll->link=tp;
        ll=ll->link;
    }

    ll->link=NULL;

    while(ll)
    {
        printf("\n%d",ll->data);
        ll=ll->link;
    }
}

//linked_list_2

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

struct list
{
    int data;
    struct list *link;
};

void linked_list(struct list *,int);

int main()
{
    struct list *ll=NULL;
    int n=3;

    ll=(struct list *)malloc(sizeof(struct list));

    linked_list(ll,n);


    while(ll)
    {
        printf("\n%d",ll->data);
        ll=ll->link;
    }
}

void linked_list(struct list *kk, int n)
{
    struct list *tp=NULL;
    int i;
    scanf("%d",&kk->data);
    for(i=1; i<n; i++)
    {
        tp=(struct list *)malloc(sizeof(struct list));
        scanf("%d",&tp->data);
        kk->link=tp;
        kk=kk->link;
    }
    kk->link=NULL;
}

[这两个程序都是相同的，第二个程序是使用功能创建链表的：void linked_list(struct list *kk, int n)第一个程序也是个链接列表创建，但没有任何功能。第二个程序正常运行，但第一个程序运行不正确。

如果两个程序的输入均为2 5 4，则第二个程序输出为2 5 4，但第一个程序输出仅为4。

为什么第一个程序不能以正确的方式运行？是什么原因？

Answer 1

第一个程序的问题是，在输入时，您正在移动链表的标题。因此，当您完成输入操作后，链接列表的头部现在位于链接列表的最后一个节点。然后，当您尝试打印出链接列表时，您将得到它的最后一个节点，因为当您接受最后一个输入时，磁头已移到那里。

理想情况下，您应该使用临时指针，将其与链表的顶部指针对齐，然后获取输入，对其进行分配和移动，并继续仅使用它来构建链表。初始化后，链表的头指针（此处为ll）不应这样移动：

ll=ll->link; //Wrong!

直到绝对需要这样做。这将导致链接列表被截断，并且您将丢失节点。

理想情况下，您的代码应该是这样的：

ll=(struct list *)malloc(sizeof(struct list));
tp = ll; //Align the temporary pointer with the head of the linked list.
scanf("%d",&tp->data);

for(i=1; i<n; i++)
{
    //Allocate memory to the link of the temporary pointer since it is also a type of struct list.
    tp->link=(struct list *)malloc(sizeof(struct list)); 
    scanf("%d",&tp->link->data);
    tp = tp->link; //Move only the temporary pointer.
}

tp->link=NULL; //Finally assign NULL when done taking inputs.

请注意，我仅使用临时指针来完成所有操作。

第二个程序起作用的原因是因为您将头指针的地址传递给了用于构建链接列表的函数。现在，此函数获得kk中地址的副本，该地址是链表的起始地址，并使用该地址在链表中构建链表。但是回到main()时，ll指针仍保留最初分配内存的原始地址。因此，构造好链表后，当您返回main()进行打印时，您可以从链表的实际头部开始保持ll的位置，然后就可以打印出整个链表。

但是它仍然具有我先前提到的相同缺陷。您正在打印链接列表（例如ll）时移动它的标题。

while(ll)
{
    printf("\n%d",ll->data);
    ll=ll->link; //This is wrong!
}

因此，在完成链接列表的打印后，链接列表的标题现在为NULL。因此，如果要在打印后对实际的链表进行某些操作，则由于将标头设置为NULL，现在将无法执行。因此，解决方案再次是使用临时指针将其与链表的头部对齐，然后使用它打印出链表。像这样的东西：

struct list *tp = ll;
while(tp)
{
    printf("\n%d",tp->data);
    tp=tp->link;
}