数据结构与算法实验报告
约瑟夫生死游戏
姓名：孙瑞霜
一、实验目的
1、熟练掌握学习的每种结构及其相应算法；
2、理论联系实际，会对现实问题建模并设计相应算法。
3、优化算法，使得算法效率适当提高
二、实验要求：
1． 认真阅读和掌握教材上和本实验相关的内容和算法；
2． 上机将各种相关算法实现；
3． 实现上面实验目的要求的功能，并能进行简单的验证。
三、实验内容
认真学习 学习通->数据结构->资料->数据结构实验指导书--陈越版，从第二章进阶实验1~10中任选一个来实现，编写程序，输入给定的数据，能得到给定的输出。总结算法思想、画出流程图，并思考程序有无改进空间，如何改进。
三、算法描述
选择实验2“约瑟夫生死游戏”。
该实验采用循环链表将30个数据串联起来，首先创建循环链表，其次进入删除函数，删除函数中采用双重循环，外循环负责控制删除数据的个数，内循环负责找出每次要删除人的位置的前一个位置，然后定义一个指针指向删除位置，将删除位置的前一个位置和后一个位置连接，输出删除位置的数据和余下的数据，释放删除的节点。
函数还可以改进，比如从根节点开始，直接找到删除的位置。
四、详细设计
五、程序代码
#include<stdio.h>
#include<stdlib.h>
/* 定义链表节点类型 */
typedef struct node{
int data;
struct node * next;
}linklist;
linklist * Init(int n,linklist * Ptrl){
linklist *p,*q;
int i;
Ptrl=(linklist *)malloc(sizeof(linklist));
q=Ptrl;
for(i=1;i<n;i++)
{
p=(linklist *)malloc(sizeof(linklist));
q->data=i;
q->next=p;
q=p;
}
q->data=n;
p->next=Ptrl;
Ptrl=q;
return Ptrl; //此时Ptrl指向链表的最后一个位置
}
void OutList(int n,int i,linklist *Ptrl){ //将幸存的人的编号输出
linklist *s;
s=Ptrl->next;
for(int t=1;t<=n-i;t++,s=s->next)
printf("%d ",s->data);
}
linklist * Delete(int n,int k,linklist *Ptrl)
{
int i,j;
linklist *p,*q;
p=Ptrl;
for(i=1;i<=n/2;i++) //剔除一半的人
{
for(j=1;j<=k-1;j++) //循环找到要删除的前一个位置 用指针p表示
p=p->next;
q=p->next; //q此时指向要删除的位置
p->next=q->next; //将要删除的位置的前一个位置与要删除的位置的后一个位置连接
printf("\n\n第%d次被抛下海的序号为:",i);
printf("%d\n",q->data);
printf("船上还剩下幸存者的序号:\n");
if(q->data==Ptrl->data) //如果刚好删除最后一个位置
Ptrl=p;
OutList(n,i,Ptrl); //将幸存的人的编号输出
free(q);
}
return Ptrl;
}
int main(){
linklist * Ptrl;
int n,k;
printf("船上的总人数(n)是:");
scanf("%d",&n);
printf("从第k个人开始抛下海:");
scanf("%d",&k);
Ptrl=Init(n,Ptrl);
Ptrl=Delete(n,k,Ptrl);
}
六、测试和结果
七、用户手册
打开Dev c++,将五部分代码拷贝进去，点击运行，按照提示输入数据，最后得出结果，关闭程序。