数据结构约瑟夫环和回文实验报告.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<Data<<"";//输出结点序号
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<Data<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、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。
升级会员 