在链表中遍历

Question

我是链表新手。我的简单代码是创建链表并在末尾插入节点并遍历它。
我的问题是——
1)-每次插入函数被调用，头指针得到空
2)-在显示功能中不正常工作…

Please help..

#include<iostream>
#include<malloc.h>
using namespace std;
struct linkedList
{
    int value;
    linkedList *next;
};
linkedList* head = NULL;
void insert(linkedList* head, int data)
{
    linkedList *ptr;
    linkedList *node;
    node = (linkedList*) malloc(sizeof(struct linkedList));
    node->value = data;
    node->next = NULL;
    if (head == NULL)
    {
        head = node;
    }
    else
    {
        ptr = head;
        while (ptr != NULL)
        {
            ptr = ptr->next;
        }
        ptr = node;
    }
}
void show(struct linkedList *head)
{
    struct linkedList *ptr;
    ptr = head;
    while (ptr != NULL)
    {
        cout << ptr->value << endl;
        ptr = ptr->next;
    }
}
int main()
{
    int size = 5;
    int array[size];
    for (int i = 0; i < 5; i++)
    {
        cout << "Enter value" << endl;
        cin >> array[i];
        insert(head, array[i]);
    }
    show(head);
}

Answer 1

在您的insert()函数中:

• 当head为NULL时，您将新节点分配给本地head参数，这不会更新调用者的head变量。这就是为什么你的全局head变量总是NULL。这是因为您按值传递head参数，因此您将新节点分配给副本，而不是原始节点。您需要通过引用/指针来传递参数。

• 当head不为NULL时，您没有正确遍历节点以找到尾部节点，因此遍历后ptr始终为NULL。您根本没有设置尾节点的next字段

另外，您的main()正在泄漏分配的节点。

试试这样写:

#include <iostream>
struct linkedNode
{
    int value;
    linkedNode *next;
};
void insertValue(linkedNode* &head, int data)
{
    linkedNode *node = new linkedNode;
    node->value = data;
    node->next = NULL;
    if (!head)
    {
        head = node;
    }
    else
    {
        linkedNode *ptr = head;
        while (ptr->next)
        {
            ptr = ptr->next;
        }
        ptr->next = node;
    }
}
void showValues(linkedNode *head)
{
    linkedNode *ptr = head;
    while (ptr)
    {
        std::cout << ptr->value << std::endl;
        ptr = ptr->next;
    }
}
void freeValues(linkedNode* &head)
{
    linkedNode *ptr = head;
    head = NULL;
    while (ptr)
    {
        linkedNode *next = ptr->next;
        delete ptr;
        ptr = next;
    }
}
int main()
{
    linkedNode* mylist = NULL;
    for (int i = 0; i < 5; ++i)
    {
        std::cout << "Enter value" << std::endl;
        int value;
        if (std::cin >> value)
            insertValue(mylist, value);
    }
    showValues(mylist);
    freeValues(mylist);
    return 0;
}

也就是说，如果您跟踪列表中的尾部节点，那么在末尾插入将更快更有效，因为您根本不需要遍历列表:

#include <iostream>
struct linkedNode
{
    int value;
    linkedNode *next;
    linkedNode(int data)
        value(data), next(NULL)
    {
    }
};
struct linkedList
{
    linkedNode *head;
    linkedNode *tail;
    linkedList()
        : head(NULL), tail(NULL)
    {
    }
    ~linkedList()
    {
        linkedNode *ptr = head;
        while (ptr)
        {
            linkedNode *next = ptr->next;
            delete ptr;
            ptr = next;
        }
    }
    void insert(int data)
    {
        linkedNode *node = new linkedNode(data);
        if (!head)
            head = node;
        if (tail)
            tail->next = node;
        tail = node;
    }
    void showValues()
    {
        linkedNode *ptr = head;
        while (ptr)
        {
            std::cout << ptr->value << std::endl;
            ptr = ptr->next;
        }
    }
};
int main()
{
    linkedList mylist;
    for (int i = 0; i < 5; ++i)
    {
        std::cout << "Enter value" << std::endl;
        int value;
        if (std::cin >> value)
            mylist.insert(value);
    }
    mylist.showValues();
    return 0;
}

在这种情况下，您可以把所有这些都扔掉，使用标准的std::list类来代替:

#include <iostream>
#include <list>
#include <algorithm>
void showValue(int value)
{
    std::cout << value << std::endl;
}
void showValues(const std::list<int> &values)
{
    std::for_each(values.begin(), values.end(), showValue);
    /* or, if you are using C++11:
    std::for_each(values.begin(), values.end(),
        [](int value){ std::cout << value << std::endl; }
    );
    */
}
int main()
{
    std::list<int> mylist;
    for (int i = 0; i < 5; ++i)
    {
        std::cout << "Enter value" << std::endl;
        int value;
        if (std::cin >> value)
            mylist.push_back(value);
    }
    showValues(mylist);
    return 0;
}