用指针实现双向链表 C++ [英] Doubly Linked List Implementation with Pointers C++

问题描述

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

I am currently teaching myself C++ and am attempting to implement a doubly-linked list in C++ using pointers which is partially complete. I am aware that the code currently fails to deal with dangling nodes or output errors, both of which I will implement next. However, the code should atleast be able to construct a list object and add elements to it. Currently, I am getting an error when I attempt to call a constructor for the list, which says that I am requesting a conversion from LinkedList* to non scalar type LinkedList. Why is my list being declared as a pointer? Any help would be much appreciated, thank you!

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);
}

推荐答案

该错误意味着您在某处将 LinkedList 列表声明为不是指针，您为其分配了 new LinkedList()是 LinkedList* 类型(而不是 LinkedList).应该是:

The error means that somewhere you have a LinkedList list declared not as a pointer, to which you assign a new LinkedList() which is of type LinkedList* (and not LinkedList). It should be:

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);

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

They are two different types which are allocated in two different storages and this is important, keep reading.

我看到更重要的是，当您使用动态分配的内存时，您应该考虑在堆对象上实际分配的情况，这些对象应该保持声明它们的范围.

What I see more importantly is that when you use dynamically allocated memory you should take case of actually allocate on heap objects that should persist the scope in which they are declared.

更具体地说，这个:

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

这会引起问题，因为temp被声明为栈上自动存储，这意味着一旦你获得了它的地址并将其分配给head或tail 或其他任何内容，一旦范围退出，该地址将不再有效.您应该在堆上分配它:

This will cause problems because temp is declared as automatic storage on stack, which means that once you obtained its address and assign it to head or tail or whatever, that address won't be valid anymore once the scope exited. You should allocate it on heap:

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

请注意，当不再需要 Node 时，这需要您自己从堆中清理内存.

Mind that this requires that you clean up memory by yourself from the heap when the Node is not needed anymore.

这篇关于用指针实现双向链表 C++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！