c - 为单链表编写适当的push() 函数。

Question

http://cslibrary.stanford.edu/103/

请抽出一些时间来复习一下这个链表基础知识文档中错误的推送功能。我只是遵循了该函数的相同实现。因此，根据文档，不应将数据添加到列表的头部。但我的工作完全符合他们所说的实现方式。我很困惑不知道问题出在哪里？

这是代码:

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

struct node{
    int data;
    struct node * next;
};

typedef struct node Node; /* Utilize a typedef for Node rather than typing
                             struct Node everytime we declare a node. */

Node* BuildOneTwoThree() {
    Node* head =NULL;   // pointer called head.
    Node* second =NULL; // pointer to second memory block
    Node* third = NULL; // pointer to third memory block

    head = (Node*)malloc(sizeof(Node));   //allocate a memory block of size node
                                          //in the heap and head pointer will 
                                          //point to this memory.
    second = (Node*)malloc(sizeof(Node)); //allocate a memory block of size node 
                                          //in the heap and second pointer will 
                                          //point to this memory
    third = (Node*)malloc(sizeof (Node)); //allocate a memory block of size node 
                                          //in the heap and third pointer will 
                                          //point to this memory

    head->data = 1;
    head->next = second; //the next pointer of node type will point to another 
                         //pointer of node type which is second!!

    second -> data = 2;
    second -> next = third;

    third -> data = 3;
    third -> next = NULL;
    return head;
}


Node* WrongPush(Node* head, int data) {

    Node* newNode = malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head;
    head = newNode; // NO this line does not work!
    return head;
}

Node* WrongPushTest() {
    Node* head = BuildOneTwoThree();
    Node* current = WrongPush(head, 4);
    return current;
}

int main(){
    Node* ptr = WrongPushTest(); //My question is why does the wrong push 
                                 //test implementation that I setup work?
    while(ptr!=NULL) {
        printf("%d\n",ptr->data);
        ptr=ptr->next;
    }
}

Answer 1

我注意到的第一件事是您实际上更改了您引用的文档中所写的实现。该文档实现 WrongPush 如下(我对其进行了修改以使用您的结构定义):

void WrongPush (Node * head, int data) {
    Node * newNode = malloc(sizeof(Node));

    newNode->data = data;
    newNode->next = head;
    head = newNode;  /* This will not work because you are not
                        modifying head in the calling function. */
}

您的实现的问题在于它不易扩展。例如，使用您的代码，尝试如下 WrongPushTest:

Node * WrongPushTest() {
    Node * head = BuildOneTwoThree();
    Node * current = WrongPush(head, 4);
    current = WrongPush(head, 5);
    current = WrongPush(head, 6);
}

输出将不是程序员想要的。目标是拥有一个利用原始 head 的推送函数，而不必每次将另一个节点推送到链表时都创建一个新节点。他们在文档中使用的示例如下:

void Push(Node** headRef, int data) {
    Node * newNode = malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *headRef;
    *headRef = newNode;
}

请注意，我没有像您的示例中那样返回指向新创建的头的指针。上面的代码允许我们通过直接操作原始 head 指针来始终将新节点推送到原始链表的头部。

Node * PushTest() {
    Node * head = BuildOneTwoThree();
    Push (&head, 4);
    Push (&head, 5);
    Push (&head, 6);
    return head;
}

希望这有助于您解决问题!