《数据结构》上机实验的目的和要求（大全）

第一篇：《数据结构》上机实验的目的和要求（大全）

《数据结构》上机实验的目的和要求

通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及调试程序的能力。

要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为：

1、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：

（1）输入的形式和输出值的范围；

（2）输出的形式；

（3）程序所能达到的功能；

（4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。

2、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。

3、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。

4、调试分析：

（1）调试过程中所遇到的问题及解决方法；

（2）算法的时空分析；

（3）经验与体会。

5、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。

6、测试结果：列出对于给定的输入所产生的输出结果。若有可能，测试随输入规模的增长所用算法的实际运行时间的变化。

第二篇：数据结构上机实验--图

数据结构上机实验六

实验内容:图的基本操作

实验要求:

1)图的遍历与基本操作要作为函数被调用.2)把自己使用的图结构明确的表达出来.3)基本上实现每个实验题目的要求.分组要求：可单独完成，也可两人一组。

实验目的:

1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对图的理解.评分标准：

1)只完成第一和第二题，根据情况得4，5分；

2）完成前3题，根据情况得5至7分；

3）在2）基础上，选做四）中题目，根据情况得8至10分。

题目:

一)建立一个无向图+遍历+插入

(1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图；

(2)对（1）中生成的无向图进行广度优先遍历并打印结果；

(3)向（1）中生成的无向图插入一条新弧并打印结果；

二)建立一个有向图+遍历+插入+删除

(1)以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图；

(2)对（1）中生成的有向图进行深度优先遍历并打印结果；

(3)在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果；

(4)在（1）中生成的有向图中，分别插入与删除一个顶点并打印结果；

(5)在（1）中生成的有向图中,各顶点的入度与出度并打印结果；

三）基本应用题

（1）编写算法，判断图中指定的两个顶点是否连通。

（2）编写算法，判断图的连通性。如果不连通，求连通分量的个数

（3）编写算法，判断图中任意两个顶点的连通性

（4）编写算法，判断图中是否存在回路。

（5）实现图的广度优先搜索算法。

四）高级应用题

（1）实现Prim算法

（2）实现Kruskal算法

（3）实现迪杰斯特拉算法

（4）实现拓扑排序算法

（5）实现关键路径算法

第三篇：上机实验要求

上机实验要求

一、实验前的准备工作

在上机实验前应事先做好准备工作，以提高上机实验的效率：

1.了解所用的计算机系统（包括C编译系统）的性能和使用方法。

2.复习和掌握与本实验有关的教学内容。

3.准备好上机所需程序。要仔细弄清题意，选择和设计合适的算法。在选择算法时，应当是在理解现有算法的基础上，自己动手画出流程图再设计源程序。手编写程序应当书写整齐，并经人工检查无误后才能上机，以提高上机效率。切忌不编写程序或抄袭他人程序，注意培养严谨踏实的学习作风。

4.对运行中可能出现的问题应率先作出估计；对程序中自己有疑问的地方，应作上记号，以便在上机时给予重视。

5.准备好调试和运行时所需的数据。

二、上机实验基本步骤

上机实验时应该独立上机。上机过程中出现的问题，除了系统问题外，一般应自己独立处理，不要轻易举手问教师。尤其对“出错信息”，应善于自己分析判断。这是学习调试程序的良好机会，碰到困难时切忌轻易放弃。

上机实验一般应包括以下步骤：

1.调出C编译系统，进入C工作环境，如Turbo C2.0集成环境。

2.输入自己编好的程序，注意正确的键盘输入指法。

3.检查一遍已经输入的程序是否有错（包括输入错误和编程中的错误）。

4.进行编译。如果编译和连接过程中发现错误，屏幕上会出现“出错信息”，则根据提示找到出错位置和原因，加以改正，再进行编译„„如此反复，直到顺利通过编译和连接为止。

5.运行程序，并分析运行结果是否正确、合理。组织多组实验数据，分别从不同情况下检查程序的正确性。

6.输出程序清单和运行结果。特别要进行上机调试记录（尤其是出错情况和排错记录），调试数据和运行结果记录、心得体会等。

