数据结构实验报告-约瑟夫环.doc

数据结构与程序设计实验
实验报告
课程名称
数据结构与程序设计实验
课程编号
0906550
实验项目名称
约瑟夫环
学号
年级
2014
姓名
专业
计算机科学与技术
学生所在学院
计算机学院
指导教师
杨静
实验室名称地点
21B276
哈尔滨工程大学
实验报告一
实验课名称:数据结构与程序设计实验
实验名称:约瑟夫环
班级
学号
姓名
时间
问题描述
设有编号为 1,2,…,n 的 n(n>0)个人围成一个圈,每个人持有一个密码 m。从第一个人开始报数,报到 m 时停止报数,报 m 的人出圈,再从他的下一个人起重新报数,报到 m 时停止报数,报 m 的出圈,……,如此下去,直到所有人全部出圈为止。当任意给定 n 和 m 后,设计算法求 n 个人出圈的次序。
数据结构设计
每个人按报数顺序有唯一的前驱与后继关系,并且报数顺序循环,所以采用单向循环链表模拟,链表节点存储序号number和m,存储结构定义如下:
typedef struct List{
int number; //序号
int m; //密码m
struct List *next; //指向下一个人的指针
}List;
为了方便查询及删除的定位,表按序号有序存储。
算法设计
,构建循环链表,依次存储序号1至n的人,链表指针 L指向序号为1的人。
List *create_list_with_one_m(List *L, int n){
List *pre; // previous node
int i=1;
for(; i <= n; i++){
List *cur = (List*)malloc(sizeof(List)); // current node
cur->number = i;
cur->next = NULL;
if(i == 1){ //只在第一次进入, init L, pre
L = cur;
pre = cur;
}else{ //链接pre与cur,并向后移动pre
pre->next = cur;
pre = cur;
}
}
pre->next = L;
return L;
}
, m=1时重新赋值m为1+循环链表的长度,所以需要一个函数获取循环链表的长度。
// 返回循环链表L的长度
int length_list(List *L){
int i = 1;
List *p = L->next;
while(p != L){
i++;
p = p->next;
}
return i;
}
, L永远指向下一个第一个报数的人,删除L开始后第m个节点,用结点指针del返回删除结点。
List *delete_node(List **L, int m, List *del){
if(m == 1){ //为了获取被删除节点的前一个节点, m=1时重新赋值为1+length
int l = length_list(*L);
m = 1+l;
}
List *pri = *