將未排序的鏈接列表變成已排序的鏈接列表？ （C++）

Question

我有問題試圖將INSERT函數轉換爲按字母順序排列節點的函數。我寫下了迄今爲止我嘗試過的內容......但它只檢查第一個節點的名稱，以查看它是否大於函數參數中新節點的給定名稱。有人可以給我一個關於如何能夠移動通過每個節點並且能夠比較它們的鍵（名稱）並相應地將它們左右放置的想法嗎？下面是我在我的代碼和我的INSERT功能到目前爲止...

// UnSortedLnkList.h 
    //---------------------------- 

    #include <iostream> 
    #include <afxwin.h> 

    using namespace std; 

    #define new DEBUG_NEW 

    struct Node { 
     string m_name; // key 
     int m_age; 

     Node* m_next; 
     Node(const string& name, int age, Node* next = NULL); 
    }; 

    ostream& operator<< (ostream&, const Node&); 

    class ULnkList { 
     friend ostream& operator<< (ostream&, const ULnkList&); // 1.5 
    public: 
     ULnkList(); 
     // copy ctor 
     ULnkList(const ULnkList& existingList);   // 5 
     ~ULnkList();          // 4 

     bool IsEmpty() const; 
     int Size() const; 
     bool Insert(const string& name, int age);   // 1 
     bool Delete(const string& name);     // 3 
     bool Lookup(const string& name, int& age) const; // 2 

     ULnkList& operator =(const ULnkList& list2);  // 6 

     bool Delete2(const string& name); 


    private: 

     Node* m_head; // points to head of the list 
     int m_num;  // the number of entries in the list 

     // helper functions: 
     void Clear();          // 7 
     void Copy(const ULnkList& list2);     // 8 
    }; 


    // UnSortedLnkList.cpp 
    //---------------------------- 
    #include "UnSortedLnkList.h" 
    #include <iostream> 
    #include <string> 
    using namespace std; 

    Node::Node(const string& name, int age, Node* next) 
    : m_name(name), m_age(age), m_next(next) 
    {} 


    ostream& operator<< (ostream& os, const Node& n) // cout << n; 
    { 
     os << "Name: " << n.m_name << "\tAge: " << n.m_age; 
     return os; 
    } 

    ULnkList::ULnkList() 
    : m_head(new Node("",-99,NULL)), m_num(0) 
    { 
     //m_head = new Node("",-99,NULL); 
    } 
    // 
    ULnkList::ULnkList(const ULnkList& existingList) 
    { 
     Copy(existingList); 
    } 

    void ULnkList::Copy(const ULnkList& existingList) 
    { 
     m_num = existingList.m_num; 
     // create dummy node 
     m_head = new Node("",-99,NULL); 
     // traverse existing list 
     Node *pe = existingList.m_head->m_next; 
     Node *pThis = m_head; 
     while(pe != 0) 
     { 
      // create a copy of the Node in OUR list 
      pThis->m_next = new Node(pe->m_name,pe->m_age,0); 

      // update pointers 
      pe = pe->m_next; 
      pThis = pThis->m_next; 
     } 
    } 

    void ULnkList::Clear() 
    { 
     Node *p = m_head->m_next; 
     Node *tp = m_head;   // trail pointer 
     while(p != 0) 
     { 
      delete tp; 

      // update pointers 
      tp = p; // 
      p = p->m_next; 
     } 

     delete tp; 
    } 

    ULnkList& ULnkList::operator =(const ULnkList& list2) // list1 = list2; 
    { 
     // list1 = list1; // check for self-assignment 
     if(this != &list2) 
     { 
      this->Clear(); // normally Clear(); 
      this->Copy(list2); 
     } 

     // l1 = l2 = l3; 

     return *this; 
    } 

    bool ULnkList::IsEmpty() const 
    { 
     return m_num == 0; 
     // return m_head->m_next == NULL; 
    } 

    int ULnkList::Size() const 
    { 

     return m_num; 
    } 
    // 

    ULnkList::Insert(const string& name, int age) 
    { 
     Node *current = m_head->m_next; 
     Node *previous = m_head; 
     if (m_head->m_next == NULL) 
     { 
      m_head->m_next = new Node(name,age,m_head->m_next); 
      m_num++; 
      return true; 
     } 
     if (name < m_head->m_next->m_name) 
     { 
      m_head->m_next = new Node(name,age,m_head->m_next); 
      m_num++; 
      return true; 
     } 




     return true; 
    } 

    // 
    ostream& operator<< (ostream& os, const ULnkList& list) // cout << list; 
    { 
     Node *p = list.m_head->m_next; // first node with data 

     while(p != 0) 
     { 
      cout << *p << endl; // ???? 

      // update p 
      p = p->m_next; 
     } 
     cout << "--------------------------------------" << endl; 

     return os; 
    } 

    // input: name 
    //// output: age if found 
    bool ULnkList::Lookup(const string& name, int& age) const 
    { 
     // linear search 
     Node *p = m_head->m_next; 

     while(p != 0) 
     { 
      if(name == p->m_name) 
      { 
       // found it 
       age = p->m_age; 
       return true; 
      } 

      // update p 
      p = p->m_next; 
     } 
     return false; 
    } 
    // 
    bool ULnkList::Delete(const string& name) 
    { 
     Node *p = m_head->m_next; 
     Node *tp = m_head;   // trail pointer 
     while(p != 0) 
     { 
      if(name == p->m_name) 
      { 
       // found it, so now remove it 
       // fix links 
       tp->m_next = p->m_next; 
       // delete the node 
       delete p; 

       return true; 
      } 

      // update pointers 
      tp = p; // tp = tp->m_next; 
      p = p->m_next; 
     } 
     return false; 
    } 

    bool ULnkList::Delete2(const string& name) 
    { 
     Node *p = m_head; 
     while(p->m_next != 0)  // ????? 
     { 
      if(p->m_next->m_name == name) 
      { 
       Node *save = p->m_next; 
       // remove the node 
       // fix links 
       p->m_next = p->m_next->m_next; 
       // delete memory 
       delete save; 
       return true; 
      } 

      // update pointers 
      p = p->m_next; 
     } 
     return false; 
    } 
    // 
    ULnkList::~ULnkList() 
    { 
     Clear(); 
    } 
    // 

