1、 第 1 页 设计设计 1 1 约瑟夫环问题约瑟夫环问题 一、一、需求分析需求分析 一、具体目标包括：一、具体目标包括： 1、实现单循环链表的初始化以及节点的创建和赋值 2、理解约瑟夫环的定义，通过循环找到每次要出列的人的位置 3、从单循环链表中删除结点，对头节点和一般结点分情况讨论 二、单循环链表的抽象数据类型定义为：二、单循环链表的抽象数据类型定义为： ADT CLink 数据对象：Dai | aiElemset,i=1,2,n,n0 数据关系：R=, | ai-1,aiD,i=2,n 基本操作： Status CreateList(CLink CLink new_node; int i;
2、 printf(“Please Input Password 1 : “); scanf(“%d“, head-number=1; head-next=NULL; before=head; for(i=1;inumber = i+1; printf(“Please Input Password %d : “, new_node-number); scanf(“%d“, new_node-next = NULL; before-next=new_node; before=new_node; new_node-next =head; return TRUE; 流程图 1 CreatList(hea
3、d ,length) head指向申请的空 间进行赋值 befor=head inext=head Return TRUE N 3 3、构建一个实现出列顺序的算法、构建一个实现出列顺序的算法 基本思想：用 ptr 只向当前出列的结点，若为头结点时则找到指向头结 第 5 页 点的指针，并做结点的删除，若不是头结点，则用 back 指针作为指向 ptr 的指针，进行结点的删除。 void selectqueue(CLink head,int n,int m) CLink ptr,back,last; int i,j; ptr=head; for(i=0;ipassword； printf(“第%d
4、 个出列的编号以及密码为:%d,%dn“,i+1,ptr-number,m); if(ptr=head) last=head; while(last-next!=head) last=last-next; last-next=head-next; free(ptr); ptr=last-next; head=ptr; 第 6 页 else back-next=ptr-next; free(ptr); ptr=back-next; 流程图 2 Slectqueue(head ,n,m) inumber N Ptr=head 找到 符合last- next=head Free(ptr)ptr=la
5、st-nezt Y back-next=ptr-next Ptr=back-next N 结束 N 第 7 页 四、运行结果及分析四、运行结果及分析 测试用例 1： （一般数据） 测试用例 2： （边界数据） 第 8 页 测试用例 3： （错误数据） 运行结果分析： （1）对一般数据能否输出正确结果？ 能输出正确结果 （2）对边界数据能否给出合适的反应？ 对于头结点要出列或者第一个上限数很大时也可以给出结果 （3）对错数据能否给出必要的提示？ 提示重新输入的语句 （4）算法的复杂度多少？ CreateList 是 O(n), Selectqueue 是 O( 2 n) 五、总结五、总结 本次实
6、验主要考察了对单循环链表的灵活应用 第 9 页 附：主要源代码附：主要源代码 #include #include #define OVERFLOW -1 #define TRUE 1 typedef int Status; typedef struct CNode int password; int number; struct CNode *next; CNode,*CLink; Status CreateList(CLink CLink new_node; int i; printf(“Please Input Password 1 : “); scanf(“%d“, head-number=1; head-next=NULL; before=head; for(i=1;inumber = i+1; printf(“Please Input Password %d : “, new_node-number); scanf(“%d“, new_node-next = NULL; bef
