航空客运订票系统数据结构课程设计报告1

信息科学和工程学院课程设计报告课题： 航空客运订票系统 目录TOC\o"1-5"\h\z\o"CurrentDocument"1・课程设计内容 31.1、 课程设计目的 31.2、 课程设计题目 31.3、 课程设计内容 3\o"CurrentDocument"1.4、 实现提示 32•需求分析 43•概要设计 43.1、 系统结构图 53.2、 算法设计 53.3、 存储结构设计 54•详细设计 64.1、 数据类型定义 74.2、 函数定义 84.3、函数流程图 84.4、程序的设计思想 125•调试分析 125.1、程序测试 12、时间复杂度分析………………13、算法的改进设想………………13问题分析及课程设计的心得体会………14使用手册 …… 158・源程序 ……・・・・・・159参考资料……………………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）退票功能根据客户提供的情况（航班、姓名），询问退票张数，然后为客户办理退票手续。接着系统自动查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。

三、 概要设计系统结构图（功能模块图）算法设计(每个模块的算法设计说明):(1)浏览航线模块：定义voiddisplay(structairline*info),用info指向结构体structairline中的每一个成员；调用list()函数输出全部航线信息。浏览订票客户信息模块：定义订票客户信息的结构体ord_ros，根据输入航班号调用find()函数寻找客户信息。(3)查询航线模块：顺着单链表查找，如果和航班号(航线)一致，输出相关信息，否则，查询不成功。(4)订票模块：查找乘客要订的航班号，判断此航班是否有空位，有则输入乘客有关信息，订票成功，否则失败。(5)退票模块：输入要退票的乘客姓名，查找乘客资料的链表中是否有这位乘客，有则删去此节点，并在空位上加1，无则退票失败。如果此时余票额大于等于候补客户的订票数量，那么候补客户订票成功。3.3存储结构设计：航班的信息：为了便于查找，航班情况的存储结构采用单链表，每个元素表示一个航班的情况，包括终点站名、航班号、飞机号、星期几、乘员定额和余票量，共六个数据项：终点站名航班号飞机号星期几乘员定额余票量单链表如下:C语言描述如下：structairline{charter_name[10];/*终点站名*/charair_num[10];/*航班号*/charplane_num[10];/*飞机号*/charday[7];/*飞行周日(星期几)*/inttkt_amt;/*乘员定额*/inttkt_sur;/*余票量*/linklist*order;/*乘员名单域，指向乘员名单链表的头指针*/linkqueuewait;/*等候替补的客户名单域，分别指向排队等候名单队头队尾的指针*/}lineinfo;structairline*start;（2）订票乘客的资料：为了便于插入和删除，同样采用单链表存储结构，每个数据元素包括姓名、订票量和舱位等级三个数据项：乘客姓名订票量余票量C语言描述如下：typedefstructord_ros{charname[10];/*客户姓名*/intord_amt;/*订票量*/intgrade;/*舱位等级*/structord_ros*next;}linklist;四、详细设计4.1数据类型定义（1） 已订票客户的结点：typedefstructord_ros{charname[10];/*客户姓名*/intord_amt;/*订票量*/intgrade;/*舱位等级*/structord_ros*next;}linklist;（2） 候补客户的结点：typedefstructwat_ros{charname[10];/*姓名*/intreq_amt;/*订票量*/structwat_ros*next;}qnode,*qptr;typedefstructpqueue/*定义单链队列*/{qptrfront;/*等候替补客户名单域的头指针*/qptrrear;/*等候替补客户名单域的尾指针*/}linkqueue;（3） 航班结点：structairline{charter_name[10];/*终点站名*/charair_num[10];/*航班号*/charplane_num[10];/*飞机号*/charday[7];/*飞行周日(星期几)*/inttkt_amt;/*乘员定额*/inttkt_sur;/*余票量*/linklist*order;/*乘员名单域，指向乘员名单链表的头指针*/linkqueuewait;/*等候替补的客户名单域，分别指向排队等候名单队头队尾的指针*/}lineinfo;structairline*start;函数定义(1)航线输出函数函数名：voidlist()操作结果：输出全部航线信息(2)航线查询函数函数名：voidsearch()操作结果：进行航班查询候补结点队列函数函数名：linkqueueappendqueue(linkqueueq,charname[],intamount)操作结果：增加候补客户名单域入队出队判空客户订票函数函数名：voidorder()操作结果：进行客户订票操作客户退票函数函数名：voidreturn_tkt()操作如果：进行客户退票操作订票客户查询函数函数名：voidprtlink()操作结果：进行订票客户信息查询操作主菜单控制函数函数名：intmenu_select()操作结果：a)浏览航线信息浏览已订票客户信息查询航线办理订票业务办理退票业务退出系统4.3函数流程图（1）浏览已订票客户信息

