双方向リスト

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を使用しました。新しい名前は、より多くの意味を作るためのいずれか、またはそれらの名前それは私が（>nNode - >Node、Add_start - - >AddNode、nItemList）識別子の一部に改名ので、私は#include <stdlib.h>

• を追加する必要がありましたに関するsystem機能を訴え：私は追加の引数を追加することによって、（強化

• （そのソリューションは、あなたのオリジナルのポストにできるだけ近い）私は最小限の変更を維持しようとした一貫性のある

• です0（デフォルト値：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; 
}