포인터로 이중 링크 된 목록 구현 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

, 당신은를 할당합니다. 10은 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); 

그들은 두 개의 서로 다른 스토리지에 할당이 계속 읽어 중요하다 두 가지 종류가 있습니다.

더 중요한 것은 동적으로 할당 된 메모리를 사용할 때 실제로 선언 된 범위를 유지해야하는 힙 개체에 할당해야한다는 것입니다. 더 구체적으로

,이 : temp이 당신의 주소를 획득 한 번하고 head 또는 tail이든, 그 주소에 할당한다는 것을 의미 스택에 자동 저장,로 선언되어 있기 때문에

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

이 문제가 발생합니다 일단 스코프가 종료되면 더 이상 유효하지 않습니다. 당신은 힙에 할당해야합니다

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

마음을이이 Node가 더 이상 필요하지 않을 때 당신은 힙에서 직접 메모리를 청소하는 것이 필요하다고.

Answer 2

new는 포인터 대신 LinkedList 객체에 할당하려고하는 LinkedList 객체에 대한 포인터를 반환합니다.

LinkedList list = new LinkedList(); 

읽어야

LinkedList list; 

Answer 3

어느

에

LinkedList list; 
list.addAtFront(0); 

또는

오류가 어딘가에 당신이 LinkedList의 목록이 포인터로하지 선언 한 것을 의미

LinkedList* list = new LinkedList(); 
list->addAtFront(0); 
delete list; 

Answer 4

이 완전히 구현 이중 연결리스트보십시오 :

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

} 

Answer 5

난 당신이 두 개의 클래스를 구현해야한다고 생각을 :

센티넬와
1. 이중 연결리스트 : Double_sentinel_list 및
2. 이중 연결 노드 : Double_node.

회원 변수. Constuctors, 소멸자 :

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.