链表 C++ 、问题自学

Question

        #include <iostream>
    using namespace std;



    struct Node
    {
        int item;   // storage for the node's item
        Node* next;   // pointer to the next node 
    };

  Node* addNode(Node*& head, int data , int& count) 
{
    Node * q;     // new node
    q = new Node;  // allocate memory for the new mode
    q->item = data;  // inserting data for the new node
    q->next = head;   // point to previous node ?? how would i do that? ( am i doing it correctly?)
    count++; // keep track of number of node
    head = q;
    return q;
}



    int main()
    {
        int a, count=0;
        int data;
        bool repeat;
        Node *head= NULL;   
        //^^ assuming thats creating the first node ^^
        do
        {
        cout << "please enter the data for the next node" <<endl;
        cin >> data;
        addNode(head, data, count);
        cout << "do you wish to enter another node? (enter true or false)" << endl;
        cin >>repeat;
        }
       while (repeat == true);


       // assuming this is the print function  
          while(head != NULL)
        {
            cout << "output" << temp->item << endl;
            cout << temp->next << endl;
        }

        system("pause");
        return 0; 
    }

好吧，我尝试在列表中添加一个新元素，我如何像后进先出内存（堆栈）一样移动头部，所以最后一个元素位于最顶部..

任何帮助将不胜感激！指针和节点最近弄乱了我的大脑......

Answer 1

temp 是一个未初始化的指针。因此 -

temp-> item = a;  // temp is not initialized or pointing to a memory location
                  // that has Node object to use operator ->

首先，需要使用 new 为 temp 分配内存位置。

temp = new Node;
temp -> item = a;

现在分配它head。类似地，也在 while 循环中为子节点分配内存。并在程序终止前使用delete将从child获取的所有资源返回到head。

Answer 2

您在这里似乎有一些误解：

您的“头”是列表的开始。这永远是开始。

通过将元素分配给最后一个节点的 next 指针，可以add 将元素追加到链表中。

第三，你没有分配任何东西。

Node *head= new Node();   
Node *temp = new Node();
cout<<"enter something into data"<<endl;
cin >> a ;
temp->item = a;
head->next = temp;

现在...要添加下一个内容，您要么需要跟踪最后一个节点（尾部），要么遍历列表以查找最后一个节点。

Node *nextNode = new Node();
nextNode->item = 0.0;
Node *i;
for (i = head; i->next != null; i = i->next);
i->next = nextNode;

这是 O(n) 的执行时间。通过跟踪尾部，您可以使其 O(1)：

Node *head= new Node();
Node *tail = head;   
Node *temp = new Node();
cout<<"enter something into data"<<endl;
cin >> a ;
temp->item = a;
tail->next = temp;
tail = temp;

Node *nextNode = new Node();
nextNode->item = 0.0;
tail->next = nextNode;
tail = nextNode;

编辑： 正如所指出的，如果您想添加到列表中，您可以：

temp->next = head;
head = temp;

Answer 3

因为我不确定每个答案都完全回答它，所以这里有一个链表实现（没有 testig 编写：

// your (correct) structure
struct Node
{
    float item;   // storage for the node's item
    Node* next;   // pointer to the next node 
};

现在我们需要两个指针来照顾列表：

/* some pointers */
struct List
{
    Node* head;
    Node* tail;
};

现在我们需要创建一些元素。正如其他人所说，你可以这样做 您

/* create some elements we want to link in */
Node* elem1 = new Node();
Node* elem2 = new Node();
Node* elem3 = new Node();
/* maybe even set their properties! */
elem1->item = 3.14;
elem2->item = 3.14;
elem3->item = 3.14;

注意到我还没有尝试将这些元素添加到列表中吗？那是因为我想到了一个如下所示的函数：

void addtolist(List &list, Node* node)
{
    /* if no head, initialise the list */
    if ( list->head == NULL )
    {
        list->head = node;
        list->tail = node;
    }
    else if ( list->head != NULL && list->tail != NULL )
    {
        /* access the tail element and set its 
           next to this ptr. 
           Move tail to this node */
        list->tail->next = node;
        list->tail = node;
    }
    else
    {
        /* probably raise an exception! */
    }
}

可以通过这样做来调用它：

List l;
addtolist(l, elem1); /* etc */

删除元素有点棘手，因为你必须转到该元素，所以记住它的前一个元素，抓住它的下一个元素，将它们连接起来并删除你所在的 Node*

现在遍历列表......你的术语 HEAD|TAIL 让我想起了 Erlang 和尾递归，其中当前元素被称为头部，其余元素被称为尾部。 如果我写：

Node* cur = l.head;
while ( cur != NULL )
{
    // do something with cur.item ? 
    cur = cur->next;
}

你可以看到用 head< 替换 cur 。由于 List 结构，这里的 /code> 是无害的。

最后，我在这里使用了一种非常类似于 C 的方法，但还有模板的范围：

template<typename T>
struct node
{
    T item;   // storage for the node's item
    Node<T>* next;   // pointer to the next node 
};

并封装 List 。 > struct 作为一个类：

template<typename T>
class List
{
protected:
    Node<T>* head;
    Node<T>* tail;
public:

    void addtolist(Node<T>* node);
    Node<T>* gethead();
    Node<T>* gettail();
}

这让您更接近 std::list。

Answer 4

另外请注意，您正在执行从 int 到 float 的隐式转换，

temp-> item = a;

因为 a 是 int，而 < code>temp->item 是一个 double。

解决你的问题：你想在访问 temp 之前分配一个新的结构，因此

temp = new Node();