图的遍历过程演示

1、数据结构实验报告航空订票系统课程设计报告 姓名：常建明 学号：131842311 设计题目 ： 图的遍历 设计题目 ：航空订票系统目 录1 图的遍历 1 图的遍历过程演示的要求 2 设计思路 3 详细设计 4 设计与调试分析 2 航空订票系统 1 问题的要求 2 问题描述 3 设计思路 4 主要功能函数设计 5 编码实现 6 运行与测试 图的遍历图的遍历过程演示的要求设计程序完成如下功能：对给定的图结构和起点，产生深度优先遍历和广度优先遍历序列，并给出求解过程的动态演示。 设计思路首先由于程序中要有对图的数据信息的创建，定义一个全局变量Max，表示最多建立的结点数。设计实现主要功能的函数有：创

2、建图的数据信息的函数CreateMGraph（）；深度优先遍历递归函数DFSM（）；广度优先遍历递归BFSM；深度优先遍历DFSTraverseM（）；广度优先遍历BFSTraverseM（）；然后在main()函数中使用一个switch()语句实现对各个子函数的调用。抽象数据类型队列的定义如下：ADT Queue 数据对象：D=ai| ai ElemSet,i=1,2,3，n,n0数据关系：R1=<ai-1,ai>| ai-1,ai D,i=1,2,3,，n 约定其中a1端为队列头，an端为队列尾。基本操作：InitQueue(&Q) 操作结果：构造一个空队列Q。Dest

