《数据结构B》课程设计报告基于飞机订票系统和全国交通模拟系统

1、数据结构b课程设计报告系 别： 计算机与电子系 专业班级： 电子0901 学生姓名： 指导教师： （课程设计时间2011年12月12至2011年12月24） 华中科技大学武昌分校课程设计报告撰写内容、格式与成绩评定一、课程设计报告的撰写内容与要求1.课程设计总结报告应包括：前言、基本原理或理论、设计计算书或实验报告、结论、图纸（框图、流程图）、参考资料等；或调查、访谈报告、调查问卷、调查提纲等。2.课程设计总结报告应书写工整，文句通顺、精炼、逻辑性强，图纸和曲线的绘制应符合规范。3.调查型课程设计应根据调查结果撰写调查报告。调查报告内容包括：题目、参加时间、地点、方式、过程、调查对象一般情况、

2、调查内容、发现的问题、调查结果和调查分析及体会等。调查报告要求语言简练、准确；叙述清楚、明白；数据、资料可靠；结论有理、有据。4.图纸应布局合理，比例恰当，线条分明，字体工整，符合国家制图标准。5.课程设计报告字数要求：理工、艺术类不少于2000字，其他专业不少于3000字。二、课程设计成绩评定1.学生的课程设计成绩由平时成绩、业务考核成绩两部分组成，均为百分制记分，其中平时成绩占总成绩的30%，业务考核成绩占70%。业务考核含设计报告（计算说明书、调查提纲、调查问卷等）、绘制的图纸、编制的软件、制作的模型、撰写的论文或问卷统计、调查分析等的完成及质量情况；平时成绩含设计表现、到课率等。2.

3、教师按学生实际成绩（百分制，含平时成绩和业务考核成绩两部分）登记并录入教务mis系统，由系统自动转化为“优秀（90100分）、良好（8089分）、中等（7079分）、及格（6069分）和不及格（60分以下）”五等。 目 录1.课程设计目的12.课程设计题目描述和要求12.1航空订票系统描述与要求12.2全国交通咨询模拟系统描述与要求：23课程设计报告内容23.1航空订票系统课程设计报告内容23.1.1设计思路23.1.2主要功能函数的设计33.1.3调试分析：33.1.4源程序代码：43.1.5运行测试123.2全国交通模拟小系统课程设计报告内容143.2.1设计思路：143.2.2主要功能函

4、数的设计：153.2.3调试分析：173.2.4参考源程序：183.2.5运行测试644总结68参考文献691.课程设计目的1) 培养自己运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。2) 培养自己独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。3) 培养自己初步的软件设计及软件测试的能力。4）培养自己分析问题，解决问题的能力。2.课程设计题目描述和要求2.1航空订票系统描述与要求【问题描述】 航空客运订票的业务活动包括；查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。【基本要求】（1）每条航线所涉及

5、的信息有：终点站名、航班名、飞机号、飞行周日（星期几）、乘员定额、余票量、已订票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、所需票量）；（2）作为示意系统，全部数据可以只放在内存中；（3）系统能实现的操作和功能如下：a.查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；b.承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可登记排队候补；c.承办退票业务：根据客户提供的情况（日期

6、、航班），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足客户的要求，则为客户办理订票手续，否则依次询问其他排队候补的客户2.2全国交通咨询模拟系统描述与要求：【问题描述】出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的旅客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优先决策的交通咨询。【基本要求】(1)提供对城市信息进行编辑(如：添加或删除)的功能。(2)城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑(增设或删除

7、)的功能。(3)提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。(4)旅途中耗费的总时间应该包括中转站的等候时间。(5)咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。3课程设计报告内容3.1航空订票系统课程设计报告内容3.1.1设计思路1）主程序伪代码：int main() 界面初始化； 输入操作命令； while（“命令” ！= “退出”） 接受命令（用户输入要实现功能）； 进入各个处理命令函数；2)主程序的流程以及各程序

