循环链表ADT模板简单应用算法设计：约瑟夫环
作者: 冯向阳时间限制: 1S章节: DS:线性表
问题描述 :
目的：使用C++模板设计循环链表的抽象数据类型（ADT）。并在此基础上，使用循环链表ADT的基本操作，设计并实现单链表的简单算法设计。
内容：（1）请使用模板设计循环链表的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的单链表ADT原型文件，自行设计循环链表的ADT。）
（2）ADT的简单应用：使用该ADT设计并实现循环链表应用场合的一些简单算法设计。
应用2：编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。请在使用循环链表ADT的基础上，设计一个算法求出圈的顺序（以编号表示）。限定人数至少为1.
参考函数原型：
template
void Joseph(CirLinkList &A, int m);
//约瑟夫环专用结点类型
struct node{
int number;
int code;
};
输入说明 :
第一行：人数n
第二行：第一个人所持的密码
第三行：第二个人所持的密码
...
第n+1行：第n个人所持的密码
第n+2行：给定的随机数m
输出说明 :
第一行至第n行：建立的循环链表的遍历结果（一个结点占据1行）
第n+1行：空行
第n+2行：出圈的顺序（编号与编号之间以“->”分隔）
#include
#include
#include
using namespace std;
/* 循环单链表的结点定义 */
template
struct LinkNode
{
ElemType data;
int node;
LinkNode *next;
//构造函数1，用于构造头结点
LinkNode(LinkNode *ptr = NULL)
{
next = ptr;
}
//构造函数2，用于构造其他结点
//函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
LinkNode(const ElemType &item,const ElemType &itam, LinkNode *ptr = NULL)
{
next = ptr;
data = item;
node=itam;
}
//取得结点的数据域的值
ElemType getData(){ return data; }
//修改结点的next域
void SetLink( LinkNode *link ){ next = link; }
//修改结点的data域
void SetLink( ElemType value ){ data = value; }
};
//带头结点的循环单链表
template
class CirLinkList
{
private:
LinkNodehead; // 头结点
LinkNode *tail; // 尾结点
public:
//无参数的构造函数
CirLinkList(){head = new LinkNode; tail = head; head->next = head;}
//带参数的构造函数
CirLinkList(const ElemType &item){head = new LinkNode(item); tail = head; head->next = head;}
//拷贝构造函数
CirLinkList(CirLinkList &List);
//析构函数
//~CirLinkList(){ListDestroy();}
//销毁链表
void ListDestroy();
//清空链表
void ListClear();
//返回链表的长度
int ListLength()
{
if(head->next==head)
return 0;
else
{LinkNode *p;
int i=1;
p=head->next;
while(p->next!=head->next)
{
p=p->next;
i++;
}
return i;}
}
//判断链表是否为空表
bool ListEmpty()
{
if(head->next==head)
return true;
else return false;
}
//获取循环链表头结点
LinkNode GetHead() { return head;}
//获取循环链表尾结点
LinkNode* GetTail() { return tail;}
//设置链表头结点
void SetHead(LinkNodep){ head = p;}
//在链表的第pos个位置之后插入e元素
void ListInsert_next(int pos,ElemType e)
{
int j;
LinkNode *p,*s,*r;
s=(LinkNode)malloc(sizeof(ElemType));
p=head->next;
j=1;
while(j
{
p=p->next;
j++;
}
r=p;
s->data=e;
p->next=s;
s->next=r->next;
}
//表头插入法动态生成链表
void CreateList_Head(int n)
{
ElemType w;
LinkNode h;
LinkNode *o;
h=head;
for(int i=n;i>0;i--)
{
o=(LinkNode)malloc(sizeof(ElemType));
cin>>w;
o->data=w;
o->node=n-i+1;
h->next=o;
tail=o;
tail->next=head->next;
h=tail;
}
}
//表尾插入法动态生成链表
//void CreateList_Tail(int n, ElemType *A);
//遍历链表
void ListTraverse()
{
LinkNode *p=head->next;
while(p->next!=head->next)
{
cout<<p->node<<" "<<p->data<<endl;
p=p->next;
}
cout<<p->node<<" "<<p->data<<endl;
cout<<endl;
return ;
}
void Joseph(int m,int cd)
{
int j=1,i;
LinkNode *p,*s;
p=head->next;
s=p;
for(i=1;i
{
while(j!=m)
{
s=p;
p=p->next;
j++;}
s->next=p->next;
m=p->data;
cout<node<<"->";
p=s->next;
j=1;
}
cout<node;
cout<<endl;
}
};
int main()
{
CirLinkList d;
int cd;
cin>>cd;
d.CreateList_Head(cd);
int m;
cin>>m;
d.ListTraverse();
d.Joseph(m,cd);
return 0;
}
所设链表为带头指针的循环链表
即头指针指向第一个元素，尾指针也指向第一个元素
但在初始化时 头指针和尾指针相等。