3）办理订票业务5）办理退票业务4.4程序的设计思想订票客户由线性表实现，链表作为其存储结构；为了插入和删除方便，候补客户由队列实现，队列也用链表做为存储结构。增删操作只需修改指针，这样系统运行效率有了很大提高。五•调试分析5.1程序测试(1)主菜单 欢迎使用航空客运订票系统 信票业业线晋票票统舫已㈱'乩系贯翥理理出浏浏查办番息信票业业线晋票票统舫已㈱'乩系贯翥理理出浏浏查办番息II..息客务务请选择幷按回车键结束:踐点站名beijingshanghailondon航班号1飞矶号B8571S1O02踐点站名beijingshanghailondon航班号1飞矶号B8571S1O02L1O03请违择并按回车键结豆汩飞行周日 乘员定额SUN 3MONFBI余票量3I户:2票级

量芈

数—位=1的盘=1?!

5-1-SII.班ts票弓号航入座座的请选择井按回车键结束冷，牛订票成功・祝您旅诛愉快!浏览已订票客户信息

士―… 请选择并按回车键结束止遠艳入砸班号注畧&姓茗订票数额舱位等级牛 2 1查询航班请选择并按回车键结束汴霸鐺■点站名喘矚飞机号飞亍周日beijing 1 请选择并按回车键结束汴霸鐺■点站名喘矚飞机号飞亍周日beijing 1 B8571SUN乘员定额3余票量1办理退票业务请选拦井按回三键结束泻:牛户请选拦井按回三键结束泻:牛户客2

票:

退量

12数

:1名••票

号姓需

棗香

人IA订人

