멤버 함수를 사용하여 이중 링크 된 목록 반전

Question

이중 연결 목록을 역전하려고합니다. 스택 오버 플로우 및 웹에 대한 다른 질문에 따르면 이중 연결 목록을 역전시키는 적절한 방법입니다. 모든 노드의 next 및 back 포인터를 교체하십시오. Xcode 6에는 전체 디버그 메뉴가 회색으로 표시되어 있기 때문에 어떤 이유로 든 작동하지 않고 디버깅 할 수 없습니다. 역순 함수는 dll.cpp의 맨 아래에 있습니다. Heres는 내 코드 :

dll.h :

#ifndef dll_h 
#define dll_h 
#include <iostream> 
using namespace std; 
template <class ItemType> 
struct NodeType 
{ 
    ItemType info; 
    NodeType* next; 
    NodeType* back; 
}; 


template <class ItemType> 
class DoublyLinkedList 
{ 
public: 
    DoublyLinkedList();  // Class constructor. 
    ~DoublyLinkedList(); // Class destructor. 

    ////////// implement these functions ////////// 
    DoublyLinkedList(DoublyLinkedList<ItemType>&); 
    void InsertItem(ItemType item); 
    void DeleteItem(ItemType item); 
    void reverseDoublyLinkedList(); 


    void FindItem(NodeType<ItemType>* listData, ItemType item, NodeType<ItemType>*& location, bool& found); 
    int LengthIs() const; 
    void MakeEmpty(); 
    void RetrieveItem(ItemType& item, bool& found); 
    void ResetList(); 
    void GetNextItem(ItemType& item); 

private: 
    NodeType<ItemType>* listData; 
    int length; 
    NodeType<ItemType>* currentPos; 
}; 
#endif 

dll.cpp :

#include "DLL.h" 
template<class ItemType> 
DoublyLinkedList<ItemType>::DoublyLinkedList() 
{ 
    listData = NULL; 
    length =0; 
    currentPos = NULL; 

} 
template<class ItemType> 
void DoublyLinkedList<ItemType>::FindItem(NodeType<ItemType>* listData, ItemType item, 
              NodeType<ItemType>*& location, bool& found) 
// Assumption: ItemType is a type for which the operators "<" and 
// "==" are defined-either an appropriate built-in type or a 
// class that overloads these operations. 
// Pre: List is not empty. 
// Post: If there is an element someItem whose key matches item's 
//  key, then found = true; otherwise, found = false. 
//  If found, location contains the address of someItem; 
//  otherwise, location contains the address of the logical 
//  successor of item. 
{ 
    bool moreToSearch = true; 

    location = listData; 
    found = false; 
    while (moreToSearch && !found) 
    { 
     if (item < location->info) 
      moreToSearch = false; 
     else if (item == location->info) 
      found = true; 
     else 
     { 
      location = location->next; 
      moreToSearch = (location != NULL); 
     } 
    } 
} 


template <class ItemType> 
int DoublyLinkedList<ItemType>::LengthIs() const 
{ 
    return length; 
} 

template <class ItemType> 
void DoublyLinkedList<ItemType>::MakeEmpty() 
// Post: List is empty; all items have been deallocated. 
{ 
    NodeType<ItemType>* tempPtr; 

    while (listData != NULL) 
    { 
     tempPtr = listData; 
     listData = listData->next; 
     delete tempPtr; 
    } 
    length = 0; 
} 

template <class ItemType> 
void DoublyLinkedList<ItemType>::ResetList() 
{ 
    currentPos = NULL; 
} 

template <class ItemType> 
void DoublyLinkedList<ItemType>::GetNextItem(ItemType& item) 
{ 
    if (currentPos == NULL) 
     currentPos = listData; 
    else 
     currentPos = currentPos->next; 
    item = currentPos->info; 
} 
template <class ItemType> 
void DoublyLinkedList<ItemType>::RetrieveItem(ItemType& item, 
               bool& found) 
{ 
    bool moreToSearch; 
    NodeType<ItemType>* location; 

    location = listData; 
    found = false; 
    moreToSearch = (location != NULL); 

    while (moreToSearch && !found) 
    { 
     if (location->info < item) 
     { 
      location = location->next; 
      moreToSearch = (location != NULL); 
     } 
     else if (item == location->info) 
     { 
      found = true; 
      item = location->info; 
     } 
     else 
      moreToSearch = false; 
    } 
} 

template <class ItemType> 
DoublyLinkedList<ItemType>:: ~DoublyLinkedList() // Class destructor. 
{ 
    MakeEmpty(); 
} 

template <class ItemType> 
void DoublyLinkedList<ItemType>::InsertItem(ItemType item) 
{ 
    NodeType<ItemType>* node = new NodeType<ItemType>; 
    node->info = item; 
    if(!length) 
    { 
     listData = node; 
     node->next = NULL; 
     node->back = NULL; 
     length++; 
     return; 
    } 
    NodeType<ItemType>* temp =listData; 
    if(temp->next == NULL) 
    { 
     if(temp->info < item) 
     { 
      node->next = NULL; 
      node->back = temp; 
      temp->next = node; 
     } 
     else 
     { 
      node->next = temp; 
      node->back = NULL; 
      temp->back = node; 
     } 
     length++; 
     return; 
    } 
    while(1) 
    { 
     if(temp->info > item) 
     { 
      node->next = temp; 
      node->back = temp->back; 
      if(temp->back != NULL) 
      { 
       node->back->next = node; 
      } 
      if(temp->back == NULL) 
       listData = node; 
      node->back = temp->back; 
      length++; 
      return; 
     } 
     else if(temp->next == NULL) 
     { 
      node->next = NULL; 
      node->back = temp; 
      temp->next = node; 
      length++; 
      return; 
     } 
     temp = temp->next; 
    } 
} 