三、撰写实验报告

做完实验后要写实验报告，对整个实验进行总结和提高，这是整个实验过程的一个重要环节，不要把它看成是一种不必要的负担，更不能敷衍了事。针对本课程的实验特点，建议在书写实验报告时应包括如下内容。

1.实验目的实验作为教学的一个重要环节，其目的在于更深入地理解和掌握课程教学中的有关基本概念和基本技术，从而进一步提高分析问题和解决问题的能力。因此，当着手做一个实验的时候，必须明确实验目的，以保证达到课程所指定的基本要求。在写实验报告时，要进一步确认是否达到了预期的目的。

2.实验内容

实验的目的是要通过解决一些具体问题来达到的。根据教学安排、进度、实验条件、可提供的上机时数、学生的基础等因素，逐步完成。在实验报告中，实验内容是指本次实验中实际完成的内容，在每一个实验题目中，一般都提出了一些具体要求，其中有些具体要求是为了达到实验目的而提出的。因此，在实验内容中，不仅要写清楚具体的实验题目，还应包括具体要求。

3.算法和流程图

算法设计是程序设计过程中一个重要步骤。本章的某些实验题目给出了方法说明，有的还提供了流程图，但有的没有给出流程图。如果在做实验的过程中，使用的算法或流程图和本书中给出的不一样，或者书中没有给出算法和流程图，则在实验报告中应给出较详细的算法说明与流程图，并对其中的主要符号与变量作相应的说明。

4.程序清单

程序设计的产品就是程序，它应与算法或流程图相一致。程序要具有易读性，符合模块化和结构化原则。

5.运行结果

程序运行结果一般是输出语句所输出的结果，对于不同的输入，其输出结果是不同的。因此，在输出结果之前一般还应注明输入的数据，以便对输出结果进行分析和比较。

6.调试分析和体会

这是实验报告中最重要的一项，也是最容易忽视的一项。实验过程中大量的工作是程序测试，在调试过程中会遇到各种各样的问题，每解决一个问题就能积累一点经验，提高编程的能力。因此，对实验的总结，最主要的是程序调试经验的总结。调试分析也包括对结果的分析。体会主要是指通过本次实验是否达到了实验目的，有哪些基本概念得到了深入理解等。

第四篇：数据结构上机实验报告

数据结构实验报告

课程 数据结构 _ 院 系

专业班级 实验地点

姓 名 学 号

实验时间 指导老师

数据结构上机实验报告1

一﹑实验名称：

实验一——链表

二﹑实验目的：

1.了解线性表的逻辑结构特性；

2.熟悉链表的基本运算在顺序存储结构上的实现，熟练掌握链式存储结构的描述方法；

3.掌握链表的基本操作（建表、插入、删除等）4.掌握循环链表的概念，加深对链表的本质的理解。5.掌握运用上机调试链表的基本方法

三﹑实验内容：

（1）（2）（3）（4）创建一个链表 在链表中插入元素 在链表中删除一个元素 销毁链表 四﹑实验步骤与程序

#include #include typedef struct LNode {int data;struct LNode *next;}Lnode, *LinkList;//假设下面的链表均为带头结点。void CreatLinkList(LinkList &L,int j){//建立一个链表L,数据为整数，数据由键盘随机输入。

LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L;

cout<<“请输入一个链表：”<

for(int i=0;i

{

p=(LinkList)malloc(sizeof(Lnode));

cin>>p->data;

p->next=q->next;

q->next=p;

q=p;

} } int PrintLinkList(LinkList &L){//输出链表L的数据元素

LinkList p;

} void LinkListLengh(LinkList &L){//计算链表L的数据元素个数。int i=0;p=L->next;if(L->next==NULL){

} cout<<“链表的数据元素为:”;while(p)

{

cout<

data<<“ ”;

p=p->next;} cout<<“链表没有元素!”<

} LinkList p;p=L->next;while(p){

i++;

p=p->next;

} cout<<“链表的数据元素个数为:”<

LinkList p,s;int j=0;p=L;