8、模块之间的调用关系:退票模块航线信息列表main()函数订票模块查询客户信息初始化航线信息3.1.2主要功能函数的设计（1）显示已初始化的航线信息void display(struct airline *info);打印每条航线的基本信息（2）航班查询业务void search():根据客户提出的终点站名输出航线struct airline *find();根据系统提示的航班号查询并以指针形势返回。（3）航班订票业务void order():班里航班订票业务，根据客户提供的航班号查询，如为空，退出该模块；如客户订票数量乘员订票总量，则退出；若未超出乘员订票总量，则订票成功并登记信息。（4）航班

9、退票业务void return_tkt();办理退票业务，调用查询函数 ，根据客户提供的航线进行搜索，再根据客户的姓名到订票客户名单域进行查询，若信息查询成功，删除订票客户名单域的信息，若未找到，则退出该模块。（5）其他航班线路查询业务void oher_search();客户订票时，剩余票量不满足时，调用该函数模块，根据客户提供的航班目的地，显示出所有能到达目的地的航班。3.1.3调试分析：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析，在调试的过程中碰到了一下问题：a. 引用形参应用不当；b. 有关指针参数和操作不熟悉，通过查参考资料数据结构实验指导和同学讨论最终解决(2

10、) 算法的时空分析：基本操作时间复杂度空间复杂度menu_select()o(1)o(1)void display()o(1)o(1)void search()o(n)o(1)void order()o(n)o(n)void return_tkt()o(n)o(n)void list()o(1)o(1)void pritlink()o(n)o(1)3.1.4源程序代码：#include#include#include#include#define maxsize 15#define air_maxnum 200typedef struct wat_ros char name20;/姓名 int

11、 req_amt;/订票量 struct wat_ros *next;qnode,*qptr;typedef struct pqueue qptr front; qptr rear;linkqueue;typedef struct ord_ros char name20;/客户信息 int ord_amt;/顶票量 int grade;/舱位等级 struct ord_ros *next;linklist; struct airline char ter_name20;/终点站名 char air_num20;/航班号 char plane_num20;/飞机号 char day7;/飞行日期

12、 int tkt_amt;/乘员定额 int tkt_sur;/余票数量 linklist *order;/乘员名单域 linkqueue wait;/等候客户名单域lineinfo;struct airline *start;void display(struct airline *info)/打印航线基本信息printf(%8st%3st%6st%6st%7dt%8dn,info-ter_name,info-air_num,info-plane_num,info-day,info-tkt_amt,info-tkt_sur);void list()/打印全部航线信息 struct airli

13、ne *info; int i=0; info=start; printf( 终点站 航班号 飞机号 飞行日期 乘员定额余票额数n); while(imaxsize) display(info); info+; i+; printf(nn);void search()/根据客户提供的终点站名输出航线信息 struct airline *info,*find(); char name20; int i=0; info=start; printf(请输入终点站名:); scanf(%s,name); while(iter_name) break; info+; i+; if(i=maxsize)p

14、rintf(对不起没有航班); else printf( 终点站 航班号 飞机号 飞行日期 乘员定额余票额数n); display(info); void oher_search()/订票要求不满足时提供其他航班线路 struct airline *info,*find(); char name20; int i=0,j=0; int amount; info=start; printf(请输入终点站名:); scanf(%s,name); printf(请您输入想要订的票量:); scanf(%d,&amount); while(iter_name) printf( 终点站 航班号 飞机号

15、飞行日期 乘员定额余票额数n); display(info); info+; i+; if(i=maxsize) printf(没有航班); struct airline *find()/根据系统提供的航班号查询 struct airline *info; char number10; int i=0; info=start; printf(请输入航班班次:); scanf(%s,number); while(iair_num) return info;info+;i+; printf(对不起没有航班); return null;void prtlink()/打印订票乘员名单域的客户名单信息

