数据结构约瑟夫环和回文实验报告.docx
- 文档编号:14091427
- 上传时间:2023-06-20
- 格式:DOCX
- 页数:13
- 大小:94.55KB
数据结构约瑟夫环和回文实验报告.docx
《数据结构约瑟夫环和回文实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构约瑟夫环和回文实验报告.docx(13页珍藏版)》请在冰点文库上搜索。
数据结构约瑟夫环和回文实验报告
数
据
结
构
实
验
报
告
实验一:
约瑟夫环的实现
一、问题描述
约瑟夫(Joseph)问题的一种描述是:
编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。
一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。
报m的人出列,将他的密码作为新的m值,从他的顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。
试设计一个程序求出出列顺序,以及密码顺序。
二、基本要求
利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。
三、测试数据
数
目
次
值
项
数
1
2
3
4
测试结果1
出队密码
顺序顺序
测试结果2
出队密码
顺序顺序
测试结果3
出队密码
顺序顺序
测试结果4
出队密码
顺序顺序
参与人数
4
35
12
6
9
上限值
5
8
1
1
第一人的密码
3
6
1
5
13
815
11
第二人的密码
4
7
5
9
41
1213
25
第三人的密码
6
12
6
6
24
312
36
第四人的密码
1
8
12
5
36
65
61
第五人的密码
3
8
4
16
412
第六人的密码
5
1
2
105
58
第七人的密码
9
8
79
第八人的密码
24
15
2
48
第九人的密码
54
20
3
27
第十人的密码
5
53
第十一人的密码
11
920
第十二人的密码
13
1111
★注(由于表格有限,特在此注明):
当输入的人数大于30时,系统提示“输入数字无效”重新输入;当输入的上限值大于10时,系统提示“输入数字无效”重新输入;;当输入的密码大于10时,系统提示“输入数字无效”重新输入。
(有两组数字的方格中,下面的数字为有效数值)
四、算法、思想
为了解决这一问题,可以先定义一个长度为30(人数)的数组作为线性存储结构,并把该数组看成是一个首尾相接的环形结构,那么每次报m的人,就要在该数组的相应位置做一个删除标记,该单元以后就不再作为计数单元。
这样做不仅算法较复杂,而且效率低,还要移动大量的元素。
用单循环链表来解决这一问题,实现的方法相对要简单得的多。
首先定义链表结点,单循环链表的结点结构与一般单链表的结点结构完全相同,只是数据域用一个整数来表示位置;然后将它们组成一个具有n个结点的单循环链表。
接下来从位置为1的结点开始数,数到第m个结点,就将此结点从循环链表中删去,然后再从删去结点的下一个结点开始数起,数到第m个结点,再将其删去,如此进行下去,直至全部删去为止。
五、代码分析
(一)创建单循环链表
structLink
{
intData;
Link*next;
};
Link*Creat(intn)
{
Link*head,*s,*r;
head=newLink;
r=head;
for(inti=0;i { s=newLink; cin>>s->Data; r->next=s; r=s; } r->next=head->next; returnhead; } (二)“约瑟夫环”的操作模块; Link*Jose(Link*p,intm) { ints=m; if(p==p->next) returnp;//递归出口即循环链表只剩下一个结点,将该结点指针返回 Link*q=NULL;//指针q用来保存删除结点的前驱 for(intj=1;j { q=p; p=p->next; }//查找要删除结点 q->next=p->next;//删除节点 cout< Jose(p->next,s);//递归调用 } (三)主程序 intmain() { cout<<"请输入Jose环中人数: "; intn,m; cin>>n; cout<<"请输入每个人手中的序号: "< Link*head=Creat(n); cout<<"请输入报数的数值"; cin>>m; Link*p=head->next; cout< cout<<"离开的序号依次是: "; Link*Result=Jose(p,m); cout< return0; } 六、运行界面 输入6个数146793,并输入报数3 七、调试分析 1、早期程序只写了约瑟夫环的实现部分,没有对输入数据进行筛选,调试的时候会经常出错。 比如是输入字母,或者输入0,大于32767溢出; 2、早期的循环过程中没有进行优化,导致循环次数过多,浪费时间; 3、为了输出时美观,分别在input和main函数主体内做了两次,输入非零的判断,浪费了资源; 4、算法的时空分析 为了限制在输入过程中不会上溢,只在输入中限定为四个不全为零的数字,但是做的是do……while循环,复杂度为o (1); 当n大于1时: 在数据输入中,链表的创建是for循环,时间复杂度为o(n-1) 在约瑟夫环实现程序中,为for循环。 时间复杂度为o(m%n-1) 当n=1时,复杂度为o (1)。 八、实验心得 1、巩固和加深了对数据结构的理解,提高综合运用本课程所学知识的能力。 2、培养了我选用参考书,查阅手册及文献资料的能力。 培养独立思考,深入研究,分析问题、解决问题的能力。 3、通过实际编译系统的分析设计、编程调试,掌握应用软件的分析方法和工程设计方法。 4、通过课程设计,培养了我严肃认真的工作作风,逐步建立正确的生产观念、经济观念和全局观念。 根据我在实习中遇到得问题,我将在以后的学习过程中注意以下几点: 实验二: 回文判断 一、问题描述 对于一个从键盘输入的字符串,判断其是否为回文。 回文即正反序相同。 如“abba”是回文,而“abab”不是回文。 二、基本要求 (1)数据从键盘读入; (2)输出要判断的字符串; (3)利用栈的基本操作对给定的字符串判断其是否是回文,若是则输出“Yes”,否则输出“No”。 三、设计具体实现 1.总体设计以及详细设计 structStack { intData; char*base; char*top; }; voidInitStack(Stack&S);//创建栈 voidPush(Stack&S,chare);//进栈 charPop(Stack&S);//出栈 #include #include usingnamespacestd; constinta=100; structStack { intData; char*base; char*top; }; voidInitStack(Stack&S)//生成栈 { S.base=(char*)malloc(a*sizeof(char)); S.top=S.base; S.Data=a; } voidPush(Stack&S,chare)//入栈 { *(S.top)=e; S.top++; } charPop(Stack&S)//出栈 { chare; S.top--; e=*(S.top); returne; } intmain() { StackS; InitStack(S); inti=0,e,q=0,p=0,l;//q的作用是如果出栈跟字符一样就加1。 最后等于栈长说明是回文 strings; cin>>s; l=s.length(); intL=l; while(l>0) { Push(S,s[i]); i++; l--; } i=0; while(S.top! =S.base) { e=Pop(S); if(e==s[i]) { q++; } i++; } if(L==q) cout<<"是回文"< else cout<<"不是回文"< return0; } 2.调试及问题解决 1,第一组测试 图表1 2.第二组测试 图表2 3.第三组测试 图表3 4,第四组测试 图表4 四、结束语(设计总结) 1、认真上好专业实验课,多在实践中锻炼自己。 2、写程序的过程中要考虑周到,严密。 3、在做设计的时候要有信心,有耐心,切勿浮躁。 4、认真的学习课本知识,掌握课本中的知识点,并在此基础上学会灵活运用。 5、在课余时间里多写程序,熟练掌握在调试程序的过程中所遇到的常见错误,以便能节省调试程序的时间。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 约瑟夫 回文 实验 报告