计算机科学与工程学院
《算法与数据结构》试验报告[一]
专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼
学生姓名肖宇博试验时间2012-2-29
试验项目算法与数据结构
试验类别基础性（）设计性（）综合性（√）其它（）
试验目的及要求（1）掌握用VC++上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。
成绩评定表
类别评分标准分值得分合计
上机表现积极出勤、遵守纪律
主动完成设计任务
30分
程序与报告程序代码规范、功能正确
报告详实完整、体现收获
70分
备注：
评阅教师：
日期：年月日
试验内容
一、实验目的和要求
1、实验目的：
（1）掌握用VC++上机调试线性表的基本方法；
（2）掌握顺序表的存储结构以及基本运算的实现。
2、实验内容
约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，m为任意一个正整数。
从第一个人开始顺时针
方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的
下一个人开始重新从1报数，报到m时停止并且报m的人出列。
如
此下去，直到所有人全部出列为止。
要求设计一个程序模拟此过程，
对任意给定的m和n，求出出列编号序列。
3、实验要求：用顺序表实现。
二、设计分析
根据实验要求，采用顺序表来完成本次实验。
实验中定义了两个顺序表，一个用来存储n个人的序号，另一个用来存储n个人的出队顺序及序号。
程序中充分考虑了如果出队的元素大于队列的元素个数时应该有的情况，如果出现这样的错误就提示！否则继续出队！
三、源程序代码
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10 // 宏替换最大值
typedef struct
{
int data[MAXSIZE];
int length;
}Sqlist;
void CreatList(Sqlist *&L,int a[],int n) //创建顺序表
{
L=(Sqlist *)malloc(sizeof(Sqlist));
for(int i=0;i<n;i++)
{
L->data[i]=a[i];
}
L->length=n;
}
void InitList(Sqlist *&L) //初始化顺序表{
L=(Sqlist *)malloc(sizeof(Sqlist));
L->length=0;
}
void DestoryList(Sqlist *&L) //释放顺序表空间{
free(L);
}
void josephus(Sqlist *&L) //约瑟夫环的核心代码{
int t=0;
int m=0;
printf("请输入数到几个人出来");
printf("\n");
scanf("%d",&m);
if(m>L->length)
{
printf("没有这么多人呀！╮(╯_╰)╭");
}
else
{
printf("出列顺序为：");
for(int q=L->length;q>=1;q--)
{
t=(t+m-1)%q;
printf("\n");
printf("\t%d\t",L->data[t]);
for(int j=t+1;j<=q-1;j++)
L->data[j-1]=L->data[j];
}
printf("\n");
}
}
void main()
{
Sqlist *s;
InitList(s);
int a[MAXSIZE];
int n=0;
printf("请键入要输入几个数");
printf("\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
a[i]=i+1;
}
CreatList(s,a,n);
josephus(s);
DestoryList(s);
printf("\n");
}四、测试用例（尽量覆盖所有分支）
1.当输入1，2，3，4。
n的这些数字范围以内的话，可以得到正确的结果如图：
2.当输入的n比较大的时候的情况如图：
3.当输入序列少，出对数大时:
4.当输入要出列的元素大于队列里的元素，这将会提示错误如图：
5.当你的输入出队的序列数有误时将会提示错误
6.当你的要输入的数大于定义的最大值时提示错误如图：
7.当你的要输入的数小于定义的最大值时提示错误如图：
五、实验总结
先后学习了C/C++,对编程语言基本上有一些了解，但在数据结构试验程序设计过程中还是学到了很多。
经过两天的设计，在不断翻阅以前资料的情况下，有针对性的复习了C/C++中指针、循环的相关理论知识和vc6.0的基础知识和应用技巧，最后比较成功的完成了本次的设计。
本次设计是运用已学的线性表中顺序表的相关内容，由于以前的指针方面知识没有学好，刚开始时有些措手不及，尤其是运用指针申请动态内存，遇到了不小的麻烦，程序检查时没有错误，但运行不了，经过仔细的思考，终于发现了问题所在，特别高兴。
程序运行后，开始考虑各种BUG，比如输入的数大于数组定义的最大值的时候抑或是数组的数小于应该输入的最小值（比如0），比如输入的要出列的元素大于队列中已有的元素抑或是小于数组中应该出现的元素，比如一些错误输入等等之内的BUG 都考虑之后的问题。
然后思考与反思后，发现程序还是有美中不足的地方，算法的核心存在一些不足，比如依次从后往前挪动一个元素的时候存在一些效率上的问题，当元素较多时，效率不高！考虑到可以采用标记法，把出队元素标记为0，以后的出队的时候跳过0，而不是进行挪动，这样程序的效率就大大提高了！
本次实验运用的是C语言，大一时就学过了，在今后的试验中应该多尝试其他的语言来写程序，提高自己思维的兼容性很重要。
这次的设计让我学到了不少的东西，而且了解到编程在现今诸多行业中应用的重要性以及今后的发展，可以说是受益匪浅，为今后开发相关系统奠定了坚实的理论基础和总结了宝贵的开发经验。