Answer 1

我猜這是家庭作業，所以我不打算寫的代碼。我建議你通過比較輸入字符串，然後執行插入邏輯，你的Insert（）函數可以從頭部移動列表直到它到達'正確'位置。這是假設您必須使用文字列表作爲您的數據結構。如果您希望平均獲得更好的插入性能，則可以使用二叉樹作爲基礎結構，但這會使列表遍歷更加複雜。

Answer 2

你的問題就出在這代碼：

if (name < m_head->m_next->m_name) 
    { 
     m_head->m_next = new Node(name,age,m_head->m_next); 
     m_num++; 
     return true; 
    } 

爲了以排序方式插入，我想可能是某種輔助函數與遞歸函數調用。

，但是這可能工作：

Node *current = m_head; 
if(name > m_head->m_name){ 
    while(name > current->m_next->m_name){ 
     current = current->m_next; 
    } 
    current->m_next = new Node(name,age,current->m_next); 
} 
else{ 
    m_head = new Node(name,age,m_head); 
}  

這將在遞增排序的方式插入。 我還沒有測試過，但是讓我知道它是否有效！希望這可以幫助！

Answer 3

我有一個忠告此代碼

if(name > m_head->m_name){ 
while(name > current->m_next->m_name){ 
    current = current->m_next; 
} 
// add temp = current->next 
current->m_next = new Node(name,age) 
// current->next->next = temp 

你不想失去你插入其中後面的列表。