数据结构试验报告

1、 3.航空订票系统：1.需求分析：（1）、可以实现航班信息的管理，包括查看航班信息，修改航班信息，删除航班信息；（2）、可以查询查询航班信息，实现按起点站查询，按终点站查询，按日期查询功能；（3）、实现订票业务，若有余票，则订购余票，若余票不够，问是否加入排队等待候列；（4）、实现退票业务，退票后，要查询在排队等待的人，看退票和原来余票量是否满足客户的要求。2.设计2.1：设计思想 （1）、数据结构设计a、由于每趟航班的信息量比较大，则需要定义一个结构体表示航班的基本信息，航班的基本信息采用链表存储，以便于查询和修改航班信息；b、至于座位等级，用一个二维数组保存座位号，第一维表示座位等级，第二

2、维表示座位号；每当座位被定时，把这个等级的座位号标记为1，表示座位状态为已定。当有客户退票时，座位号的标记又变为0，表示状态为未定；c、用一个链表来存储已经订票的客户的信息，必要的时候可以查看已定客户的信息；d、再用一个队列来保存等待的客户的信息，当有人退票时，需要查看在等待的用户是否能够订票。（2）、算法设计 这个程序中没有用到特别的什么算法，主要是对链表和队列操作。2.2、设计表示 （1）、函数调用关系 main（）>Menuselect( )(输出菜单的函数) 选择1：>manage( )(管理航班信息) 选择1：>store( )（存储航班信息) 选择2：>De

3、lete( ) (删除航班信息) 选择3：>revise( ) (修改航班信息) 选择4：>check() (查看当前航班信息)>display（）(输出航班信息) 选择2：>find( )(查找航班信息) 选择1：>FindInPlaneNumber()（按航班号查询） 选择2：>FindInStartPoint()（按起点查询） 选择3：>FindInEndPoint()（按终点站查询） 选择4：>FindInDate()（按日期查询） 选择3：>Ordertickets()（订票函数） >WaitForMore（）（排队等候）

4、选择4：>Returntickets()（退票函数） 选择1：>WaitedReturn（）（加入过等待用户的退票） 选择2：>UnwaitedReturn（）（没有加入过顶戴用户的订票） （2）、函数接口规格说明 void ListInitiate()/初始化各个指针void display(airline *find)/输出航班信息函数void store()/存取航班信息void Delete()/删除航班信息void rivise()/修改航班信息void check()/查询航班信息void Manage()/管理航班系统的函数struct airline *Fin

5、dInPlaneNumber()/按航班号查询void FindInStartPoint()/按起点站查询void FindInEndPoint()/按终点站查询void FindInDate()/按日期查询void find()/查询函数void WaitForMore(char number,int amount,int grade,char name,airline *p)/等待更多票的用户void Ordertickets()/订票函数void WaitedReturn(char name)/等待过的用户退票void UnwaitedReturn(char name)/没有等待过的用户

6、退票void Returntickets()/退票函数int Menuselect()/显示菜单界面的函数void main()/主函数3调试分析 1、关于参数传递的问题：由于之前学习的c语言中关于参数传递的部分没有学扎实，在传递数组的时候，出现了错误，后来在同学的帮助下，学会了正确的传递参数的方法。 2、关于座位号有没有被定得问题：开始的时候，直接用加减法来计算座位订购情况，发现在当前边的作为被退的时候，不能正确的输出座位号，后来苦思冥想，想出了用标记的方法来区分座位是否被订购。 3.关于判断等候的人是否可以订票的问题：开始的时候，没有加循环，导致如果第一个等候的人不能订票，后边的人都不能订

7、票，后来在老师的提示下，加入了一个循环，解决了这个问题。 4、改进思想：可以再增加部分退票的功能，其实也不难，就是让顾客输入要退票的座位号，然后，把这些作为好的标志修改一下。 5、经验体会：通过这个程序的实习，完全掌握了对链表和队列的的应运，同时又加深了程序模块化的思想。 6、时间复杂度和空间复杂度：本程序的时间复杂度和空间复杂度都为O（n）。4、用户手册 1、程序运行后，首先显示的是主菜单界面； 2、用户可进行选择操作； 3、存取航班是需要按提示的顺序输入航班的信息；删除航班时要输入航班号；修改航班时也是要重新输入航班信息； 4、查询航班时：按每种方式查询，都需要按照提示输入对应的信息； 5