while(p&&j

} if(!p||j>i-1){ p=p->next;++j;

}

} cout<<“插入元素的位置不合理!”;return 0;s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i){//删除链表L的第I个数据元素。

LinkList p,q;int j=0;p=L;while(p->next&&j

} if(!(p->next)||j>i-1){ p=p->next;++j;

}

} cout<<“删除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void DestroyLinkList(LinkList &L){//销毁链表L。

LinkList p,q;p=L->next;while(L->next!=NULL){ q=p->next;L->next=q;

free(p);} p=q;

free(L);

cout<<“链表已经被销毁!”<

LinkList L;

int i,j,x;cout<<“第一次数据结构上机实验—链表”<>j;

CreatLinkList(L,j);

LinkListLengh(L);

PrintLinkList(L);

cout<<“在第几个元素前插入:”;cin>>i;cout<<“输入插入的元素:”;cin>>x;

InsertLinkList(L,i,x);

LinkListLengh(L);

PrintLinkList(L);

cout<<“输入删除元素的位置:”;cin>>i;

DeleteLinkList(L,i);

LinkListLengh(L);

PrintLinkList(L);

cout<<“销毁程序后为:”<

DestroyLinkList(L);} 五﹑实验结果

六﹑实验心得体会：

链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。

实验的程序设计规划（实现的功能、分几个模块、子函数）（1）编写链表创建子函数void CreatLinkList(L,j)（2）编写链表插入子函数 int InsertLinkList(LinkList &L, int i, int x)（3）链表的打印int PrintLinkList(LinkList &L)（4）编写链表删除子函数 int DeleteLinkList(LinkList &L,int i)（5）编写链表销毁子函数void DestroyLinkList(LinkList &L)（6）编写主函数Main()，通过功能菜单调用子函数（7）编译调试程序

经过多次的调试，修改，实验结果终于正确了，在这个过程中，经历了不知道怎么进行声明区的编写如包含文件，宏定义，函数声明，全局变量声明，结构体等的定义等的结合，到学会了使用先把程序主要规划为四个部分来写就简单多了，第一，定义；第二，写所要调用的子函数；第三，写主函数，调用子函数；第四就是程序的编译与调试，修改。数据结构实验需要我们对每个程序的算法有深刻的理解，才能应用到实际中去，因此我们需要在做实验之前要熟悉实验的内容，且先把所要实验的程序写出来，在实验中就可以查找错误并加以改正，这是一个成长的过程。

数据结构上机实验报告一﹑实验名称：

实验二—队列

二﹑实验目的： 1.掌握队列这种抽象数据类型的特点, 掌握栈与队列在实际问题中的应用和基本编程技巧,并能在相应的问题中选用它;2.熟练掌握循环队列和链队列的基本操作实现算法，特别是队满和队空的描述方法；

3．掌握栈与队列的数据类型描述及特点；

4.掌握栈的顺序和链式存储存表示与基本算法的实现； 5.掌握队列的链式存储表示与基本操作算法实现;6.按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性； 7.认真书写实验报告，并按时提交。

三﹑实验内容：

对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求：

（1）掌握栈和队列的特点，即后进先出和先进先出的原则。（2）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空；

（3）编写主函数进行测试。

四﹑实验步骤与程序

#include #include #include

#define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){

} Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){

} void EnQueue(LinkQueue &Q,int e){

} int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“该链队为空:”);else printf(“该链队不为空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入队成功”,e);

} if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p;

return OK;void DeQueue(LinkQueue &Q){

} void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“队首元素删除成功”);

} if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;printf(“队首元素为:%d”,p->data);void OutQueue(LinkQueue &Q){

} void LengthQueue(LinkQueue &Q){

int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;while(p!=Q.rear->next){

} printf(“%d%,”,p->data);p=p->next;

} printf(“该队列的长度为:%d”,f);else {

} p=Q.front->next;while(p!=Q.rear->next){

} printf(“该队列的长度为:%d”,f);p=p->next;f++;void main(){

system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************链队列功能菜单***********************n”);printf(“1:初始化链队列，2:判断链队列是否为空, 3:进入队列，4:取出队首元素n”);printf(“5:输出该队列的所有元素,6:输出该队列的长度，7:结束程序，8:清屏n”);

