本文实例为大家分享了C++实现双向循环链表的具体代码，供大家参考，具体内容如下

一、概念

1.在双链表中的每个结点应有两个链接指针：

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

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表示前驱方向，否则为后继方向 DblList<int> L; DblNode<int> *head = NULL, *current; while(!finished) { cout << "\n*********菜单*********\n"; cout << "1:建立双链表\n"; cout << "2:双链表的长度\n"; cout << "3:双链表是否为空？\n"; cout << "4:取附加头结点\n"; cout << "5:设置附加头结点地址\n"; cout << "6:在链表中沿后继方向寻找等于给定值x的结点\n"; cout << "7:在链表中定位第i个结点，d=0按前驱方向，否则按后继方向\n"; cout << "8:在第i个结点后插入x，d=0按前驱方向，否则按后继方向\n"; cout << "9:删除第i个结点，x带回删除其值，d=0按前驱方向，否则按后继方向\n"; cout << "10:输出双链表中的数据:\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); // 设置附加头结点地址 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;}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。