约瑟夫环-课程设计.doc

目 录1题目11.1问题描述11.2功能要求12算法思想描述：12.1算法概述：12.2算法具体分析23 程序结构33.1主函数流程图33.2 josephus()函数流程图44 实验结果与分析54.1实验测试中的关键代码与各模块测试结果的分析与说明54.2试验过程中所遇到的问题分析与解决115课程设计总结12参 考 文 献131题目约瑟夫环1.1问题描述编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 1.2功能要求a利用单循环链表作为存储结构模拟此过程；b键盘输入总人数、初始报数上限值m及各人密码；c按照出列顺序输出各人的编号。2算法思想描述：2.1算法概述：建立一个循环单链表,然后输入要建立结点的个数,在每个结点输入一个密码,同时按输入时的顺序进行编号:1,2,3,4, n.任选一个正整数x作为初始报数上限值.从定义的那个头结点开始,数到x,输出该结点所储存的编号和密码.并将该密码作为新的x值,同时还将该密码所在的结点删除.如此循环链表还剩最后一个数据的时候停止此循环.再将最后一个没在循环里面的编号和密码另外输出.循环链表如图1所示:图22.2算法具体分析（1） window(),switch(),upbar（）, downbar（）,key()这几个函数是构建本程序菜单所必须的函数.window()用于开窗口,以坐标的形式开辟一个窗口,并且可以在窗口里面储存数据.switch()创建菜单选项,key()主要用于获取键盘上的字符(包括字母和方向键,enter键),upbar()和 downbar()实现光条的上移和下移. textbackground()，textcolor()。窗口背景颜色和里面文本颜色的设置。（2） initlist()初始化循环链表,开辟一个空间作为头结点,并让l=l-next先让它指向自己,令链表循环起来. listinsert()向循环链表里面插入数据(包括编号和密码), displist()以定义的头结点为第一个数,输出循环链表.（3） josephus()主要用于解决约瑟夫环问题,首先调用initlist()建立循环链表,再调用listinsert()插入数据,再调用displist()把储存的数据输出来.定义两个指针s和q,再定义count作为计数器,此时需要任意输入一个正整数x作为初始报数上限值,当计数器count=x时就把该指针所指向的数据输出并把该数据赋给x,作为新的报数上限值.然后删除该结点,s和q的主要作用是在把输出数据之后的结点删除.如此循环,直到还剩最后一个结点,同时定义ai,bi用来储存编号和密码。（4） passcode（）把josephus()里所储存到数组ai,bi的数据传递到passcode（）,方便在退出josephus()函数之后还可以再次查看。（5） about()约瑟夫环问题的解析说明，增强使用者对本程序的理解。3 程序结构3.1主函数流程图流程图1开始 选择选项quitjosephus()about()passcode()结束等待进入程序welcome主菜单输出所储存的编号和密码选退出选返回选退出选返回程序说明解决约瑟夫环问题并储存密码和编号 3.2 josephus()函数流程图 流程图2 4 实验结果与分析上述程序在win-tc环境下加以实现，经过多次的测试，程序运行正确。4.1实验测试中的关键代码与各模块测试结果的分析与说明do ky=key();/*检查按键*/ switch(ky) case key_q: y=5, ky=key_enter; break; case key_a: y=6, ky=key_enter; break; case key_b: y=7, ky=key_enter; break; case key_c: y=8, ky=key_enter; break; case key_down: if(y5) downbar(y); y-; break; /*创建一个弹出式主菜单*/ system(cls);/*清屏*/ window(2,2,30,10);/*创建主菜单并设置好字体颜色*/ textbackground(13); textcolor(15); clrscr(); window(3,3,29,9); textbackground(1); textcolor(4); clrscr(); gotoxy(3,3); cprintf( q:关闭rn); gotoxy(3,4); cprintf( a:输入约瑟夫环数据rn); gotoxy(3,5); cprintf( b:输出密码rn); gotoxy(3,6); cprintf( c:什么是约瑟夫环rn); y=5; upbar(y-1); (1)创建一个弹出式主菜单下面代码是其设计界面的代码. 文本框1是界面代码, 文本框2是获取键盘方向代码.效果如图2所示: 文本框1文本框2 图2图3(2)实现光标的上移和下移,其代码文本框3所示, 其效果,请对比图2和图3.upbar(int y) /*光条上移函数*/ int i; typedef struct texel_struct unsigned char ch; unsigned char attr; texel; texel t; for(i=7;i=24;i+) gettext(i,y,i,y,&t); t.attr=0x1f; /*字符为白色,背景为蓝色*/ puttext(i,y,i,y,&t); gettext(i,y+1,i,y+1,&t); t.attr=0x4f; /*字符为白色,背景为红色*/ puttext(i,y+1,i,y+1,&t); gotoxy(5,y-1); return; downbar(int y) /*光条下移函数*/ int i; typedef struct texel_struct unsigned char ch; unsigned char attr; texel; texel t; for(i=7;idata=e; l-next=l; /*元素插入*/ l-y=i; /*编号*/ return 1; else p=l; while(jnext; s=(linklist *)malloc(sizeof(linklist); s-data=e; s-y=i; /*编号*/ s-next=p-next; p-next=s; return 1; 文本框4图4(4)进入约瑟夫环问题的数据处理.其实现代码如文本框5所示,效果如图5所示:q=head; /*让q指向头结点,也就是从第一个开始计数*/ count=1; i=1; while(q-next!=q) /*当链表还剩最后一个结点时退出循环*/ if(count=x-1 & x!=1) /*当count计数计到x-1时,s和q指向同一个结点*/ s=q; if(count=x) /*当count计数计到x时,输出数据.*/ printf(输出各个人的密码:编号%d,密码%dn,q-y,q-data); ai=q-y; /*储存编号*/ bi=q-data; /*储存数据*/ i+; x=q-data; s-next=q-next; count=0; count+; if(q=head) /*在头结点被删之前,把头结点移到下一个数*/ head=q-next; free(q); /*删除输出数据的结点*/ displist(head); /*输出删除后的链表*/ q=s-next; else count+; q=q-next; printf(输出各个人的密码:编号%d,密码%dn,q-y,q-data);/*最后一个并没有进入循环所以要在这里输出*/ ai=q-y; /*储存编号*/ bi=q-data; /*储存数据*/ printf(n数据已储存,需要再次查看密码请返回主菜单.);文本框5图5(3)查看已储存的数据.其代码如文本框6所示,其效果如图6所示:passcode(int amax,int bmax)int i;system(cls); if(!k) printf(还没输入数据,请返回主菜单输入数据.); getch(); return ; printf(编号:);for (i=1;ik+1;i+)printf(%d,ai);printf(密码:);for (i=1;inext;将头结点移到下一个数据.问题四:在删除结点时,没有删除到输出数据那个结点.解决方案: 用两个指针s和q ,当计数count=x-1时,先将s=q,计数计到count=x后,这时q指向要输出的数据,再将s-next=q-next,再free(q),这样就可以删除对应的结点了.问题五:因为v c+6.0不支持window()这个函数,无法创建弹出式菜单,需要转移到win-tc下. josephus()函数在v c+6.0编译环境下运行没问题,复制到win-tc下就出现问题,已经定义的指针,提示我在还没定义之前就已经使用了.解决方案: v c+6.0环境下: void initlist(linklist *&l)l=(linklist *)malloc(sizeof(linklist);l-next=l;在win-tc环境下: void initlist(linklist *l) (*l)=(linklist *)malloc(sizeof(linklist); (*l)-next=*l; 只要把v c+6.0下的&改成二级指针,便可以在win-tc环境下使用了.5课程设计总结 两周的课程设计将要结束了,课程设计弥补了平时学习上被遗忘的一些知识,同时也当作期末考试复习的一部分,约瑟夫环问题,主要是以链表和指针知识为主的编程设计,此次课程设计不但加深了自己对链表认识,同时也了解了更多关于链表在数据结构中的其它应用,从双链表,循环双链表到链栈,链串.自己都有认真去看了一次.指针方面的知识,在c语言中是极其重要的,之前对于指针的使用一直不怎么熟悉,经过这次课程设计之后,指针的使用,基本上都懂了.还有就是各个函数之间的传递和调用,运用起来也比较熟悉了,不像以前那样,不知怎么用. 这次课程设计的最大缺点就是,菜单的设计不应该选择弹出式菜单,因为约瑟夫环这道题目的要求只有三个,把解决约瑟夫环问题的主函数做出来之后,发现代码比较少,当时为了追求代码的数量,才选择了弹出式菜单.不仅花费了不少的时间,而且做出来的菜单也不美观.虽然在功能上是比其它的菜单好,但是对于修改菜单,菜单界面的修改都是挺麻烦的. 刚开始的时候,由于对题目错误的理解,对自己的