2

我目前正在自学 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);
}
4

5 回答 5

5

该错误意味着您在某处有一个 LinkedList 列表声明为不是指针，您为其分配了 anew 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请注意，这需要您在不再需要时自行从堆中清理内存。

于 2013-10-21T00:33:53.910 回答
1

new 返回指向您试图分配给 LinkedList 对象的 LinkedList 对象的指针，而不是指针。

LinkedList list = new LinkedList();

应该读

LinkedList list;
于 2013-10-21T00:30:36.383 回答
1

试试这个完全实现的双向链表：

#include <stdio.h>

struct node{
int data;
struct node *next,*prev;
};

struct node *head=NULL;

void insert(int data, int position)
{
    struct node *newNode=malloc(sizeof(struct node));
    newNode->data=data;

    if(position<1)
    {
      printf("Invalid Insertion Position \n");
      return;
    }
    if(head==NULL && position==1)
    {
        newNode->next=NULL;
        newNode->prev=NULL;
        head=newNode;
    }
    else if(head==NULL && position!=1)
    {
        printf("Invalid Insertion Position \n");
    }
    else if(position==1)
    {
        newNode->next=head;
        newNode->prev=NULL;
        if(head->next!=NULL)
        {
           head->next->prev=newNode;
        }
        head=newNode;
    }
    else
    {
        int i=0;
        struct node *temp=head;
        while(temp->next!=NULL && i<position-2)
        {
            i++;
            temp=temp->next;
        }
        if(i<position-2)
        {
            printf("Invalid Insertion Position \n");
        }
        else
        {
        newNode->next=temp->next;
        temp->next=newNode;
        newNode->prev=temp;
        if(temp->next!=NULL)
        {
            temp->next->prev=newNode;
        }
        }

    }
}

void delete(int position)
{
    int i=0;
    if(position<1)
    {
        printf("Invalid Position of Deletion \n");
        return;
    }
    if(head==NULL)
    {
        return;
    }
    if(position==1)
    {
        head=head->next;
        if(head!=NULL)
        {
        head->prev=NULL;
        }
    }
    else
    {
        struct node *temp=head;
        while(temp->next->next!=NULL && i<position-2)
        {
            i++;
            temp=temp->next;
        }
         if(i<position-2)
            {
                printf("Invalid Position of Deletion \n");
                return;
            }
        else
            {
                temp->next=temp->next->next;
                if(temp->next!=NULL)
                temp->next->prev=temp;
            }
    }
}



void printlist()
{
    if(head==NULL)
    {
        printf("Empty List!! \n");
        return;
    }
    struct node *temp=head;

    while(temp!=NULL)
    {
        printf("%d",temp->data);
        printf("\t");
        temp=temp->next;
    }
    printf("\n");
}

int main()
{
    int t;
    printf("Enter number of Test Cases: \t");
    scanf("%d", &t);
    printf("\nEnter Queries in this format: \n");
    printf("For Insertion: \t I data position \n");
    printf("\tEx:\t I 25 5 \n");
    printf("For Deletion: \t D position \n");
    printf("\tEx:\t D 2 \n\n");

    while(t--)
    {
        char c;
        int a,b;
        printf("Enter query: \t");
        scanf("%c", &c);
        scanf("%c", &c);

        if(c=='I')
        {
            scanf("%d %d", &a,&b);
            insert(a,b);
        }
        else if(c=='D')
        {
           scanf("%d", &a);
           delete(a);
        }
        printlist();
    }

}
于 2014-09-22T23:43:58.160 回答
1

我认为你应该实现两个类：

  1. 带有标记的双向链表：Double_sentinel_list和
  2. 双链节点：Double_node.

成员变量。构造函数，析构函数：

int size() const; 
  //Returns the number of items in the list.
bool empty() const;  
  // Returns true if the list is empty, false otherwise.
Type front() const;  
  // Retrieves the object stored in the node pointed to by the next pointer of the head sentinel. This function throws a underflow if the list is empty. 
Type back() const;   
  // Retrieves the object stored in the node pointed to by the previous pointer of the tail sentinel. This function throws a underflow if the list is empty.
Double_node<Type> *head() const;  
  // Returns the head pointer.
Double_node<Type> *tail() const;  
  // Returns the tail pointer.
int count( Type const & ) const;  
  // Returns the number of nodes in the linked list storing a value equal to the argument. Mutators

这个类有七个突变体：

void swap( Double_sentinel_list & );  
  // The swap function swaps all the member variables of this linked list with those of the argument.
Double_sentinel_list &operator=( Double_sentinel_list & );  
  // The assignment operator makes a copy of the argument and then swaps the member variables of this node doubly linked sentinel list those of the copy.
void push_front( Type const & );  
  // Creates a new Double_node<Type> storing the argument, the next pointer of which is set to the next pointer of the sentinel and the previous pointer is set to point to the sentinel. Theprevious pointer of what was the first node is set to the new node.
void push_back( Type const & );  
  //  Similar to push_front, this places a new node at the back of the list.
Type pop_front();  
  // Delete the first non-sentinel node at the front of the linked list and the previous and next pointers of any other node (including the sentinels) within the list. Return the object stored in the node being popped. Throw an underflow exception if the list is empty.
Type pop_back();  
  // Similar to pop_front, delete the last non-sentinel node in the list. This function throws a underflow if the list is empty.
int erase( Type const & );  
  // Delete the first node (from the front and other than the sentinals) in the linked list that contains the object equal to the argument (use == to to test for equality with the retrieved element). Update the previous and next pointers of any other node (including possibly the sentinels) within the list. Return the number of nodes that were deleted.
于 2016-09-29T05:10:58.453 回答
0

任何一个

LinkedList list;
list.addAtFront(0);

或者

LinkedList* list = new LinkedList();
list->addAtFront(0);
delete list;
于 2013-10-21T00:30:53.713 回答