约瑟夫环实验报告总结
【篇一：约瑟夫环实验报告】
实验 报 告
课程名称：数据结构
实验名称：顺序表和链表的应用 实验编号：实验一 指导教师： 一、实验目的
（1） 掌握线性表的基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结
构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。
（2） 掌握线性表的链式存储结构的应用。 二、实验内容与实验步骤 （1）实验内容：
实现约瑟夫环，约瑟夫环（joseph）问题的一种描述是：编号为1、2、3……n的n个人按照顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按照顺时针的方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。
（2）抽象数据类型和设计的函数描述，说明解决设想。
首先定义一个链表，用其中的data项存储每个人的编号，用
password项存储每个人所持有的密码，并且声明一个指针。之后使用creatlist_cl函数来创建一个循环链表，在其中的data和
password中存入编号和密码，最后使最后一个节点的next指向l，使其能够形成循环队列。定义了函数display来显示链表当中的内容，以确定存储的数据没有错误。定义了函数delete_l来实现约瑟夫环中依次删除的功能，依次比较，如果某个人所持的密码和m值相等，则删除这个结点，并且输出此时该结点的编号和密码，实现出列的功能。
（3） 简短明确地写出实验所采用的存储结构，并加以说明。
该实验我主要采用的是线性表的链式存储结构，首先定义了链表的结构，其中包括data项和password项，分别存储每个人的编号和所持密码，还声明了指向下一个结点的指针，该指针可以连接各个结点，并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。
三、实验环境
操作系统：windows 7 调试软件名称：vc++ 版本号：6.0
上机地点：综合楼311 四、实验过程与分析
（1）主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧班级： 学号： 姓名： 组号： 实验成绩： 批阅教师签字： 实验日期： 实验时间： 妙之处。
本实验中主要的函数包括创建链表、显示链表内容和出列过程四个部分。主要函数的代 码如下： 创建链表：
typedef int datatype;
typedef struct node//链表的定义 {
datatype data; int password;
struct node *next; }listnode,*clinklist;
void creatlist_cl(clinklist *l,int n)//创建一个链表 {
int i,pin;
clinklist p,q;
(*l)=(clinklist)malloc(sizeof(listnode)); if((*l)==null) printf(error\\n); else
(*l)-next=null; q=*l;
for(i=0;in;i++)
{
p=(clinklist)malloc(sizeof(listnode)); if(p==null)
printf(error\\n);
printf(请输入第%d个人的密码：,i+1); scanf(%d,pin); p-data=i+1;
p-password=pin; q-next=null; q-next=p; q=p; }
q-next=(*l)-next;//指向l结点，形成 }
创建这个链表的时间复杂度为o(n)，空间复杂度为o（n2）。 显示链表中的信息内容：
void display(clinklist *l,int n) {
int i;
clinklist p; p=(*l)-next;
printf(\\n显示链表内容\\n); for(i=0;in;i++) {
printf(编号：-密码：%d\\n,p-data,p-password); p=p-next; } }
该算法的时间复杂度为o（n）,空间复杂度为o(n2)。 删除结点，完成出列功能：
void delete_l(clinklist *l,int n,int m) {
int i=0,j;
clinklist p,q; q=(*l);
p=(*l)-next;
printf(\\n删除的顺序：\\n); while(in) {