课程名称数据结构课程设计

1、 课程名称 数据结构课程设计 教师姓名 李桂玲 本科生姓名 张玉彬 本科生学号 20111004302 本科生专业 网络工程二班 所在院系 计算机学院 类别: 本科生论文 日期: 2012年12月28日 独立工作成果声明 本人声明所呈交的数据结构课程设计报告，是我个人在导师指导下进行的程序编制工作及取得的成果。尽我所知，除文中已经标明的引用内容，和已经标明的他人工作外，本报告未包含任何抄袭自他人的工作成果。对本报告的工作做出贡献的个人，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 报告作者签名： 日期： 年 月 日 航空管理系统 TOC o 1-3 t h z u HY

2、PERLINK l _Toc127921.需求分析： PAGEREF _Toc12792 1 HYPERLINK l _Toc297292.设计 PAGEREF _Toc29729 2 HYPERLINK l _Toc892.1设计思想 PAGEREF _Toc89 2 HYPERLINK l _Toc78192.2设计表示 PAGEREF _Toc7819 5 HYPERLINK l _Toc27103.调试分析： PAGEREF _Toc2710 16 HYPERLINK l _Toc12794.用户手册 PAGEREF _Toc1279 17 HYPERLINK l _Toc253035

3、.测试数据及测试结果 PAGEREF _Toc25303 18 HYPERLINK l _Toc20605.1测试数据 PAGEREF _Toc2060 18 HYPERLINK l _Toc108505.2测试结果 PAGEREF _Toc10850 18 HYPERLINK l _Toc253246. 参考文献 PAGEREF _Toc25324 26 PAGE 21 航空订票系统1.需求分析：试设计一个航空订票系统，基本要求如下： 每条航班所涉及的信息有：航班号，航班机型，起飞机场，降落机场，日期（星期几），起飞时间，降落时间，飞行时长，价格，乘员定额，余票量，订定票的客户名单(包括姓名

4、，订票量，舱位等级（头等舱、公务舱、经济仓）以及等候替补的客户名单（包括姓名、所需数量）。采用链式存储结构。 系统能实现的操作和功能如下：航班信息管理。航空信息录入；航班信息删除；航班信息显示 ； （2）查询航线，按以下几种方式查询：按航班号查询；按起点站查询；按终点站查询；按日期查询；每种查询方式中，查询后输出如下信息：航班号，航班机型，起飞机场，降落机场，日期（星期几），起飞时间，降落时间，飞行时长，价格，余票量。 （3）承办订票业务：根据客户提出的要求(航班号，订票数额)查询该航班票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余票少于订票额,则需重新询问客户要求。若需要

5、，可登记排队候补。 （4）承办退票业务：根据客户提出的情况(日期，航班号)，为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。2.设计2.1设计思想数据结构设计。存储结构设计：由题目所给定要求，该题需要用到链式存储结构来完成飞机信息的存取，而其后的waitingclient中需要的是按序访问，所以最好是以队列存储等候者信息完成先入先出比较。存储结构如下：class flightprivate:flightNode *head;string key;class flightNodefriend

6、 class flight;public:flightNode();string flightnum; /航班号string flightmodel; /机型string start; /起点string end; /终点string date; /日期int price3; /价格int maxnum3; /三种等级舱座位数int remaining3; /余留的各等级舱座位数int firstclassMAXFIRSTCLASS;int bussinessclassMAXBUSSINESSCLASS;int economyMAXECONOMY;int departure2; int arr

7、ival2;void printout(); void printspace();void timecheck(); /飞行时长函数。 private:int flighttime2; /飞行时长flightNode *next; orderclient *head1; waitingclient *front; waitingclient *rear;class orderclientfriend class flight;string name;int level;int seat;orderclient *next;friend class flightNode;class waitin

8、gclientfriend class flight; string name; int level; waitingclient *next; friend class flightNode;逻辑结构设计：该题所要求的是通过链式存储结构而存储的，所以该题的逻辑结构应是线性结构。算法设计。算法思想：该题是航空订票系统，有航班信息，有航班中乘客的信息，其中的存入，删除都可以通过链表中的指针从头结点开始移动来遍历，所以定义了三组结构体，第一组的flight可视为整个航空系统，其中有flightNode的指针，第二组的flightNode是航班 信息，其中有orderclient和waitingcl

9、ient指针，第三组的waitingclient、orderclient分别代表等候列表与乘客列表。 在该系统中，可分为存入航班信息、订票与退票三个模块，之间由于是对内存的改变所以所以没有接口，存入即访问flight遍历flightNode结点，在最后插入新的结点，并将航班内容存入，删除时即删除该结点，在航班信息输入时，还调用了一个timecheck函数，用来计算飞行时长。订票时，先通过访问flightNode中的flightnum来确定所选航班，再通过访问flightNode中对应等级舱的余票，若大于零则进行插入操作，将内容存orderclient中，若等于零则存入链式队列waitingcl

10、ient中进行排队操作，退票时，当该flightNode结点存有同name的人，将其orderclient中的信息删除，并访问waitingclient查找最先相同等级要求的顾客并插入到该orderclient中。主函数流程图如下：2.2设计表示函数的调用关系图如下：详细设计/航班信息的录入函数。(备注：管理员密码为123456，仅可在构造函数中更改。）void flight:record() flightNode *t,*h; t=new flightNode; cout录入航班信息：(航班号 航班机型 起点 终点 飞行日期 起飞时间 降落时间 座位及价格)t-flightnum; cint

11、-flightmodel; cint-start; cint-end; cint-date; cint-departure0; cint-departure1; cint-arrival0; cint-arrival1; cint-maxnum0t-price0t-maxnum1t-price1t-maxnum2t-price2; t-remaining0=t-maxnum0; t-remaining1=t-maxnum1; t-remaining2=t-maxnum2; for(int i=0;imaxnum0;i+)t-firstclassi=0; for( i=0;imaxnum1;i+

12、)t-bussinessclassi=0; for( i=0;imaxnum2;i+)t-economyi=0; t-timecheck(); h=head; while(h-next) h=h-next; t-next=h-next; h-next=t; cout信息录入成功。endl=0) flighttime1=(arrival1-departure1); flighttime0=(arrival0-departure0); else flighttime1=(arrival1-departure1)+60; flighttime0=(arrival0-departure0)-1; if

13、(flighttime00)flighttime0=flighttime0+24;/航班订票函数。void flight:reserve() string a; cout请输入航班号a; flightNode *curr; curr=head-next; while(航班结点不为空) if(找到该航班) int i; cout请输入要选舱位等级(头等舱请输入1，公务舱请输入2， 经济舱请输入3.i; if(i3|i1) cout无该等级舱位，请重新输入：; goto loop; orderclient *t; t=new orderclient; cout请输入姓名:t-name; if(该等

14、级舱余票不为0） t-level=i; cout购票成功。endl; cout航班号flightnum 姓名:name; coutlevel)/找到空位，并标志为有人，输出座位号。 case 1:cout头等舱; for(头等舱找到空座); 座位号存入。 该座位号标记为1 该等级余票量减1. break; case 2:cout公务舱; for( 商务舱找到空座); 座位号存入。 该座位号标记为1 该等级余票量减1. break; case 3:couthead1; while(找到已订票者链尾); a-next=t; t-next=NULL; coutseat号printspace(); /

15、航班输出界面。 curr-printout(); /航班信息输出。 return; else cout该舱位已满，是否进入候补(Y/N)?q; if(q=Y|q=y) waitingclient *p; p=new waitingclient; p-name=t-name; p-level=i; if(等候队列为空) 插入队列第一个。 队头队尾皆指向该等候者。 else 找到队尾，并该等候者信息。 waitingclient *u; /判断等候列表中同等级舱位的等候者。 u=curr-front; int m=0; while(u) if(u-level=i) m+; u=u-next; co

16、ut您前面等候者有m-1人endl; return; else return; else 飞机结点指针后移。 if(飞机结点为空)cout抱歉!没有对应的航班!endl;航空订票信息流程图如下：/航空退票系统。void flight:refund()cout请输入航班号a;flightNode *curr;curr=head-next;while(curr)if(找到航班) cout请输入姓名:b;orderclient *s;s=curr-head1;while(等候者存在)if(找到名字)coutq;if(q=Y|q=y)cout退票成功。next;waitingclient *m,*n;

17、m=curr-front;/从等候队列中选顾客。 if(队列非空) n=curr-front-next;if(curr-front-level=p-level) /队列第一个 人就满足购票条件。cout等候者front-name购 票成功。rear)/访问waitingclient 可购票人。 if(n-level=p-level) /队列末尾排除。cout等候者name购 票成功。level=p-level) /队列末尾判断。cout等候者rear-name 购票成功。level)/如果等待中无满足要求者，将 座位腾出。case 1:头等舱该座位号标记为0，头等舱余票量 加1.break;