16、linklist *p; struct airline *info; info=find(); p=info-order; if(p!=null) printf(客户名字 机票号 座位号n);while(p) printf(%stt%dt%dn,p-name,p-ord_amt,p-grade); p=p-next; else printf(航班没有乘客信息);linklist *insertlink(linklist *head,int amount,char name,int grade)/增加订票乘员名单域的客户信息 linklist *p1,*ne; p1=head; ne=(link

17、list*)malloc(sizeof(linklist); if(!ne) printf(钱不足!n);return null; strcpy(ne-name,name); ne-ord_amt=amount; ne-grade=grade; ne-next=null; if(head=null) head=ne;ne-next=null; else head=ne; ne-next=p1; return head;linkqueue appendqueue(linkqueue q,char name,int amount)/增加排队等候的客户名单域 qptr ne; ne=(qptr)ma

18、lloc(sizeof(qnode); strcpy(ne-name,name); ne-req_amt=amount; ne-next=null; if(q.front=null) q.front=ne; else q.rear-next=ne;q.rear=ne;return q;void order()/办理订票业务 struct airline *info; int amount,grade; char name20; info=start; if(!(info=find() return; printf(请您输入想要订的票量:); scanf(%d,&amount); if(amou

19、ntinfo-tkt_amt) printf(n对不起,您输入的票的数量已经超过乘员定额!);return; if(amounttkt_sur) int i;printf(请输入您的名字:);scanf(%s,name);printf(请订票,请付款.n您要的舱位等级);scanf(%d,&grade);info-order=insertlink(info-order,amount,name,grade);for(i=0;itkt_amt-info-tkt_sur+i+1);info-tkt_sur-=amount;printf(n 祝您旅途愉快！n); else char r; printf

20、(n没有多余的票了，您需要排队等候吗？（y/n）); r=getch(); printf(%c,r); if(r=y|r=y) printf(n请输入您的名字：); scanf(%s,name); info-wait=appendqueue(info-wait,name,amount); printf(n注册成功！n); else printf(n欢迎下次订购！n); void return_tkt()/办理退票业务 struct airline *info; qnode *t,*back,*f,*r; int grade; linklist *p1,*p2,*head; char cusna

21、me20; 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(p1=null) printf(对不起,您没有订票！n);return; else if(p1=head) head=p1-next; else p2-next=p1-next;info-tkt_sur+=p1-ord_amt;grade=p1-grade;printf(%s

22、 退票成功!n,p1-name);free(p1); info-order=head; f=(info-wait).front; r=(info-wait).rear; t=f; while(t) if(info-tkt_sur=info-wait.front-req_amt) int i; info-wait.front=t-next; printf(%s 购票成功!n,t-name); for(i=0;ireq_amt;i+) printf(%s 的座位号是：%dn,t-name,(info-tkt_sur)-i); info-tkt_sur-=t-req_amt; info-order=

23、insertlink(info-order,t-req_amt,t-name,grade); free(t); break;back=t;t=t-next;if(info-tkt_sur)=(t-req_amt)&t!=null) int i; back-next=t-next; printf(% 订票成功！n,t-name); for(i=0;ireq_amt;i+) printf(的座位号是：%dn,t-name,(info-tkt_sur)-i); info-tkt_sur-=t-req_amt; info-order=insertlink(info-order,t-req_amt,t-

24、name,grade); free(t); break; if(f=r)break; int menu_select()/菜单界面 int c; char s20;printf(*n); printf(* 欢迎进入武汉航空旅客服务系统 *n);printf(* 1.显示航班信息 *n);printf(* 2.打印订票乘客信息 *n);printf(* 3.航班查询业务 *n);printf(* 4.航班订票业务 *n);printf(* 5.航班退票业务 *n); printf(* 6.其他航班路线情况 *n);printf(* 7.退出系统 *n);printf(*);printf(*);

25、do printf( 请选择您需要的业务:); scanf(%s,s); c=atoi(s); while(c7); return c;int main(void) printf(*n); printf(* 制作信息简介 *n); printf(* 学院：计算机与电子系 *n); printf(* 专业：电子科学与技术 *n); printf(* 班级：电子 *n); printf(* 姓名：高傲 *n); printf(* 学号： *n); printf(* 指导老师：徐琴 *n); printf(* 未完待续. *n); printf(*n); printf(*n); printf(请按任

26、何键以继续); getchar(); struct airline airmaxsize= beijing,1,b8571,sun,air_maxnum,air_maxnum, tianjing,2,s4652,mon,air_maxnum,air_maxnum, nanjing,3,h8600,tus,air_maxnum,air_maxnum, shanghai,4,t5201,wes,air_maxnum,air_maxnum, hongkong,5,b1314,fri,air_maxnum,air_maxnum, beijing,6,k2930,sun,air_maxnum,air_m

27、axnum, londou,7,b8478,sat,air_maxnum,air_maxnum, englang,8,t4782,fir,air_maxnum,air_maxnum, london,9,k4717,sun,air_maxnum,air_maxnum, xiamen,10,b2787,wes,air_maxnum,air_maxnum, guangzhou,11,b5300,sat,air_maxnum,air_maxnum, shanghai,12,n9768,tus,air_maxnum,air_maxnum, hongkong,13,b6547,fri,air_maxnum

28、,air_maxnum, tanwan,14,k4727,sun,air_maxnum,air_maxnum, englang,15,w4712,fir,air_maxnum,air_maxnum,; system(cls); start=air; for(;) switch(menu_select() case 1:system(cls);list();break; case 2:system(cls);prtlink();break; case 3:system(cls);search();break; case 4:system(cls);order();break; case 5:sy

29、stem(cls);return_tkt();break; case 6:system(cls);oher_search();break; case 7:printf(n欢迎再次进入系统，再见！n); exit(0); printf(n 请按任意键继续！n); getch(); return(0);3.1.5运行测试1）制作信息界面2)界面显示3）航班信息显示4）订票流程界面5）订票客户信息6）航班查询业务7）退票业务8）票量不足时排队注册界面9）票量不满足时其他航线查询3.2全国交通模拟小系统课程设计报告内容 3.2.1设计思路：主程序的流程以及各程序模块之间的调用关系：退出显示交通系统pr

30、intgraph用户咨询userdemand管理员管理administer主函数main（） 返回上一级菜单列车车次编辑administer飞机航班编辑administer城市编辑cityedit管理员管理administer初始化交通系统initgraph返回上一级菜单最少中转次数transferdispose最少旅行时间timedispose用户咨询userdemand最少旅行费用expendituredisposeuserdemand显示城市显示飞机航班显示列车车次返回上一级菜单显示交通系统printgraph删除城市新增城市城市编辑cityedit删除航班新增航班飞机航班编辑plane

31、edit删除车次新增车次火车列次编辑trainedit3.2.2主要功能函数的设计：1)void administer(algraph *g);管理员模式2)void cityedit(algraph *g);城市编辑3)void copytimetree(timetree p,timetree q);航班列车时间编辑4)void createcityfile();创建城市信息文件5)void creategraph(algraph *g);建立全国交通图6)void createplanefile();创建航班信息文件7)voidcreatetimetree(timetreep,inti,i

32、nt j,linkqueue *q,infolist (*arcs)max_vertex_num);时间编辑8)void createtrainfile();创建列车信息文件,9)int deleteplanearc(algraph *g);删除航班信息10)void deletequeue(linkqueue *q,int *x);队列存储方式删除11)int deletetrainarc(algraph *g);删除列车车次12)void deletevertex(algraph *g);图中删除节点信息13)void demanddispose(int n,algraph g); 交通咨

