滴水逆向联盟

标题: VC++2012编程演练数据结构《15》双循环链表 [打印本页]

作者: 大灰狼 时间: 2014-9-2 07:57
标题: 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();
}

效果如下

欢迎光临滴水逆向联盟 (http://www.dtdebug.com/) Powered by Discuz! X3.2