1、数据结构c语言课设报告航空客运订票系统 沈阳 理 工 大 学 课 程 设 计 数据结构课程设 航班客运订票系 信息工程与自动化学 通信工102专业班 201210404225 指导教 2015年12月30日 一、设计任务与要求 . 1 1.1课程设计目的. 1 1.2课程设计题目. 1 1.3课程设计内容. 1 1.4 实现提示. 1 二、需求分析 . 2 三、概要设计 . 2 3.1系统结构图 . 2 3.2 算法设计 . 4 3.3 存储结构设计 . 4 四、详细设计 . 6 4.1 数据类型定义. 6 4.2 函数定义. 7 4.3 函数流程图. 7 4.4 程序的设计思想. 12 调试
2、分析 . 12五、 5.1 程序测试. 12 5.2 时间复杂度分析. 13 5.3 算法的改进设想. 13 问题分析及课程设计的心得体会 . 14六、 源程序 . 15七、 一、设计任务与要求 1.1 课程设计目的 1数据结构课程设计是综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C语言），自行实现一个较为完整的应用系统。 2通过课程设计，自己通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。 3 学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。 （1）熟练掌握链表存
3、储结构及其建立过程和常用操作； （2）熟练掌握队列的建立过程和常用操作； （3）学会自己调试程序的方法并掌握一定的技巧。 1.2课程设计题目 1、 每条航线所涉及的信息有：终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名和所需数量）。 2、 系统能实现的操作和功能如下： 1） 查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行和余票额； 2） 承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余
4、票量少余订票额，则需重新询问客户要求。若需要，可登记排队候补； 3） 承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。 1.3 课程设计内容 航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。 1.4 实现提示 两个客户名单分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，以链表作为存储结构。由于预约人数无法预计，队列也用链
5、表作为存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线不变，可采用顺序存储结构，并按航班有序或终点站名有序。每条航线是这张表上的一个记录，包含上述8个域，其中乘员名单- 1 - 域为指向成员名单链表的头指针，等候替补的客户名单域为分别指向对头和队尾的指针。 二、需求分析 本订票系统能够实现全部航线信息的浏览功能、订票客户信息的查询功能、单条航线查询功能、订票功能和退票功能 。 具体分析如下： a) 全部航线信息的浏览功能 浏览全部系统预设的航线信息，每条航线包含的信息有：终点站名、航班号、飞机号、飞行周日（星期几飞行）、乘员定额和余票量。 b) 订票客户信息的查询功能 根据输
6、入的航班号查询该航线所有订票客户的信息，包括客户姓名、订票数额和舱位等级。 c) 单条航线查询功能 根据客户输入的终点站名查看该航线上所涉及的信息。 d) 订票功能 根据客户提出的要求（航班号、订票数量）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于定票额，则询问客户是否愿意排队等候，若愿意，系统则自动登记排队候补。 e) 退票功能 根据客户提供的情况（航班、姓名），询问退票张数，然后为客户办理退票手续。接着系统自动查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。 三、概要
7、设计 3.1 系统结构图（功能模块图） - 2 - 航空订票系统 办 理 退 票 业 务 查 办 询 理 航 订线 票 业 务 浏 览 航 线 信 息 浏 览 订 票 客 户 信 息 退 出 系 统 图3-1航空订票系统系统结构图- 3 - 3.2 算法设计（每个模块的算法设计说明) （1） 浏览航线模块： 定义void display( struct airline *info),用info指向结构体struct airline中的每一个成员；调用list（）函数输出全部航线信息。 （2） 浏览订票客户信息模块： 定义订票客户信息的结构体ord_ros,根据输入航班号调用find（）函数寻找
8、客户信息。 （3） 查询航线模块： 顺着单链表查找，如果与航班号（航线）一致，输出相关信息，否则，查询不成功。 （4） 订票模块： 查找乘客要订的航班号，判断此航班是否有空位，有则输入乘客有关信息，订票成功, 否则失败。 （5） 退票模块： 输入要退票的乘客姓名，查找乘客资料的链表中是否有这位乘客，有则删去此节点，并在空位上加1，无则退票失败。如果此时余票额大于等于候补客户的订票数量，那么候补客户订票成功。 3.3 存储结构设计 （1） 航班的信息：为了便于查找，航班情况的存储结构采用单链表，每个元素表示一个航班的情况，包括终点站名、航班号、飞机号、星期几、乘员定额和余票量，共六个数据项： 终
9、点站名 航班号 飞机号 星期几 乘员定额 余票量 单链表如下： h D1 D2 D3 每个节点包含数据域和指针域： 数据域 指针域 图3-2 航班的存储结构 C语言描述如下： - 4 - struct airline char ter_name10;/*终点站名 */ char air_num10;/*航班号*/ char plane_num10;/*飞机号*/ char day7;/*飞行周日（星期几）*/ int tkt_amt;/*乘员定额*/ int tkt_sur;/*余票量*/ linklist *order;/*乘员名单域，指向乘员名单链表的头指针*/ linkqueue wai
10、t;/*等候替补的客户名单域，分别指向排队等候名单队头队尾的指针*/ lineinfo; struct airline *start; 订票乘客的资料：为了便于插入和删除，同样采用单链表存储结构，每个）2（ 数据元素包括姓名、订票量和舱位等级三个数据项： 余票量 乘客姓名 订票量 Ptr Ptr Ptr Ptr 图3-3订票结点的创建 C语言描述如下： typedef struct ord_ros char name10;/*客户姓名*/ int ord_amt;/*订票量*/ int grade;/*舱位等级*/ struct ord_ros *next; linklist; - 5 - 起
11、飞城 市航班信息结点（ 抵达城市 Airplane时起飞间 ）抵达时间 航班号 票价 剩余票量 票信订息的指 针*ptr 指身自 针*next *next 自身指针身份证号 设置的密码 订票数量客户姓名 message）订票信息结点（ 3-4结点类型图 四、详细设计 数据类型定义4.1 ）已订票客户的结点：（ 1typedef struct ord_ros */ 客户姓名 char name10;/*/ 订票量 int ord_amt;/*/ 舱位等级 int grade;/* struct ord_ros *next; linklist; （ 2）候补客户的结点：typedef struct
12、 wat_ros */ char name10;/*姓名 */ int req_amt;/*订票量 struct wat_ros *next; qnode,*qptr; */ /*定义单链队列typedef struct pqueue */ qptr front;/*等候替补客户名单域的头指针 */ 等候替补客户名单域的尾指针 qptr rear;/*linkqueue; ）航班结点： （3struct airline */ char ter_name10;/*终点站名 */ char air_num10;/*航班号 */ 飞机号 char plane_num10;/* */ char day
13、7;/*飞行周日（星期几） */ 乘员定额 int tkt_amt;/*/ int tkt_sur;/* 余票量- 6 - linklist *order;/*乘员名单域，指向乘员名单链表的头指针*/ linkqueue wait;/*等候替补的客户名单域，分别指向排队等候名单队头队尾的指针*/ lineinfo; struct airline *start; 4.2 函数定义 （1）航线输出函数 函数名：void list() 操作结果：输出全部航线信息 （2）航线查询函数 函数名：void search() 操作结果：进行航班查询 （3）候补结点队列函数 函数名：linkqueue app
14、endqueue(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
15、.3 函数流程图 - 7 - （1）浏览已订票客户信息 输入航班 调fin（）函 N =NULL Y 有输出客户信客户信! 结 - 8 - 查询航线 (2 ) 输入终点站名 iter _name) Y 调用i+ info+， i=MAXSIZE N display(info)函数输出 该航线 未找到 结束 - 9 - （3）办理订票业务 开始 N N 初始化 info=find() 客户订票额不超过乘员定额 Y Y 客户登记信息 在排队等候乘员名单 域中添加客户信息 加到客户名单域（info-order=insertlink(info-order,amount,name,grade);） 结束
16、 - 10 - （4）办理退票业务 开始 N N 退票成功，删除客户信息 重新将航线名单域指向订票单链 表的头指针， 队列的尾结点， 单队列的头结点， N 输入航班号 是否找到输入姓名 Y 是否找到 Y 输入退票张数 r指向排队等候名单f指向排队等候名t=f 满足条件者为头结点 Y t不为空 将客户信息插到订票 客户名单链表 将客户信息插到订票客户名单链表中- 11 - 结束 4.4 程序的设计思想 订票客户由线性表实现，链表作为其存储结构；为了插入和删除方便，候补客户由队列实现，队列也用链表做为存储结构。增删操作只需修改指针，这样系统运行效率有了很大提高。 五调试分析 5.1程序测试 （1）
17、主菜单 ）浏览航线信息（2 办理订票业务）3（ - 12 - （4）浏览已订票客户信息 （5）查询航班 （6）办理退票业务 ）再次浏览航线信息7（ 时间复杂度分析5.2 ）1； 浏览遍历整张航线线性表的时间复杂度：O（ ）；线性表的插入和删除操作的时间复杂度：O（n ；（n） 查询为线性表的查找，时间复杂度：O ）；n 订票为线性表的查找，时间复杂度：O（ 为航班总数，）O（n*e,其中ne 退票是查找两张线性表，时间复杂度为： 为对应航班已订票人数。 算法的改进设想5.3 ）在算法效率上，由于此课程设计所用的是线性表的建立、查找、插入、1（ 删除、和队列的建立、插入、删除，所涉及的是查找和排
18、序问题，所以在建立插- 13 - 入时按照客户姓名进行有序，查找时采用分块查找，因此对订票客户信息的存储应采用指针数组存储。 （2）在函数重组，把处理不同问题相同算法思想（如线性表的插入、删除、查找等等）写在一个函数中，其它函数要用到这种操作时只需调用这些函数，这样会减少整个程序的代码量，方便理解、阅读和使用。 六问题分析及课程设计的心得体会 总体体会： 看着简单，做着难，不过尝试，努力付出还真有蛮多收获。 (1)学与做： 做了这次课程设计，我觉得课程设计这种形式真的是我们需要的，可以让我们学到很多，包括书上的、书外的。理论永远不等于实际。 我在调试时出现了很多的问题，下面列举几个：程序中定义
19、了一个字符串“new”,但在C-Free中“敮屷不是以未定义的形式存在，所以把“new”改写成“NEW”就可以了；C-Free中“getchar”表示读取下一个字符的含义，而“getch”不表示，出现“getch”时系统会报错；在编写退票模块的代码时，设计先输入退票数然后进行退票，调试时发现舱位等级的输出出现了混乱，后来经仔细分析才知道，原来“grade=p1-grade;”放在了if()大循环的后面，而在if循环里p1已经释放，所以把“grade=p1-grade;”放在第一个“free(p1);”之前就可以了。真正会了这些算法，理论和实际永远 差那么一点，不去做是体会不出来的。坐在电脑前才
20、真正知道自己会不会，眼高手低是要不得的。 (2)C与算法描述： 在学数据结构的时候总是分不清算法与C语言的区别，总觉得算法就是程序了，通过这两周的课程设计总算是把它们之间的关系搞透彻了。其实算法是解决问题的步骤；程序是算法的代码实现；算法要依靠程序来完成功能；程序需要算法作为灵魂。两者是相互联系密不可分的。 (3)小收获： 摸索着做完课程设计，增强了自己的自学能力，这应该是最有用的吧，语言会过时，学习的能力却不会过时。构造结构体;定义清晰明确的各种变量；主函数、子函数的声明及定义。另外：对函数调用，参数传递很有体会。 (4)遇到的问题与感受： 这次课程设计面临的大问题就是选择的余地太大，头脑不
21、好受。连续几天的思考，我都不能决定攻克哪个，好几个都是考虑了一部分又放弃了，以至前功尽弃。这使我认识到认定干一件事就必须将它干到底，以使自己的思想连续。我也开始考虑当事情有重叠时，如何去应对，虽然最后的抉择不一定是对的。我也在这段时间内好好地看了一遍书，对书中的算法思想有一个更深的了解，虽然在应用中显得不是很自如，可我通过这次课设体验到可视化编程的乐趣。这也给我以后编程莫大的激励，因为我认为所谓算法通过老师的传授每个人都会一点点，而课外的东西则是通过自己的学习获得的。写程序是一种乐趣，特别是当我看到程序运行成功时，我会感到无比的喜悦。而数据结构是任何程序的基础，没有数据结构的支持，就没有程序的
22、存在，至少说不会存在有- 14 - 价值的程序。有了数据结构的知识，再加上程序设计技术，这对以后的深入学习应该会有很大的帮助 七源程序 #include #include #include #define MAXSIZE 3 /*定义航线量的最大值*/ typedef struct wat_ros char name10;/*姓名*/ int req_amt;/*订票量*/ struct wat_ros *next; qnode,*qptr; typedef struct pqueue /*定义单链队列*/ qptr front;/*等候替补客户名单域的头指针*/ qptr rear;/*等候替补客户名单域的尾指针*/ linkqueue; typedef struct ord_ros char name10;/*客户姓名*/ int ord_amt;/*订票量*/ int grade;/*舱位等级*/ struct ord_ros *next; linklist; struct airline char ter_name10;/*终点站名 */ char air_num10;/*航班号*/ char plane_num10;/*飞机号*/ char day7;/*飞行周日（星期几）*/ int tkt_amt;/*乘员