8、、订票时需要按照提示输入航班号，订票量，舱位等级和姓名 6、退票时也需要输入姓名和有没有加入过排队等候的队列。5、测试数据及测试结果6、源程序清单#include <iostream>#include <string.h>#include <conio.h>using namespace std;#define MAXSIZE 20typedef struct waitchar PlaneNumber10;/航班号char name10;/姓名int NeedNumber;/总订票量 int WaitNumber;/等待订票量 int grade;/舱位等级

9、char OrderedNumber350;/保存已经订票的座位号int OrderNumber;/已经订票量 struct wait *next;qnode,*qptr;struct wait *begin;typedef struct pqueue qptr front;/等候替补客户名单域的头指针 qptr rear;/等候替补客户名单域的属指针linkqueue;typedef struct orderchar PlaneNumber10;/已定票的航班号char name10;/客户姓名 int Ordernumber;/订票量 int grade;/舱位等级 int sitsnum

10、ber350;/保存已定座位号 order *next;linklist; struct order *start;typedef struct airlinechar PlaneNumber10;char PlaneType10;char StartPoint10;char EndPoint10;char Date10;char StartTime10;char EndTime10;int FlyTime;int GradePrice3;int SitsNumber3;/int LeftNumber3; int target3100;/标记已经订过的座位号为1struct airline *

