约瑟夫环实验报告

约瑟夫环实验 数据结构实习 数据结构实习数据结构实习 数据结构实习报告 报告报告 报告 题目:编写一个程序求出约瑟夫环出列顺序 班级: 08052712 姓名: 周凌霄 学号: 08052241 一 一一 一、 、、 、 需求分析 需求分析需求分析 需求分析 1、 约瑟夫环描述:编号为1，2，3，…，n的n个人按顺时针方向 围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整 数作为报数的上限值m，从第一个人开始按顺时针方向自1开始 顺序报数，报到m时停止。报m的人出列，将他的密码作为新 的m值，从他在顺时针方向上的以一个人开始重新从1报数，如 此下去直到所有人出列。 2、 求解给定约瑟夫环的出列顺序。 3、 利用单项循环链表存储结构模拟。 4、 测试数据:m=20,n=7,密码依次为3、1、7、2、4、8、4 二 二二 二、 、、 、 概要 概要设计概要设计 概要设计 1、 单向循环链表的抽象数据结构为: ADT LinkList { 数据对象:D={ai | aii ? int ，i = 1,2,3,…,n, n>=0} 数据关系:R={| ai ,ai+1?D} 基本操作: InitList(LinkList &L) 操作结果:构造一个空的循环链表L。 DestroyList(LinkList &L) 初始条件:循环链表L存在 操作结果:删除链表L IsEmpty(LinkList &L) 初始条件:循环链表L存在 操作结果:若链表为空返回true，否则返回false Insert(LinkList &L,ElemType e) 初始条件:循环链表L存在 操作结果:将数据元素插入链表L Delete(LinkList &L,ElemType &e,int m) 初始条件:循环链表L存在，并且不为空 操作结果:将数据元素按照约瑟夫环出列的规则，出列一个数据元素。 } ADT LinkList 2、 集合的抽象数据类型为: 数据对象:D={ai|ai ? int ，i = 1,2,3,…,n, n>=0} 数据关系:R={| ai ,ai+1?D} 基本操作: DoJoesph(LinkList &L) 初始化条件:链表L已经建立，并且为空。 操作结果:按要求输入约瑟夫环顺序，输出出列顺序 3、 本程序包含模块: 主程序模块: void main(){ 初始化 调用DoJoesph(L) } 循环链表模块——实现循环链表的抽象数据类型 三 三三 三、 、、 、 详细设计 详细设计详细设计 详细设计 主程序代码: #include #include"LinkList.h" void DoJoesph(LinkList &L){ &L,ElemType &e,int m) int n,m,i,x=0;//n为人数 m是第一次移动次数 x表示第x个退出的人 ElemType e; printf("please input two numbers m & n: "); scanf("%d%d",&m,&n); printf("please input all the password from 1 to n: \n"); for(i = 0; i < n; i++) { scanf("%d",&e.password); e.num = i+1; Insert(L,e); } L.top = L.top->next;//把头指针指向 第一个节点 while(!IsEmpty(L)) { Delete(L,e,m); m = e.password; printf("第%d个退出约瑟夫环的人为:%d\n",++x,e.num); } printf("\n"); } void main() { LinkList L; InitList(L); DoJoesph(L); } 循环链表代码:#include typedef struct ElemType{ int num; int password; }ElemType; //定义人的属性 num为人的序号 password为密码 typedef struct LNode{ ElemType elem; LNode *next; }LNode; //链表节点 typedef struct LinkList{ 细设计 详细设计 主程序代码: #includeelem.num = e.num; L.top->elem.password = e.password; L.top->next = L.top; L.length++; }//若链表为空 把信息写到第一个节点 else { LNode *temp; temp = (LNode *)malloc(sizeof(LNode)); temp->elem.num = e.num; temp->elem.password = e.password; temp->next = L.top->next; L.top->next = temp; L.top = L.top->next; L.length++; }//若链表不为空 重新申请节点 链接到链表尾部 return true; }//链表插入 bool Delete(LinkList &L,ElemType &e,int m) f W@?{ if(IsEmpty(L)) return false; else { LNode *temp; temp = L.top; if(m==1) { while(1) { temp = temp->next; if(temp->next == L.top) break; } } else { while(m>2){ temp = temp->next; m--; } } L.top = temp->next; e.num = L.top->elem.num; e.password = L.top->elem.password; temp->next = L.top->next; temp = L.top; L.top = L.top->next; L.length--; delete temp; } return true; }//删除节点 按要求删除相应节点 四 四四 四、 、、 、 调试分析 调试分析调试分析 调试分析 1. 1.1. 1. 对于 对于对于 对于出列位置的判断不正确 出列位置的判断不正确出列位置的判断不正确 出列位置的判断不正确， ，， ，导致问题 导致问题导致问题 导致问题。 。。 。 2. 2.2. 2. 对于最后一个出列的人判断不对 对于最后一个出列的人判断不对对于最后一个出列的人判断不对 对于最后一个出列的人判断不对， ，， ，导致指针越界 导致指针越界导致指针越界 导致指针越界。 。。 。 3. 3.3. 3. 时间复杂度分析 时间复杂度分析时间复杂度分析 时间复杂度分析 因为插入每次为在最后一个插入 因为插入每次为在最后一个插入因为插入每次为在最后一个插入 因为插入每次为在最后一个插入， ，， ，故时间复杂度为 故时间复杂度为故时间复杂度为 故时间复杂度为O OO O( (( (1 11 1) )) ), ,, ,而删除时每次要做 而删除时每次要做而删除时每次要做 而删除时每次要做 m mm m次的位移 次的位移次的位移 次的位移， ，， ，有 有有 有n nn n个人 个人个人 个人， ，， ，故删除的时间复杂度为 故删除的时间复杂度为故删除的时间复杂度为 故删除的时间复杂度为O(n*m) O(n*m)O(n*m) O(n*m) 五 五五 五、 、、 、 用户手册 用户手册用户手册 用户手册 1 11 1、 、、 、 本程序运行环境为 本程序运行环境为本程序运行环境为 本程序运行环境为DOS DOSDOS DOS系统 系统系统 系统， ，， ，执行文件为 执行文件为执行文件为 执行文件为: :: :Joesph.exe Joesph.exeJoesph.exe Joesph.exe