VC++2012编程演练数据结构《15》双循环链表

大灰狼

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

打开IDE

我们来创建一个工程实践之

类的声名如下

[cpp] view plaincopy

• #if !defined(AFX_DCIRLINKL_H__4D93E797_B8BC_4781_BD9A_0EF8A6458A75__INCLUDED_)  
• #define AFX_DCIRLINKL_H__4D93E797_B8BC_4781_BD9A_0EF8A6458A75__INCLUDED_  
•   
• #if _MSC_VER > 1000  
• #pragma once  
• #endif // _MSC_VER > 1000  
•   
• //双向循环链表的类定义  
• typedef int ElemType;  
• //双向链表结点的类型定义  
• typedef struct DuLNode {  
•   ElemType  data;  
•   struct DuLNode *prior;//左指针  
•   struct DuLNode *next;//右指针  
• }DuLNode;  
• #define LEN 20  
•   
• class DuLinkList  
• {private:  
• DuLNode *head;//指向表头的指针  
• DuLNode *curr;//当前结点指针  
• int count;// 双向循环链表的结点个数  
• public:  
•     //构造函数  
•     DuLinkList();  
•     //析构函数  
•     ~DuLinkList(){delete head;}  
•     //创建有序或无序的带头结点的双向循环链表  
•     DuLNode *CreateCLinkL(int,int,int mark=0);  
•     //清空单循环链表  
•     void ClearCList();  
•     //求双向循环链表长度  
•     int CListSize();  
•     //检查双向循环链表是否为空  
•     bool CListEmpty();  
•     //返回指向第pos个结点的指针  
•     DuLNode *Index(int pos);  
•     //返回双向循环链表中指定序号的结点值  
•     ElemType GetElem(int pos);  
•     //遍历双向循环链表  
•     void TraverseCList();  
•     //当前指针curr指向pos结点并返回curr  
•     DuLNode *Reset(int pos=0);  
•     //当前指针curr指向下一结点并返回  
•     DuLNode *Next();  
•     //当前指针curr指向上一结点并返回  
•     DuLNode *Prior();  
•     // 判双向循环链表当前指针curr==head 否  
•     bool EndOCList();  
•     //判双向循环链表当前指针curr->next是否到达表尾  
•     bool EndCList();  
•     //判双向循环链表当前指针curr->prior是否到达表尾  
•     bool PEndCList();  
•     //删除curr->next所指结点,并返回所删结点的data  
•     ElemType DeleteNt();  
•     //从双向循环链表中查找元素  
•     bool FindCList(ElemType& item);  
•     //更新双向循环链表中的给定元素  
•     bool UpdateCList(const ElemType &item,ElemType &e);  
•     //向链表中第pos个结点前插入域值为item的新结点  
•     void InsertCLfront(const ElemType& item,int pos);  
•     //向链表中第pos个结点后插入域值为item的新结点  
•     void InsertCLafter(const ElemType& item,int pos);  
•     //从链表中删除第pos个结点并返回被删结点的data  
•     ElemType DeleteCList(int pos);  
• };  
•   
• #endif // !defined(AFX_DCIRLINKL_H__4D93E797_B8BC_4781_BD9A_0EF8A6458A75__INCLUDED_)  
  

类的实现如下

[cpp] view plaincopy

