C++链接列表

Question

我正在努力使链表与此类似:

C中的链表

那就是在另一个结构中让我首先调用它的"头".但是我发现做了那个改变.难以将值添加到list_item结构中.我尝试了一些事情,看它是否有效.它编译,但是当我运行代码时它会崩溃.任何帮助在这里都会有所帮助.我知道崩溃的原因是我想将new_node指向linked_list.

#include <iostream>

using namespace std;

struct list_item
{
    int key;
    int value;
    list_item *next;
};

struct list
{
    struct list_item *first;
};

int main()
{
    list *head;
    list *new_node;

    head = NULL;
    head->first = NULL;

    for(int i = 0; i < 10; i++)
    {
        //allocate memory for new_node
        new_node = (list*)malloc(sizeof(list));
        new_node->first = (list_item*)malloc(sizeof(list_item));
        //adding the values
        new_node->first->key = i;
        new_node->first->value = 10 + i;

        //point new_node to first;
        new_node->first->next = head->first;

        //point first to new_node;
        head->first = new_node->first;

    }

    //print
     list *travel;
     travel->first = head->first;

     int i = 0;
     while(travel != NULL)
     {
         cout << travel->first->value << endl;
         travel->first = travel->first->next;
     }

    return 0;
}

Answer 1

您正在创建10个列表,我想您可能会尝试执行以下操作:

#include <iostream>

using namespace std;

struct list_item
{
    int key;
    int value;
    list_item *next;
};

struct list
{
    struct list_item *first;
};

int main()
{
    //Just one head is needed, you can also create this
    // on the stack just write:
    //list head;
    //head.first = NULL;
    list *head = (list*)malloc(sizeof(list));
    list_item *new_node = NULL;

    head->first = NULL;

    for(int i = 0; i < 10; i++)
    {
        //allocate memory for new_node
        new_node = (list_item*)malloc(sizeof(list_item));
        //adding the values
        new_node->key = i;
        new_node->value = 10 + i;

        //if the list is empty, the element you are inserting
        //doesn't have a next element

        new_node->next = head->first;

        //point first to new_node. This will result in a LIFO
        //(Last in First out) behaviour. You can see that when you 
        //compile
        head->first = new_node;

    }

     //print the list 
     list_item *travel;
     travel = head->first;

     while(travel != NULL)
     {
         cout << travel->value << endl;
         travel = travel->next;
     }

    //here it doesn't matter, but in general you should also make
    //sure to free the elements
    return 0;
}

这是正在发生的事情.起初你只有一个头而没有元素.

head
  |
  |
  V
 NULL

然后添加第一个元素.确保"new_node-> next == NULL":

head
  |
  |
  V
node:   ------------------> NULL
key = 0
value = 10

然后在前面添加另一个节点,但将第一个节点附加到下一个节点.您将指针从头部移动到新节点

head:
first
  |
  |
  V
node:   ---------> node:  -------------> NULL
key: 1             key: 0   
value: 11          value: 10  

等等

由于您使用的是c ++,因此可以考虑使用"new"和"delete".只需更换

new_node = (list_item*)malloc(sizeof(list_item));

同

list *head = new list