数据结构课程实训报告
- 格式：doc
- 大小：1.31 MB
- 文档页数：26
数据结构课程实训报告书
第 1 页
数据结构
课程实训报告
设计题目：
( 1 )基础题：5. 统计顺序串S中每一种字符出现的次数。
( 2 )综合题：1. 内部排序演示
2. 校园导游咨询
专 业：
班 级：
学 生：
学 号：
指导教师 ：
起止时间 ：
********学院
2010 年 6 月
数据结构课程实训报告书
第 2 页
第一章 需求分析
1.1 输入/输出形式和输出值的范围
（1）字符串S可为任意英文字符，长度限定在99999以内。最多输入128种不同的字符。
（2）内部排序问题中，输入的待排序数据，必须都是为整形数。此程序中设定了待排序数据为10个。如要修改，可在主函数（main）中将m.length改成你所需要的数据个数即可。主菜单选择对应功能时，可以输入任意数字，会有不同的结果。
（3）校园导游咨询程序。其才主菜单中只能输入整形数据，并且只能是1~4之间的数，否则将无法实现其对应的功能。在景点信息查询以及路经查询中也只能输入数字0~9；
1.2 程序功能
（1）基础题：5、编写程序，统计顺序串S中每一种字符出现的次数。
在在这个问题中，可由操作者自己输入字符串。系统会对输入的数据进行判断，将其字符串进行排序，把相同的字符放在一起。并且以ASCII码的顺序进行排序。能让我们很直观地验证结果的正确性，系统最后会输出每一种字符出现的次数。
（2）内部排序演示。
这个程序编写了多个函数，去实现对应的功能，分别是那六种排序方法，以及统计其在排序过程中，关键字所比较的次数，以及移动的次数。在此程序中，提供了操作人员自我选择的空间，可以自行选择所要的排序方法。也能选择重新输入待排序的数据，或者退出。当输入错误的时候，程序会提醒操作人员进行重新输入。
（3）校园导游咨询。
编写此程序，让我们能够通过此程序查询到校园景点的相关信息，为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 数据结构课程实训报告书
第 3 页
1.3 测试数据
1.3.1正确的输入及输出结果。
（1）字符串S问题；
1.首先输入待统计的字符串，并对输入的数据进行排序。排好续后，输入的字符串已经按照ASCII码的顺序进行了排序。这样，我们就能直观的看出每一种字符出现的次数了。
2.输出每一种字符出现的次数。将其与上图进行比较与验证，可以看出结果是否正确。
（2）内部排序演示问题。
程序开始就要求连续输入10个数据，输入完成，弹出对话菜单。操作人员可以选择对应的功能，输出排序的结果，以及关键字移动、比较的次数。
（3）校园导游咨询问题。
在此程序中输入正确的数据会得到正确的对应的功能，可以得到所有校园景点的代号、地名以及简介信息，最短路径以及其长度咨询。
1.3.2 错误的输入及输出结果
（1）字符串S问题。
在本题中，无错误的输入输出。所以程序也不存在有输入输出的提示。
（2）内部排序演示
在这程序中，当输入的待排序数据为非整形时，可能会使程序无法正常进行下去。比如输入6h，结过将是出现死循环。使内部排序演示失败。当在给出功能选择菜单的时候，如果输入的不是整形，也同样会出现死循环的结果。当输入其它整形数据的时候，程序会出现对应的提示，比如在菜单选择时，输入菜单中没有的选项，程序给出了提示，并要求重新选择。
（3）校园导游图
所有输入必须都是整形数字。如果输入错误，比如输入了字母，结果将是程序进入死循环。要是输入了除要求以外的整形数时，程序会给予提示，提醒你输入的数据错误，操作人员可以进行重新的选择输入，不会提供给操作人员错误的信息。
数据结构课程实训报告书
第 4 页
第2章 概要设计
2.1 设计思想
（1）用一维数组来保存输入的字符串，依然用原始的字符串保存排序后的字符串。在统计每个字符串出现的次数时，用两个一维数组分别保存每一种字符和每种字符出现的次数。
（2）用一个结构体保存数据长度，以及待排序的那10个数据。并且采用六种方法堆这10个数据进行排序（数据的个数可以通过对main()函数中m.length进行修改。其它地方不用修改即可。程序提供给操作人员一个自我选择的空间，可自由选择自己想要的对应功能。
（3）用一个结构体保存校园景点总数和各景点的代号、地名以及简介信息。本程序采用了读取（. txt）文件的方式进行数据信息的输入，使我们在修改这些信息的时候更方便、快捷。而且本程序还使用了较多的函数实现相应的功能。很程序更简洁。
2.2 函数间的关系
（1）字符串S问题中，程序的流程关系，如下图所示：
数据结构课程实训报告书
第 5 页 （2）内部排序演示的流程图；
（3）校园导游咨询流程图；
主函数main（）
选择
程序终止 4 退出 1
景点信息查询
2
最短路径查询
3
输出所有景点 数据结构课程实训报告书
第 6 页 第3章 详细设计
（完整源程序见后面附录）
3.1 字符串S问题
其的源程序各功能函数的声明及说明如下：
void play(char s[],int h)； //对输入的字符串进行统计，并输出。
3.2 内部排序演示
（1）结构体定义：
typedef struct{
int key; //数据值
}redtype;
typedef struct{
redtype r[11]; //存储数据的值；
int length; //数据的长度；
int flag; //标识符，确定大堆还小堆；
}sqlist;
（2）主要函数声明及功能描述如下：
void Bubblesort(sqlist &l)； //(1)冒泡排序并输出结果
void insert(sqlist &l)； //(2)直接插入排序并输出结果
void select(sqlist &l)； //(3)直接选择排序并输出结果
void qsort(sqlist &l,int low,int high); //(4)快速排序
int partition(sqlist &l,int low,int high);
void shell_insert(sqlist &l,int dk); //(5)希尔排序并输出结果
void shell_sort(sqlist &l);
void heapadjust(sqlist &l,int s,int m); //(6)堆排序并输出结果
void heapsort(sqlist &l);
数据结构课程实训报告书
第 7 页 3.3 校园导游咨询
（1）结构体定义
#define max 100
#define endless 5000
#define t 20 //最大顶点数
typedef char dingdian; //顶点值类型
typedef int quanzhi; //权值类型
typedef struct{
dingdian vexnum[t][20]; //顶点信息域
quanzhi matrix[t][t]; //邻接矩阵
int n,e; //图中顶点总数与边数
}graph;
typedef struct
{ int n; //总景点数
int num[M]; //景点代号
char name[t][20]; //景点名称
char info[t][500]; //景点简介
}pic; //邻接矩阵表示的图类型
（2）主要函数声明及功能描述如下：
void creat(graph *g,char *s ,int c); //建立邻接矩阵；
void creats(pic *JINGDIAN,graph *g,char *s);//读取信息并创建；
void nm(int i)； //统计、找出最短路径，并输出；
void GJ(graph g,int v0)；
int bill()； //菜单选择；
void play(int m)； //输出景点相关信息；
void find(int s)； //查找景点信息；
数据结构课程实训报告书
第 8 页 第4章调试分析
4.1测试并列出测试结果
4.1.1字符串S问题测试结果。
1、首先输入待统计的字符串，并对输入的数据进行排序
此时，输入的字符串已经按照ASCII码的顺序进行了排序。这样，我们就能直观的看出每一种字符出现的次数了。
2、输出每一种字符出现的次数。将其与上图进行比较与验证，可以看出结果是否正确。
