C中的简单链表-Java 学习之路

我即将创建一个可以插入和显示的链接到现在为止：

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

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

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 |下一步指向下一个点 . 然后我改变了head指向NewNode的位置，因为NewNode现在是LinkedList中的第一个Node .

为什么这不起作用？我会很感激任何可以让我朝着正确方向前进的提示 . 我认为LinkedList有点难以理解 .

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

10 回答

我认为，为了确保列表中每个节点的非正式链接， addNode 方法必须如下所示：

void addNode(struct node *head, int n) {
  if (head->Next == NULL) {
    struct node *NewNode = new node;
    NewNode->value = n;
    NewNode->Next = NULL;
    head->Next = NewNode;
  }
  else 
    addNode(head->Next, n);
}

回复于 2024-05-03T16:29:48+08:00

这是我在这种情况下可以想到的最简单的例子，并没有经过测试 . 请考虑这使用了一些不好的做法，并且不会像往常那样使用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，后进先出）

回复于 2024-05-03T16:29:48+08:00

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

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

回复于 2024-05-03T16:29:48+08:00

34
这两个功能都错了 . 首先，函数 initNode 有一个令人困惑的名字 . 它应该命名为例如 initList ，不应该执行addNode的任务 . 也就是说，它不应该向列表中添加值 .

事实上，函数initNode没有任何意义，因为列表的初始化可以在定义头时完成：
```
Node *head = nullptr;
```
要么
```
Node *head = NULL;
```
因此，您可以从列表设计中排除函数 initNode .

同样在您的代码中，不需要为结构 Node 指定详细的类型名称，即在名称 Node 之前指定关键字struct .

函数 addNode 将改变head的原始值 . 在函数实现中，只更改作为参数传递给函数的头的副本 .

该函数可能看起来像：
```
void addNode(Node **head, int n)
{
    Node *NewNode = new Node {n, *head};
    *head = NewNode;
}
```
或者，如果您的编译器不支持初始化的新语法，那么您可以编写
```
void addNode(Node **head, int n)
{
    Node *NewNode = new Node;
    NewNode->x = n;
    NewNode->next = *head;
    *head = NewNode;
}
```
或者不使用指向指针的指针，而是可以使用对Node指针的引用 . 例如，
```
void addNode(Node * &head, int n)
{
    Node *NewNode = new Node {n, head};
    head = NewNode;
}
```
或者您可以从函数返回更新的头：
```
Node * addNode(Node *head, int n)
{
    Node *NewNode = new Node {n, head};
    head = NewNode;
    return head;
}
```
并在 main 写道：
```
head = addNode(head, 5);
```
回复于 2024-05-03T16:29:48+08:00
2
addNode 函数需要能够更改 head . 现在只需更改局部变量 head （参数）即可 .

将代码更改为
```
void addNode(struct Node *& head, int n){
    ...
}
```
会解决这个问题，因为现在 head 参数是通过引用传递的，被调用的函数可以改变它 .
回复于 2024-05-03T16:29:48+08:00

我会加入战斗 . 自从我写完C以来已经太久了 . 此外，这里没有完整的例子 . OP的代码基本上是C，所以我继续使用GCC .

之前已经涵盖了这些问题; next 指针未被提升 . 这就是问题的症结所在 .

我也借此机会进行了建议编辑;而不是有两个函数 malloc ，我把它放在 initNode() 然后使用 initNode() 到 malloc 两者（如果你愿意， malloc 是"the C new"） . 我更改 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 -o ll ll.c

输出：

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

回复于 2024-05-03T16:29:48+08:00

以下是一个示例链接列表