18、case 2:商务舱该座位号标记为0，商务余票量 加1.break;case 3:经济舱该座位号标记为0，经济舱余票量 加1.break;s-next=p-next;free(p); 信息输入。输出更改后航班信息。return; else 等候者指针后移。if(s-next=NULL)cout查无此人endl;return; else 飞机结点指针后移。if(curr=NULL)cout查无此航班endl;航空退票信息流程图如下：3.调试分析：主要问题：该程序设计之中，第一个问题就是代码太长，编写量大，第二个就是指针的关系，有时由于代码太长判断条件太多而遗漏指针的后移或初始化等。解决方法：首先

19、，对这个系统先进行框架分析，留下大概的设计步骤，再在头文件中首先声明函数体，再一步步定义，而指针问题，则根据循环中的来判断指针循环的范围并小心检查，多调试，而由于编程中复合语句会有后移的区分，所以检查时在两等行的大括号下分析处理。设计编码回顾分析：这题是一次不小的考验，由于使用C+的数据结构，起初在定义各个类的指针交互上有些模糊，不过现在已经学习到了很多，受益匪浅。在编码过程中，我深刻的体会到一个程序的编写需要一个清晰的思路，否则就是在原地打转，此次在订票和退票操作上耗时较大，需要判断的条件较多，很容易出现指针未后移的问题，不过，在花费了许多时间之后得到的产物还是比较满意的，有不小的成就感，并