饉番输321!t-t-AE-!功号号号退亜B蚩陛功的的7)再次浏览航线信息终点站名beijingshanghailorndon航班号12终点站名beijingshanghailorndon航班号12请二飞机号B8571S1302L丄S03择并按回玄键结束疽飞行周日 乘貝定额SUN 3MON 2FBI 1余票量Q115.2时间复杂度分析浏览遍历整张航线线性表的时间复杂度：0(1)；线性表的插入和删除操作的时间复杂度：O(n)；查询为线性表的查找，时间复杂度：O(n)；订票为线性表的查找，时间复杂度：O(n)；退票是查找两张线性表，时间复杂度为：O(n*e)，其中n为航班总数，e为对应航班已订票人数。5.3算法的改进设想在算法效率上，由于此课程设计所用的是线性表的建立、查找、插入、删除、和队列的建立、插入、删除，所涉及的是查找和排序问题，所以在建立插入时按照客户姓名进行有序，查找时采用分块查找，因此对订票客户信息的存储应采用指针数组存储。在函数重组，把处理不同问题相同算法思想(如线性表的插入、删除、查找等等)写在一个函数中，其它函数要用到这种操作时只需调用这些函数，这样会减少整个程序的代码量，方便理解、阅读和使用。六．问题分析及课程设计的心得体会总体体会：看着简单，做着难，我自己眼高收低，心太急，不过敢想敢写感尝试，努力付出还真有蛮多收获。(1)学和做：做了这次课程设计，我觉得课程设计这种形式真的是我们需要的，可以让我们学到很多，包括书上的、书外的。理论永远不等于实际。我在调试时出现了很多的问题，下面列举几个:程序中定义了一个字符串"new",但在C-Free中“new"不是以未定义的形式存在，所以把“new”改写成“NEW”就可以了；C-Free中“getchar”表示读取下一个字符的含义，而“getch”不表示，出现“getch”时系统会报错；在编写退票模块的代码时，设计先输入退票数然后进行退票，调试时发现舱位等级的输出出现了混乱，后来经仔细分析才知道，原来“grade=pl->grade;”放在了if()大循环的后面，而在f循环里pl已经释放，所以把“grade=p1->grade;”放在第一个“free(p1);”之前就可以了。真正会了这些算法，理论和实际永远差那么一点，不去做是体会不出来的。坐在电脑前才真正知道自己会不会，眼高手低是要不得的。(2)C和算法描述:在学数据结构的时候总是分不清算法和C语言的区别，总觉得算法就是程序了，通过这两周的课程设计总算是把它们之间的关系搞透彻了。其实算法是解决问题的步骤；程序是算法的代码实现；算法要依靠程序来完成功能；程序需要算法作为灵魂。两者是相互联系密不可分的。(3)小收获:摸索着做完课程设计，增强了自己的自学能力，这应该是最有用的吧，语言会过时，学习的能力却不会过时。构造结构体;定义清晰明确的各种变量；主函数、子函数的声明及定义。另外:对函数调用，参数传递很有体会。(4)遇到的问题和感受:这次课程设计面临的大问题就是——选择的余地太大，头脑不好受。连续几天的思考，我都不能决定攻克哪个，好几个都是考虑了一部分又放弃了，以至前功尽弃。这使我认识到认定干一件事就必须将它干到底，以使自己的思想连续。我也开始考虑当事情有重叠时，如何去应对，虽然最后的抉择不一定是对的。我也在这段时间内好好地看了一遍书，对书中的算法思想有一个更深的了解，虽然在使用中显得不是很自如，可我通过这次课设体验到可视化编程的乐趣。这也给我以后编程莫大的激励，因为我认为所谓算法通过老师的传授每个人都会一点点，而课外的东西则是通过自己的学习获得的。写程序是一种乐趣，特别是当我看到程序运行成功时，我会感到无比的喜悦。而数据结构是任何程序的基础，没有数据结构的支持，就没有程序的存在，至少说不会存在有价值的程序。有了数据结构的知识，再加上程序设计技术，这对以后的深入学习应该会有很大的帮助七•用户使用手册说明书本程序可以运行在c-free最新5.0版本完美运行1浏览航线信息按数字1即可查询2浏览已订票客户的信息要输入你订票客户的航班号根据提出的航班号课查询是否有订票客户的信息。如果没有则会输出“该航线没有客户信息”如果有订票客户。则会显示改客户订票信息3查询航线首先输入终点站名，如果没有该终点站，则会输出“对不起。该航线未找到！”如果有改终点站，则会输出该航线的信息4办理订票业务首先输入航班号，如果没有该航班号。则会输出“对不起，该航线未找到！"如果有该航班，则按照输入顺序。输入订票数量，订票客户，舱位等级。系统会给出你的座位号如果你订票数量大于总数，则会输出“对不起。您输入的票的数量已经超过成员定额！”如果你订票的数量大于剩余票数，那么系统会提示你是否需要排队。如果你需要，则输入排队的客户信息5办理退票业务先输入航班号，如果你输入的航班号不存在，那么系统会输出“对不起。该航线未找到！”如果你输入的航班号存在，那么系统会让你输入你退票客户的名字。如果有该客户，那么退票成功。如果没有该客户。那么系统会输出“对不起。你没有定过票”6查询剩余票数并排序系统会按航线剩余票数的多少进行排序0退出系统系统退出八．源程序#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE3/*定义航线量的最大值*/typedefstructwat_ros{charname[10];/*姓名*/intreq_amt;/*订票量*/structwat_ros*next;}qnode,*qptr;typedefstructpqueue/*定义单链队列*/{qptrfront;/*等候替补客户名单域的头指针*/qptrrear;/*等候替补客户名单域的尾指针*/}linkqueue;typedefstructord_ros{charname[10];/*客户姓名*/intord_amt;/*订票量*/intgrade;/*舱位等级*/structord_ros*next;}linklist;structairline{charter_name[10];/*终点站名*/charair_num[10];/*航班号*/charplane_num[10];/*飞机号*/charday[7];/*飞行周日(星期几)*/inttkt_amt;/*乘员定额*/inttkt_sur;/*余票量*/linklist*order;/*乘员名单域，指向乘员名单链表的头指针*/linkqueuewait;/*等候替补的客户名单域，分别指向排队等候名单队头队尾的指针*/}lineinfo;structairline*start;voiddisplay(structairline*info)/*打印每条航线的基本信息*/{printf("%8s\t%3s\t%s\t%4s\t\t%3d\t%10d\n",info->ter_name,info->air_num,info->plane_num,info->day,info->tkt_amt,info->tkt_sur);}voidlist()/*打印全部航线信息*/{structairline*info;inti=0;info=start;printf("终点站名\t航班号\t飞机号\t飞行周日\t乘员定额\t余票量\n");while(i<MAXSIZE){display(info);info++;i++;}printf("\n\n");voidsearch()/*根据客户提出的终点站名输出航线信息*/{structairline*info,*find();charname[10];inti=0;info=start;printf(“请输入终点站名:")；scanf("%s",name);while(i<MAXSIZE){if(!strcmp(name,info->ter_name))break；info++；i++；}if(i>=MAXSIZE)printf("对不起，该航线未找到!\n");else{printf("终点站名\t航班号\t飞机号\t飞行周日\t乘员定额\t余票量\n");display(info);}}structairline*find()/*根据系统提出的航班号查询并以指针形式返回*/{structairline*info;charnumber[10];inti=0;info=start;printf("请输入航班号:")；scanf("%s",number);while(i<MAXSIZE){if(!strcmp(number,info->air_num))returninfo;info++;i++;}printf("对不起，该航线末找到!\n");returnNULL;}voidprtlink()/*打印订票乘员名单域的客户名单信息*/{linklist*p;structairline*info;info=find();p=info->order;if(p!=NULL){printf(“客户姓名订票数额舱位等级\n");while(p){printf("%s\t\t%d\t%d\n",p->name,p->ord_amt,p->grade);p=p->next;}}elseprintf("该航线没有客户信息!!\n");}linklist*insertlink(linklist*head,intamount,charname[],intgrade)/*增加订票乘员名单域的客户信息*/{linklist*p1,*NEW;p1=head;NEW=(linklist*)malloc(sizeof(linklist));if(!NEW){printf("\nOutofmemory!!\n");returnNULL;}strcpy(NEW->name,name);NEW->ord_amt=amount;NEW->grade=grade;NEW->next=NULL;if(head==NULL)/*若原无订票客户信息*/{head=NEW;NEW->next=NULL;}elsehead=NEW;NEW->next=p1;returnhead;}linkqueueappendqueue(linkqueueq,charname[],intamount)/*增加排队等候的客户名单域*/{qptrNEW;NEW=(qptr)malloc(sizeof(qnode));strcpy(NEW->name,name);NEW->req_amt=amount;NEW->next=NULL;if(q.front==NULL)/*若原排队等候客户名单域为空*/q.front=NEW;elseq.rear->next=NEW;q.rear=NEW;returnq;voidorder()/*办理订票业务*/{structairline*info;intamount,grade;charname[10];info=start;if(!(info=find()))return;/*根据客户提供的航班号进行查询，如为空，退出该模块*/printf("请输入您订票的数量:")；scanf("%d",&amount);if(amount>info->tkt_amt)/*若客户订票额超过乘员定票总额，退出*/{ printf("\n对不起，您输入订票的数量已经超过乘员定额!")；return;}if(amountv=info->tkt_sur)/*若客户订票额末超过余票量，订票成功并等记信息*/{inti；printf("请输入您的姓名(订票客户)：")；scanf("%s",name)；printf("请输入％s票的舱位等级:",name);scanf("%d",&grade)；info->order=insertlink(info->order,amount,name,grade);/*在订票乘员名单域中添加客户信息*/for(i=0;ivamount;i++)/*依次输出该订票客户的座位号*/printf("%s的座位号是:％d\n",name,info->tkt_amt-info->tkt_sur+i+l);info->tkt_sur-=amount;/*该航线的余票量应减掉该客户的订票量*/printf("\n订票成功，祝您旅途愉快！\n");}else /*若满员或余票额少于订票额，询问客户是否需要进行排队等候*/{charr;printf("\n已经没有更多的票，您需要排队等候吗?(需要请按'Y',若不需要请按'N')");fflush(stdin);scanf("%c",&r);if(r=='Y'||r=='y'){printf("\n请输入您的姓名(排队订票客户)：")；scanf("%s",name);info->wait=appendqueue(info->wait,name,amount);/*在排队等候乘员名单域中添加客户信息*/printf("\n注册成功!\n");}elseprintf("\n欢迎您下次再次订购！\n");}}voidreturn_tkt()/*退票模块*/{structairline*info;qnode*t,*back,*f,*r;intgrade,num;linklist*p1,*p2,*head;charcusname[10];if(!(info=find()))return;/*调用查询函数，根据客户提供的航线进行搜索*/head=info->order;p1=head;printf("请输入你的姓名(退票客户)：")；scanf("%s",cusname);while(p1!=NULL){/*根据客户提供的姓名到订票客户名单域进行查询*/if(!strcmp(cusname,p1->name))break;p2=p1;p1=p1->next;}if(pl==NULL){printf("对不起，你没有订过票!\n");return;}/*若未找到，退出本模块*/else{/*若信息查询成功，删除订票客户名单域中的信息*/printf("您的订票量为：％d\n",p1->ord_amt);printf("请输入您的退票数量：")；scanf("%d",&num);if(p1==head){grade=p1->grade;if(p1->ord_amt==num){head=p1->next;free(p1);}else{if(p1->ord_amt>num)head->ord_amt-=num;}}else{if(p1->ord_amt==num){p2->next=p1->next;free(p1);}else{if(p1->ord_amt>num)p1->ord_amt-=num;}}info->tkt_sur+=num;printf("\n成功退票！\n");}info->order=head;/*重新将航线名单域指向订票单链表的头指针*/f=(info->wait).front;/*f指向排队等候名单队列的头结点*/r=(info->wait).rear;/*r指向排队等候名单队列的尾结点*/t=f;/*t为当前满点条件的排队候补名单域*/while(t){if(info->tkt_sur>=info->wait.front->req_amt){/*若满足条件者为头结点*/inti;info->wait.front=t->next;printf("%s订票成功！\n",t->name);for(i=0;ivt->req_amt;i++)/*输出座位号*/printf("%s的座位号是:％d\n",t->name,(info->tkt_sur)-i);info->tkt_sur-=t->req_amt;info->order=insertlink(info->order,t->req_amt,t->name,grade);/*插入至U订票客户名单链表中*/free(t);b