鏈接列表：以C++的物理和邏輯順序顯示列表

Question

我想弄清楚如何讓我的鏈接列表以數字順序顯示數值變量。我知道我需要設置另一個空白，但我迷失了，按數字順序設置。這裏是我的源代碼：

#include <iostream> 
struct node 
{ 
    int number; 
    node *next; 
}; 
bool isEmpty(node *head); 
char menu(); 
void insertAsFirstElement(node *&head, node *&last, int number); 
void insert(node *&head, node *&last, int number); 
void remove(node *&head, node *&last); 
void showList(node *current); 
void showLogic(node *current); 

bool isEmpty(node *head) 
{ 
    if (head == NULL) 
     return true; 
    else 
     return false; 
} 

char menu() 
{ 
    char choice; 
    cout << "Menu\n"; 
    cout << "1. Add an item.\n"; 
    cout << "2. Remove an item.\n"; 
    cout << "3. Show the list Physically.\n"; 
    cout << "4. Show the list Logically.\n"; 
    cout << "5. Exit.\n"; 

    cin >> choice; 
    return choice; 

} 

void insertAsFirstElement(node *&head, node *&last, int number) 
{ 
    node *temp = new node; 
    temp->number = number; 
    temp->next = NULL; 
    head = temp; 
    last = temp; 
} 

void insert(node *&head, node *&last, int number) 
{ 
    if (isEmpty(head)) 
     insertAsFirstElement(head, last, number); 
    else 
    { 
     node *temp = new node; 
     temp->number = number; 
     temp->next = NULL; 
     last->next = temp; 
     last = temp; 
    } 
} 

void remove(node *&head, node *&last) 
{ 
    if (isEmpty(head)) 
     cout << "The list is already empty.\n"; 
    else if (head == last) 
    { 
     delete head; 
     head == NULL; 
     last == NULL; 
    } 
    else 
    { 
     node *temp = head; 
     head = head->next; 
     delete temp; 
    } 
} 

void showList(node *current) 
{ 
    if (isEmpty(current)) 
     cout << "The list is empty\n"; 
    else 
    { 
     cout << "The list contains: \n"; 
     while(current != NULL) 
     { 
      cout << current->number << endl; 
      current = current->next; 
     } 
    } 
} 

void showLogic(node *current) 
{ 

} 

int main() 
{ 
    node *head = NULL; 
    node *last = NULL; 

    char choice; 
    int number; 

    do 
    { 
     choice = menu(); 
     switch(choice) 
     { 
     case '1': cout << "Please enter a number: "; 
        cin >> number; 
        insert (head,last,number); 
        break; 
     case '2': remove(head,last); 
        break; 
     case '3': showList(head); 
        break; 
     case '4': 
      break; 
     default: cout << "System Exit\n"; 
     } 
    } 
    while(choice != '5'); 

    system ("pause"); 
    return 0; 
} 

Answer 1

一種解決方案是排序鏈接列表。最簡單的方法是獲取列表中的值，將它們存儲在容器中，然後對容器進行排序。既然你不允許改變節點的順序（保持物理順序），或許就顯示排序列表而言，這是最好的選擇。首先，從頭到尾遍歷列表 - 你的showList（）函數已經完成了大部分工作。但是，不是顯示每個節點，而是將該節點的數據放入容器（動態數組，矢量或簡單數組）中。如果它是一個簡單的數組，請確保您有足夠的空間容納所有元素，並記錄元素的數量。

然後你拿出容器，並使用任意數量的排序算法進行排序 - 最簡單的就是氣泡排序。然後，將排序後的容器顯示給用戶。

所以總結一下，你實際上並沒有改變鏈表，甚至在很大程度上使用鏈表。你所要做的就是收集每個節點中的所有數據，將它放在一個容器中，然後所有真正的排序工作從鏈接列表轉移到容器。