template <class ItemType> 
void DoublyLinkedList<ItemType>::DeleteItem(ItemType item) 
{ 
    NodeType<ItemType>* node = listData; 
    if(node == NULL) 
     return; 
    while(node != NULL && node->info != item) 
     node = node->next; 
    if(node == NULL) 
     return; 
    if(node->back != NULL) 
     node->back->next = node->next; 
    if(node->next != NULL) 
     node->next->back = node->back; 
    delete node; 
    length--; 
} 

template <class ItemType> 
DoublyLinkedList<ItemType>::DoublyLinkedList(DoublyLinkedList<ItemType>& original) 
{ 
    length = 0; 
    currentPos = NULL; 
    listData = NULL; 
    NodeType<ItemType>* copy = original.listData; 
    while(copy != NULL) 
    { 
     InsertItem(copy->info); 
     copy = copy->next; 
    } 
} 

template<class ItemType> 
void DoublyLinkedList<ItemType>::reverseDoublyLinkedList() 
{ 
    if(listData == NULL || listData->next == NULL) 
     return; 
    NodeType<ItemType>* node = listData; 

    while(node!=NULL) 
    { 
     swap(node->next, node->back); 

     listData = node; 

     node = node->back; 
    } 
    currentPos = NULL; 
} 

MAIN.CPP :

#include <iostream> 
#include "dll.h" 
#include "dll.cpp" 

int main() 
{ 
    DoublyLinkedList<int> s; 
    s.InsertItem(3); 
    s.InsertItem(4); 
    s.InsertItem(1); 
    s.DeleteItem(2); 
    s.DeleteItem(4); 
    cout<<"Length of s: "<<s.LengthIs()<<endl; 
    DoublyLinkedList<int> t = s; 
    cout<<"Length of t: "<<t.LengthIs()<<endl; 
    t.InsertItem(5); 
    t.InsertItem(13); 
    t.InsertItem(10); 
    t.InsertItem(-3); 
    int a; 
    t.ResetList(); 
    for(int i=0;i<t.LengthIs();i++) 
    { 
     t.GetNextItem(a); 
     cout<<"Item #"<<i<<": "<<a<<endl; 
    } 
    cout<<endl; 
    t.reverseDoublyLinkedList(); 
    t.ResetList(); 
    for(int i=0;i<t.LengthIs();i++) 
    { 
     t.GetNextItem(a); 
     cout<<"Item #"<<i<<": "<<a<<endl; 
    } 
    cout<<endl; 
} 

관련없는하지만 사람이 말해 줄 수 있다면 왜 엑스 코드 6.1은 내 새로운 MacBook Pro에서도 도움이 될 것입니다.

EDIT : 출력 : 라인 item = currentPos->info;의 멤버 함수 GetNextItem()에 충돌 끝에

Length of s: 2 
Length of t: 2 
Item #0: -3 
Item #1: 1 
Item #2: 3 
Item #3: 5 
Item #4: 10 
Item #5: 13 

Item #0: 13 
Item #1: 5 
Item #2: 3 
Item #3: 1 
Program ended with exit code: 9 

.

Answer 1

문제는 InsertItem과 관련이 있습니다. 지금은 지나치게 복잡합니다.

항목을 순서대로 삽입하려고합니다. 따라서 가장 쉬운 방법은 한 쌍의 노드를 가져 와서 항목이 쌍 사이에 들어가는 지 확인하는 것입니다. 보다 쉬운 구현 방법은 다음과 같습니다.

template <class ItemType> 
void DoublyLinkedList<ItemType>::InsertItem(ItemType item) 
{ 
    NodeType<ItemType>* node = new NodeType<ItemType>; 
    node->info = item; 
    if (!length) 
    { 
     listData = node; 
     node->next = NULL; 
     node->back = NULL; 
     length++; 
     return; 
    } 

    NodeType<ItemType>* temp = listData; 
    while (temp) 
    { 
     // get the next node 
     NodeType<ItemType>* nextNode = temp->next; 

     // make sure we have a pair of nodes 
     if (nextNode) 
     { 
      // test for inbetween 
      if (item >= temp->info && item <= nextNode->info) 
      { 
       // set the pointers and return 
       // make sure we set the node in-between the temp and nextNode 
       temp->next = node; 
       nextNode->back = node; 

       // now set node to point to temp (back), and nextNode (next) 
       // for the in-between to link correctly 
       node->next = nextNode; 
       node->back = temp; 

       // increase the length and get out 
       ++length; 
       return; 
      } 
     } 
     else 
     { 
      // we're at the last node, so only place for this is at the back 
      // set the pointers and return 
      temp->next = node; 
      node->back = temp; 

      // last node, so make sure it points to NULL as next 
      node->next = NULL; 

      // increase length and get out 
      ++length; 
      return; 
     } 
     // go to next node and get next pair 
     temp = nextNode; 
    } 
} 

이제는 작동합니다. 더 나아질 수 있습니까? 아마, 요점은 무슨 일이 일어나고 있는지 이해하기 쉽다는 것입니다.

수행해야 할 일을 종이로 그린 경우 위의 내용은 종이에 그릴 내용에 가장 근접한 것입니다. 즉 노드가 2 개인 경우 항목이 두 노드 사이에 들어가는 지 확인하십시오. 그렇지 않은 경우 get 다음 노드 쌍 등 ...