while(flag){

printf(“n请输入操作符:”);scanf(“%d”,&i);switch(i){ case 1:

int e,n,k;printf(“请输入队列的长度:”);scanf(“%d”,&n);printf(“请输入队列的元素:”);for(e=1;e<=n;e++){

} printf(“初始化链队成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q);

break;case 3:

int j;printf(“请输入要进入队列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5:

printf(“该队列的元素为:”);OutQueue(Q);break;

case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break;

} } 五﹑实验结果

六﹑实验心得体会：

程序主要构造了主函数main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等调用函数，实现了队列的创立，队列是否为空的判断，入队和出队等功能。

通过此次实验，加深了对队列的存储结构的了解，同时也对程序设计能力有了提高，加深了对队列先进先出性质的理解，它允许在表的一端进行插入，在另一端删除元素，这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。我们往往写不出程序，这其中的原因我觉得是对程序的结构不是很了解，对实验的内容也不熟练的结果，数据结构给我们许多程序的算法和模型，对我们写程序的思维有很大的锻炼，我们应珍惜每次上机实验的机会去实践课堂上所学的东西并从中发现问题，从而达到提升写程序的能力。

数据结构上机实验报告一﹑实验名称：

实验三—二叉树的遍历

二﹑实验目的：

1、熟悉二叉树的结构特性，了解相应的证明方法；

2、掌握二叉树的生成，掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；

3、理解二叉树的三种遍历方法：先序遍历、中序遍历和后序遍历；

4、学会编写实现树的各种操作的算法。

二、实验内容：

1、使用类定义实现二叉树，补充完整所缺的函数，并实现创建和遍历二叉树的基本操作；

2、编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递归或者非递归实现，遍历算法为在先序、中序和后序遍历算法。

三、实验步骤与程序：

#include #include #include typedef struct BiTNode { char data;struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;//定义结点类型 BiTree CreateBiTree()//创建树 { char p;BiTree T;scanf(“%c”,&p);if(p==' ')T=NULL;else { T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间 T->data=p;T->lchild=CreateBiTree();T->rchild=CreateBiTree();} return(T);}

void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函数 {

printf(“------------二叉树的遍历-------------n”);printf(“请输入要遍历的数：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍历:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍历:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍历:”);printf(“n”);PostOrder(Ta);} 五﹑实验结果

六﹑实验心得体会：

实验的程序设计规划（实现的功能、分几个模块、子函数）（1）先序遍历递归算法函数：void PreOrder(BiTree T)（2）中序遍历递归算法函数：void InOrder(BiTree T)（3）后续遍历递归算法函数：void PostOrder(BiTree T)（4）主函数的实现：void main()

在实验前我认真阅读关于二叉树的实现的内容，为编程实现第一步，本次实验通过按上述的实验步骤一步步实现的，实验过程中出现了一些错误，经过一步步的调试，修改错误，得到了二叉树的遍历用递归运算的方法的程序。通过这个实验，我体会到了理解数据结构的重要性，这有真正理解了定义数据类型的好处，才能用好这样一种数据结构。二叉树的先序，中序与后序的输出都用了递归的算法，而且用起来不是很复杂，这使我更进一步理解了函数递归调用并得到灵活运用；在实现算法上，从算法的效率看，递归方法书写形式较为简洁，更为直观，一般具有较好的空间效率。

总之，不管做什么实验，我们在做实验前都要先预习，对所做的实验有较深的理解，在做实验的时候需要很严谨，仔细的查找错误，从而能在实验中收获知识，提升自己。

数据结构上机实验报告4 一﹑实验名称：

实验四—查找

二﹑实验目的：

1、熟悉掌握顺序表的查找方法；

2、熟练掌握二叉排序树的构造方法和查找算法

3、掌握描述查找过程的判定树的构造方法，以及按照定义计算各种查找方法在等概率情况下查找成功时的平均查找长度；

4、学会定义线性表的储存类型，实现C++程序的基本结构对线性表的一些基本操作和具体的函数定义；

5、掌握顺序表的基本操作，实现顺序表的查找的等基本运算；

6、掌握对于多函数程序的输入，编辑，调试和运算过程。

二、实验内容：

1、实现顺序表的查找算法

2、关于衡量查找的主要操作—查找的查找平均效率的平均长度的讨论。

三、实验步骤与程序：

#include #define MAX_SIZE 100 typedef struct{ int key;}element;

element list[MAX_SIZE];

int seqsearch(element list[],int searchnum,int num);int main(){

int i,num,searchnum,k;

printf(“---------------数据结构查找实验-------------n”);printf(“请输入数据元素的个数：”);scanf(“%d”,&num);printf(“请输入数据的元素：n”);for(i=0;i

printf(“请输入要查询的数据元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查询元素的下标为：”);printf(“%dn”,k);} else printf(“查询元素不存在。n”);} return 0;}