• #include "stdafx.h"  
• #include "dcirlinkl.h"  
•   
• //双向循环链表的实现  
• #include<iostream>  
• #include<stdlib.h>  
•   
• //构造函数  
• DuLinkList::DuLinkList()  
• {head=new DuLNode;  
• head->prior=head;  
• head->next=head;  
• curr=NULL;  
• count=0;  
• }  
• //创建有序或无序的带头结点的双向循环链表  
• DuLNode *DuLinkList::CreateCLinkL(int n,int m,int mark)  
• {ElemType x,a[LEN];  
• srand(m);  
• for(int i=0;i<n;i++) a=rand()%100;  
• for(int i=0;i<n-1;i++)  
•   {int k=i;  
•    for(int j=i+1;j<n;j++)  
•     if(a[k]>a[j]) k=j;  
•    if(k!=i)  
•    {x=a[k];a[k]=a;a=x;}}  
• DuLNode *p;  
• head=new DuLNode;  
• head->prior=NULL;  
• head->next=curr=p=new DuLNode;  
• curr->prior=head;  
• for(int i=0;i<n;i++){  
•   if(mark==1) p->data=a;//升序  
•   else  
•    if(mark==-1) p->data=a[n-1-i];//降序  
•    else p->data=rand()%100;//无序  
•   if(i<n-1){curr=curr->next=new DuLNode;  
•    curr->prior=p;p=curr;}  
•   count++;}  
• head->prior=curr;  
• curr->next=head;  
• return head;  
• }  
• //清空双向循环链表  
• void DuLinkList::ClearCList()  
• {DuLNode *cp,*np;  
• cp=head->next;  
• while(cp!=head)  
• {np=cp->next;delete cp;cp=np;}  
• head=NULL;  
• }  
• //求双向循环链表长度  
• int DuLinkList::CListSize()  
• {DuLNode* p=head->next;  
• int i=0;  
• while(p!=head)  
•   {i++;p=p->next;}  
• return i;  
• }  
• //检查双向循环链表是否为空  
• bool DuLinkList::CListEmpty()  
• {return head->next==head;}  
• //返回指向第pos个结点的指针  
• DuLNode *DuLinkList::Index(int pos)  
• {if(pos<1)  
•   {cerr<<"pos is out range!"<<endl;exit(1);}  
• DuLNode* p=head->next;  
• int i=0;  
• while(p!=head)  
•   {i++;  
•    if(i==pos) break;  
•    p=p->next;}  
• if(p!=head) return p;  
• else {cerr<<"pos is out range!"<<endl;  
•   return NULL;}  
• }  
• //返回双向循环链表中指定序号的结点值  
• ElemType DuLinkList::GetElem(int pos)  
• {if(pos<1)  
• {cerr<<"pos is out range!"<<endl;exit(1);}  
• DuLNode* p=head->next;  
• int i=0;  
• while(p!=head)  
•   {i++;  
•    if(i==pos) break;  
•    p=p->next;}  
• if(p!=head) return p->data;  
• else {cerr<<"pos is out range!"<<endl;  
•   return pos;}  
• }  
• //遍历双向循环链表  
• void DuLinkList::TraverseCList()  
• {DuLNode *p=head->next;  
• while(p!=head)  
•   {cout<<setw(4)<<p->data;  
•    p=p->next;}  
• cout<<endl;  
• }  
• //当前指针curr指向pos结点并返回curr  
• DuLNode *DuLinkList::Reset(int pos)  
• {DuLNode* p=curr=head->next;  
• int i=-1;  
• while(p!=head)  
•   {i++;  
•    if(i==pos) break;  
•    p=p->next;curr=curr->next;}  
• return curr;  
• }  
• //当前指针curr指向下一结点并返回  
• DuLNode *DuLinkList::Next()  
• {curr=curr->next;  
• return curr;   
• }  
• //当前指针curr指向上一结点并返回  
• DuLNode *DuLinkList::Prior()  
• {curr=curr->prior;  
• return curr;  
• }  
• // 判双向循环链表当前指针curr==head 否  
• bool DuLinkList::EndOCList()  
• {return curr==head;}  
• //判双向循环链表当前指针curr->next是否到达表尾  
• bool DuLinkList::EndCList()  
• {return curr->next==head;}  
• //判双向循环链表当前指针curr->prior是否到达表尾  
• bool DuLinkList::PEndCList()  
• {return curr->prior==head;}  
• //删除curr->next所指结点,并返回所删结点的data  
• ElemType DuLinkList::DeleteNt()  
• {DuLNode *p=curr->next;  
• curr->next=p->next;  
• curr->next->next->prior=p->prior;  
• ElemType data=p->data;  
• delete p;  
• count--;  
• return data;  
• }  
• //从双向循环链表中查找元素  
• bool DuLinkList::FindCList(ElemType& item)  
• {DuLNode* p=head->next;  
• while(p!=head)  
•   if(p->data==item)  
•    {item=p->data;return true;}  
•   else p=p->next;  
• return false;  
• }  
• //更新双向循环链表中的给定元素  
• bool DuLinkList::UpdateCList(const ElemType &item,ElemType &e)  
• {DuLNode* p=head->next;  
• while(p!=head)  //查找元素  
•   if(p->data==item) break;  
•   else p=p->next;  
• if(p==head) return false;  
• else {  //更新元素  
•   p->data=e;return true;}  
• }  
• //向链表中第pos个结点前插入域值为item的新结点  
• void DuLinkList::InsertCLfront(const ElemType& item,int pos)  
• {DuLNode *newP=new DuLNode;  
• newP->data=item;  
• DuLNode* p=head->next;  
• int i=0;  
• while(p!=head)  
•   {i++;  
•    if(i==pos) break;  
•    p=p->next;}  
• newP->prior=p->prior;  
• p->prior->next=newP;  
• newP->next=p;  
• p->prior=newP;  
• count++;  
• }  
• //向链表中第pos个结点后插入域值为item的新结点  
• void DuLinkList::InsertCLafter(const ElemType& item,int pos)  
• {DuLNode *newP=new DuLNode;  
• newP->data=item;  
• DuLNode* p=head->next;  
• int i=-1;  
• while(p!=head)  
•   {i++;  
•    if(i==pos) break;  
•    p=p->next;}  
• newP->prior=p->prior;  
• p->prior->next=newP;  
• newP->next=p;  
• p->prior=newP;  
• count++;  
• }  
• //从链表中删除第pos个结点并返回被删结点的data  
• ElemType DuLinkList::DeleteCList(int pos)  
• {if(pos<1)  
•   {cerr<<"pos is out range!"<<endl;exit(1);}  
• DuLNode *p=head->next;  
• ElemType data;  
• int i=0;  
• while(p!=head)  
•   {i++;  
•    if(i==pos) break;  
•    p=p->next;}  
• if(p!=head)  
•   {data=p->data;  
•    p->prior->next=p->next;  
•    p->next->prior=p->prior;  
•    delete []p;count--;return data;}  
• else return pos;   
• }  
  

