数据结构上机实验报告
题目：用单循环链表解决约瑟夫问题
学生姓名
学生学号
学院名称 计算机学院
专 业计算机科学与技术
时 间 20##.10.7
目 录
第一章、需求分析 ………………………………………… 1
1.1 原题表述 …………………………………………… 1
1.2 所选的要求及整体规划 …………………………… 1
第二章、概要设计 ………………………………………… 2
2.1 抽象数据类型 ………………………………………… 2
2.2 算法 …………………………………………………… 2
第三章、详细设计 ………………………………………… 3
3.1 程序代码 ……………………………………………… 3
第四章、调试分析 ………………………………………… 7
4.1 调试工作 ……………………………………………… 7
4.2 时间复杂度 ………………………………………… 7
第五章、测试结果 ………………………………………… 8
5.1 输入数据和输出数据样例 ………………………… 8
第一章 需求分析
1.1 原题表述
设n个人围坐在一圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局者的下一人重新开始报数，数到第m个人，再让他出局······如此反复，直到所有的人全部出局为止。
1.2 所选的要求及整体规划
对于任意给定的n、s和m，求出这个n个人的出局序列，数据结构采用单循环链表。构造不带头结点的单循环链表。
第二章 概要设计
2.1 抽象数据类型
不带头结点的单循环链表
2.2 算法
建立一个不带头结点的空循环链表，依次在链表中添加数据域为1~n的n个数据元素，此时指针head指向第一个元素，再用一个for循环让头指针head指向第s个元素，之后用while循环让head指向第m-1个元素，删除第m个元素，head指向第m+1个元素，直至链表中只剩一个元素。依次输出被删除的元素及最后剩余的元素。
第三章 详细设计
3.1 程序代码
#include
#include
typedef struct node
{
int data;
struct node *next;
}node;
//函数功能：构造不带头结点的循环链表并赋值1~n，头指针head指向第s个人
node* create(int n,int s)
{
node *head;
node *p, *q, *r;
int i,j;
if(n＜=0) return NULL; //若分配内存失败返回
//把长度为n的链表赋值1~n
head=(node*)malloc(sizeof(node));
head-＞data=1;
head-＞next=NULL;
p=head;
for(i=1; i
{
q=(node*)malloc(sizeof(node));
q-＞data=i+1;
p-＞next=q;
p=q;
}
//构造循环链表
q=(node*)malloc(sizeof(node));
q-＞data=n;
p-＞next=q;
q-＞next=head;//不带头结点
for(j = 1; j ＜ s; j++)//从第s个人开始数
{
r = head -＞ next;
head = r;
}
return head;
}
int del(node *head)//删除
{
node *p, *q;
if(head==NULL) return -1;
p=head;
q=p-＞next;
p-＞next=q-＞next;
p=q-＞next;
free(q);
head=p;
return 1;
}
int main()
{
int n,m,s,person;
node *head,*r,*p;
//输入n、m、s
printf("Enter n: \n");
scanf("%d",&n);
printf("Enter m: \n");
scanf("%d",&m);
printf("Enter s: \n");
scanf("%d",&s);
head = create(n,s);//head指向第s个人
while(head -＞ next != head)//循环结束后链表只剩一个元素
{
//数到第m个删除，head指向m的前一个
for(int i = 1; i ＜ m-1; i++)
{
r = head -＞ next;
head = r;
}
person = head -＞ next -＞data;
printf("Number %d is out\n",person);
p = head -＞ next -＞ next;
del(head);
head = p;
}
person = head -＞ data;
printf("Number %d is out\n",person);
system("pause");
return 0;
}
第四章 测试分析
4.1 调试工作
检测每个循环输出的被删除的元素是否正确，输出结果是否完整
4.2 时间复杂度
O（n^2）
第五章 输出结果
5.1 输入数据和输出数据样例
分别输入参数n、m、s，输出结果如图所示。