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

1、.数据结构与程序设计实验实 验 报 告课程名称数据结构与程序设计实验课程编号实验项目名称约瑟夫环学号年级2014姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学实验报告一实验课名称：数据结构与程序设计实验实验名称：约瑟夫环班级 学号 姓名 时间 2016.04.05一、 问题描述设有编号为 1,2,n 的 n（n0）个人围成一个圈，每个人持有一个密码 m。从第一个人开始报数，报到 m 时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报到 m 时停止报数，报 m 的出圈，如此下去，直到所有人全部出圈为止。当任意给定 n 和 m 后，设计

2、算法求 n 个人出圈的次序。二、 数据结构设计每个人按报数顺序有唯一的前驱与后继关系，并且报数顺序循环，所以采用单向循环链表模拟，链表节点存储序号number和m，存储结构定义如下：typedef struct List int number; /序号 int m; /密码m struct List *next; /指向下一个人的指针List;为了方便查询及删除的定位，表按序号有序存储。三、 算法设计1.初始化，构建循环链表，依次存储序号1至n的人,链表指针 L指向序号为1的人。List *create_list_with_one_m(List *L, int n) List *pre; /

3、previous node int i=1; for(; i 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;2.为了获取被删除节点的前一个节点, m=1时重新赋值m为1+循环链表的长度，所以需要一个函数获取循环链表的长度。/ 返回循环链表L的长度int length_list(List *L) int i = 1; List *p =

4、 L-next; while(p != L) i+; p = p-next; return i;3.模拟报数过程， 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 = *L; / prior node int j = 0; while(j next; j+; del = pri-next;

5、/delete node pri-next = del-next; *L = pri-next; return del;4.输入构建好的链表L，人数n，密码m，每次调用delete_node函数删除一人，进行n次。void joseph_with_one_m(List *L, int n, int m) int i = 1; while(i number); free(del); i+; 5.如果密码m不同，则删除节点后，以删除节点的密码m作为新的m。void joseph_with_diff_m(List *L, int n) int i = 1; int m = L-m; while(i

6、number); m = del-m; free(del); i+; 6.在主函数中获取人数和密码m，构建链表，调用joseph函数。int main() int n, m; printf(请输入人数n: ); scanf(%d, &n); printf(请输入所有人的m: ); scanf(%d, &m); List *L; L = create_list_with_one_m(L, n); joseph_with_one_m(L, n, m); return 0;四、界面设计程序需要获取人数n，密码m（相同的密码m和不同的密码m），输出出圈顺序。所以以提示的形式获取n和m。五、运行测试与分

7、析（1）运行程序，显示输入提示，如图所示。（2）根据提示，输入人数，并输入密码，即可输出结果。（3）需要不同密码的程序可根据提示输入不同密码，即可输出结果。六、实验收获与思考1. 掌握了循环链表的初始化，删除，求长等常用方法的使用，巩固了相关数据结构。2. 在实验中熟悉了C语言对数据结构的描述，发现了过去的薄弱之处，重新进行学习。3. 体会到了正确的数据结构对程序的重要性。七、附录1.相同密码#include #include typedef struct List int number; int m; struct List *next;List;/* * 构建循环链表，依次存储1-n, L

8、指向1 * pre:previous node * cur:current node */ List *create_list_with_one_m(List *L, int n) List *pre; int i=1; for(; i 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;/ 返回循环链表L的长度int length_lis

9、t(List *L) int i = 1; List *p = L-next; while(p != L) i+; p = p-next; return i;/* * 删除L开始后第m个节点，用del返回 * L永远指向第一个报数的人 * pri: prior node * del: delete node*/ 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 = *L; in

10、t j = 0; while(j next; j+; del = pri-next; pri-next = del-next; *L = pri-next; return del;void joseph_with_one_m(List *L, int n, int m) int i = 1; while(i number); free(del); i+; int main() int n, m; printf(请输入人数n: ); scanf(%d, &n); printf(请输入所有人的m: ); scanf(%d, &m); List *L; L = create_list_with_on

11、e_m(L, n); joseph_with_one_m(L, n, m); return 0;2.不同密码#include #include typedef struct List int number; int m; struct List *next;List;/* * 构建循环链表，依次存储1-n, L指向1 * pre:previous node * cur:current node */ List *create_list_with_diff_m(List *L, int n) List *pre; int i=1; for(; i number = i; printf(请输入第%

12、d人的m: , i); scanf(%d, &(cur-m); 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;/ 返回循环链表L的长度int length_list(List *L) int i = 1; List *p = L-next; while(p != L) i+; p = p-next; return i;/* * 删除L开始后第m个节点，用de

13、l返回 * L永远指向第一个报数的人 * pri: prior node * del: delete node*/ 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 = *L; int j = 0; while(j next; j+; del = pri-next; pri-next = del-next; *L = pri-next; return del;void joseph_with_diff_m(List *L, int n) int