调用如下

[cpp] view plaincopy

• #include "stdafx.h"  
•   
• #include "dcirlinkl.h"  
• void main()  
• {  
• cout<<"运行结果:\n";  
• int m=150,i,n=10,x,it;  
• DuLinkList p,t,q,mylink;  
• p.CreateCLinkL(n,m,1);  
• if(p.CListEmpty()) cout<<"双向循环链表p空!\n";  
• else cout<<"双向循环链表p非空!\n";  
• cout<<"双向循环链表p(升序):\n";  
• p.TraverseCList();  
• if(p.CListEmpty()) cout<<"双向循环链表p空!\n";  
• else cout<<"双向循环链表p非空!\n";  
• if(p.EndCList()) cout<<"双向循环链表p满!\n";  
• else cout<<"双向循环链表p非满!\n";  
• cout<<"双向循环链表t(无序):\n";  
• t.CreateCLinkL(n-2,m);  
• t.TraverseCList();  
• cout<<"双向循环链表t的长度:"<<t.CListSize()<<endl;  
• cout<<"双向循环链表q(降序):\n";  
• q.CreateCLinkL(n,m,-1);  
• q.TraverseCList();  
• cout<<"双向循环链表q的长度:"<<q.CListSize()<<endl;  
• cout<<"链表q的第1个元素:"<<q.GetElem(1)<<endl;  
• cout<<"链表q的第1个元素地址:"<<q.Index(1)<<endl;  
• cout<<"链表q的第5个元素:"<<q.GetElem(5)<<endl;  
• cout<<"链表q的第5个元素地址:"<<q.Index(5)<<endl;  
• cout<<"链表q的第10个元素:"<<q.GetElem(10)<<endl;  
• cout<<"链表q的第10个元素地址:"<<q.Index(10)<<endl;  
• cout<<"链表q的curr->next所指元素地址:"<<q.Next()<<endl;  
• x=65;it=66;  
• if(q.FindCList(x)) cout<<x<<"查找成功!\n";  
• else cout<<x<<"查找不成功!\n";  
• if(q.UpdateCList(x,it)) cout<<x<<"更新成功!\n";  
• else cout<<x<<"更新不成功!\n";  
• cout<<"更新后双向循环链表q:\n";  
• q.TraverseCList();  
• cout<<"插入后双向循环链表q:\n";  
• it=100;q.InsertCLfront(it,1);  
• q.TraverseCList();  
• cout<<"插入后双向循环链表q:\n";  
• it=101;q.InsertCLfront(it,5);  
• q.TraverseCList();  
• cout<<"插入后双向循环链表q:\n";  
• it=102;q.InsertCLfront(it,13);  
• q.TraverseCList();  
• cout<<"插入后q表长:"<<q.CListSize()<<endl;  
• cout<<"第1个数:"<<q.DeleteCList(1)<<"删除成功!\n";  
• cout<<"删除后q表长:"<<q.CListSize()<<endl;  
• q.TraverseCList();  
• cout<<"第5个数:"<<q.DeleteCList(5)<<"删除成功!\n";  
• cout<<"删除后q表长:"<<q.CListSize()<<endl;  
• q.TraverseCList();  
• cout<<"第11个数:"<<q.DeleteCList(11)<<"删除成功!\n";  
• cout<<"删除后q表长:"<<q.CListSize()<<endl;  
• q.TraverseCList();  
• cout<<"删除的数为:"<<q.DeleteNt()<<endl;  
• cout<<"删除后q表长:"<<q.CListSize()<<endl;  
• q.TraverseCList();  
• cout<<"求解约瑟夫(Josephus)问题\n";  
• cout<<"输入人数n:";cin>>n;  
• cout<<"输入第次数m:";cin>>m;  
• for(i=0;i<n;i++) mylink.InsertCLafter(i+1,i);  
• cout<<"员工编号依次为:";  
• DuLNode *w=mylink.Reset();  
• while(!mylink.EndOCList())  
• {cout<<setw(3)<<w->data;  
• w=mylink.Next();}  
• cout<<endl;  
• cout<<"删除次序依次为:\n";  
• mylink.Reset(-1);  
• for(i=0;i<n-1;i++)  
• {for(int j=0;j<m-1;j++)  
• {w=mylink.Next();  
• if(mylink.EndOCList()) w=mylink.Next();}  
• if(mylink.EndCList()) w=mylink.Next();  
• cout<<"删除第"<<mylink.DeleteNt()<<"人\n";}  
• cout<<"最后剩下的是:第"<<mylink.GetElem(1)<<"个人\n";  
• cin.get();cin.get();  
• }  
  

效果如下