使用指针C++实现双链表实现

Question

我目前正在自学C++,并尝试使用部分完成的指针在C++中实现双向链表.我知道代码当前无法处理悬空节点或输出错误,我将在下面介绍这两个节点.但是,代码应该至少能够构造一个列表对象并向其添加元素.目前,当我尝试调用列表的构造函数时,我收到一个错误,表示我正在请求从LinkedList*到非标量类型LinkedList的转换.为什么我的列表被声明为指针？非常感谢任何帮助,谢谢!

LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

struct dataElement {
  int key;
  int id;
};

struct Node
{
    dataElement data;
    Node* next;
    Node* prev;
};


class LinkedList
{
public:
    /** Default constructor */
    LinkedList();
    /** Default destructor */
    virtual ~LinkedList();
    void addAtFront(int newElement);
    void addAtBack(int newElement);
    int removeTop();
    int removeBottom();
    int getTop();
    int getBottom();
    int findKey(int keyToFind);
protected:
private:
    Node* head;
    Node* tail;
    int size;
};

#endif // LINKEDLIST_H


LinkedList.cpp
#include "LinkedList.h"
#include <iostream>
#include <stdlib.h>


LinkedList::LinkedList()
{
size = 0;
}

LinkedList::~LinkedList()
{
//dtor
}

void LinkedList::addAtFront(int newElement)
{
if (size == 0)
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    head = &temp;
    tail = &temp;
    ++size;
}
else
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = size;
    temp.next = head;
    head->prev = &temp;
    head = &temp;
    ++size;
}
}

void LinkedList::addAtBack(int newElement)
{
if (size == 0)
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    head = &temp;
    tail = &temp;
    ++size;
}
else
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    tail->next = &temp;
    temp.prev = tail;
    tail = &temp;
    ++size;
}
}

LinkedListTest.cpp
#include "LinkedListTest.h"
#include "LinkedList.h"

int main()
{
LinkedList list = new LinkedList();
list.addAtFront(0);
}

Answer 1

该错误意味着您将某个LinkedList列表声明为不作为指针,您指定new LinkedList()哪个类型LinkedList*(而不是LinkedList).它应该是:

LinkedList* list = new LinkedList(); // I declare a pointer to a list
list->addAtFront(0); // I call a method on a pointer to an object

要么

LinkedList list;
list.addAtFront(0);

它们是两种不同的类型,分配在两个不同的存储器中,这很重要,请继续阅读.

我更重要的是,当你使用动态分配的内存时,应该考虑实际分配堆对象,这些对象应该保持声明它们的作用域.

更具体地说,这个:

{
  Node temp;
  ..
  head = &temp;
  ..
}

因为这将导致问题temp被声明为堆栈自动存储,这意味着一旦你得到它的地址,并将其分配给head或tail也好,该地址将不再有效,一旦退出范围.你应该在堆上分配它:

Node temp = new Node(value, id);
head = temp;
tail = temp;
++size;

请注意,这需要您在Node不再需要时从堆中清除内存.