C++實現(xiàn)雙向循環(huán)鏈表
更新時間：2020年04月27日 16:04:43 作者：ChanJose
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)雙向循環(huán)鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
本文實例為大家分享了C++實現(xiàn)雙向循環(huán)鏈表的具體代碼，供大家參考，具體內(nèi)容如下
一、概念
1.在雙鏈表中的每個結(jié)點應(yīng)有兩個鏈接指針：
lLink -> 指向前驅(qū)結(jié)點 （前驅(qū)指針或者左鏈指針）
rLink->指向后繼結(jié)點（后驅(qū)指針或者右鏈指針）
2.雙鏈表常采用帶附加頭結(jié)點的循環(huán)鏈表方式：
first：頭指針，不存放數(shù)據(jù)，或者存放特殊要求的數(shù)據(jù)。它的lLink指向雙鏈表的尾結(jié)點（最后一個結(jié)點），
它的rLink指向雙鏈表的首結(jié)點（第一個有效結(jié)點）。鏈表的首結(jié)點的左鏈指針lLink和尾結(jié)點的右鏈指針
rLink都指向附加頭結(jié)點。
二、實現(xiàn)程序
1.DblList.h
#ifndef DblList_h
#define DblList_h
#include <iostream>
using namespace std;
template <class T>
struct DblNode { // 鏈表結(jié)點定義
T data;
DblNode<T> *lLink, *rLink; // 鏈表前驅(qū)（左鏈）和后繼（右鏈）指針
DblNode(DblNode<T> *left = NULL, DblNode<T> *right = NULL):lLink(left), rLink(right){} // 構(gòu)造函數(shù)
DblNode(T value, DblNode<T> *left = NULL, DblNode<T> *right = NULL):data(value), lLink(left), rLink(right){} // 構(gòu)造函數(shù)
};
template <class T>
class DblList { // 雙鏈表（雙向循環(huán)鏈表）
public:
DblList(); // 構(gòu)造函數(shù)：建立附加頭結(jié)點
~DblList(); // 析構(gòu)函數(shù)：釋放所有存儲
void createDblList(); // 創(chuàng)建雙向鏈表
int Length()const; // 計算雙鏈表的長度
bool isEmpty(); // 判雙鏈表空否
DblNode<T> *getHead()const; // 取附加頭結(jié)點
void setHead(DblNode<T> *ptr); // 設(shè)置附加頭結(jié)點地址
DblNode<T> *Search(const T x); // 在鏈表中沿后繼方向?qū)ふ业扔诮o定值x的結(jié)點
DblNode<T> *Locate(int i, int d); // 在鏈表中定位第i個結(jié)點，d=0按前驅(qū)方向，否則按后繼方向
bool Insert(int i, const T x, int d); // 在第i個結(jié)點后插入x，d=0按前驅(qū)方向，否則按后繼方向
bool Remove(int i, T &x, int d); // 刪除第i個結(jié)點，x帶回刪除其值，d=0按前驅(qū)方向，否則按后繼方向
void Output(); // 輸出雙鏈表中的數(shù)據(jù)
private:
DblNode<T> *first; // 附加頭結(jié)點
};
template <class T>
DblList<T>::DblList() {
// 構(gòu)造函數(shù)：建立附加頭結(jié)點
first = new DblNode<T>();
if(NULL == first) {
cerr << "動態(tài)分配內(nèi)存空間失??！" << endl;
exit(1);
}
first->rLink = first->lLink = first; // 指向自身
}
template <class T>
DblList<T>::~DblList() { // 析構(gòu)函數(shù)：釋放所有存儲
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() {
// 創(chuàng)建雙向鏈表
int n, val;
DblNode<T> *current = first;
cout << "請輸入要輸入的個數(shù)n:";
cin >> n;
cout << "請輸入要輸入的數(shù)：" << endl;
for(int i = 0; i < n; i++) {
cin >> val;
DblNode<T> *newNode = new DblNode<T>(val);
if(NULL == newNode) {
cerr << "動態(tài)分配內(nèi)存空間失??！" << 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 {
// 取附加頭結(jié)點
return first;
}
template <class T>
void DblList<T>::setHead(DblNode<T> *ptr) {
// 設(shè)置附加頭結(jié)點地址
first = ptr;
}
template <class T>
DblNode<T> *DblList<T>::Search(const T x) {
// 在鏈表中沿后繼方向?qū)ふ业扔诮o定值x的結(jié)點
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; // 搜索前驅(qū)方向
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個結(jié)點
if(current == NULL) // i不合理，插入失敗
return false;
DblNode<T> *newNode = new DblNode<T>(x);
if(newNode == NULL) {
cerr << "內(nèi)存空間分配失?。? << endl;
exit(1);
}
if(d == 0) { // 前驅(qū)方向插入
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個結(jié)點
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() {
// 輸出雙鏈表中的數(shù)據(jù)
DblNode<T> *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表示前驅(qū)方向，否則為后繼方向
DblList<int> L;
DblNode<int> *head = NULL, *current;
while(!finished) {
cout << "\n*********菜單*********\n";
cout << "1:建立雙鏈表\n";
cout << "2:雙鏈表的長度\n";
cout << "3:雙鏈表是否為空？\n";
cout << "4:取附加頭結(jié)點\n";
cout << "5:設(shè)置附加頭結(jié)點地址\n";
cout << "6:在鏈表中沿后繼方向?qū)ふ业扔诮o定值x的結(jié)點\n";
cout << "7:在鏈表中定位第i個結(jié)點，d=0按前驅(qū)方向，否則按后繼方向\n";
cout << "8:在第i個結(jié)點后插入x，d=0按前驅(qū)方向，否則按后繼方向\n";
cout << "9:刪除第i個結(jié)點，x帶回刪除其值，d=0按前驅(qū)方向，否則按后繼方向\n";
cout << "10:輸出雙鏈表中的數(shù)據(jù):\n";
cout << "11:退出\n";
cout << "請輸入選擇[1-11]：\n";
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); // 設(shè)置附加頭結(jié)點地址
break;
case 6:
cout << "請輸入要查找的值x:";
cin >> x;
if(L.Search(x) != NULL)
cout << "查找成功！" << endl;
else
cout << "查找失敗！" << endl;
break;
case 7:
cout << "請輸入要定位第i個結(jié)點的i和方向d(d=0按前驅(qū)方向，否則按后繼方向):";
cin >> i >> d;
current = L.Locate(i, d);
if(current == NULL)
cout << "定位失敗!" << endl;
else
cout << "定位成功！" << endl;
break;
case 8:
cout << "在第i個結(jié)點后插入x，d=0按前驅(qū)方向，否則按后繼方向。請輸入i, x和d:";
cin >> i >> x >> d;
if(L.Insert(i, x, d))
cout << "插入成功!" << endl;
else
cout << "插入失??！" << endl;
break;
case 9:
cout << "刪除第i個結(jié)點，x帶回刪除其值，d=0按前驅(qū)方向，否則按后繼方向。請輸入i和d:";
cin >> i >> d;
if(L.Remove(i, x, d))
cout << "刪除成功，刪除的值為：" << x << endl;
else
cout << "刪除失敗！" << endl;
break;
case 10:
cout << "雙鏈表中的數(shù)據(jù)為：" << endl;
L.Output();
break;
case 11:
finished = 1;
break;
default:
cout << "輸入錯誤, 請重新輸入！" << endl;
} // switch
} // while
return 0;
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
QTableWidget設(shè)置只讓某一列可編輯的實現(xiàn)
本文介紹了如何將QTableWidget的某一列設(shè)置為可編輯,以便用戶可以輸入自定義數(shù)據(jù),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-08-08
C語言數(shù)據(jù)結(jié)構(gòu)與算法之鏈表(一)
鏈表是線性表的鏈?zhǔn)酱鎯Ψ绞?。鏈表的?nèi)存是不連續(xù)的，前一個元素存儲地址的下一個地址中存儲的不一定是下一個元素。小編今天就將帶大家深入了解一下鏈表，快來學(xué)習(xí)吧2021-12-12
這篇文章主要為大家詳細(xì)介紹了基于樹莓派實現(xiàn)播放MP3音樂，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-06-06
這篇文章主要介紹了C++利用鏈表寫一個簡單的棧實例詳解的相關(guān)資料,需要的朋友可以參考下2017-05-05
c++中為什么可以通過指針或引用實現(xiàn)多態(tài)詳解
這篇文章主要給大家介紹了關(guān)于c++中為何可以通過指針或引用實現(xiàn)多態(tài)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
本篇文章是對C語言的指令進(jìn)行了詳細(xì)的分析與介紹，需要的朋友參考下2013-05-05
Cocos2d-x學(xué)習(xí)筆記之CCScene、CCLayer、CCSprite的默認(rèn)坐標(biāo)和默認(rèn)錨點實驗
這篇文章主要介紹了Cocos2d-x學(xué)習(xí)筆記之CCScene、CCLayer、CCSprite的默認(rèn)坐標(biāo)和默認(rèn)錨點實驗,這是一個非常值得研究的問題,需要的朋友可以參考下2014-09-09
本文給大家匯總介紹了3種c++實現(xiàn)生成不重復(fù)的隨機(jī)數(shù)的函數(shù)，十分的簡單實用，有需要的小伙伴可以參考下。2015-05-05
C++實現(xiàn)LeetCode(21.混合插入有序鏈表)
這篇文章主要介紹了C++實現(xiàn)LeetCode(21.混合插入有序鏈表),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語言函數(shù)調(diào)用底層實現(xiàn)原理分析
這篇文章主要介紹了C語言函數(shù)調(diào)用底層實現(xiàn)原理，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02