11、next;linklist *order; /指向乘员名单链表的头指针linkqueue wait; /指向等候域的头指针SLNode;struct airline *head;void ListInitiate()head=(SLNode *)malloc(sizeof(SLNode);start=(linklist *)malloc(sizeof(linklist);begin=(qnode *)malloc(sizeof(qnode);head->next=NULL;start->next=NULL;begin->next=NULL;void display(airli

12、ne *find)/输出航班信息函数int i;cout<<"航 航 起 降 日 起 降 飞 三个等 三个等 "<<endl; cout<<"班 班 飞 落 飞 落 行 级舱位 级的乘 "<<endl; cout<<" 机 机 机 时 时 时 的价格 员定额 "<<endl; cout<<"号 型 场 场 期 间 间 长 分别为 分别为 "<<endl;cout<<find->PlaneNumber&l

13、t;<" "<<find->PlaneType<<" "<<find->StartPoint<<" "<<find->EndPoint<<" "<<find->Date<<" "<<find->StartTime<<" "<<find->EndTime<<" "<&l

14、t;find->FlyTime<<" "<<find->GradePrice0<<","<<find->GradePrice1<<","<<find->GradePrice2<<" "<<find->SitsNumber0<<","<<find->SitsNumber1<<","<<find->

15、;SitsNumber2<<" "<<endl;cout<<"头等舱的座位号是：1-"<<find->SitsNumber0<<endl;cout<<"头等舱剩余票座位号是："<<endl;for(i=0;i<find->SitsNumber0;i+)if(find->target0i=0)cout<<i+1<<" "cout<<endl;cout<<"

16、;公务舱的座位号是："<<find->SitsNumber0<<"-"<<find->SitsNumber0+find->SitsNumber1<<endl;cout<<"公务舱剩余票座位号是："<<endl;for(i=find->SitsNumber0;i<(find->SitsNumber0+find->SitsNumber1);i+)if(find->target1i=0)cout<<i+1<<

17、" "cout<<endl;cout<<"经济舱的座位号是："<<find->SitsNumber0+find->SitsNumber1<<"-"<<find->SitsNumber0+find->SitsNumber1+find->SitsNumber2<<endl;cout<<"经济舱剩余票座位号是："<<endl;for(i=find->SitsNumber0+find->

18、SitsNumber1;i<find->SitsNumber0+find->SitsNumber1+find->SitsNumber2;i+)if(find->target2i=0)cout<<i+1<<" "cout<<endl<<endl;void manageselect() cout<<"*"<<endl;cout<<"1.存取航班"<<endl<<"2.删除航班"<

19、;<endl<<"3.修改航班信息"<<endl<<"4.查看航班信息"<<endl<<"5.返回主菜单"<<endl;cout<<"*"<<endl; cout<<"请按以上方式选择:"<<endl;void store()/存取航班信息int i;struct airline *p,*q;p=(SLNode *)malloc(sizeof(SLNode);cout&l

20、t;<"请输入要存取的航班信息："<<endl;cout<<"航班号为："<<endl;cin>>p->PlaneNumber;cout<<"航班类型为:"<<endl;cin>>p->PlaneType;cout<<"起飞机场为："<<endl;cin>>p->StartPoint;cout<<"降落机场为:"<<endl;ci

21、n>>p->EndPoint; cout<<"日期为:"<<endl;cin>>p->Date;cout<<"起飞时间为:"<<endl;cin>>p->StartTime;cout<<"降落时间为:"<<endl;cin>>p->EndTime; cout<<"飞行时长为:"<<endl;cin>>p->FlyTime ;cout

22、<<"头等舱的价格是:"<<endl;cin>>p->GradePrice0;cout<<"公务舱的价格是:"<<endl;cin>>p->GradePrice1;cout<<"经济舱的价格是:"<<endl;cin>>p->GradePrice2;cout<<"头等舱的座位数是:"<<endl;cin>>p->SitsNumber0;cout<

23、;<"公务舱的座位数是:"<<endl;cin>>p->SitsNumber1;cout<<"经济舱的座位数是:"<<endl;cin>>p->SitsNumber2;for(i=0;i<p->SitsNumber0;i+)p->target0i=0;for(i=p->SitsNumber0;i<p->SitsNumber0+p->SitsNumber1;i+)p->target1i=0;for(i=p->SitsNumbe

24、r0+p->SitsNumber1;i<p->SitsNumber0+p->SitsNumber1+p->SitsNumber2;i+)p->target2i=0; p->next=head->next;head->next=p;q=head->next;cout<<"现有的航班是:"<<endl;while(q)display(q);q=q->next;void Delete() struct airline *p,*s;char number10; p=head->next;

25、s=head;cout<<"请输入要删除的的航班号："<<endl;cin>>number;while(p)if(!strcmp(number,p->PlaneNumber)&&s->next=p)s->next=p->next;s=s->next;p=p->next;void rivise()char number10;struct airline *p;p=head->next;cout<<"请选择要修改的航班号"<<endl;cin

26、>>number;while(p)if(!strcmp(number,p->PlaneNumber)cout<<"请输入要修改的航班信息："<<endl; cout<<"航班号为："<<endl; cin>>p->PlaneNumber; cout<<"航班类型为:"<<endl; cin>>p->PlaneType;cout<<"起飞机场为："<<endl; cin

27、>>p->StartPoint; cout<<"降落机场为:"<<endl; cin>>p->EndPoint; cout<<"日期为:"<<endl; cin>>p->Date; cout<<"起飞时间为:"<<endl; cin>>p->StartTime; cout<<"降落时间为:"<<endl; cin>>p->EndTi

28、me; cout<<"飞行时长为:"<<endl; cin>>p->FlyTime ; cout<<"头等舱的价格是:"<<endl; cin>>p->GradePrice0; cout<<"公务舱的价格是:"<<endl; cin>>p->GradePrice1; cout<<"经济舱的价格是:"<<endl; cin>>p->GradePrice

29、2; cout<<"头等舱的座位数是:"<<endl; cin>>p->SitsNumber0; cout<<"公务舱的座位数是:"<<endl; cin>>p->SitsNumber1; cout<<"经济舱的座位数是:"<<endl; cin>>p->SitsNumber2;p=p->next;void check()struct airline *q;q=head->next;cout<

30、<"现在的航班信息为："<<endl;while(q!=NULL)display(q);q=q->next;void Manage()/管理航班系统的函数 int i=0,flag=0; manageselect();while(!flag)cin>>i; if(i!=1&&i!=2&&i!=3&&i!=4&&i!=5)cout<<"选择错误，请重新输入"<<endl; cin>>i;elseswitch(i)case

31、1:store();manageselect();break; case 2:Delete(); manageselect();break; case 3:rivise(); manageselect();break;case 4:check();manageselect();break; case 5:flag=1;struct airline *FindInPlaneNumber()/按航班号查询airline *find,*p;char number10;find=head->next;p=head;cout<<"请输入飞机号:"<<en

32、dl;cin>>number;while(find)if(!strcmp(number,find->PlaneNumber) display(find); return find;void FindInStartPoint()/按起始地点查询airline *find,*p;char point10;find=head->next;p=head;cout<<"请输入起点站名字:"<<endl;cin>>point;while(find)if(!strcmp(point,find->StartPoint) di

33、splay(find); if(find->next=NULL&&(strcmp(point,p->StartPoint)cout<<"对不起，没有找到你所需要的航班"<<endl;find=find->next;p=p->next;void FindInEndPoint()/按终点站查询airline *find,*p;char point10;find=head->next;p=head;cout<<"请输入终点站名:"<<endl;cin>>p

34、oint;while(find)if(!strcmp(point,find->EndPoint) display(find); if(find->next=NULL&&(strcmp(point,p->StartPoint) cout<<"对不起，没有找到你所需要的航班"<<endl;find=find->next;p=p->next;void FindInDate()/按日期查询airline *find,*p;char Date10;find=head->next;p=head;cout<

35、<"请输入航班日期:"<<endl;cin>>Date;while(find)if(!strcmp(Date,find->Date) display(find); if(find->next=NULL&&(strcmp(Date,find->Date) cout<<"对不起，没有找到你所需要的航班"<<endl;find=find->next;p=p->next;void find()/查询函数int i; cout<<"*"

36、;<<endl;cout<<"1.按航班号查询"<<endl<<"2.按起点站查询"<<endl<<"3.按终点站查询"<<endl<<"4.按日期查询"<<endl; cout<<"*"<<endl;cout<<"请按以上方式选择:"<<endl;cin>>i;if(i!=1&&i!=2&am

37、p;&i!=3&&i!=4)cout<<"选择错误，请重新输入"<<endl;cin>>i;elseswitch(i)case(1):FindInPlaneNumber();break;case(2):FindInStartPoint();break;case(3):FindInEndPoint();break;case(4):FindInDate();break;void WaitForMore(char number,int amount,int grade,char name,airline *p)/等待定更

38、多的票int k,m=0,i,j=0;wait *q;q=(qnode *)malloc(sizeof(qnode);for(i=0;i<p->SitsNumber0+p->SitsNumber1+p->SitsNumber2;i+)if(p->targetgrade-1i=0)j+;if(j=0)cout<<"已经没有剩余的票，加入排队等候业务成功！"<<endl;q->grade=grade; strcpy(q->PlaneNumber,number); strcpy(q->name,name);

39、q->NeedNumber=amount;q->OrderNumber=0; q->WaitNumber=amount;for(k=0;k<p->SitsNumbergrade-1;k+)q->OrderedNumbergrade-1k=0;/q->OrderedNumbergrade-1;/ cout<<q->Waitnumber<<endl; q->next=begin->next; begin->next=q;elsecout<<"已经订票的座位号为："<<

40、;endl;for(k=0;k<p->SitsNumbergrade-1;k+)if(p->targetgrade-1k=0)cout<<k+1<<" " p->targetgrade-1k=1; q->OrderedNumbergrade-1m=k+1; m+;q->grade=grade; strcpy(q->PlaneNumber,number); strcpy(q->name,name); q->WaitNumber=amount-m; q->OrderNumber=m; q->

41、;NeedNumber=amount; q->next=begin->next; begin->next=q;/*cout<<endl; q->grade=grade;strcpy(q->PlaneNumber,number);strcpy(q->name,name);q->WaitNumber=amount-m;q->OrderNumber=m;q->NeedNumber=amount;/cout<<q->Waitnumber<<endl;q->next=begin->next;beg

42、in->next=q;*/void Ordertickets()/订票函数airline *p;order *q;int amount,grade,i,j=0,k,m=0;char number10;char name10;p=head;q=(linklist *)malloc(sizeof(linklist);cout<<"所有的航班信息为："<<endl;check();cout<<"请输入订票的航班号："<<endl;cin>>number;cout<<"请输入

43、订票的数量"<<endl;cin>>amount;cout<<"请输入舱位等级（头等舱为1、公务舱为2、经济舱为3）"<<endl;cin>>grade;cout<<"请输入你的姓名"<<endl;cin>>name;while(strcmp(number,p->PlaneNumber)p=p->next;for(i=0;i<p->SitsNumber0+p->SitsNumber1+p->SitsNumber2;

44、i+)if(p->targetgrade-1i=0)j+; /计算出还剩多少票/cout<<j;if(amount<=j)cout<<"订票成功，您的座位号是："<<endl;for(k=0;k<p->SitsNumber0+p->SitsNumber1+p->SitsNumber2;k+)if(p->targetgrade-1k=0&&m<amount)cout<<k+1<<" "p->targetgrade-1k=1;q-

45、>sitsnumbergrade-1m=k+1;m+;cout<<endl; strcpy(q->name,name);strcpy(q->PlaneNumber,number);q->Ordernumber=amount;q->grade=grade;q->next=start->next;start->next=q;elsecout<<"你订购的票数已经超过了这个等级的乘员定额!"<<endl;cout<<"您有以下选择："<<endl;cou

46、t<<"1.放弃订票,返回系统首页"<<endl<<"2.订购剩余的票，不够的排队等候"<<endl;cout<<"请选择："<<endl; cin>>j;if(j!=1&&j!=2)cout<<"选择错误，请重新选择！"<<endl;cin>>j;elseswitch(j)case 1:break;case 2:WaitForMore(number,amount,grade,na

47、me,p);break;return;void WaitedReturn(char name)/等待的人退票int i,k=0,m=0;wait *s,*q,*a;airline *t;order *p,*r;r=(linklist *)malloc(sizeof(linklist);a=begin;q=begin->next;t=head->next; p=start->next;s=begin->next;while(s)if(!(strcmp(name,s->name)while(strcmp(t->PlaneNumber,s->PlaneNum

48、ber)t=t->next;for(i=0;i<s->OrderNumber;i+)t->targets->grade-1s->OrderedNumbers->grade-1i=0;cout<<"您退票已经成功！"<<endl;while(q)for(i=0;i<t->SitsNumberp->grade-1;i+)if(t->targetp->grade-1i=0)k+;if(q->WaitNumber<k)cout<<q->name<<

49、;"等候的用户可以订票了！"<<endl;cout<<q->name<<"用户订票的座位号为："<<endl;for(i=0;i<t->SitsNumberp->grade-1;i+)if(t->targetp->grade-1i=0&&m<q->WaitNumber)cout<<i+1<<" "t->targetp->grade-1i=1;r->sitsnumberp->gr

50、ade-1m=k+1;m+; strcpy(r->name,q->name); strcpy(r->PlaneNumber,q->PlaneNumber); r->Ordernumber=q->WaitNumber; r->grade=q->grade; r->next=start->next; start->next=r;a->next=q->next;a=a->next;q=q->next;s=s->next;void UnwaitedReturn(char name)/没有等待过的退票int

51、i,k=0,m=0;order *p,*s;s=(linklist *)malloc(sizeof(linklist);wait *q,*a;a=begin;q=begin->next;airline *t; p=start->next;t=head->next;while(p)if(!strcmp(name,p->name)while(strcmp(t->PlaneNumber,p->PlaneNumber)t=t->next;for(i=0;i<p->Ordernumber;i+)t->targetp->grade-1p-&

52、gt;sitsnumberp->grade-1i-1=0;cout<<"您退票成功！"<<endl;while(q)for(i=0;i<t->SitsNumberp->grade-1;i+)if(t->targetp->grade-1i=0)k+;if(q->WaitNumber<k)m=0;cout<<q->name<<"等候的用户可以订票了！"<<endl;cout<<q->name<<"用户订票的

53、座位号为："<<endl;for(i=0;i<t->SitsNumberp->grade-1;i+)if(t->targetp->grade-1i=0&&m<q->WaitNumber)cout<<i+1<<" "t->targetp->grade-1i=1;s->sitsnumberp->grade-1m=k+1;m+; strcpy(s->name,q->name); strcpy(s->PlaneNumber,q->P

54、laneNumber); s->Ordernumber=q->WaitNumber; s->grade=q->grade; s->next=start->next; start->next=s;cout<<endl;a->next=q->next;a=a->next;q=q->next;p=p->next;return;void Returntickets()/退票函数int i;order *q;wait *p;q=start->next;p=begin->next;char name10;cou

55、t<<"请输入你的姓名："<<endl;cin>>name;while(q)if(q->next=NULL&&(strcmp(name,q->name)cout<<"对不起，你没有定过票!"<<endl;return;cout<<"加入过排队区的用户退票请按1，没有加入过的请按2"<<endl;cout<<"请选择："<<endl;cin>>i;switch(i)cas

56、e 1:WaitedReturn(name);return;case 2:UnwaitedReturn(name);return;int Menuselect()/菜单界面 int c; char s20; cout<<"*"<<endl;cout<<" 航空客运订票系统 "<<endl; cout<<" 1.管理系统 "<<endl; cout<<" 2.查找航班信息 "<<endl; cout<<&quo

57、t; 3.办理订票业务 "<<endl; cout<<" 4.办理退票业务 "<<endl;cout<<" 0.退出系统 "<<endl; cout<<"*"<<endl; doprintf("请选择:"); scanf("%s",s); c=atoi(s); while(c<0|c>7); return c;void main()/start=air;ListInitiate();while(1)switch(Menuselect()case 1:Manage()