33、询14)void destorytimetree(timetree p);删除时间信息15)void enterplanearc(algraph *g);增加航班信息16)void enterqueue(linkqueue *q,int x);队列存储方式增加17)void entertrainarc(algraph *g);增加图中列车节点18)void entervertex(algraph *g); 增加图中航班节点19)voidexpendituredispose(intk,infolist(*arcs)max_vertex_num,algraph g,int v0,int v1,fl

34、oat *m,int *final);旅行花费,根据目的地计算旅程所需总的费用。20)void flightedit(algraph *g);图中航班节点信息编辑21)void initgraph(algraph *g);初始化交通系统（图）22)void initqueue(linkqueue *q); 初始化交通系统（单链表）23)int isempty(linkqueue *q);判队空24)int locatevertex(algraph *g,char *v);25)void minexpenditure(infolist arcs,float *expenditure,int *r

35、oute);根据提供的路径计算最小花费。26)void mintime(infolist arcs,int *time,int *route); 根据提供的路径计算最少耗时。27)void printgraph(algraph *g);显示交通系统28)int save(algraph *g);保存图中的节点信息29)void timedispose(int k,infolist (*arcs)max_vertex_num,algraph g,int v0,int v1,int (*t)2,int *final);中转时间（图）30)void timetreedispose(node *hea

36、d,infolist (*arcs)max_vertex_num);根据算法计算最少中转时间31void trainedit(algraph *g);图中列车节点信息编辑32)void transferdispose(int k,infolist (*arcs)max_vertex_num,algraph g,int v0,int v1);最少中转次数模块函数33)void userdemand(algraph g);用户模式34)void visittimetree(timetree p);3.2.3调试分析： 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析，在调试的过程中

