数据结构约瑟夫生者死者游戏课程设计汇总.doc

数据结构约瑟夫生者死者游戏课程设计汇总
1

数据机构课程设计
选题名结点的数值;
2
3、系统的设计
josphu链表的实现
Josphu链表——链式表示和实现约瑟夫（Josephu）问题：已知N个人围坐在一张圆桌周围（不妨以1,2，„„，N对每一个人依次编号），现在先从序号为K的人开始报数，数到m的那个人出列,他的下一个人又从1开始数，报数到m的人出列„„直到所有人都出出列为止。给出出列的顺序。

表示和实现和顺序栈相似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了C语言中描述方便起 在此我们约定，初始化建空队列时front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置从上述分析可见，在C++中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。
3

#include<>
#include<>
typedef struct node{
int data;
struct node*next;
}ListNode,*LinkList;
void main()
{
LinkList R=NULL;
int n,k;
LinkList InitRing(int n ,LinkList R);
LinkList DeleteDeath(int n,int k,LinkList R);
void OutRing(int n ,LinkList R);
printf("输入总人数n和报数上限 k：");
scanf("%d%d",&n,&k);
R=InitRing(n,R);
R=DeleteDeath(n,k,R);
OutRing(n,R);
}
LinkList InitRing(int n ,LinkList R)
4
{
ListNode *p,*q;
int i ;
R=q=(ListNode *)malloc(sizeof(ListNode));
for(i=1;i<n;i++){
p=(ListNode *)malloc(sizeof(ListNode));
q->data=i;
q->next=p;
q=p;
}
p->data=n;
p->next=R;
R=p;
return R;
}
LinkList DeleteDeath(int n ,int k ,LinkList R)
{
int i ,j ;
ListNode *p,*q;
p=R;
printf("抛入大海者的编号如下：\n");
for(i=1;i<=n/2;i++)
5
{
for(j=1;j<=k-1;j++)
p=p->next;
q=p->next;
p->next=q->next;
printf("%4d",q->data);
if(i%10==0)printf("\n");
free(q);
}
printf("\n");
R=p;return R;
}
void OutRing(int n ,LinkList R)
{
int i ;
ListNode *p;
p=R;
printf("幸存者编号如下:\n");
for(i=1;i<=(n+1)/2;i++,p=p->next)
{
printf("%4d",p->data);
6
if(i % 10==0)printf("\n");
}
printf("\n");
}
开始

输入n,m值
创建列表
计数
删除结点
连接链表
结束
I<=n/2