信息科学和工程学院课程设计报告课题:航空客运订票系统目录1.课程设计内容 (3)1.1、课程设计目的 (3)1.2、课程设计题目 (3)1.3、课程设计内容 (3)1.4、实现提示 (3)2.需求分析 (4)3.概要设计 (4)3.1、系统结构图 (5)3.2、算法设计 (5)3.3、存储结构设计 (5)4.详细设计 (6)4.1、数据类型定义 (7)4.2、函数定义 (8)4.3、函数流程图 (8)4.4、程序的设计思想 (12)5.调试分析 (12)5.1、程序测试 (12)5.2 、时间复杂度分析 (13)5.3 、算法的改进设想 (13)6.问题分析及课程设计的心得体会 (14)7.使用手册 (15)8. 源程序 (15)9 参考资料 (22)一、课程设计内容1.1 课程设计目的1．数据结构课程设计是综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C语言），自行实现一个较为完整的使用系统。
2．通过课程设计，自己通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握使用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的使用。
3．学会将知识使用于实际的方法，提高分析和解决问题的能力，增加综合能力。
（1）熟练掌握链表存储结构及其建立过程和常用操作；（2）熟练掌握队列的建立过程和常用操作；（3）学会自己调试程序的方法并掌握一定的技巧。
1.2课程设计题目1、每条航线所涉及的信息有：终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名和所需数量）。
2、系统能实现的操作和功能如下：1）查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行和余票额；2）承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余票量少余订票额，则需重新询问客户要求。
若需要，可登记排队候补；3）承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。
1.3 课程设计内容航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。
设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。
1.4 实现提示两个客户名单分别由线性表和队列实现。
为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，以链表作为存储结构。
由于预约人数无法预计，队列也用链表作为存储结构。
整个系统需汇总各条航线的情况登录在一张线性表上，由于航线不变，可采用顺序存储结构，并按航班有序或终点站名有序。
每条航线是这张表上的一个记录，包含上述8个域，其中乘员名单域为指向成员名单链表的头指针，等候替补的客户名单域为分别指向对头和队尾的指针二、需求分析本订票系统能够实现全部航线信息的浏览功能、订票客户信息的查询功能、单条航线查询功能、订票功能和退票功能。
具体分析如下：a) 全部航线信息的浏览功能浏览全部系统预设的航线信息，每条航线包含的信息有：终点站名、航班号、飞机号、飞行周日（星期几飞行）、乘员定额和余票量。
b) 订票客户信息的查询功能根据输入的航班号查询该航线所有订票客户的信息，包括客户姓名、订票数额和舱位等级。
c) 单条航线查询功能根据客户输入的终点站名查看该航线上所涉及的信息。
d) 订票功能根据客户提出的要求（航班号、订票数量）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于定票额，则询问客户是否愿意排队等候，若愿意，系统则自动登记排队候补。
e) 退票功能根据客户提供的情况（航班、姓名），询问退票张数，然后为客户办理退票手续。
接着系统自动查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。
三、概要设计3.1 系统结构图（功能模块图）3.2 算法设计（每个模块的算法设计说明):（1）浏览航线模块：定义void display( struct airline *info),用info指向结构体struct airline中的每一个成员；调用list（）函数输出全部航线信息。
（2）浏览订票客户信息模块：定义订票客户信息的结构体ord_ros,根据输入航班号调用find（）函数寻找客户信息。
（3）查询航线模块：顺着单链表查找，如果和航班号（航线）一致，输出相关信息，否则，查询不成功。
（4）订票模块：查找乘客要订的航班号，判断此航班是否有空位，有则输入乘客有关信息，订票成功, 否则失败。
（5）退票模块：输入要退票的乘客姓名，查找乘客资料的链表中是否有这位乘客，有则删去此节点，并在空位上加1，无则退票失败。
如果此时余票额大于等于候补客户的订票数量，那么候补客户订票成功。
3.3 存储结构设计：（1）航班的信息：为了便于查找，航班情况的存储结构采用单链表，每个元素表示一个航班的情况，包括终点站名、航班号、飞机号、星期几、乘员定额和余票量，共六个数据项：C语言描述如下：struct airline{ char ter_name[10];/*终点站名*/char air_num[10];/*航班号*/char plane_num[10];/*飞机号*/char day[7];/*飞行周日（星期几）*/int tkt_amt;/*乘员定额*/int tkt_sur;/*余票量*/linklist *order;/*乘员名单域，指向乘员名单链表的头指针*/linkqueue wait;/*等候替补的客户名单域，分别指向排队等候名单队头队尾的指针*/}lineinfo;struct airline *start;（2）订票乘客的资料：为了便于插入和删除，同样采用单链表存储结构，每个数据元素包括姓名、订票量和舱位等级三个数据项：C语言描述如下：typedef struct ord_ros{ char name[10];/*客户姓名*/int ord_amt;/*订票量*/int grade;/*舱位等级*/struct ord_ros *next;}linklist;四、详细设计4.1 数据类型定义（1）已订票客户的结点：typedef struct ord_ros{ char name[10];/*客户姓名*/int ord_amt;/*订票量*/int grade;/*舱位等级*/struct ord_ros *next;}linklist;（2）候补客户的结点：typedef struct wat_ros{ char name[10];/*姓名*/int req_amt;/*订票量*/struct wat_ros *next;}qnode,*qptr;typedef struct pqueue /*定义单链队列*/{ qptr front;/*等候替补客户名单域的头指针*/qptr rear;/*等候替补客户名单域的尾指针*/}linkqueue;（3）航班结点：struct airline{ char ter_name[10];/*终点站名*/char air_num[10];/*航班号*/char plane_num[10];/*飞机号*/char day[7];/*飞行周日（星期几）*/int tkt_amt;/*乘员定额*/int tkt_sur;/*余票量*/linklist *order;/*乘员名单域，指向乘员名单链表的头指针*/linkqueue wait;/*等候替补的客户名单域，分别指向排队等候名单队头队尾的指针*/}lineinfo;struct airline *start;4.2 函数定义（1）航线输出函数函数名：void list()操作结果：输出全部航线信息（2）航线查询函数函数名：void search()操作结果：进行航班查询（3）候补结点队列函数函数名：linkqueue appendqueue(linkqueue q,char name[],int amount)操作结果：增加候补客户名单域入队出队判空（4）客户订票函数函数名：void order()操作结果：进行客户订票操作（5）客户退票函数函数名：void return_tkt()操作如果：进行客户退票操作（6）订票客户查询函数函数名：void prtlink()操作结果：进行订票客户信息查询操作（7）主菜单控制函数函数名：int menu_select()操作结果：a) 浏览航线信息b) 浏览已订票客户信息c) 查询航线d) 办理订票业务e) 办理退票业务f）退出系统4.3 函数流程图（1）浏览已订票客户信息（3）办理订票业务4.4 程序的设计思想订票客户由线性表实现，链表作为其存储结构；为了插入和删除方便，候补客户由队列实现，队列也用链表做为存储结构。
增删操作只需修改指针，这样系统运行效率有了很大提高。
五．调试分析5.1程序测试（1）主菜单（2）浏览航线信息（3）办理订票业务（4）浏览已订票客户信息（5）查询航班（6）办理退票业务（7）再次浏览航线信息5.2 时间复杂度分析浏览遍历整张航线线性表的时间复杂度：O（1）；线性表的插入和删除操作的时间复杂度：O（n）；查询为线性表的查找，时间复杂度：O（n）；订票为线性表的查找，时间复杂度：O（n）；退票是查找两张线性表，时间复杂度为：O（n*e）,其中n为航班总数，e 为对应航班已订票人数。
5.3 算法的改进设想（1）在算法效率上，由于此课程设计所用的是线性表的建立、查找、插入、删除、和队列的建立、插入、删除，所涉及的是查找和排序问题，所以在建立插入时按照客户姓名进行有序，查找时采用分块查找，因此对订票客户信息的存储应采用指针数组存储。
（2）在函数重组，把处理不同问题相同算法思想（如线性表的插入、删除、查找等等）写在一个函数中，其它函数要用到这种操作时只需调用这些函数，这样会减少整个程序的代码量，方便理解、阅读和使用。
六．问题分析及课程设计的心得体会总体体会：看着简单，做着难，我自己眼高收低，心太急，不过敢想敢写感尝试，努力付出还真有蛮多收获。
(1)学和做：做了这次课程设计，我觉得课程设计这种形式真的是我们需要的，可以让我们学到很多，包括书上的、书外的。
理论永远不等于实际。
我在调试时出现了很多的问题，下面列举几个：程序中定义了一个字符串“new”,但在C-Free中“new"不是以未定义的形式存在，所以把“new”改写成“NEW”就可以了；C-Free 中“getchar”表示读取下一个字符的含义，而“getch”不表示，出现“getch”时系统会报错；在编写退票模块的代码时，设计先输入退票数然后进行退票，调试时发现舱位等级的输出出现了混乱，后来经仔细分析才知道，原来“grade=p1->grade;”放在了if()大循环的后面，而在if循环里p1已经释放，所以把“grade=p1->grade;”放在第一个“free(p1);”之前就可以了。