C语言中的简单链表

Question

我将创建一个可以插入并显示到现在的链接：

struct Node {
    int x;
    Node *next;
};

这是我的初始化函数，只会为第一个节点调用该函数：

void initNode(struct Node *head, int n){
    head->x = n;
    head->next = NULL;
}

要添加Node，我认为我的链表不正确的原因是在这个函数中：

void addNode(struct Node *head, int n){
    struct Node *NewNode = new Node;
    NewNode-> x = n;
    NewNode -> next = head;
    head = NewNode;
}

我的main函数：

int _tmain(int argc, _TCHAR* argv[])
{
    struct Node *head = new Node;

    initNode(head, 5);
    addNode(head, 10);
    addNode(head, 20);
    return 0;
}

让我运行这个程序，因为我认为它的工作。首先，我将头Node初始化为Node，如下所示：

head = [ 5 |  NULL ]

然后我添加一个n=10的新节点，并传递head作为我的参数。

NewNode=[x | next]，其中next指向头部。然后我改变了head指向NewNode的位置，因为NewNode是LinkedList中的第一个节点。

为什么这不起作用？如果有任何提示能让我朝着正确的方向前进，我将不胜感激。我觉得LinkedList有点难理解。

当我打印这个时，它只返回5：




Answer 1

我要加入战斗。我已经很久没有写C了。再说，这里也没有完整的例子。OP的代码基本上是C，所以我继续使用GCC。

这些问题以前都有解决过；next指针未被提升。这是问题的关键。

我还借此机会提出了一个编辑建议；我没有为malloc设置两个函数，而是将它放在initNode（）中，然后将initNode（）用于malloc这两个函数（malloc是“新的C”（如果您愿意的话）。我更改了initNode（）以返回指针。

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

// required to be declared before self-referential definition
struct Node;

struct Node {
    int x;
    struct Node *next;
};

struct Node* initNode( int n){
    struct Node *head = malloc(sizeof(struct Node));
    head->x = n;
    head->next = NULL;
    return head;
}

void addNode(struct Node **head, int n){
 struct Node *NewNode = initNode( n );
 NewNode -> next = *head;
 *head = NewNode;
}

int main(int argc, char* argv[])
{
    struct Node* head = initNode(5);
    addNode(&head,10);
    addNode(&head,20);
    struct Node* cur  = head;
    do {
        printf("Node @ %p : %i\n",(void*)cur, cur->x );
    } while ( ( cur = cur->next ) != NULL );

}

编译：gcc-ll。c

输出：

Node @ 0x9e0050 : 20
Node @ 0x9e0030 : 10
Node @ 0x9e0010 : 5

Answer 2

你应该参考头指针。否则，指针修改在函数外部不可见。

void addNode(struct Node *&head, int n){
    struct Node *NewNode = new Node;
 NewNode-> x = n;
 NewNode -> next = head;
 head = NewNode;
}

Answer 3

这是本案例中我能想到的最简单的例子，不做测试。请考虑这使用了一些不好的实践，并且不像通常使用C时那样（初始化列表、声明和定义的分离，等等）。但这是我不能在这里谈论的话题。

#include <iostream>
using namespace std;

class LinkedList{
    // Struct inside the class LinkedList
    // This is one node which is not needed by the caller. It is just
    // for internal work.
    struct Node {
        int x;
        Node *next;
    };

// public member
public:
    // constructor
    LinkedList(){
        head = NULL; // set head to NULL
    }

    // destructor
    ~LinkedList(){
        Node *next = head;
        
        while(next) {              // iterate over all elements
            Node *deleteMe = next;
            next = next->next;     // save pointer to the next element
            delete deleteMe;       // delete the current entry
        }
    }
    
    // This prepends a new value at the beginning of the list
    void addValue(int val){
        Node *n = new Node();   // create new Node
        n->x = val;             // set value
        n->next = head;         // make the node point to the next node.
                                //  If the list is empty, this is NULL, so the end of the list --> OK
        head = n;               // last but not least, make the head point at the new node.
    }

    // returns the first element in the list and deletes the Node.
    // caution, no error-checking here!
    int popValue(){
        Node *n = head;
        int ret = n->x;

        head = head->next;
        delete n;
        return ret;
    }

// private member
private:
    Node *head; // this is the private member variable. It is just a pointer to the first Node
};

int main() {
    LinkedList list;

    list.addValue(5);
    list.addValue(10);
    list.addValue(20);

    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    // because there is no error checking in popValue(), the following
    // is undefined behavior. Probably the program will crash, because
    // there are no more values in the list.
    // cout << list.popValue() << endl;
    return 0;
}

我强烈建议您阅读一点关于C和面向对象编程的知识。一个好的起点可以是：http://www.galileocomputing.de/1278?GPP=opoo

编辑：增加了一个弹出功能和一些输出。如你所见，程序将推3个值5,10,20，然后弹出它们。之后顺序会颠倒，因为此列表在堆栈模式下工作（LIFO，后进先出）