3、royQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则FALSE。QueueLength(Q) 初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e) 初始条件：Q为非空队列。 操作结果：用e返回Q的对头元素。EnQueue(&Q,e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。DeQueue

4、(&Q,&e) 初始条件：队列Q已存在。 操作结果：删除Q的对头元素，并用e返回其值。QueueTraverse(Q,visit() 初始条件：Q已存在且非空。 操作结果：从对头到对尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。详细设计 #include<stdio.h>/*头文件*/#include<stdlib.h>#define Max 10#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef struct c

5、har vexsMax; int edgesMaxMax; int n,e;MGraph;/*以邻接矩阵作为图的存储结构*/int visitedMax;/*将visitedMax定义为全局变量并分配最大空间*/ main() MGraph *G,a; char ch1; int i,j,ch2; G=&a;ch1='y'/*设置控制语句标志*/ while(ch1='y'|ch1='Y') /*菜单栏*/ printf("n");printf("tt+图的遍历过程演示+n"); printf(&q

6、uot;tt+ 选择菜单 +n"); printf("tt+n"); printf("tt+ 创建图的数据请按:1 +n"); printf("tt+ 深度优先搜索请按:2 +n"); printf("tt+ 广度优先搜索请按:3 +n"); printf("tt+ 退出搜索请按:0 +n"); printf("tt+n"); printf("ntt请选择菜单号（0-3）："); scanf("%d",&ch2); g

7、etchar(); switch(ch2) case 1: CreateMGraph(G);/*选1创建一个新的图矩阵*/ break; case 2: DFSTraverseM(G);/*选2进入深度优先搜索*/ break; case 3: BFSTraverseM(G);/*选3进入广度优先搜索*/ break; case 0:/*选0结束搜索，退出程序*/ ch1='n' break; default: system("cls"); printf("ntt输入有误！n"); break; if(ch2=1|ch2=2|ch2=3)

8、 printf("nntt ");/*控制格式*/ typedef struct int front; int rear; int count; int dataQueueSize;CirQueue;/*定义队列的数据结构*/void InitQueue(CirQueue *Q) Q->front=Q->rear=0; Q->count=0; int QueueEmpty(CirQueue *Q) return Q->count=QueueSize;/*返回队列的最大长度*/ int QueueFull(CirQueue *Q) return Q-&

9、gt;count=QueueSize;/*返回队列的最大长度*/void EnQueue(CirQueue *Q,int x) if(QueueFull(Q)/*队列满则出错*/ Error("Queue overflow"); else Q->count+;/*否则count+，将x进队*/ Q->dataQ->rear=x; Q->rear=(Q->rear+1)%QueueSize; int DeQueue(CirQueue *Q) int temp;/*定义整型的变量*/ if(QueueEmpty(Q)/*若为真则出错*/ Error

10、("Queue underflow"); else/*为假则count-，将队员出队*/ temp=Q->dataQ->front;/*用temp返回其值*/ Q->count-; Q->front=(Q->front+1)%QueueSize; return temp;/*返回出队元素值*/ void CreateMGraph(MGraph *G) int i,j,k;/*定义整型变量*/ char ch1,ch2;/*定义字符型变量*/ printf("n请输入顶点数，边数（格式：3，4）:"); scanf("

11、;%d,%d",&(G->n),&(G->e);/*输入图的顶点数和边数*/ for(i=0;i<G->n;i+) getchar(); printf("n请输入第%d个顶点序号",i+1); scanf("%c",&(G->vexsi);/*输入顶点的序号*/ for(i=0;i<G->n;i+) for(j=0;j<G->n;j+) G->edgesij=0;/*初始化矩阵*/ for(k=0;k<G->e;k+) getchar(); prin

12、tf("n请输入第%d条边的顶点序号（格式：i，j）:",k+1); scanf("%c,%c",&ch1,&ch2);/*输入边的顶点序号*/ for(i=0;ch1!=G->vexsi;i+); for(j=0;ch2!=G->vexsj;j+); G->edgesij=1;/*有边则赋值为1*/ void DFSM(MGraph *G,int i) int j; printf("%c ",G->vexsi); visitedi=TRUE;/*标记visitedi*/ /*依次优先搜索访问v

13、isitedi的每个邻接点*/for(j=0;j<G->n;j+) /*若visitedi的一个有效邻接点visitedj未被访问过，则从visitedj出发进行递归调*/ if(G->edgesij=1&&!visitedj) DFSM(G,j);void DFSTraverseM(MGraph *G) int i; printf("n 深度优先遍历序列:");for(i=0;i<G->n;i+) visitedi=FALSE;/*访问标志数组初始化*/ for(i=0;i<G->n;i+) if(!visited

14、i)/*对尚未访问的顶点调用DFSM*/ DFSM(G,i); void BFSM(MGraph *G,int k) int i,j; CirQueue Q;/*定义一个队列Q，初始化队列为空*/ InitQueue(&Q); printf("%c ",G->vexsk);/*访问初始点，并将其标记已访问过*/ visitedk=TRUE; EnQueue(&Q,k);/*将以访问过的初始点序号k入队*/ while(!QueueEmpty(&Q)/*队列非空进行循环处理*/ i=DeQueue(&Q);/*将队首元素出队*/ for(

15、j=0;j<G->n;j+)/*依次搜索vexsk的每一个可能的邻接点*/ if(G->edgesij=1 &&! visitedj) visitedj=TRUE;/*标记vexsj已访问过*/ EnQueue(&Q,j);/*顶点序号j入队*/ void BFSTraverseM(MGraph *G) int i; printf("n 广度优先遍历序列:");for(i=0;i<G->n;i+) visitedi=FALSE;/*访问标志数组初始化*/ for(i=0;i<G->n;i+) if(!visi

16、tedi)/*对尚未访问的顶点调用BFSM*/ BFSM(G,i); 7）各个模块之间的调用关系如下：广度优先遍历图修改图的信息深度优先遍历图进入菜单选择用户登录图信息的录入 退出程序设计与调试分析从上面的算法和调用关系可以看出，这个程序的基本样子已经非常的清楚，但是真正的程序中还要考虑各种限制条件。在调试过程中，程序中出现了许多的错误，有错误的调用、一些变量没有定义、等等。不断的对程序进行调试以得到最好的结果，程序中特别要注意的是类的对象作为作为参数时要注意如何去调用它，使程序有一个令人满意的结果，具体的调试是在上机过程中进行的，在编写程序的过程中主要有如下错误：1、在编写程序的过程出现了一

17、些函数名、变量的大小写不统一的错误，导致程序在运行的过程中出现函数名、变量没有被定义等问题；2、在编写程序的过程中数组的大小写没有被确定；3、在编写程序的过程中一些变量没有被定义，导致程序出错；4、数组visitedMax应定义为全局变量，若不是则会出错；5、函数的返回类型要确定，是void还是其他类型要十分注意；6、在编程的过程中，函数里一些控制语句的嵌套使用，括号要引起注意，这次的课程设计就有一些括号漏了或者多打了，导致括号不配套；创建数据就是把最开始要输入的数据输入到系统里。界面如下：按照深度优先搜索来遍历图。界面如下：按照广度优先搜索来遍历图。界面如下：重新创建另一个图的数据。界面如下

18、：完成任务后，退出的界面如下： 航空订票系统问题的要求 设计航班信息，订票信息的存储结构，设计程序完成如下功能：录入：可以录入航班情况(数据可以存储在一个数据文件中，数据结构、具体数据自定)查询：可以查询某个航线的情况(如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓)；可以输入起飞抵达城市，查询飞机航班情况；订票：(订票情况可以存在一个数据文件中，结构自己设定)可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件问

19、题描述航空订票的业务活动一般包括查询航线信息、客票预订、办理退票等。每条航线所涉及的信息由：终点站名、航班号、飞机号、成员数额、余票量、已订票的客户名单。设计思路主要有三个方面的内容，查询航线信息、订票和退票业务。程序的基本功能有：(1) 查询航线。根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票数。(2) 承办订票业务。根据客户提出的要求查询该航班票额情况，若有余票，为客户办理订票手续，输出座位号。若无票，则须重新询问客户要求。若需要，可登记排队等候。（3） 退票业务。根据客户提供的情况，为客户办理退票手续，然后查询该航班是否有人排队等候，首先询问排在

20、第一的客户，若所退票额能瞒住他的要求，则为他办理退票手续，否则依次询问其他排队候补的客户。主要功能函数设计（1）总航线信息预览：通过调用display()预览已经建立的全部航线的相关信息（航班号、飞机号 、终点站 、飞行日期 、 定额 、余票数 、排队等候人数），预览完返回主菜单。（2）查询单条航线信息：根据乘客提出的终点站名或航班号调用Search()函数来查询并输出此条航线的相关信息（航班号、飞机号 、终点站 、飞行日期 、 定额 、余票数 、已订票乘客名单、排队等候乘客名单）。 并且查询完后询问乘客是否订票，是就调用订票Book()函数来为乘客进行订票，否就返回主菜单。（3）办理订票业务

21、：客户先输入的终点站名、订票数、姓名信息再来调用订票Book()函数，Book()函数根据客户提供的终点站名查询到该航线信息，若客户订票额末超过余票量，订票成功并登记信息，在订票乘员名单链表中添加乘客的信息； 如果暂时余票数不足是，询问客户是否要排队等侯，如果是，则在排队等候的队列中增加该乘客的订票信息。（4）办理退票业务：调用tuipiao()查询函数，根据客户提供的航线进行搜索根据客户提供的姓名到订票客户名单域进行查询。退票成功后，重新将航线名单域指向订票单链表的头指针。根据队列中从出的客户信息判断是否满足要求，如果满足，则将该客户的信息插入到乘客信息链表中。（5）录入航班信息：调用Cre

22、atPlane（）函数，根据输入的航班的相关的信息（航班号、飞机号 、终点站 、飞行日期 、 定额 、余票数），将此航班加入到原来的航班组中。（6）退出系统编码实现#include<stdio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAXSIZE100typedef struct Cust/已订票乘客信息char Name15;/乘客姓名 char number10;/乘客所乘飞机航班号 char end15;/乘客终点typedef struct waitN

23、ode/排队等候客户信息 char name15;/乘客姓名int ticket;/乘客的订票数struct waitNode *next;waitNode,*waitlink;typedef structwaitlink front;waitlink rear;waitQueue;typedef struct Plane/航班信息char number10;/航班号int planenum;/飞机号char end15;/终点站char date10;/飞行日期int dinge;/成员定额 int tick;/剩余票数 int k;/排队等候的人数Customer *first;/链接已订

24、票客户waitQueue Q;/链接候补客户PlaneLink;int Search(PlaneLink *p,int N) int i=0,Q; cout<<"=n" cout<<" 1.按终点站名查询n"cout<<" 2.按航班号查询 n"cout<<"_n"cout<<">>>>>>n"cout<<" 请选择查询方式 (1/2)：" cin>>Q;i

25、f(Q=1)char end10;cout<<" 请您输入要查询的航班的终点站名: " /按站点名查询航班信息 cin>>end; while(i<N) if(strcmp(pi.end,end)=0) /先查看是否存在到该站点的航班 cout<<"n*您所查询的航班信息如下*n" cout<<"_n" cout<<" 航班号 飞机号 终点站 飞行日期 余票数n" cout<<" "<<pi.number&

26、lt;<setw(7)<<pi.planenum<<setw(12)<<pi.end<<setw(10)<<pi.date<<setw(10)<<pi.tick<<endl; cout<<"n=n" break; i+;else if(Q=2) char num10; cout<<" 请您输入要查询的航班的航班号: " /按站点名查询航班信息 cin>>num; while(i<N) if(strcmp(pi.n

27、umber,num)=0) /查看是否存在该航班号的航班 cout<<"n*您所查询的航班信息如下：*n" cout<<"_n" cout<<" 航班号 终点 飞行日期 余票数n" cout<<" "<<pi.number<<setw(12)<<pi.end<<setw(12)<<pi.date<<setw(12)<<pi.tick<<endl; cout<<&

28、quot;n=n" break; i+; display_s(p, i, N); /调用display_s()函数输出该航班的已订票乘客和排队等候乘客的名单信息if(i<N) /如果存在该航班，询问客户是否要预定 该航班的 机票int j; cout<<" 是否需要预定 该航班的票(1/0):" cin>>j; if(j=1) char name10; int ticket; cout<<" 请输入订票数目、姓名：" cin>>ticket>>name; Book(p,pi.en

29、d,ticket, name, N); else cout<<" 很抱歉，没有您查询的航班信息!n" return 0;int Book(PlaneLink *p,char end,int ticket,char name,int N) int i; for(i=0;i<N;i+)if(strcmp(pi.end,end)=0) /先找出是否存在要订票的航班 if(pi.tick>=ticket) /查看 余票数是否 >= 订票客户 订票数pi.tick-=ticket;Customer *t=(Customer *)malloc(sizeof

30、(Customer);t->ticket=ticket;strcpy(t->Name,name);strcpy(t->number,pi.number); strcpy(t->end,pi.end);t->next=pi.first; pi.first=t; / 此使用的是头插法将订票乘客的信息放入到 链表中 cout<<" 您订票成功!n"cout<<" 您的航班信息如下:n"cout<<"_n"cout<<" 航班号 飞机号 终点站 飞行日期

31、定额n"cout<<"_n"cout<<" "<<setw(9)<<pi.number<<setw(6)<<pi.planenum<<setw(12)<<pi.end<<setw(12)<<pi.date<<setw(10)<<pi.dinge<<endl;cout<<"=nn"break;else if(pi.dinge<ticket) /订票数超出航

32、班的定额时，不能订票，也不能无法排队等候了 cout<<" 您预订的票数超过了航班定额，无法为您订票!n" break; else / 余票数不足时，询问乘客是否排队等候char z;cout<<" 该航班剩余票数为："<<pi.tick<<endl;cout<<" 很抱歉，剩余的票数不够!n" cout<<" 您是否需要排队等候 (Y(y)/N(n): " cin>>z; if(z='Y'|z='y'

33、;) Queue(p,end,ticket , name, N,i); /调用入队列函数，将乘客信息插入排队等候的人后面break;if(i>=N) cout<<" 很抱歉，没有您所需要的航班!n" return 0;int display_s(PlaneLink *p,int i,int N) /输出已定票及排队乘客的名单信息if(pi.first!=NULL) /pi.first!=NULL说明已订票链表不为空， 输出 已订票乘客的名单信息cout<<"*该航班的已订票乘客名单如下：*n" cout<<&qu

34、ot;_n"cout<<" 姓名 订票量n"Customer *t=pi.first;while(t) cout<<setw(10)<<t->Name<<" "<<setw(7)<<t->ticket<<endl; t=t->next;if(i<N&&pi.Q.front!=NULL) /pi.Q.front!=NULL，输出正在排队等候乘客的名单信息 cout<<"*该航班等候订票的乘客名单如下:

35、*n"cout<<" 姓名 订票量n"waitlink S=pi.Q.front; while(S!=NULL)cout<<setw(10)<<S->name<<" "<<setw(7)<<S->ticket<<endl;S=S->next; cout<<"=n" return 0;int Queue(PlaneLink *p,char end,int ticket,char name,int N ,int i)

36、 /入队函数，将等候排队的乘客放入原来的队列中system("cls");system("color 2e");waitlink q=(waitlink)malloc(sizeof(waitNode); /将要的入队的结点，存储将要入队乘客的信息strcpy(q->name,name);q->ticket=ticket;q->next=NULL; if(pi.Q.front=NULL) pi.Q.front=pi.Q.rear=q; pi.k+; /pi.k用来记录排队人数elsepi.Q.rear->next=q;pi.Q.re

37、ar=q; pi.k+; cout<<"已为您登记，请耐心等候！n"return 0;int tuipiao(PlaneLink *p,int N) int i; Customer *R,*S;char number10,Name15;cout<<">>>>>>n"cout<<" 请输入您的航班号与姓名:"cin>>number>>Name;for(i=0;i<N;i+) if(strcmp(pi.number,number)=0&a

38、mp;&pi.first!=NULL)if(strcmp(pi.first->Name,Name)=0)pi.tick=pi.tick+pi.first->ticket;pi.first=pi.first->next;cout<<" 您已成功退票!nn"else R=pi.first; S=pi.first->next;while(S!=NULL)if(strcmp(S->Name,Name)=0)pi.tick=pi.tick+S->ticket;R->next=S->next;cout<<&

39、quot; 您已经成功退票!nn" break;R=R->next; S=S->next;if(S=NULL) cout<<" 很抱歉,在该航班上没有找到您的姓名，请核实信息!nn"if(pi.Q.front!=NULL)waitlink Q=pi.Q.front , q; while(Q!=NULL)if(pi.tick>=Q->ticket)if(Q=pi.Q.front)cout<<" 正在为等候的乘客 "<<Q->name<<"办理订票!n"

40、;Book(p,pi.end,Q->ticket,Q->name,N);if(pi.Q.front=pi.Q.rear)pi.Q.front=pi.Q.rear=NULL;Q=Q->next;else pi.Q.front=pi.Q.front->next; Q=Q->next;elsecout<<" 正在为等候的乘客 "<<Q->name<<"办理订票!n"Book(p,pi.end,Q->ticket,Q->name,N);q->next=Q->next;

41、 Q=Q->next;else q=Q; Q=Q->next; break; if(strcmp(pi.number,number)=0&&pi.first=NULL)cout<<" 很抱歉，该航班目前没有已订票的乘客，无法为你退票，请核实信息!nn" break;if(i>=N) cout<<" 很抱歉，没有该航班信息,无法为你退票，请核实信息!nn"return 0;void CreatPlane(PlaneLink *p,int n,int N) int i,j;for(i=N;i<N

42、+n;i+)pi.first=NULL; / 带头结点的单链表为空时的条件pi.Q.front=pi.Q.rear=NULL; /队列为空时的条件cout<<">>>>>>n" cout<<" 请输入航班号: " cin>>pi.number;cout<<" 输入终点站名: " cin>>pi.end;for( j=0;j<N;j+)if(strcmp(pi.number,pj.number)=0) /查看该航班号是否已经存在cout

43、<<" 已经存在该航班号!n " break; if(strcmp(pi.end,pj.end)=0) / 查看是否存在到改站点的航班cout<<" 已经有到该站点的航班!n " break;if(j=N)cout<<" 飞机号、飞行日期、成员定额：n" cin>>pi.planenum>>pi.date>>pi.dinge; pi.tick=pi.dinge; pi.k=0;cout<<" 录入完成!n"int display(PlaneLink *p,int N) /N为当前的航班数 cout<<&