课程设计说明书

计算机科学与技术教研室。

2014-2015学年第1学期）

注：成绩均用百分制。总成绩=平时成绩*20%+报告成绩*40%+演示与答辩成绩*40%

设计题目：航班信息的查询与检索系统。

1、课程设计目的。

1）数据结构课程设计是综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（c++语言），自行实现一个较为完整的应用系统。

2）通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。

3）学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。

①掌握顺序存储结构及其相应的操作；

②熟练运用各种排序和查找学会自己调试程序并掌握了一定的技巧；

③通过温习旧的知识，学习新知识，并提高分析和解决问题的能力等。

2、课程设计正文。

2.1概要设计。

2.1.1 系统分析。

该设计是对飞机航班信息进行排序和查找。可按航班的航班号、起点站、终点站、起飞时间以及到达时间等信息进行查询。对于本设计，可采用排序方法对一组具有结构特征的飞机航班号进行排序，利用二分查找的方法对排好序的航班记录按航班号实现快速查找，按其他次关键字找采用最简单的顺序查找方法进行，它们用的较少。

每个航班记录包括八项，分别为：航班号、起点号、终点站、航班期、起飞时间、到达时间、机型以及票价，假设航班信息表（8条记录）如表1所示。

表1 航班信息表。

该系统主要功能包括：对航班信息进行排序和查找。

分析：1）给数组初始化，然后用c++语言对航班信息表进行相应的排序和查找；

2）排序功能：利用快速排序、冒泡排序、选择排序、希尔排序、直接插入排序和归并排序对各个关键字进行排序；

3）查找功能：利用顺序查找和二分法查找对各个关键字进行查找；

2.1.2系统结构图。

系统要实现的功能：（1）排序；（2）查找。

系统结构图如图1所示。

图1 系统结构图。

2.2详细设计。

2.2.1数据类型定义

struct hangban h[maxsize

typedef struct node radixnode;

struct node

datatype info; /数据信息。

radixnode *next;

typedef radixnode *radixlist;

2.2.2 存储结构：

1）航班的信息：为了便于查找，航班情况的存储结构采用数组格式，每个元素表示一个航班的情况，包括航班号、起始站、终点站、票价、起飞时间、到达时间、机型、班期，共八个数据项：

结构体的声明如下：

typedef struct hangban

char num[10];/航班号。

char start[10];/起始站。

char finalstop[10];/终点站。

int price;//票价。

char starttime[10];/起飞时间。

char finaltime[10];/到达时间。

char type[10];/机型。

char data[10];/班期。

}datatype;

2）其中航班号一项的格式为：

k0k1k2k3k4k5

其中k0和k1的输入值是航空公司的别称，用两个大写字母表示，后4位航班编号，可将这种航班关键字分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，除票价可以定义为数值型外，均定义为字符串型即可。

2.2.3 函数声明。

（1）复制函数

函数名：void copy(hangban h,node element)

操作结果：将node的结构体变量element中的记录复制给hangban的结构体变量h

分析：定义一个指针指向element的首地址，然后将头结点中的记录复制给h[0],用一个for循环，在每一次循环的最后让指针下移指向下一个地址，依次把记录复制给h[1],h[2],.h[maxsize-1]。

（2）选择排序函数。

函数名：void sort_num()

操作结果：对航班号进行从小到大排序。

分析：用两个for循环和一个if语句进行排序，排序的每一趟在n-i+1（i=1，2，..n-i），个记录中选取航班号最小的记录作为有序序列中第i个记录。

（3）冒泡排序函数。

函数名：void sort_starttime()

操作结果：对起飞时间进行从早到晚排序。

分析：用一个while语句，一个for语句，一个if语句进行排序，第i趟起泡排序是从第1到n-i+1个记录依次比较相邻的两个记录的起飞时间，并在“逆序”时交换相邻记录。

（4）直接插入排序。

函数名：void sort_finaltime()

操作结果：对到达时间进行从早到晚排序。

分析：运用了两个for循环和if语句进行排序，先将序列中的第i个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按到达时间非递减有序序列为止。

（5）快速排序函数。

函数名：void sort_type(int low,int high)

操作结果：对机型进行从小到大排序。

分析：先用while语句进行一趟排序，然后经过递归调用在分别对分成的两部分进行快速排序，也就是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的机型均比另一部分的机型小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。

（6）希尔排序函数。

函数名：void sort_price()

操作结果：对票价进行从小到大排序。

分析：即先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，在整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

（7）归并排序函数。

函数名：void sort_price(int，int)

操作结果：对票价进行从大到小排序。

分析：将数组中的前后相邻的两个有序序列归并为一个有序序列。

（8）二分法查找函数。

函数名：void search_num()

操作结果：对航班号进行查找。

分析：用while语句和if语句进行查找，先确定待查记录所在范围，然后逐步缩小范围直到找到或找不到该记录为止。

（9）顺序查找函数。

函数名：void search_start()

操作结果：对起始站进行查找。

分析：用一个for语句和一个if语句进行查找，从表中第一个记录开始，逐个进行记录的起始站和给定值进行比较，若某个记录的起始站和给定值比较相等，则查找成功，找到所查记录，反之，若直至最后一个记录，其起始站和给定值比较都不相等，则表明表中没有所查记录，查找不成功。

（10）航班信息表函数。

函数名：void chart_message()

操作结果：显示航班信息表。

（11）输出函数。

函数名：void output()

操作结果：输出排序后的航班信息表。

（12）主菜单函数。

函数名：int menu()

操作结果：显示总菜单：①排序，②查找，③退出。

（13）排序菜单函数。

函数名：int sort()

操作结果：显示排序关键字：①航班号，②起始时间，③到达时间，④机型，⑤票价（从小到大），⑥票价（从大到小）

（14）查找菜单函数。

函数名：int search()

操作结果：显示查找关键字：①航班号，②起始站，③终点站。

2.2.4函数流程图。

1）冒泡排序流程图如图2所示。

图2 冒泡排序流程图。

2）选择排序流程图如图3所示。

课程设计说明书

课程设计说明书

课程设计说明书

课程设计说明书

其他用户还读了