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

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

2、m 后，设计算法求 n 个人出圈的次序。二、 数据结构设计每个人按报数顺序有唯一的前驱与后继关系， 并且报数顺序循环， 所以采用单向循环链 表模拟，链表节点存储序号 number 和 m，存储结构定义如下：typedef struct Listint number; 始化，构建循环链表，依次存储序号1 至 n 的人 , 链表指针 L 指向序号为 1 的人。List *create_list_with_one_m(List *L, int n)List *pre; 了获取被删除节点的前一个节点 , m=1时重新赋值 m为 1+循环链表的长度， 所以需要一个函数获取循环链表的长度。拟报数过程， L

3、 永远指向下一个第一个报数的人，删除L 开始后第 m个节点，用结点指针del 返回删除结点。List *delete_node(List *L, int m, List *del)if(m = 1) 入构建好的链表 L，人数 n ，密码 m，每次调用 delete_node 函数删除一 人，进行 n 次。void joseph_with_one_m(List *L, int n, int m)int i = 1;while(i <= n)果密码 m 不同，则删除节点后，以删除节点的密码m 作为新的 m。void joseph_with_diff_m(List *L, int n)int

4、i = 1;int m = L->m;while(i <= n)主函数中获取人数和密码 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;四、界面设计 程序需

5、要获取人数 n，密码 m（相同的密码 m和不同的密码 m），输出出圈顺序。所以以提示 的形式获取 n 和 m。五、运行测试与分析 （1）运行程序，显示输入提示，如图所示。2）根据提示，输入人数，并输入密码，即可输出结果。（3）需要不同密码的程序可根据提示输入不同密码，即可输出结果。六、实验收获与思考1. 掌握了循环链表的初始化，删除，求长等常用方法的使用，巩固了相关数据结构。2. 在实验中熟悉了 C 语言对数据结构的描述，发现了过去的薄弱之处，重新进行学习。3. 体会到了正确的数据结构对程序的重要性。七、附录1. 相同密码#include <>#include <>ty

6、pedef struct Listint number;int m;struct List *next;List;/* 构建循环链表，依次存储 1-n, L 指向 1* pre:previous node* cur:current node*/List *create_list_with_one_m(List *L, int n)List *pre;int i=1;for(; i <= n; i+)List *cur = (List*)malloc(sizeof(List); cur->number = i;cur->next = NULL;if(i = 1) 同密码#inc

7、lude <>#include <> typedef struct Listint 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 <= n; i+)List *cur = (List*)malloc(sizeof(List); cur->number = i;pri

8、ntf(" 请输入第 %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->

9、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)1+lengthif(m = 1) /为了获取被删除节点的前一个节点 , m=1 时重新赋值为int l = length_list(*L);m = 1+l;List *pri = *L;int j = 0;while(j < m-2) /移动 m-2

10、 次 , 获取 pripri = pri->next; j+;del = pri->next; pri->next = del->next;*L = pri->next; return del;void joseph_with_diff_m(List *L, int n)int i = 1;int m = L->m;while(i <= n) /每次 del 一个 nodeList *del = delete_node(&L, m, del); printf("第 %d个出圈的序号是 %dn", i, del->number);m = del->m;free(del); i+; int main()