int seqsearch(element list[],int searchnum,int num){ int j;

list[num].key=searchnum;

for(j=0;list[j].key!=searchnum;j++);return j

六﹑实验心得体会：

实验的程序设计规划为先写一个主函数int main()，再写一个查找的子函数int seqsearch(element list[],int searchnum,int num)，主函数通过调用子函数的方法实现程序的设计。

所谓“查找”即为在一个众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录），通过本次实验，我更进一步的了解数据结构程序实验设计实现算法的基本模型，和算法实现等基本内容，学会了顺序表的查找方法。

数据结构上机实验报告5 一﹑实验名称：

实验五—内部排序

二﹑实验目的：

1、通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况，并加以灵活应用。

2、掌握各种排序时间复杂度的分析方法。

二、实验内容：

1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

2、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。

3、讨论各种内部排序方法的基本思路，算法特点，排序过程及它们的时间复杂度的分析。

三、实验步骤与程序：

#include void main(){

} int x;void charu();void kuaisu();printf(“----------内部排序---------n”);printf(“

1、插入排序：n”);printf(“

2、选择排序：n”);printf(“请根据序号选择：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m;

printf(“插入排序n”);

printf(“请输入个您想排序的数据:n”);

for(i=0;i<7;i++)scanf(“%d”,&a[i]);

for(j=1;j<7;j++)

{ m=a[j];

for(i=j-1;i>=0;i--)

{

if(a[i]

break;

else a[i+1]=a[i];

}

a[i+1]=m;

}

printf(“排序成功:”);

for(i=0;i<7;i++)

printf(“ %d”,a[i]);

printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key;

key=L[first];

while(left

{ while((left=key))

right--;

if(left

L[left++]=L[right];

while((left

left++;

if(left

L[left]=key;

return left;

}

quick_sort(int L[],int first,int end)

{ int split;

if(end>first)

{ split=quick(first,end,L);

quick_sort(L,first,split-1);

quick_sort(L,split+1,end);

}

} void kuaisu(){

int a[7],i;

printf(“快速排序n”);

printf(“请输入个您想排序的数据:n”);

for(i=0;i<7;i++)

scanf(“%d”,&a[i]);

quick_sort(a,0,9);

printf(“排序成功:”);

for(i=0;i<7;i++)

printf(“ %d”,a[i]);

printf(“n”);} 五﹑实验结果：

六﹑实验心得体会：

排序的功能是将一个数据元素（或记录）的任意序列，从新排成按关键字有序的序列；直接插入排序的稳定性比快速排序高，且算法较简单。本次实验运用到的是插入排序和快速排序。

第五篇：数据结构上机实验报告

实习报告

题 目 : 实现一个约瑟夫环程序

班级：031021姓名：王帅学号：03102076

一、需求分析

1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。

2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。

3． 程序执行的命令包括：

1)构造单向循环链表；2）进行数值的输入，并作判断分析；3）约瑟夫算法的实现与结果输出；4）结束。

4． 测试数据

m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，（正确的出列顺序为6，1，4，7，2，1，3，5）。

二、概要设计

1．单向循环链表的抽象数据类型定义为：

ADT List｛

数据对象：D=｛ai | ai↔正整数，I=1，2，......，n,n≥0｝数据关系：R1=｛< ai-1，ai > |，ai-1，ai↔D,I=1，2，......，n｝基本操作：

Init List(&L)

操作结果：构造一个空的线性表L。

List Insert(&L,i,e)

初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据元素e，L长度加1。List Delete(&L,i,&e)

初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。

2． 程序包含四个模块：

1）主程序模块：

void main()

{

初始化；

for（;;）

{}

while（命令=开始）

{

接受命令；

处理命令；

}

for（;;）

{ }

}

2）有序表单元模块——实现有序表的抽象数据类型；

3）节点结构单元模块——定义有序表的节点结构；

4）数据输入分析模块——判断输入数据正确有效；

各模块之间的调用关系如下：

主程序模块

↓

有序表结构模块

↓

节点结构单元模块

↓

数据输入分析模块

三、详细设计

1、结点类型，指针类型

TypedefstructLNode{

int code,date;//code 为人所在位置 date为人持有的密码 struct LNode *next;

};// 结点类型，指针类型

2、构造单向循环链表

struct LNode *p,*head,*q;//定义头节点，和指针

for(i=2;i<=n;i++)

{

struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配

新结点空间

s->code=i;

input(s->date);

p->next=s;

p=p->next;

}

p->next=head;//根据输入的人数，进行单项循环链表的创建，p指向最后一个结点，并与头节点链接，形成单项循环链表

3、约瑟夫环的程序实现部分

while(n!=1)//判断输入人数，如为1则直接输出结果，不循环

{

for(i=1，m=m%n;i

{

p=p->next;

}

q=p->next;//找到要删除节点

p->next=q->next;//找到要删除节点的后继，并连接新环m=q->date;//找到下一个密码

printf(“%d”,q->code);

free(q);//释放已删除节点空间

n--;//链表长度减一

}

printf(“%d”,p->code);//约瑟夫环的结果输出

4、其他函数代码

数值的输入限制

int input()

{

int y,k,z=0;

char c;//元素类型

char a[4];//数组初始化

if(!z)//输入判断，确定位数字或控制字符且位置和密码不为零 {

for(y=0;y<4;y++)

{

c=getch();

if(c>=48&&c<=57)//确定为输入数字

{a[y]=c;

putch(c);

}

else

{

y--;

if(c=='r')//确定输入为控制字符 即回车或者删除

break;

else

if(c==8)

{a[y]='n';

y--;}

continue;

}

}

k=atoi(a);//确定最终输入数字的值

printf(“n”);

z=k;

if(z==0)

printf(“ERROR!The number couldn't be 0!n”);// 输入为零，重新输入 }

return(k);//数值的返回

5、函数的调用关系图反映程序层次结构

Main→input

四、调试分析

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）。

五、用户手册

用户根据提示，先输入起始密码m，然后输入人数n，再根据人数，分别输入每个人的密码date，数值均不能为0，否则会提示重新输入，输入为字母则自动丢弃，输入错误可用删除键进行修改，输入完成后按回车键确定本次输入完毕（若输入数字大于9999，则第五位自动转换为下一个数字的起始位，依此类推）。

当n个数字全部输入完毕，则自动显示结果，按任意键则退出本程序。

六、测试结果

第一组：m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，出列顺序为6，1，4，7，2，1，3，5。

第二组： m 的初值为30；n=8，7个人的密码依次为：5，1，6，9，4，7，2，3，出列顺序为6，5，2，3，7，1，4，8。

第三组 : m 的初值为15；n=6，7个人的密码依次为：5，3，4，7，6，9，出列顺序为3，1，2，6，4，5。

七、附录

源程序头文件名清单：

#include “malloc.h”//内存空间分配头文件

#include “stdio.h”//输入输出函数头文件

#include “stdlib.h”//input函数中字符串转短整形函数的头文件 #include “conio.h”//最后显示结果、清屏函数头文件