课程设计说明模书版2).doc

设计1 约瑟夫环问题 一、需求分析 1、利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号，只适用于一个案例。 具体目标包括： （1）实现单循环链表的初始化； （2）理解约瑟夫环的定义，用循环找到每次报数人的序号； （3）从单循环链表中删除节点，并判断链表空与非空的临界条件。 2、构造一个含有n个元素的单向循环链表 ADT CircleList{ 数据对象：D{ai | ai∈Elemset,i=1,2,…,n,n≥0} 数据关系：R={ai-1,ai,an,a1 | ai-1,ai∈D,i=2,…n} 基本操作： Link InitList（int n） 操作结果：构造一个含有n个元素的单向循环链表。 3、程序中，先输入总人数 PN与初始密码SN，再输入输入 n 个正整数，作为这n个人的密码，接下来初始密码 m。 4、测试数据 PN=5 SN=2 ，N 个人的密码依次 = 1 4 6 4 8。 出列为：2 1 3 5 4。 二、概要设计 1、函数功能在main函数中实现 void main(void) { int PN, SN,i; LinkList L; printf(请输入总人数PN,和出示密码SN：); scanf(%d%d,PN,SN); int a[N]; a[0]=SN;//将a[0]保存为初始密码 printf(请输入%d个人各自所持的密码:\n,PN); for(i=1;iPN+1;i++) scanf(%d,a[i]); //创建链表 CreatLinkList(L, PN); //报数删人，输出结果 printf(Result:\n); deldata(L,PN,a); } 2、程序包括两部分 （1）结点类型 （2）main函数实现约瑟夫环 三、详细设计 1、结点类型 typedef struct Node { int data;//将这一圈人按从1~PN贴上序号 struct Node *next; }Node,*LinkList; LinkList head; 3、构建一个单循环链表算法 void CreatLinkList(LinkList *L,int PN) { Node *p, *q; int i; (*L) = (LinkList)malloc(sizeof(Node)); p = (*L); p-data = 1; for (i=2;i=PN;i++) { q=(LinkList)malloc(sizeof(Node)); q-data=i; p-next=q; p=q; } p-next =(*L); } 流程图1 2、程序主模块实现算法 从头结点开始，根据报数上限找到下一个出列人的序号，并读出该人的密码作为新的报数上限，从此节点的下一个节点开始进行新的查找。 取每次将要删除的人的密码，用于下次报数的上限.通过指针依次删除出列人相应的节点，直到该链表中无节点，退出循环。 四、运行结果及分析 1.调试分析 （1）进入程序后按提示输入程序初始数据回车后即可得到结果，输出结果表示依次出列人的序号，程序结束。若输入过程中输入有误，程序直接结束。算法时间复杂度正比于2n加上所有人的密码和。 （2）结果分析： 对一般数据与边界数据能输出正确结果；对错误数据能做出合适的反应。 2.测试结果 输入值不符合条件是： 五、总结 1.本程序比较简单，只有一个main函数，功能在main函数中实现，程序有待优化。本次实验主要考察了对单循环链表的应用。 2.调试过程中，由于指针使用不当多次出现错误，对指针的设计还需要熟练掌握。 附：主要源代码 #includestdio.h #includestdlib.h #define N 100 typedef struct Node { int data;//将这一圈人按从1~PN贴上序号 struct Node *next; }Node,*LinkList; void CreatLinkList(LinkList *L,int PN) { Node *p, *q; int i; (*L) = (LinkList)malloc(sizeof(Node)); p = (*L); p-data = 1; for (i=2;i=PN;i++) { q=(LinkList)malloc(sizeof(Node)); q-data=i; p-next=q; p=q; } p-next =(*L); } void deldata(LinkList *L,int PN,int a[]) { Node *