#include <string>
    #include <iostream>

    using namespace std;


    template<class T>
    class Node
    {
    public:
        Node();
        Node(const T& item, Node<T>* ptrnext = NULL);
        T value;
        Node<T> * next;
    };

    template<class T>
    Node<T>::Node()
    {
        value = NULL;
        next = NULL;
    }
    template<class T>
    Node<T>::Node(const T& item, Node<T>* ptrnext = NULL)
    {
        this->value = item;
        this->next = ptrnext;
    }

    template<class T>
    class LinkedListClass
    {
    private:
        Node<T> * Front;
        Node<T> * Rear;
        int Count;
    public:
        LinkedListClass();
        ~LinkedListClass();
        void InsertFront(const T Item);
        void InsertRear(const T Item);
        void PrintList();
    };
    template<class T>
    LinkedListClass<T>::LinkedListClass()
    {
        Front = NULL;
        Rear = NULL;
    }

    template<class T>
    void LinkedListClass<T>::InsertFront(const T  Item)
    {
        if (Front == NULL)
        {
            Front = new Node<T>();
            Front->value = Item;
            Front->next = NULL;
            Rear = new Node<T>();
            Rear = Front;
        }
        else
        {
            Node<T> * newNode = new Node<T>();
            newNode->value = Item;
            newNode->next = Front;
            Front = newNode;
        }
    }

    template<class T>
    void LinkedListClass<T>::InsertRear(const T  Item)
    {
        if (Rear == NULL)
        {
            Rear = new Node<T>();
            Rear->value = Item;
            Rear->next = NULL;
            Front = new Node<T>();
            Front = Rear;
        }
        else
        {
            Node<T> * newNode = new Node<T>();
            newNode->value = Item;
            Rear->next = newNode;
            Rear = newNode;
        }
    }
    template<class T>
    void LinkedListClass<T>::PrintList()
    {
        Node<T> *  temp = Front;
        while (temp->next != NULL)
        {
            cout << " " << temp->value << "";
            if (temp != NULL)
            {
                temp = (temp->next);
            }
            else
            {
                break;
            }
        }
    }

    int main()
    {
        LinkedListClass<int> * LList = new LinkedListClass<int>();
        LList->InsertFront(40);
        LList->InsertFront(30);
        LList->InsertFront(20);
        LList->InsertFront(10);
        LList->InsertRear(50);
        LList->InsertRear(60);
        LList->InsertRear(70);
        LList->PrintList();
    }

回复于 2024-05-03T16:29:48+08:00

3
head 在主要内部定义如下 .
```
struct Node *head = new Node;
```
但是你只是改变了 addNode() 和 initNode() 函数的头部 . 这些变化并没有反映在主要方面 .

将头部的声明设为全局，不要将其传递给函数 .

功能应如下 .
```
void initNode(int n){
    head->x = n;
    head->next = NULL;
}

void addNode(int n){
    struct Node *NewNode = new Node;
    NewNode-> x = n;
    NewNode->next = head;
    head = NewNode;
}
```
回复于 2024-05-03T16:29:48+08:00

使用：

#include<iostream>

using namespace std;

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

Node *head = NULL;
Node *tail = NULL;

void AddnodeAtbeggining(){
    Node *temp = new Node;
    cout << "Enter the item";
    cin >> temp->num;
    temp->next = NULL;
    if (head == NULL)
    {
        head = temp;
        tail = temp;
    }
    else
    {
        temp->next = head;
        head = temp;
    }
}

void addnodeAtend()
{
    Node *temp = new Node;
    cout << "Enter the item";
    cin >> temp->num;
    temp->next = NULL;
    if (head == NULL){
        head = temp;
        tail = temp;
    }
    else{
        tail->next = temp;
        tail = temp;
    }
}

void displayNode()
{
    cout << "\nDisplay Function\n";
    Node *temp = head;
    for(Node *temp = head; temp != NULL; temp = temp->next)
        cout << temp->num << ",";
}

void deleteNode ()
{
    for (Node *temp = head; temp != NULL; temp = temp->next)
        delete head;
}

int main ()
{
    AddnodeAtbeggining();
    addnodeAtend();
    displayNode();
    deleteNode();
    displayNode();
}

回复于 2024-05-03T16:29:48+08:00

在代码中有一个错误：

void deleteNode ()
{
    for (Node * temp = head; temp! = NULL; temp = temp-> next)
        delete head;
}

这是必要的：

for (; head != NULL; )
{
    Node *temp = head;
    head = temp->next;

    delete temp;
}

回复于 2024-05-03T16:29:48+08:00

C中的简单链表

10 回答

相关问题