双向列表

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; 
}