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

数据结构与程序设计实验 实 验 报 告 课程名称 数据结构与程序设计实验 课程编号 0906550 实验项目名称 约瑟夫环 学号 年级 2014 姓名 专业 计算机科学与技术 学生所在学院 计算机学院 指导教师 杨静 实验室名称地点 21B276 哈尔滨工程大学 实验报告一 实验课名称：数据结构与程序设计实验 实验名称：约瑟夫环 班级 学号 姓名 时间 2016.04.05 问题描述 设有编号为 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.初始化，构建循环链表，依次存储序号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; } 2.为了获取被删除节点的前一个节点, 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; } 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 m-2){ //移动m-2次,获取pri pri = pri-next; j++; } del = pri-next; //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 = n){ // 每次del一个node List *del; del = delete_node(L, m, del); printf(第%d个出圈的序号是%d\n, i, del-number);