C++を実現する双方向循環チェーン表
本論文の例では、C++双方向循環チェーンの具体的なコードを共有しています。参考にしてください。具体的な内容は以下の通りです。
一、概念
1.ダブルリンク表の各ノードは、2つのリンクポインタが必要です。
lLink->前駆の結点を指します。 （前駆ポインタまたは左鎖ポインタ）
rLink->後続の結点（後駆ポインタまたは右チェーンポインタ）を指します。
2.デュアルチェーンは常に付加的なヘッダ・ノードを持つ循環チェーンの方式を採用しています。
first：ヘッドポインタ、データを保存しない、または特別な要求のデータを保存します。そのlLinkは二重リンクの最後の結点を指しています。
そのrLinkは二重リンク表の最初の結点（最初の有効な結点）を指します。チェーンの最初の接合点の左チェーンの針lLinkと最後の接合点の右チェーンの針
rLinkは付加的な頭の結点を指します。
二、実現プログラム
1.DblList.h
一、概念
1.ダブルリンク表の各ノードは、2つのリンクポインタが必要です。
lLink->前駆の結点を指します。 （前駆ポインタまたは左鎖ポインタ）
rLink->後続の結点（後駆ポインタまたは右チェーンポインタ）を指します。
2.デュアルチェーンは常に付加的なヘッダ・ノードを持つ循環チェーンの方式を採用しています。
first：ヘッドポインタ、データを保存しない、または特別な要求のデータを保存します。そのlLinkは二重リンクの最後の結点を指しています。
そのrLinkは二重リンク表の最初の結点（最初の有効な結点）を指します。チェーンの最初の接合点の左チェーンの針lLinkと最後の接合点の右チェーンの針
rLinkは付加的な頭の結点を指します。
二、実現プログラム
1.DblList.h
#ifndef DblList_h
#define DblList_h
#include <iostream>
using namespace std;
template <class T>
struct DblNode { //
T data;
DblNode<T> *lLink, *rLink; // （ ） （ ）
DblNode(DblNode<T> *left = NULL, DblNode<T> *right = NULL):lLink(left), rLink(right){} //
DblNode(T value, DblNode<T> *left = NULL, DblNode<T> *right = NULL):data(value), lLink(left), rLink(right){} //
};
template <class T>
class DblList { // （ ）
public:
DblList(); // ：
~DblList(); // ：
void createDblList(); //
int Length()const; //
bool isEmpty(); //
DblNode<T> *getHead()const; //
void setHead(DblNode<T> *ptr); //
DblNode<T> *Search(const T x); // x
DblNode<T> *Locate(int i, int d); // i ，d=0 ，
bool Insert(int i, const T x, int d); // i x，d=0 ，
bool Remove(int i, T &x, int d); // i ，x ，d=0 ，
void Output(); //
private:
DblNode<T> *first; //
};
template <class T>
DblList<T>::DblList() {
// ：
first = new DblNode<T>();
if(NULL == first) {
cerr << " ！" << endl;
exit(1);
}
first->rLink = first->lLink = first; //
}
template <class T>
DblList<T>::~DblList() { // ：
DblNode<T> *current = first->rLink;
while(current != first) {
current->rLink->lLink = current->lLink; // lLink
current->lLink->rLink = current->rLink; // rLink
delete current; //
current = first->rLink;
}
delete first;
first = NULL;
}
template <class T>
void DblList<T>::createDblList() {
//
int n, val;
DblNode<T> *current = first;
cout << " n:";
cin >> n;
cout << " ：" << endl;
for(int i = 0; i < n; i++) {
cin >> val;
DblNode<T> *newNode = new DblNode<T>(val);
if(NULL == newNode) {
cerr << " ！" << endl;
exit(1);
}
//
while(current->rLink != first)
current = current->rLink; //
newNode->rLink = current->rLink;
current->rLink = newNode;
newNode->rLink->lLink = newNode;
newNode->lLink = current;
current = current->rLink; // current
}
}
template <class T>
int DblList<T>::Length()const {
//
DblNode<T> *current = first->rLink;
int count = 0;
while(current != first) {
current = current->rLink;
count++;
}
return count;
}
template <class T>
bool DblList<T>::isEmpty() {
//
return first->rLink == first;
}
template <class T>
DblNode<T> *DblList<T>::getHead()const {
//
return first;
}
template <class T>
void DblList<T>::setHead(DblNode<T> *ptr) {
//
first = ptr;
}
template <class T>
DblNode<T> *DblList<T>::Search(const T x) {
// x
DblNode<T> *current = first->rLink;
while(current != first && current->data != x)
current = current->rLink;
if(current != first)
return current; //
else //
return NULL;
}
template <class T>
DblNode<T> *DblList<T>::Locate(int i, int d) {
//
if((first->rLink == first) || (i = 0))
return first;
DblNode<T> *current;
if(d == 0)
current = first->lLink; //
else
current = first->rLink;
for(int j = 1; j < i; j++)
{
if(current == first)
break;
else if(d == 0)
current = current->lLink;
else
current = current->rLink;
}
if(current != first) //
return current;
else
return NULL;
}
template <class T>
bool DblList<T>::Insert(int i, const T x, int d) {
//
DblNode<T> *current = Locate(i, d); // i
if(current == NULL) // i ，
return false;
DblNode<T> *newNode = new DblNode<T>(x);
if(newNode == NULL) {
cerr << " ！" << endl;
exit(1);
}
if(d == 0) { //
newNode->lLink = current->lLink;
current->lLink = newNode;
newNode->lLink->rLink = newNode;
newNode->rLink = current;
}
else { //
newNode->rLink = current->rLink;
current->rLink = newNode;
newNode->rLink->lLink = newNode;
newNode->lLink = current;
}
return true;
}
template <class T>
bool DblList<T>::Remove(int i, T &x, int d) {
//
DblNode<T> *current = Locate(i, d); // i
if(current == NULL) // i ，
return false;
current->rLink->lLink = current->lLink; // lLink
current->lLink->rLink = current->rLink; // rLink
x = current->data;
delete current; //
current = NULL; //
return true; //
}
template <class T>
void DblList<T>::Output() {
//
DblNode<T> *current = first->rLink;
while(current != first) {
cout << current->data << " ";
current = current->rLink;
}
cout << endl;
}
#endif /* DblList_h */
#include "DblList.h"
using namespace std;
int main(int argc, const char * argv[]) {
int finished = 0, choice, i, x, d, len; // i i ，d: -》0 ，
DblList<int> L;
DblNode<int> *head = NULL, *current;
while(!finished) {
cout << "
********* *********
";
cout << "1:
";
cout << "2:
";
cout << "3: ？
";
cout << "4:
";
cout << "5:
";
cout << "6: x
";
cout << "7: i ，d=0 ，
";
cout << "8: i x，d=0 ，
";
cout << "9: i ，x ，d=0 ，
";
cout << "10: :
";
cout << "11:
";
cout << " [1-11]：
";
cin >> choice;
switch(choice) {
case 1:
L.createDblList(); //
break;
case 2:
len = L.Length(); //
cout << " ：" << len << endl;
break;
case 3:
if(L.isEmpty()) //
cout << " " << endl;
else
cout << " " << endl;
break;
case 4:
head = L.getHead();
break;
case 5:
L.setHead(head); //
break;
case 6:
cout << " x:";
cin >> x;
if(L.Search(x) != NULL)
cout << " ！" << endl;
else
cout << " ！" << endl;
break;
case 7:
cout << " i i d(d=0 ， ):";
cin >> i >> d;
current = L.Locate(i, d);
if(current == NULL)
cout << " !" << endl;
else
cout << " ！" << endl;
break;
case 8:
cout << " i x，d=0 ， 。 i, x d:";
cin >> i >> x >> d;
if(L.Insert(i, x, d))
cout << " !" << endl;
else
cout << " ！" << endl;
break;
case 9:
cout << " i ，x ，d=0 ， 。 i d:";
cin >> i >> d;
if(L.Remove(i, x, d))
cout << " ， ：" << x << endl;
else
cout << " ！" << endl;
break;
case 10:
cout << " ：" << endl;
L.Output();
break;
case 11:
finished = 1;
break;
default:
cout << " , ！" << endl;
} // switch
} // while
return 0;
}