20、且巩固了一些相关的专业知识。算法的时间、空间复杂度分析：在该系统中，一共存在着4种函数类型，第一个是添加飞机信息，由于其中包含的第一个是查询位子是否为空，和define的座位最大数有关，为常数，其次是飞机结点指针的后移，所以时间复杂度是O(n)，空间复杂度因仅与飞机结点大小有关所以是O(1),第二个是查询，时间复杂仅与飞机结点数有关，所以为O（1），无空间利用，所以空间复杂度为O(1),第三个是订票，主要时间耗在找飞机结点上与其中的订单者指针的后移，所以时间复杂度为O（n*m），空间复杂度为O(m).第四个是退票，时间复杂度在飞机结点后移与订单者后移，所以为O(n*m),空间复杂度为O（1）。

21、4.用户手册备注:(航空订票.cpp，flight detail.cpp，flight detail.h三个文件应放在一起，特别是头文件flight detail.h不能丢，在VC上运行时应先打开主函数文件航空订票.cpp，然后再打开flight detail.cpp文件方能正确运行，然后进入系统进行功能测试及错误检测)进入该飞机订票系统后，主菜单上会出现两种身份的选择，键盘输入1是以管理员身份进入，进入前需要拥有管理员密码，输入错误则返回主菜单，进入后，可以键入1来添加航班信息，输入2来删除航班信息，输入3来查看现有航班信息，输入4返回主菜单，输入5则退出该系统，而在主菜单中输入2则是以顾客身份登录系统，拥有的主要功能有，输入1返回上级主菜单，输入2是按航班号查询，输入3是按航线起点查询，输入4是按航线终点查询，输入5是按照航线日期查询，输入6是订票，7是退票，而8则是所有航班的信息显示，9则是退出该航空订票系统。在整个系统中，如果输入的功能选项不存在，都会返回该层界面进行重新输入。5.测试数据及测试结果5.1测试数据航班号 航班机型 起点 终点 日期