城乡住房和城乡建设部网站首页,wordpress 网站排名优化,手机网站建站cms,php开发微信小程序本文实例为大家分享了C实现双向循环链表的具体代码#xff0c;供大家参考#xff0c;具体内容如下一、概念1.在双链表中的每个结点应有两个链接指针#xff1a;lLink - 指向前驱结点 (前驱指针或者左链指针)rLink-指向后继结点(后驱指针或者右链指针)2.双链表常采用…本文实例为大家分享了C实现双向循环链表的具体代码供大家参考具体内容如下一、概念1.在双链表中的每个结点应有两个链接指针lLink - 指向前驱结点 (前驱指针或者左链指针)rLink-指向后继结点(后驱指针或者右链指针)2.双链表常采用带附加头结点的循环链表方式first头指针不存放数据或者存放特殊要求的数据。它的lLink指向双链表的尾结点(最后一个结点)它的rLink指向双链表的首结点(第一个有效结点)。链表的首结点的左链指针lLink和尾结点的右链指针rLink都指向附加头结点。二、实现程序1.DblList.h#ifndef DblList_h#define DblList_h#include using namespace std;template struct 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){} // 构造函数};template class 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个结点d0按前驱方向否则按后继方向bool Insert(int i, const T x, int d); // 在第i个结点后插入xd0按前驱方向否则按后继方向bool Remove(int i, T x, int d); // 删除第i个结点x带回删除其值d0按前驱方向否则按后继方向void Output(); // 输出双链表中的数据private:DblNode *first; // 附加头结点};template DblList::DblList() {// 构造函数建立附加头结点first new DblNode();if(NULL first) {cerr 动态分配内存空间失败 endl;exit(1);}first-rLink first-lLink first; // 指向自身}template DblList::~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;}template void 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往后移}}template int DblList::Length()const {// 计算双链表的长度DblNode *current first-rLink;int count 0;while(current ! first) {current current-rLink;count;}return count;}template bool DblList::isEmpty() {// 判双链表空否return first-rLink first;}template DblNode *DblList::getHead()const {// 取附加头结点return first;}template void DblList::setHead(DblNode *ptr) {// 设置附加头结点地址first ptr;}template DblNode *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;}template DblNode *DblList::Locate(int i, int d) {// 定位if((first-rLink first) || (i 0))return first;DblNode *current;if(d 0)current first-lLink; // 搜索前驱方向elsecurrent first-rLink;for(int j 1; j i; j){if(current first)break;else if(d 0)current current-lLink;elsecurrent current-rLink;}if(current ! first) // 定位成功return current;elsereturn NULL;}template bool 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;}template bool 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; // 删除成功}template void 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.husing namespace std;int main(int argc, const char * argv[]) {int finished 0, choice, i, x, d, len; // i存储第i个d:存储方向 -》0表示前驱方向否则为后继方向DblList L;DblNode *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个结点d0按前驱方向否则按后继方向\n;cout 8:在第i个结点后插入xd0按前驱方向否则按后继方向\n;cout 9:删除第i个结点x带回删除其值d0按前驱方向否则按后继方向\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;elsecout 双链表不空 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;elsecout 查找失败 endl;break;case 7:cout 请输入要定位第i个结点的i和方向d(d0按前驱方向否则按后继方向):;cin i d;current L.Locate(i, d);if(current NULL)cout 定位失败! endl;elsecout 定位成功 endl;break;case 8:cout 在第i个结点后插入xd0按前驱方向否则按后继方向。请输入i, x和d:;cin i x d;if(L.Insert(i, x, d))cout 插入成功! endl;elsecout 插入失败 endl;break;case 9:cout 删除第i个结点x带回删除其值d0按前驱方向否则按后继方向。请输入i和d:;cin i d;if(L.Remove(i, x, d))cout 删除成功删除的值为 x endl;elsecout 删除失败 endl;break;case 10:cout 双链表中的数据为 endl;L.Output();break;case 11:finished 1;break;default:cout 输入错误, 请重新输入 endl;} // switch} // whilereturn 0;}以上就是本文的全部内容希望对大家的学习有所帮助也希望大家多多支持脚本之家。
