数据结构实验-图实验报告

数据结构实验报告

目的要求１．掌握图的存储思想及其存储实现..２．掌握图的深度、广度优先遍历算法思想及其程序实现..３．掌握图的常见应用算法的思想及其程序实现..实验内容１．键盘输入数据;建立一个有向图的邻接表..２．输出该邻接表..3．在有向图的邻接表的基础上计算各顶点的度;并输出..4．以有向图的5．采用邻接表存储实现6．采用邻接表存储实现7．在主函数中设计一个简单的邻接表为基础实现输出它的拓扑排序序列..无向图的深度优先递归遍历..无向图的广度优先遍历..菜单;分别调试上述算法..源程序：主程序的头文件：队列#include<stdio.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintQElemType;typedefstructQNode{//队的操作QElemTypedata;structQNode*next;}QNode;*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;voidInitQueueLinkQueue&Q{//初始化队列Q.front=Q.rear=QueuePtrmallocsizeofQNode;ifQ.frontexitOVERFLOW;//存储分配失败Q.front->next=NULL;}intEnQueueLinkQueue&Q;QElemTypee//插入元素e为Q的新的队尾元素{QueuePtrp;p=QueuePtrmallocsizeofQNode;ifpexitOVERFLOW;p->data=e;

p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}intDeQueueLinkQueue&Q;QElemType&e//删除Q的队头元素;用e返回其值{ifQ.front==Q.rearreturnERROR;QueuePtrp;p=Q.front->next;e=p->data;Q.front->next=p->next;ifQ.rear==pQ.rear=Q.front;freep;returnOK;}主程序：#include<stdio.h>#include<stdlib.h>#include"duilie.h"#defineTRUE1#defineFALSE0#defineStatusint#defineMAX_VERTEX_NUM8/*顶点最大个数#defineVertexTypechar/*顶点元素类型enumBOOlean{False;True};*/*/BOOleanvisitedMAX_VERTEX_NUM;//全局变量——访问标志数组typedefstructArcNode{intadjvex;structArcNode*nextarc;intweight;/*边的权*/}ArcNode;/*表结点*/typedefstructVNode{intdegree;indegree;/*顶点的度;入度*/VertexTypedata;ArcNode*firstarc;}VNode/*头结点*/;AdjListMAX_VERTEX_NUM;typedefstruct{AdjListvertices;intvexnum;arcnum;/*顶点的实际数;边的实际数*/}ALGraph;//建立图的邻接表voidcreat_linkALGraph*G{inti;j;ArcNode*s;

printf"请依次输入顶点数、边数：";scanf"%d%d";&G->vexnum;&G->arcnum;fori=0;i<G->vexnum;i++{G->verticesi.data='A'+i;G->verticesi.firstarc=NULL;}fori=0;i<G->vexnum;{printf"请输入顶点的数组坐标若退出;请输入-1：";scanf"%d";&i;ifi==-1break;printf"请输入顶点所指向下一个顶点的数组坐标：";scanf"%d";&j;s=ArcNode*mallocsizeofArcNode;s->adjvex=j;s->nextarc=G->verticesi.firstarc;G->verticesi.firstarc=s;}}//输出邻接表voidvisitALGraphG{inti;ArcNode*p;printf"%4s%6s%18s\n";"NO";"data";"adjvexsofarcs";fori=0;i<G.vexnum;i++{printf"%4d%5c";i;G.verticesi.data;forp=G.verticesi.firstarc;p;p=p->nextarcprintf"%3d";p->adjvex;printf"\n";}}//计算各顶点的度及入度voidcacuALGraph*G{ArcNode*p;inti;fori=0;i<G->vexnum;i++{G->verticesi.degree=0;G->verticesi.indegree=0;}//度与初度初始化为零fori=0;i<G->vexnum;i++forp=G->verticesi.firstarc;p;p=p->nextarc{G->verticesi.degree++;G->verticesp->adjvex.degree++;G->verticesp->adjvex.indegree++;}

}voidprint_degreeALGraphG{inti;printf"\nNomdatadegreeindegree\n";fori=0;i<G.vexnum;i++printf"\n%4d%5c%7d%8d";i;G.verticesi.data;G.verticesi.degree;G.verticesi.indegree;printf"\n";}//拓扑排序StatusTopologiSortALGraphG{inti;count;top=0;stack50;ArcNode*p;cacu&G;print_degreeG;printf"\nTopologiSortis\n";fori=0;i<G.vexnum;i++ifG.verticesi.indegreestacktop++=i;count=0;whiletop=0{i=stack--top;ifcount==0printf"%c";G.verticesi.data;elseprintf"-->%c";G.verticesi.data;count++;forp=G.verticesi.firstarc;p;p=p->nextarcif--G.verticesp->adjvex.indegreestacktop++=p->adjvex;}ifcount<G.vexnumreturnFALSE;elsereturnTRUE;}//在图G中寻找第v个顶点的第一个邻接顶点intFirstAdjVexALGraphG;intv{ifG.verticesv.firstarcreturn0;elsereturnG.verticesv.firstarc->adjvex;}//在图G中寻找第v个顶点的相对于u的下一个邻接顶点intNextAdjVexALGraphG;intv;intu{ArcNode*p;p=G.verticesv.firstarc;whilep->adjvex=up=p->nextarc;//在顶点v的弧链中找到顶点uifp->nextarc==NULLreturn0;//若已是最后一个顶点;返回0

