图的遍历过程演示

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

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

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

4、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 structchar vexsMax;int

5、 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("tt+选择菜单+n");pr

6、intf("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 ):");11 / 25scanf("%d”,&ch2);getchar();switch(ch2)case 1:CreateMGraph

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

8、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->count=QueueSize;/*返回队列的最大长度 */void EnQueue(CirQueue *Q,int x

9、) 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("Queue underflow");else/* 为假则count-,将队员出队*/tem

10、p=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("%d,%d",&(G->n),&(G->e);/*输入图的顶点数和边数*/fo

11、r(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();printf("n请输入第条边的顶点序号(格式：i , j ) :",k+1);scanf("%c,%c&qu

12、ot;,&ch1,&ch2);/*输入边的顶点序号 */for(i=0;ch1!=G->vexsi;i+);forO=0;ch2!=G->vexsj;j+);G->edgesij=1;/*有边则赋值为 1*/void DFSM(MGraph *G,int i)int j；printf("%c ",G->vexsi);visitedi=TRUE;/* 标记visitedi*/*依次优先搜索访问visitedi 的每个邻接点*/for(j=0;j<G->n;j+)/* 若visitedi的一个有效邻接点 visitedj 未被

13、访问过，则从 visitedj出发进行递归调*/if(G->edgesij=1&&!visitedj) DFSM(G,j);void DFSTraverseM(MGraph *G)int i;printf("nfor(i=0;i<G->n;i+)visitedi=FALSE;/*for(i=0;i<G->n;i+)if(!visitedi)/*DFSM(G,i);void BFSM(MGraph *G,int k)深度优先遍历序列：");访问标志数组初始化*/对尚未访问的顶点调用DFSM*/int i,j;CirQueue Q;

14、/*定义一个队列Q,初始化队列为空*/访问初始点，并将其标记已访问过*/InitQueue(&Q);printf("%c ”,G->vexsk);/*visitedk=TRUE;EnQueue(&Q,k);/*将以访问过的初始点序号k入队*/while(!QueueEmpty(&Q)/*队列非空进行循环处理 */i=DeQueue(&Q);/*将队首元素出队*/for(j=0;j<G->n;j+)/*依次搜索vexsk的每一个可能的邻接点 */if(G->edgesij=1 &&! visitedj) visit

15、edj=TRUE;/*标记 vexsj已访问过 */EnQueue(&Q,j);/*顶点序号 j 入队*/void BFSTraverseM(MGraph *G)int i;printf("nfor(i=0;i<G->n;i+)visitedi=FALSE;/*for(i=0;i<G->n;i+)if(!visitedi)/*广度优先遍历序列：");访问标志数组初始化*/对尚未访问的顶点调用 BFSM*/BFSM(G,i);7)各个模块之间的调用关系如下:数据结构实验报告航空订票系统15/ 25进入菜单选广度优先 遍历图修改图的信息深度优先

16、厂遍历图.退出程序设计与调试分析从上面的算法和调用关系可以看出，这个程序的基本样子已经非常的清楚，但是真正的程序中还要考虑各 种限制条件。在调试过程中，程序中出现了许多的错误，有错误的调用、一些变量没有定义、等等。不断的对程序进行 调试以得到最好的结果，程序中特别要注意的是类的对象作为作为参数时要注意如何去调用它，使程序有一 个令人满意的结果，具体的调试是在上机过程中进行的，在编写程序的过程中主要有如下错误：1、在编写程序的过程出现了一些函数名、变量的大小写不统一的错误，导致程序在运行的过程中出现函 数名、变量没有被定义等问题；2、在编写程序的过程中数组的大小写没有被确定；3、在编写程序的过程

17、中一些变量没有被定义，导致程序出错；4、数组visitedMax 应定义为全局变量，右不是则会出错；5、函数的返回类型要确定，是 void还是其他类型要十分注意；6、在编程的过程中，函数里一些控制语句的嵌套使用，括号要引起注意,这次的课程设计就有一些括号漏了或者多打了，导致括号不配套；创建数据就是把最开始要输入的数据输入到系统里。界面如下：+-* * * + ; 23* + * S : - * 二毒一 演慧密请U 寥n漱曩请一 功择一的先先索一 遍选(图 的一建度馍出一 图2创ml.退一 * +-按照深度优先搜索来遍历图。界面如下:请选择菜单号-刃:2深度优先遍历序匕4 5 2 3按照广度优先

18、搜索来遍历图。界面如下:ca -C : XDociment s and Se+t lngsAdMlniis1 ra± orDebugt raversinggrapti- exeC : DocusLent s and Settnisi rat orOe=bvi£t reae* *- S - S + 示 2 寅 f 请主旧Iff:8f-+ 亶-E按- 过某一数辑请一 历择一的先先素- 遍选7 的一建度度比一 目 *可亲*请选择菜单号小7). 3广度优先遍历序列;1 2 3 4 5重新创建另一个图的数据。界面如下:完成任务后，退出的界面如下:"C: D0cuAent2

19、and SettingsA<i*inist rat orDebugt raver sing g raph. exe* +12 3 * +*:,+ 示一 WK H 寅 t青肩王IR:0r 亶按H 过菜-数甚请+ 历择H的先先肃+ 遍选A图+ 的+-建度理出+. 图一创深广退+4- +-*请选建菜单号57): 0Press ang key to continue航空订票系统问题的要求设计航班信息，订票信息的存储结构，设计程序完成如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班

20、票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件问题描述 航空订票的业务活动一般包括查询航线信息、客票预订、办理退票等。每条航线所涉及的信息由:终点站名、航班号、飞机号、成员数额、余票量、已订票的客户名单。数据结构实验报告航空订票系统设计思路主要有三个方面的内容，查询航线信息、订票和退票业务。程序的基本功能有：(1)

21、查询航线。根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期 和余票数。(2)承办订票业务。根据客户提出的要求查询该航班票额情况，若有余票，为客户办理订票手续，输出座位号。若无票，则须重新询问客户要求。若需要，可登记排队等候。(3)退票业务。根据客户提供的情况，为客户办理退票手续，然后查询该航班是否有人排队等候，首先询问排在第一的客户，若所退票额能瞒住他的要求，则为他办理退票手续，否则依次询问其他排队候补的客户。主要功能函数设计(1)总航线信息预览：通过调用display。 预览已经建立的全部航线的相关信息(航班号、飞机号 、终点站、飞行日期、定额、余票数、排队

22、等候人数)，预览完返回主菜单。(2)查询单条航线信息：根据乘客提出的终点站名或航班号调用Search()函数来查询并输出此条航线的相关信息(航班号、飞机号 、终点站、飞行日期、定额、余票数、已订票乘客名单、排队等候乘客名单)。 并且查询完后询问乘客是否订票，是就调用订票Book()函数来为乘客进行订票，否就返回主菜单。(3)办理订票业务：客户先输入的终点站名、订票数、姓名信息再来调用订票Book()函数，Book()函数根据客户提供的终点站名查询到该航线信息，若客户订票额末超过余票量，订票成功并登记信息，在订票乘员名单链表中添加乘客的信息；如果暂时余票数不足是，询问客户是否要排队等侯，如果是，

23、则在排队等候的队列中增加该乘客的订票信息。(4)办理退票业务：调用tuipiao()查询函数，根据客户提供的航线进行搜索根据客户提供的姓名到订票客户名单域进行查询。退票成功后，重新将航线名单域指向订票单链表的头指针。根据队列中从出的客户信息判断是否满足要求，如果满足，则将该客户的信息插入到乘客信息链表中。(5)录入航班信息：调用 CreatPlane ()函数，根据输入的航班的相关的信息(航班号、飞机号 、终点站、飞行日期、定额、余票数)，将此航班加入到原来的航班组中。(6)退出系统编码实现#include<stdio.h>#include<stdio.h>#inclu

24、de<stdlib.h>#include<string.h>#define MAXSIZE 100typedef struct Cust已订票乘客信息char Name15;char number10;char end15;typedef struct waitNodechar name15;int ticket;/乘客姓名/乘客所乘飞机航班号/乘客终点排队等候客户信息/乘客姓名/乘客的订票数struct waitNode *next;waitNode,*waitlink;typedef structwaitlink front;waitlink rear;waitQu

25、eue;typedef struct Planechar number10;int planenum;char end15;char date10;int dinge;int tick;int k;Customer *first;waitQueue Q;PlaneLink;int Search(PlaneLink *p,int N)/航班信息/航班号飞机号/终点站飞行日期/成员定额/剩余票数/排队等候的人数/链接已订票客户/链接候补客户int i=0,Q;cout<<"=n"cout<<"1.按终点站名查询n"cout<&l

26、t;"2.按航班号查询n"# / 25数据结构实验报告航空订票系统cout<<"n"cout<<">>>>>>n"cout<<"请选择查询方式(1/2) ： " cin>>Q;if(Q=1)(char end10;cout<<"请您输入要查询的航班的终点站名："按站点名查询航班信息 cin>>end;while(i<N) (if(strcmp(pi.end,end)=0) /先查看是

27、否存在到该站点的航班cout<<"n*您所查询的航班信息如下*n"25 / 25cout<<"n"cout<<"航班号 飞机号 终点站飞行日期余票数n"cout<<""<<pi.number<<setw(7)<<pi.planenum<<setw(12)<<pi.end<<setw(10)<<pi.date<<setw(10)<<pi.tick<<e

28、ndl;cout<<"n=n"break;i+;else if(Q=2)(char num10;cout<<"请您输入要查询的航班的航班号："/按站点名查询航班信息cin>>num;while(i<N)(if(strcmp(pi.number,num)=0)(/查看是否存在该航班号的航班cout<<"n*您所查询的航班信息如下：*优cout<<"n"cout<<"航班号 终点飞行日期余票数n"cout<<"

29、 "<<pi.number<<setw(12)<<pi.end<<setw(12)<<pi.date<<setw(12)<<pi.tick<<endl; cout<<"n=n"break;i+;display_s(p, i, N); 调用display_s()函数输出该航班的已订票乘客和排队等候乘客的名单信息 if(i<N)/如果存在该航班，询问客户是否要预定该航班的机票int j;cout<<"是否需要预定该航班的票(1/0):

30、" cin>>j;if(j=1)char name10; int ticket;cout<<"请输入订票数目、姓名："cin>>ticket>>name;Book(p,pi.end,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.e

31、nd,end)=0)/先找出是否存在要订票的航班if(pi.tick>=ticket) /查看余票数是否>=订票客户订票数( pi.tick-=ticket; Customer *t=(Customer *)malloc(sizeof(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&l

32、t;<"您订票成功！n"cout<<"您的航班信息如下：n"cout<<"n"cout<<" 航班号 飞机号 终点站 飞行日期 定额n"cout<<"n" cout<<""<<setw(9)<<pi.number<<setw(6)<<pi.planenum<<setw(12)<<pi.end<<setw(12)<<p

33、i.date<<setw(10)<<pi.ding e<<endl;cout<<"=nn" break;else if(pi.dinge<ticket)订票数超出航班的定额时，不能订票，也不能无法排队等候了 cout<<"您预订的票数超过了航班定额，无法为您订票！n" break; else/余票数不足时，询问乘客是否排队等候 char z; cout<<"该航班剩余票数为："<<pi.tick<<endl; cout<<

34、"很抱歉，剩余的票数不够！n" cout<<"您是否需要排队等候(Y(y)/N(n): " cin>>z;if(z='Y'|z='y') 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(

35、pi.first!=NULL)/pi.first!=NULL说明已订票链表不为空，输出 已订票乘客的名单信息cout<<"*该航班的已订票乘客名单如下：*n"cout<<"n"cout<<" 姓名订票量n"Customer *t=pi.first; while(t) cout<<setw(10)<<t->Name<<""<<setw(7)<<t->ticket<<endl;t=t->next

36、; if(i<N&&pi.Q.front!=NULL) /pi.Q.front!=NULL ,输出正在排队等候乘客的名单信息 cout<<"*该航班等候订票的乘客名单如下：*n"cout<<" 姓名订票量n"waitlink S=pi.Q.front; while(S!=NULL) cout<<setw(10)<<S->name<<""<<setw(7)<<S->ticket<<endl;S=S->n

37、ext; cout<<"=n" return 0; int Queue(PlaneLink *p,char end,int ticket,char name,int N ,int i) / 入队函数，将等候排队的乘客放入原 来的队列中system("cls");system("color 2e");waitlink q=(waitlink)malloc(sizeof(waitNode);/将要的入队的结点，存储将要入队乘客的信息strcpy(q->name,name);q->ticket=ticket; q-&

38、gt;next=NULL; if(pi.Q.front=NULL) pi.Q.front=pi.Q.rear=q; pi.k+; /pi.k 用来记录排队人数 else pi.Q.rear->next=q; pi.Q.rear=q; pi.k+;cout<<"已为您登记，请耐心等候！n"return 0; int tuipiao(PlaneLink *p,int N) int i;Customer *R,*S;char number10,Name15;cout<<">>>>>>n"cout

39、<<"请输入您的航班号与姓名："；cin>>number>>Name;for(i=0;i<N;i+)if(strcmp(pi.number,number)=0&&pi.first!=NULL)if(strcmp(pi.first->Name,Name)=0)pi.tick=pi.tick+pi.first->ticket;pi.first=pi.first->next;cout<<"您已成功退票！nn"elseR=pi.first; S=pi.first->ne

40、xt;while(S!=NULL)if(strcmp(S->Name,Name)=0)pi.tick=pi.tick+S->ticket;R->next=S->next;cout<<"您已经成功退票！nn" break;R=R->next; S=S->next;!nn"if(S=NULL) cout<<"很抱歉，在该航班上没有找到您的姓名，请核实信息if(pi.Q.front!=NULL)waitlink Q=pi.Q.front , q;while(Q!=NULL)if(pi.tick>

41、=Q->ticket)if(Q=pi.Q.front) cout<<"正在为等候的乘客"<<Q->name<<"办理订票！n"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; else cout<<"正在为等候的乘客"

42、;<<Q->name<<"办理订票！n"Book(p,pi.end,Q->ticket,Q->name,N); q->next=Q->next; 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<<&qu

43、ot;很抱歉，没有t航班信息，无法为你退票，请核实信息 ！nn"return 0;void CreatPlane(PlaneLink *p,int n,int N)int i,j；for(i=N;i<N+n;i+)pi.first=NULL; /带头结点的单链表为空时的条件pi.Q.front=pi.Q.rear=NULL; / 队列为空时的条件cout<<">>>>>>n"cout<<"请输入航班号："cin>>pi.number;cout<<"

44、;输入终点站名："； cin>>pi.end;for( j=0;j<N;j+)if(strcmp(pi.number,pj.number)=0) / 查看该航班号是否已经存在cout<<"已经存在该航班号！n " break;if(strcmp(pi.end,pj.end)=0) /查看是否存在到改站点的航班cout<<"已经有到该站点的航班！n " break;if(j=N)cout<<"飞机号、飞行日期、成员定额：n"cin>>pi.planenum>

45、;>pi.date>>pi.dinge;pi.tick=pi.dinge; pi.k=0;cout<<”录入完成！n"int display(PlaneLink *p,int N) /N 为当前的航班数(cout<<"=n"cout<<" 航班号 飞机号 终点站飞行日期定额 余票数排队等候人数n"cout<<"n" for(int i=0;i<N;i+) (cout<<setw(9)<<pi.number<<setw(6)<<pi.planenum<<setw(12)<<pi.end<<setw(12)<<pi.date<<setw(10)<< pi.dinge<<setw(10)<<pi.tick<<setw(10)<<