约瑟夫环-joseph环-数据结构与算法课程设计报告.docx

约瑟夫环-joseph环-数据结构与算法课程设计报告 合肥学院 计算机科学与技术系 课程设计报告 20222022学年第二学期 课程数据结构与算法 课程设计名称joseph环 学生姓名朱玉庭 学号0804012029 专业班级08计本(2) 指导教师王昆仑、张贯虹 2022 年06月08号 一、问题分析和任务定义： 约瑟夫环是一个数学游戏，根据游戏内容的描述，能够很容易的看出，游戏中的玩家顺时针围坐一圈，能够很容易的发现，这跟本课上的单循环链表非常相似，所以可以通过单循环链表存储结构模拟此过程，当游戏中的玩家出列时，可以通过删除单循环链表中的结点来实现。 二、数据结构的选择和概要设计： 选择带为指针的单循环链表来解决这个问题，先建立一个空链表，然后根据人数生成具有相应结点的单循环链表，知道密码后，通过循环来找到对应的结点，然后将该结点的编号输出，改变密码，最后删除结点，以此类推，知道编码全部输完，即可得到结果序列。 三、详细设计和编码： 本题目是通过单循环链表存储结构来模拟此过程的，首先要先明确该单循环链表中结点的结构类型，定义如下： typedef struct Node int key; /每个人持有的密码 int num; /这个人的编号 struct Node *next; /指向下一个结点 Link; 当生成单循环链表时，就需要用到课本上创建单循环链表的有关内容了，可以先通过子函数Link *InitList()建立一个空链表，返回指针L，然后将返回的指针代入子函数Link *Creater(Link *L,int n)的形参中，对循环链表进行初始化，并且也返回一个指针，然后再将这个返回的指针代入到输出函数void Output(Link *L,int n,int m)的形参中，要想根据题目要求完成序列的输出，需要通过两个for循环来实现，第一个循环for(i=1;inum)，并将该编号下的密码赋值给m 即m=q->key，当循环完毕时正好将编号全部输出，第二个循环for(j=1;jnext; q=p->next; 用以找到相应的结点，并用指针q指向它，当完成了编号的输出和密码的赋值后，删除q指向的结点，将两个循环适当结合，即可输出正确的结果序列，其中的人数n和初始密码在主函数中确定。 四、上机调试： （1）有2个玩家，初始密码为21； （2）有3个玩家，初始密码为5： （3）有5个玩家，初始密码为8： （4）有7个玩家，初始密码为10： 五、测试结果及分析： （1）程序运行后，只能执行一部分，错误情况如下： 错误原因如下： 调用子函数时，传递给形参的并不是L的地址，而是传递的内容，以至在对链表进行初始化时，语句L->next=p不能执行，for循环不了，故程序只能运行一部分，将程序略作修改，建空链表时，不用形参即可，修改如下： （2）程序运行时，结果输不出来，错误情况如下： 错误原因如下： 两个形参中的L不能联系在一起，因为在进入约瑟夫环的函数Creater（L，n）后，L 的地址虽然变化了，但是不会对主函数中L的地址造成影响，故在调用输出函数Output（L，n，m）时，其中的L的地址不是Creater（L，n）中改变后的地址，所以不能联系到一起，将程序略作修改，在生成约瑟夫环的函数中返回一个指针，将此返回的指针代入到输出函数Output中即可，修改如下： 六、用户使用说明： 进入程序运行界面后，根据提示输入相应的信息，第一步输入的是总人数n，第二步输入初始密码m，紧接着依次输入n个学生的密码，输入完成后，即可显示出最终结果。 示例： 请先输入总人数：3 请确定开始时的报数上限值： 5 第1个人的密码：4 第2个人的密码：6 第3个人的密码：2 结果序列为：2 1 3 七、参考文献： 1 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2022年5月。 2 何钦铭，颜晖. C语言程序设计. 北京：高等教育出版社，2022年1月。 3 郑莉，董渊. C+语言程序设计（第三版）. 北京：清华大学出版社，2022年1月。 4 谭浩强. C语言设计（第三版）. 北京：清华大学出版社，2022年3月。 5 百度。 八、附录： #include"stdio.h" #include"stdlib.h" typedef struct Node int key; /每个人持有的密码 int num; /这个人的编号 struct Node *next; /指向下一个节点 Link; void Menu() printf("tt*n"); printf("ttt*Joseph环-课程设计*n"); printf("tt*n"); Link *InitList() /创建一个空的链表 Link *L; L=(Link *)malloc(sizeof(Link); L->key=0; L->num=0; L->next=L; return L; Link *Creater(Link *L,int n) /初始化链表 Link *p,*q; int i; q=L; for(i=1;ikey); p->num=i; L->next=p; L=p; L->next=q->next; free(q); return L; void Output(Link *L,int n,int m) Link *p,*q; int i,j; p=L; printf("ttt*Order*n"); printf("ttt结果序列为："); for(i=1;inext; /q指向目的结点 m=q->key; printf("%d ",q->num); p->next=q->next; /此两步是为了释放目的结点，即删除 free(q); printf("nttt*End*n"); void main() Link *L,*S; int n,m; system("color A"); L=InitList(); /构造出一个只有头结点的空链表 Menu(); printf("请先输入总人数:"); scanf("%d",&n); /总共的人数n printf("请确定开始时的报数上限值:"); scanf("%d",&m); /初始密码为m S=Creater(L,n); /建立好一个约瑟夫环 Output(S,n,m);