约瑟夫环课程设计.docx
- 文档编号:17948655
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:17
- 大小:227.14KB
约瑟夫环课程设计.docx
《约瑟夫环课程设计.docx》由会员分享,可在线阅读,更多相关《约瑟夫环课程设计.docx(17页珍藏版)》请在冰点文库上搜索。
约瑟夫环课程设计
目录
1题目1
1.1问题描述1
1.2功能要求1
2算法思想描述:
1
2.1算法概述:
1
2.2算法具体分析2
3程序结构3
3.1主函数流程图3
3.2josephus()函数流程图4
4实验结果与分析5
4.1实验测试中的关键代码与各模块测试结果的分析与说明5
4.2试验过程中所遇到的问题分析与解决11
5课程设计总结12
参考文献13
1题目
约瑟夫环
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所示:
图2
2.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的主要作用是在把输出数据之后的结点删除.如此循环,直到还剩最后一个结点,同时定义a[i],b[i]用来储存编号和密码。
(4)passcode()把josephus()里所储存到数组a[i],b[i]的数据传递到passcode(),方便在退出josephus()函数之后还可以再次查看。
(5)about()约瑟夫环问题的解析说明,增强使用者对本程序的理解。
3程序结构
3.1主函数流程图
3.2josephus()函数流程图
4实验结果与分析
上述程序在win-TC环境下加以实现,经过多次的测试,程序运行正确。
4.1实验测试中的关键代码与各模块测试结果的分析与说明
do
{ky=key();/*检查按键*/
switch(ky)
{caseKey_Q:
{y=5,
ky=Key_ENTER;}
break;
caseKey_A:
{y=6,
ky=Key_ENTER;}
break;
caseKey_B:
{y=7,
ky=Key_ENTER;}
break;
caseKey_C:
{y=8,
ky=Key_ENTER;}
break;
caseKey_DOWN:
if(y<8)
{upbar(y);
y++;}
break;
caseKey_UP:
if(y>5)
{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:
关闭\r\n");
gotoxy(3,4);
cprintf("A:
输入约瑟夫环数据\r\n");
gotoxy(3,5);
cprintf("B:
输出密码\r\n");
gotoxy(3,6);
cprintf("C:
什么是约瑟夫环\r\n");
y=5;
upbar(y-1);
(1)创建一个弹出式主菜单下面代码是其设计界面的代码.文本框1是界面代码,文本框2是获取键盘方向代码.效果如图2所示:
文本框1
文本框2
图2
图3
(2)实现光标的上移和下移,其代码文本框3所示,其效果,请对比图2和图3.
upbar(inty)/*光条上移函数*/
{
inti;
typedefstructtexel_struct
{
unsignedcharch;
unsignedcharattr;
}texel;
texelt;
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(inty)/*光条下移函数*/
{
inti;
typedefstructtexel_struct
{
unsignedcharch;
unsignedcharattr;
}texel;
texelt;
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(3,y-3);
return;}
文本框3
(3)在循环链表里输入数据,其实现代码如文本框4所示,效果如图4所示.
intListInsert(LinkList*L,inti,ElemTypee)/*在循环链表里插入元素并编号*/
{intj=0;
LinkList*p=L,*s;
if(i==1)
{L->data=e;
L->next=L;/*元素插入*/
L->y=i;/*编号*/
return1;}
else
{
p=L;
while(j {j++; p=p->next;} s=(LinkList*)malloc(sizeof(LinkList)); s->data=e; s->y=i;/*编号*/ s->next=p->next; p->next=s; return1;}} 文本框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,密码%d\n",q->y,q->data); a[i]=q->y;/*储存编号*/ b[i]=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,密码%d\n",q->y,q->data); /*最后一个并没有进入循环所以要在这里输出*/ a[i]=q->y;/*储存编号*/ b[i]=q->data;/*储存数据*/ printf("\n数据已储存,需要再次查看密码请返回主菜单.");} 文本框5 图5 (3)查看已储存的数据.其代码如文本框6所示,其效果如图6所示: passcode(inta[max],intb[max]) { inti; system("cls"); if(! k) {printf("还没输入数据,请返回主菜单输入数据."); getch(); return;} printf("编号: "); for(i=1;i {printf("%d,",a[i]);} printf("密码: "); for(i=1;i {printf("%d,",b[i]);} 文本框6 图6 (3)查看约瑟夫环问题的内容: 其效果如图7所示: 图7 4.2试验过程中所遇到的问题分析与解决 问题一: 在创建弹出式菜单时,光标的上移和下移,无法实现. 解决方案: 将弹出式菜单的教程重新看了一遍,里面的光标上移和下移,都是通过各个坐标来实现的,例如window(3,3,29,9);前两个数是窗口的左上角的横坐标和竖坐标,后两个数是窗口右下角的坐标和竖坐标.经过反复调试之后,建了一个小的主菜单.光标上移和下移是在同学的帮助下实现的.因为自己还没完全理解这个过程的操作. 问题二: 在创建循环链表时,没有在头结点储存数据,造成在密码和编号输出不正确. 解决方案: 在输入数据时,从头结点开始储存数据. 问题三: 当链表被一个个删除的时候,如果头结点被删除的话,输出时会出现乱码. 解决方案: 加入一个判断语句if(q==head),当指针指到头的时候执行这一步head=q->next;将头结点移到下一个数据. 问题四: 在删除结点时,没有删除到输出数据那个结点. 解决方案: 用两个指针s和q,当计数count==x-1时,先将s=q,计数计到count==x后,这时q指向要输出的数据,再将s->next=q->next,再free(q),这样就可以删除对应的结点了. 问题五: 因为vC++6.0不支持window()这个函数,无法创建弹出式菜单,需要转移到win-tc下.josephus()函数在vC++6.0编译环境下运行没问题,复制到win-TC下就出现问题,已经定义的指针,提示我在还没定义之前就已经使用了. 解决方案: vC++6.0环境下: voidInitList(LinkList*&L) { L=(LinkList*)malloc(sizeof(LinkList)); L->next=L; } 在win-tc环境下: voidInitList(LinkList**L) { (*L)=(LinkList*)malloc(sizeof(LinkList)); (*L)->next=*L; } 只要把vC++6.0下的&改成二级指针,便可以在win-tc环境下使用了. 5课程设计总结 两周的课程设计将要结束了,课程设计弥补了平时学习上被遗忘的一些知识,同时也当作期末考试复习的一部分,约瑟夫环问题,主要是以链表和指针知识为主的编程设计,此次课程设计不但加深了自己对链表认识,同时也了解了更多关于链表在数据结构中的其它应用,从双链表,循环双链表到链栈,链串.自己都有认真去看了一次.指针方面的知识,在C语言中是极其重要的,之前对于指针的使用一直不怎么熟悉,经过这次课程设计之后,指针的使用,基本上都懂了.还有就是各个函数之间的传递和调用,运用起来也比较熟悉了,不像以前那样,不知怎么用. 这次课程设计的最大缺点就是,菜单的设计不应该选择弹出式菜单,因为约瑟夫环这道题目的要求只有三个,把解决约瑟夫环问题的主函数做出来之后,发现代码比较少,当时为了追求代码的数量,才选择了弹出式菜单.不仅花费了不少的时间,而且做出来的菜单也不美观.虽然在功能上是比其它的菜单好,但是对于修改菜单,菜单界面的修改都是挺麻烦的. 刚开始的时候,由于对题目错误的理解,对自己的编程造成了一些影响,里面说到密码,就想到了密码应该包括英文字母,没有注意到括号里面的正整数,如果是英文字母的话,难度相对大一些.开始在这个问题上耗了不少时间,后来在同学的提醒下,把错误修改了过来. 这次课程设计,给了自己很大的帮助,只是一道题目涉及的内容有点少,一道题目只涉及到一两个知识点,如果题目能够涉及到,树,图,栈,队列,串,这些数据结构中的重要知识点,这样对我们的能力培养会更好一点. 参考文献 [1]严蔚敏,吴伟民编.数据结构[M].北京: 清华大学出版社,2004.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 约瑟夫 课程设计
![提示](https://static.bingdoc.com/images/bang_tan.gif)