elsereturnp->nextarc->adjvex;//返回下一个邻接顶点的序号}//采用邻接表存储实现无向图的深度优先递归遍历voidDFSALGraphG;inti{intw;visitedi=True;//访问第i个顶点printf"%d->";i;forw=FirstAdjVexG;i;w;w=NextAdjVexG;i;wifvisitedwDFSG;w;//对尚未访问的邻接顶点w调用DFS}voidDFSTraverseALGraphG{inti;printf"DFSTraverse:";fori=0;i<G.vexnum;i++visitedi=False;//访问标志数组初始化fori=0;i<G.vexnum;i++ifvisitediDFSG;i;//对尚未访问的顶点调用DFS}//按广度优先非递归的遍历图G;使用辅助队列Q和访问标志数组visitedvoidBFSTraverseALGraphG{inti;u;w;LinkQueueQ;printf"BFSTreverse:";fori=0;i<G.vexnum;i++visitedi=False;//访问标志数组初始化InitQueueQ;//初始化队列fori=0;i<G.vexnum;i++ifvisitedi{visitedi=True;//访问顶点iprintf"%d->";i;EnQueueQ;i;//将序号i入队列whileQ.front==Q.rear//若队列不空;继续{DeQueueQ;u;//将队头元素出队列并置为uforw=FirstAdjVexG;u;w;w=NextAdjVexG;u;wifvisitedw//对u的尚未访问的邻接顶点w进行访问并入队列{visitedw=True;printf"%d->";w;EnQueueQ;w;}}}}voidmain{ALGraphG;

intselect;printf"do{图的有关操作实验\n";printf"\n1创建printf"3.输出该有向图的度和入度printf"5.创建一个无向图的邻接表一个有向图的邻接表2输出该邻接表\n";4.输出该有拓扑排序序列\n";6.深度优先递归遍历该无向图\n";0.退出向图printf"7.广度优先遍历该无向图printf"请输入选择：";scanf"%d";&select;switchselect{\n";case1:printf"\n创建一个有向图的邻接表：\n";creat_link&G;break;case2:printf"\n输出该邻接表：\n";visitG;break;case3:printf"\n输出该有向图的度和入度：\n";cacu&G;print_degreeG;break;case4:printf"\n输出该有向图拓扑排序序列：\n";ifTopologiSortGprintf"Toposortisnotsuccess";break;case5:printf"\n创建一个无向图的邻接表:\n";creat_link&G;break;case6:printf"\n深度优先递归遍历该无向图:\n";DFSTraverseG;break;case7:printf"\n广度优先遍历该无向图：\n";BFSTraverseG;break;case0:break;default:printf"输入选项错误重新输入\n";}

}2.创建一个有向图的领接表4.在有向图的邻接表的基础上计算各顶点的度;并输出..5.输出它的拓扑排序序列6.输出所建无向图的邻接表7.