雙向列表

Question

以下代碼計算大於3且小於8的單向列表項的元素總和，並將總和的結果更改爲列表的開頭。

#include <iostream> 

using namespace std; 

struct List 
{ 
    int num; 
    List* nItem; 
}; 

int Input() 
{ 
    int number; 
    cout << "Enter the number: "; cin >> number; 
    return number; 
} 

void MakeList(List **head, int n) 
{ 
    if (n > 0) { 
     *head = new List; 
     (*head)->num = Input(); 
     (*head)->nItem = NULL; 
     MakeList(&(*head)->nItem, n - 1); 
    } 
} 

void Print(List* head) 
{ 

    if (head != NULL) { 
     cout << head->num << " "; 
     Print(head->nItem); 
    } 
} 

List* Add_start(List* head, int index, int elm) 
{ 
    List* p = new List; 
    p->num = elm; 
    p->nItem = NULL; 

    if (head == NULL) { 
     head = p; 
    } 
    else { 
     List* current = head; 
     for (int i = 0; (i < index - 1) && (current->nItem != NULL); i++) 
     { 
      current = current->nItem; 
     } 
     if (index == 0) 
     { 
      p->nItem = head; 
      head = p; 
     } 
     else { 
      if (current->nItem != NULL) { 
       p->nItem = current->nItem; 
      } 
      current->nItem = p; 
     } 
    } 

    return head; 
} 

int Sum(List* head) 
{ 
    int sum = 0; 
    List* p = head; 
    while(p) { 
     if ((p->num > 3) && (p->num < 8)) 
      sum += p->num; 
     p = p->nItem; 
    } 

    return sum; 
} 

void DeleteList(List* head) 
{ 
    if (head != NULL) { 
     DeleteList(head->nItem); 
     delete head; 
    } 
} 

int main() 
{ 
    int n = 10; 
    List* head = NULL; 

    cout << "Enter 10 number to the list\n" << endl; 
    MakeList(&head, n); 
    int sum = Sum(head); 
    head = Add_start(head, 0, sum); 

    cout << "\nList: "; 
    Print(head); 
    cout << endl; 

    DeleteList(head); 

    system("pause"); 
    return 0; 
} 

如何使用雙向列表執行相同的操作？

Answer 1

注：

• 雙向（或雙聯的）列表中，還具有指向前一節點的成員：這是在2種列表類型之間的整體差別（作爲結果的第一元素 - 或者位於左側的列表中，該成員將指向NULL）。所以，當這樣一個節點被創建/插入到列表中時，這個新成員也應該被設置（我在代碼中發生了這種情況的地方發表了評論），新節點和它後面的節點（如果有的話）。

• 我修改瞭如何創建列表的方式 - MakeList替換爲_MakeList2 + MakeList2;在下劃線（_）在_MakeList2參數表明這是莫名其妙私人（約定從借來的Python） - 它是不是很漂亮，但我認爲它更容易這樣

• 我沒有的Visual Studio在這臺電腦上，所以我用gcc。它抱怨system功能，所以我不得不添加#include <stdlib.h>

• 我改名一些標識符（List - >Node，Add_start - >AddNode，nItem - >nNode）或者是因爲新的名稱更有意義，或者他們的名字是一致的

• 我試圖保持變爲最小（所以解決的辦法是儘可能接近你原來的職位）

• 我增強（通過增加一個額外的參數：toRight（默認值：1））的Print FUNC，所以它可以遍歷列表兩種方式 - 刪除列表

• 我糾正一些（小了，我循環到左（用於測試目的右））編碼作風問題

下面是修改後的代碼：

#include <iostream> 
#include <stdlib.h> 

using namespace std; 

struct Node { 
    int num; 
    Node *pNode, *nNode; // Add a new pointer to the previous node. 
}; 

int Input() { 
    int number; 
    cout << "Enter the number: "; cin >> number; 
    return number; 
} 

Node *_MakeList2(int n, Node *last=NULL) { 
    if (n > 0) { 
     Node *node = new Node; 
     node->num = Input(); 
     node->pNode = last; 
     node->nNode = _MakeList2(n - 1, node); 
     return node; 
    } 
    return NULL; 
} 

Node *MakeList2(int n) { 
    return _MakeList2(n); 
} 

void Print(Node *head, int toRight=1) { 
    if (head != NULL) { 
     cout << head->num << " "; 
     if (toRight) 
      Print(head->nNode, 1); 
     else 
      Print(head->pNode, 0); 
    } 
} 

Node* AddNode(Node *head, int index, int elm) { 
    Node *p = new Node; 
    p->num = elm; 
    p->pNode = NULL; // Make the link between this node and the previous one. 
    p->nNode = NULL; 

    if (head == NULL) { 
     head = p; 
    } else { 
     Node *current = head; 
     for (int i = 0; (i < index - 1) && (current->nNode != NULL); i++) { 
      current = current->nNode; 
     } 
     if (index == 0) { 
      p->nNode = head; 
      head->pNode = p; // Make link between next node's previous node and the current one. 
      head = p; 
     } else { 
      if (current->nNode != NULL) { 
       p->nNode = current->nNode; 
      } 
      p->pNode = current; // Make the link between this node and the previous one. 
      current->nNode = p; 
     } 
    } 
    return head; 
} 

int Sum(Node* head) { 
    int sum = 0; 
    Node *p = head; 
    while(p) { 
     if ((p->num > 3) && (p->num < 8)) 
      sum += p->num; 
     p = p->nNode; 
    } 

    return sum; 
} 

void DeleteList(Node *head) { 
    if (head != NULL) { 
     DeleteList(head->nNode); 
     delete head; 
    } 
} 

int main() { 
    int n = 10; 
    Node *head = NULL, *tail = NULL; 

    cout << "Enter " << n << " number(s) to the list" << endl << endl; 
    head = MakeList2(n); 
    int sum = Sum(head); 
    head = AddNode(head, 0, sum); 

    cout << endl << "List: "; 
    Print(head); 
    cout << endl; 

    tail = head; 
    if (tail) { 
     while (tail->nNode != NULL) 
      tail = tail->nNode; 
     cout << endl << "List reversed: "; 
     Print(tail, 0); 
     cout << endl; 
    } 
    DeleteList(head); 

    system("pause"); 
    return 0; 
}