c语言实现双向循环链表（c语言双向循环链表）

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

一、概念

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

lLink -> 指向前驱结点（前驱指针或者左链指针）

rLink->指向后继结点（后驱指针或者右链指针）

2.双链表常采用带附加头结点的循环链表方式：

first：头指针，不存放数据，或者存放特殊要求的数据。它的lLink指向双链表的尾结点（最后一个结点），

它的rLink指向双链表的首结点（第一个有效结点）。链表的首结点的左链指针lLink和尾结点的右链指针

rLink都指向附加头结点。

二、实现程序

1.DblList.h

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 #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 */

2.main.cpp

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 #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; }