C++實現雙向循環鏈表

本文實例為大家分享了C++實現雙向循環鏈表的具體代碼，供大家參考，具體內容如下

一、概念

1.在雙鏈表中的每個結點應有兩個鏈接指針：

lLink -> 指向前驅結點 （前驅指針或者左鏈指針）

rLink->指向後繼結點（後驅指針或者右鏈指針）

2.雙鏈表常採用帶附加頭結點的循環鏈表方式：

first：頭指針，不存放數據，或者存放特殊要求的數據。它的lLink指向雙鏈表的尾結點（最後一個結點），

它的rLink指向雙鏈表的首結點（第一個有效結點）。鏈表的首結點的左鏈指針lLink和尾結點的右鏈指針

rLink都指向附加頭結點。

二、實現程序

1.DblList.h

#ifndef DblList_h #define DblList_h #include

using namespace std; templatestruct DblNode { // 鏈表結點定義 T data; DblNode*lLink, *rLink; // 鏈表前驅（左鏈）和後繼（右鏈）指針 DblNode(DblNode*left = NULL, DblNode*right = NULL):lLink(left), rLink(right){} // 構造函數 DblNode(T value, DblNode*left = NULL, DblNode*right = NULL):data(value), lLink(left), rLink(right){} // 構造函數 }; templateclass DblList { // 雙鏈表（雙向循環鏈表） public: DblList(); // 構造函數：建立附加頭結點 ~DblList(); // 析構函數：釋放所有存儲 void createDblList(); // 創建雙向鏈表 int Length()const; // 計算雙鏈表的長度 bool isEmpty(); // 判雙鏈表空否 DblNode*getHead()const; // 取附加頭結點 void setHead(DblNode*ptr); // 設置附加頭結點地址 DblNode*Search(const T x); // 在鏈表中沿後繼方向尋找等於給定值x的結點 DblNode*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*first; // 附加頭結點 }; templateDblList::DblList() { // 構造函數：建立附加頭結點 first = new DblNode(); if(NULL == first) { cerr << "動態分配內存空間失敗！" << endl; exit(1); } first->rLink = first->lLink = first; // 指向自身 } templateDblList::~DblList() { // 析構函數：釋放所有存儲 DblNode*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; } templatevoid DblList::createDblList() { // 創建雙向鏈表 int n, val; DblNode*current = first; cout << "請輸入要輸入的個數n:"; cin >> n; cout << "請輸入要輸入的數：" << endl; for(int i = 0; i < n; i++) { cin >> val; DblNode*newNode = new DblNode(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往後移 } } templateint DblList::Length()const { // 計算雙鏈表的長度 DblNode*current = first->rLink; int count = 0; while(current != first) { current = current->rLink; count++; } return count; } templatebool DblList::isEmpty() { // 判雙鏈表空否 return first->rLink == first; } templateDblNode*DblList::getHead()const { // 取附加頭結點 return first; } templatevoid DblList::setHead(DblNode*ptr) { // 設置附加頭結點地址 first = ptr; } templateDblNode*DblList::Search(const T x) { // 在鏈表中沿後繼方向尋找等於給定值x的結點 DblNode*current = first->rLink; while(current != first && current->data != x) current = current->rLink; if(current != first) return current; // 搜索成功 else // 搜索失敗 return NULL; } templateDblNode*DblList::Locate(int i, int d) { // 定位 if((first->rLink == first) || (i = 0)) return first; DblNode*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; } templatebool DblList::Insert(int i, const T x, int d) { // 插入 DblNode*current = Locate(i, d); // 查找第i個結點 if(current == NULL) // i不合理，插入失敗 return false; DblNode*newNode = new DblNode(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; } templatebool DblList::Remove(int i, T &x, int d) { // 刪除 DblNode*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; // 刪除成功 } templatevoid DblList::Output() { // 輸出雙鏈表中的數據 DblNode*current = first->rLink; while(current != first) { cout << current->data << " "; current = current->rLink; } cout << endl; } #endif /* DblList_h */

2.main.cpp

#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表示前驅方向，否則為後繼方向 DblListL; DblNode*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; }