37、碰到了一下问题：a. 引用形参应用不当；b. 文件操作中遇到读入错误或找不到文件；解决方案：a. 对引用形参了解的不是很透彻，导致错误，通过查阅相关书籍如数据结构c语言版和请教编程能力较高的人，最终解决问题。b. 通过参考谭浩强编著的c程序设计中的文件操作，文件格式和相关文件路径的设置，最终解决问题。 算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想：基本操作时间复杂度空间复杂度void administer(algraph *g)o(1)o(1)void cityedit(algraph *g)o(n)o(n)void copytimetree(timetre

38、e p,timetree q)o(n)o(1)void createcityfile()o(n)o(n)void creategraph(algraph *g)o(n)o(n)void createplanefile()o(1)o(1)void createtimetree(timetree p,int i,int j,linkqueue *q,infolist (*arcs)max_vertex_num)o(n)o(n)void createtrainfile()o(1)o(1)int deleteplanearc(algraph *g)o(n)o(n)void deletequeue(li

39、nkqueue *q,int *x)o(1)o(1)int deletetrainarc(algraph *g)o(n)o(n)void deletevertex(algraph *g)o(n)o(n)void demanddispose(int n,algraph g)o(1)o(1)void destorytimetree(timetree p)o(n)o(1)void enterplanearc(algraph *g)o(n)o(n)void enterqueue(linkqueue *q,int x)o(1)o(1)void entertrainarc(algraph *g)o(1)o

40、(1)void entervertex(algraph *g)o(n)o(n)voidexpendituredispose(intk,infolist (*arcs)max_vertex_num,algraphg,int v0,int v1,float *m,int *final)o(n)o(1)void flightedit(algraph *g)o(1)o(1)void initgraph(algraph *g)o(1)o(n)void initqueue(linkqueue *q)o(1)o(1)int isempty(linkqueue *q)o(1)o(1)int locatever

41、tex(algraph *g,char *v)o(n)o(1)void minexpenditure(infolist arcs,float *expenditure,int *route)o(n)o(n)void mintime(infolist arcs,int *time,int *route)o(n)o(n)void printgraph(algraph *g)o(1)o(n)int save(algraph *g)o(1)o(1)void timedispose(int k,infolist (*arcs)max_vertex_num,algraph g,int v0,int v1,

42、int (*t)2,int *final)o(n)o(n)void timetreedispose(node *head,infolist (*arcs)max_vertex_num)o(n)o(n)void trainedit(algraph *g)o(1)o(1)void transferdispose(int k,infolist (*arcs)max_vertex_num,algraph g,int v0,int v1)o(n)o(n)void userdemand(algraph g)o(1)o(1)void visittimetree(timetree p)o(n)o(n)3.2.

43、4参考源程序：#define max_vertex_num 18#define null 0#define max_arc_size 100#define max_route_num 5#include#include#include#include#define false 0#define true 1#define infinity 10000typedef structint number;/编号float expenditure;/花费 int begintime2;/起始时间 int arrivetime2;/到达时间vehide;typedef structvehide stat

44、amax_route_num;/开始城市 int last;infolist;typedef struct arcnodeint adjvex;struct arcnode *nextarc; infolist info;arcnode;typedef struct vnode/城市信息编辑char cityname10;/城市名称arcnode *planefirstarc,*trainfirstarc;/到达城市的飞机线路，列车线路vnode,adjlistmax_vertex_num;typedef structadjlist vertices; int vexnum,planearcn

45、um,trainarcnum;/列车车次，航班号algraph;typedef struct nodeint adjvex; int route;/线路 struct node *next;node;typedef struct qnodeint adjvex; struct qnode *next;qnode;typedef structqnode *front; qnode *rear;linkqueue;typedef struct timenode/起始，到达时间编辑int adjvex; int route;/线路 int begintime2;/起始时间 int arrivetime2;/到