双向循环链表C++实现(完整版)
#include<iostream> using namespace std; /* *节点类 */ struct DCNode { int data; DCNode * prior; DCNode * next; }; /* *链表类 */ struct DCList { DCList() { size = 0; } size_t size;//记录节点数的个数 DCNode * head;//指向链表的头结点 }; /* *分配一个节点,并给该节点的数据域赋值,默认值为0; */ DCNode * MakeNode(int t=0) { DCNode * p = (DCNode *)malloc(sizeof(DCNode)); p->data = t; return p; } //初始化一个空的双向循环链表 void InitDCList(DCList &list) { //分配一个头结点 DCNode * p = MakeNode(); list.head = p; list.size = 0; p->next = p; p->prior = p; } //释放所指向的节点 void FreeNode(DCNode * p) { delete p; } //清空一个线性表 void clear(DCList &list) { DCNode * p = list.head; p = p->next; while(p!= list.head) { DCNode * p1 = p->next; delete p; p = p1; } list.size = 0; } //将s所指向的节点插入到链表的第一个节点之前 bool InsFirst(DCList &list,DCNode * s) { s->next = list.head->next; list.head->next->prior = s; list.head->next = s; s->prior = list.head; list.size++; return true; } //删除链表中的第一个节点并以q指针返回 bool DelFirst(DCList &list,DCNode * & q) { if(list.head->next==list.head)//如果链表为空 { q = 0; return false; } q = list.head->next; list.head->next->next->prior = list.head; list.head->next = list.head->next->next; list.size--; return true; } //将s所指向的节点串接在链表的最后一个节点之后 bool Append(DCList &list,DCNode * s) { s->prior = list.head->prior; s->next = list.head; list.head->prior->next = s; list.head->prior = s; list.size++; return true; } //删除链表中的尾节点,并以指针q返回 bool Remove(DCList &list,DCNode * & q) { if(list.head->next==list.head)//如果链表为空 { q = 0; return false; } q = list.head->prior; list.head->prior->prior->next = list.head; list.head->prior = list.head->prior->prior; list.size--; return true; } //将s所指向的节点插入链表中p所指向的节点之前 bool InsBefore(DCList &list,DCNode * p,DCNode * s) { DCNode * p1 = list.head->next; while(p1!=list.head) { if(p1==p)//找到该链表中是否存在p所指向的节点 { s->next = p; s->prior = p->prior; p->prior->next = s; p->prior = s; list.size++; return true; } p1 = p1->next; } //没找到 return false; } //将s所指向的节点插入链表中p所指向的节点之后 bool InsAfter(DCList &list,DCNode * p,DCNode * s) { DCNode * p1 = list.head->next; while(p1!=list.head) { if(p1==p)//找到该链表中是否存在p所指向的节点 { s->next = p->next; s->prior = p; p->next->prior = s; p->next = s; list.size++; return true; } p1 = p1->next; } //没找到 return false; } //判断链表是否为空 bool Empty(DCList &list) { if(list.size==0) return true; else return false; } //返回链表的长度 int GetLength(DCList &list) { return list.size; } //返回链表中第i个节点的指针 DCNode * LocatePos(DCList &list,int i) { if(i<=0&&i>(int)list.size ) return 0;//如果不存在第i个节点则返回一个0指针 int n = 0; DCNode * p1 = list.head->next; while(p1!=list.head) { n++; if(n==i)//找到 { return p1; } p1 = p1->next; } return 0; } //在链表中查找第一个元素值与t相等的节点指针 DCNode * LocateElem(DCList &list,int t) { if(list.head->next==list.head)//如果链表为空 { return 0; } DCNode * p1 = list.head->next; while(p1!=list.head) { if(p1->data==t)//找到 { return p1; } p1 = p1->next; } return 0; } //在链表中查找第一个元素值与t满足compare函数关系的节点指针 DCNode * LocateElem(DCList &list,int t,bool (* compare)(int ,int)) { if(list.head->next==list.head)//如果链表为空 { return 0; } DCNode * p1 = list.head->next; while(p1!=list.head) { if((*compare)(p1->data,t))//找到了 { return p1; } p1 = p1->next; } return 0; } //依次对链表中的每一个元素调用visit函数,一旦visit函数调用失败,则整个操作失败 bool ListTraverse(DCList &list,bool (*visit)(int &)) { DCNode * p1 = list.head->next; while(p1!=list.head) { if(!(*visit)(p1->data))//找到了 { return false; } p1 = p1->next; } return true; } //合并两个双向循环链表 DCList & MergeList(DCList &list1,DCList &list2) { if(Empty(list1)) { return list2; } if(Empty(list2)) { return list1; } list1.head->prior->next = list2.head->next; list2.head->next->prior = list1.head->prior; list1.head->prior = list2.head->prior; list2.head->prior->next = list1.head; return list1; } //判断是否一个数为偶数 bool judge(int a,int b) { if(a%b==0) return true; return false; } bool visit(int & t) { t = t+1; return true; } int main() { //创建并初始化一个空的双向循环链表 DCList myList; InitDCList(myList); //在链表的尾端添加元素 //现分配一个节点 DCNode * s = MakeNode(1); Append(myList,s); s = MakeNode(3); Append(myList,s); s = MakeNode(5); Append(myList,s); s = MakeNode(7); Append(myList,s); //遍历该链表,并输出该链表的元素个数 DCNode * p1 = myList.head->next; cout<<"新建一个双向链表,并初始化元素值为1,3,5,7"<<endl; while(p1!=myList.head) { cout<<p1->data<<" "; p1 = p1->next; } cout<<endl; cout<<"链表的元素个数为:"<<GetLength(myList)<<endl; //在链表的第一个数据节点之前插入两个元素 s = MakeNode(9); InsFirst(myList,s); s = MakeNode(0); InsFirst(myList,s); cout<<"在链表的第一个数据节点之前插入两个元素值为0,9的节点:"<<endl; p1 = myList.head->next; while(p1!=myList.head) { cout<<p1->data<<" "; p1 = p1->next; } cout<<endl; //删除链表中的第一个节点和尾节点 cout<<"删除的第一个节点"<<endl; if(DelFirst(myList,s)) { cout<<"被删除的第一个节点数据为:"<<s->data<<endl; } p1 = myList.head->next; while(p1!=myList.head) { cout<<p1->data<<" "; p1 = p1->next; } cout<<endl; //释放被删除的节点空间 FreeNode(s); cout<<"删除的尾节点"<<endl; if( Remove(myList,s) ) { cout<<"被删除的尾节点数据为:"<<s->data<<endl; } p1 = myList.head->next; while(p1!=myList.head) { cout<<p1->data<<" "; p1 = p1->next; } cout<<endl; //释放被删除的节点空间 FreeNode(s); //在第二个节点之前插入元素 p1 = LocatePos(myList,2); cout<<"第二个节点数据为:"<<p1->data<<endl; s = MakeNode(11); InsBefore(myList,p1,s); cout<<"在第二个节点之前插入一个元素值为11的新节点:"<<endl; p1 = myList.head->next; while(p1!=myList.head) { cout<<p1->data<<" "; p1 = p1->next; } cout<<endl; //在第二个节点之后插入元素 s = MakeNode(16); p1 = LocatePos(myList,2); InsAfter(myList,p1,s); cout<<"再在第二个节点之后插入一个元素值为16的新节点:"<<endl; p1 = myList.head->next; while(p1!=myList.head) { cout<<p1->data<<" "; p1 = p1->next; } cout<<endl; //查找第一个元素值为4的倍数的节点 p1 = LocateElem(myList,4,judge); cout<<"找到第一个元素值为4的倍数的节点数据为:"<<p1->data<<endl; //将链表中所有的元素值都增加1 ListTraverse(myList,visit); cout<<"将链表中所有的元素值都增加1:"<<endl; p1 = myList.head->next; while(p1!=myList.head) { cout<<p1->data<<" "; p1 = p1->next; } cout<<endl; //新建一个元素值为1,3,9的链表 DCList myList2; InitDCList(myList2); //在链表的尾端添加元素 //现分配一个节点 s = MakeNode(1); Append(myList2,s); s = MakeNode(3); Append(myList2,s); s = MakeNode(9); Append(myList2,s); //遍历该链表,并输出该链表的元素个数 cout<<"新建一个元素值为1,3,9的链表:"<<endl; p1 = myList2.head->next; while(p1!=myList2.head) { cout<<p1->data<<" "; p1 = p1->next; } cout<<endl; //合并两个链表 myList = MergeList(myList,myList2); cout<<"合并两个链表:"<<endl; p1 = myList.head->next; while(p1!=myList.head) { cout<<p1->data<<" "; p1 = p1->next; } cout<<endl; cout<<"最后清空myList链表!"<<endl; clear(myList); }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。