图的存储结构与遍历 数据结构实验.docx
- 文档编号:14826653
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:22
- 大小:60.81KB
图的存储结构与遍历 数据结构实验.docx
《图的存储结构与遍历 数据结构实验.docx》由会员分享,可在线阅读,更多相关《图的存储结构与遍历 数据结构实验.docx(22页珍藏版)》请在冰点文库上搜索。
图的存储结构与遍历数据结构实验
实验报告
June11
2015
姓名:
陈斌学号:
E11314079专业:
13计算机科学与技术
数据结构第七次实验
学号E11314079专业计算机科学与技术姓名陈斌
实验日期2015.06.11教师签字成绩
实验报告
【实验名称】图的存储结构与遍历
【实验目的】
(1)掌握图的相关概念;
(2)掌握图的存储结构;
(3)掌握图的遍历算法并编程实现。
【实验内容】
编写一个程序,实现图的相关运算,并在此基础上设计一个主程序,完成如下功能:
(1)建立如教材图7.9所示的有向图G的邻接矩阵,并分别输出顶点表和邻接矩阵。
(2)由有向图G的邻接矩阵产生邻接表,并依次输出每一顶点和其邻接表。
(3)再由
(2)的邻接表产生对应的邻接矩阵,并输出该矩阵。
(4)在图G的邻接矩阵存储表示基础上,输出从顶点V1开始的深度优先遍历序列(递归算法)。
(5)在图G的邻接表存储表示基础上,输出从顶点V1开始的广度优先遍历序列。
(6)利用非递归算法重解任务(4)(选做)。
源代码:
head.h:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
//OVERFLOW在math.h中已定义为3
typedefintStatus;
typedefintBoolean;//布尔类型
main.cpp:
#include"head.h"
#defineMAX_NAME5/*顶点字符串的最大长度+1*/
#defineMAX_INFO20/*相关信息字符串的最大长度+1*/
typedefintVRType;
typedefintInfoType;
typedefcharVertexType[MAX_NAME];
#defineINFINITYINT_MAX/*用整型最大值代替∞*/
#defineMAX_VERTEX_NUM20/*最大顶点个数*/
typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/
/*图的数组(邻接矩阵)存储表示*/
typedefstruct
{
VRTypeadj;/*顶点关系类型。
对无权图,用1(是)或0(否)表示相邻否;对带权图,c则为权值类型*/
InfoType*info;/*该弧相关信息的指针(可无)*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/
AdjMatrixarcs;/*邻接矩阵*/
intvexnum,arcnum;/*图的当前顶点数和弧数*/
GraphKindkind;/*图的种类标志*/
}MGraph;
/*图的邻接表存储表示*/
typedefstructArcNode
{
intadjvex;/*该弧所指向的顶点的位置*/
structArcNode*nextarc;/*指向下一条弧的指针*/
InfoType*info;/*该弧相关信息的指针*/
}ArcNode;/*表结点*/
typedefstruct
{
VertexTypedata;/*顶点信息*/
ArcNode*firstarc;/*第一个表结点的地址,指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM];/*头结点*/
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;/*图的当前顶点数和弧数*/
intkind;/*图的种类标志*/
}ALGraph;
intLocateVex(MGraphG,VertexTypeu)
{/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
for(inti=0;i if(strcmp(u,G.vexs[i])==0) returni; return-1; } StatusCreateDG(MGraph&G) {/*采用数组(邻接矩阵)表示法,构造有向图G*/ inti,j,k; VertexTypeva,vb; VRTypew; cout<<"请输入有向图G的顶点数弧数(用空格隔开): "; cin>>G.vexnum>>G.arcnum; cout<<"请输入"< \n"; for(i=0;i cin>>G.vexs[i]; for(i=0;i for(j=0;j { G.arcs[i][j].adj=INFINITY;/*图*/ G.arcs[i][j].info=NULL; } cout<<"请输入"< \n"; for(k=0;k { cin>>va>>vb>>w; i=LocateVex(G,va); j=LocateVex(G,vb); G.arcs[i][j].adj=w; } G.kind=DG; returnOK; } voidPrintAdjMatrix(MGraphG)//输出邻接矩阵 { charch='*'; cout<<"-----------------------"< cout<<""; for(inti=0;i cout< cout< for(i=0;i { cout< for(intj=0;j { if(G.arcs[i][j].adj==INFINITY) cout< else cout< } cout< } cout<<"-----------------------"< } voiddisplay(MGraphG)//输出顶点表和邻接矩阵 { cout<<"-----------------------"< cout<<"顶点表: \n"; for(inti=0;i cout< cout<<"\n-----------------------"< cout<<"\n邻接矩阵('*'代表无穷大): \n"; PrintAdjMatrix(G); } voidCreateMGtoDN(ALGraph&G2,MGraph&G) { //由有向图G的邻接矩阵产生邻接表 ArcNode*p; G2.kind=G.kind; G2.vexnum=G.vexnum; G2.arcnum=G.arcnum; for(inti=0;i {//构造表头向量 strcpy(G2.vertices[i].data,G.vexs[i]); G2.vertices[i].firstarc=NULL;//初始化指针 } for(i=0;i for(intj=0;j if(G.arcs[i][j].adj! =INFINITY) { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=G2.vertices[i].firstarc; p->info=G.arcs[i][j].info; G2.vertices[i].firstarc=p; } } voidPrintAdjList(ALGraphG)//输出邻接表 { cout<<"-----------------------"< for(inti=0;i { ArcNode*p=G.vertices[i].firstarc; cout< while(p) { cout<<"→"< p=p->nextarc; } cout< } cout<<"-----------------------"< } voidCreateDNtoMG(MGraph&G3,ALGraph&G2) {//由邻接表产生对应的邻接矩阵 inti,j; ArcNode*p; G3.kind=GraphKind(G2.kind); G3.vexnum=G2.vexnum; G3.arcnum=G2.arcnum; for(i=0;i strcpy(G3.vexs[i],G2.vertices[i].data); for(i=0;i { p=G2.vertices[i].firstarc; while(p) { G3.arcs[i][p->adjvex].adj=1; p=p->nextarc; }//while for(j=0;j if(G3.arcs[i][j].adj! =1) G3.arcs[i][j].adj=INFINITY; }//for } Booleanvisited[MAX_VERTEX_NUM];/*访问标志数组(全局量)*/ void(*VisitFunc)(char*v);/*函数变量(全局量)*/ //从第v个顶点出发递归地深度优先遍历图G。 /*查找第1个邻接点*/ intFirstAdjVex(MGraph&G,intv) { for(intm=0;m if(G.arcs[v][m].adj! =INFINITY) returnm; return-1; } /*查找下一个邻接点*/ intNextAdjVex(MGraph&G,intv,intw) { for(intj=w+1;j if(G.arcs[v][j].adj! =INFINITY) returnj; return-1; } voidDFS(MGraph&G,intv) {//从第v个顶点出发递归地深度优先遍历图G cout< visited[v]=TRUE; for(intw=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))//访问第W个顶点 if(! visited[w])//对v的尚未访问的邻接点w递归调用DFS DFS(G,w); } voidvisits(MGraph&G,int&v) {//判断结点是否已经访问过 v=-1; for(inti=0;i if(! visited[i]) v=i; } voidDFSTraverse(MGraphG,intv) {//对图G作深度优先遍历 for(inti=0;i visited[i]=FALSE;//访问标志数组初始化 while(v>=0&&v { DFS(G,v); visits(G,v); } } /*栈的顺序存储表示*/ typedefintSElemType;/*栈类型*/ #defineSTACK_INIT_SIZE10/*存储空间初始分配量*/ #defineSTACKINCREMENT2/*存储空间分配增量*/ typedefstructSqStack { SElemType*base;/*在栈构造之前和销毁之后,base的值为NULL*/ SElemType*top;/*栈顶指针*/ intstacksize;/*当前已分配的存储空间,以元素为单位*/ }SqStack;/*顺序栈*/ StatusInitStack(SqStack&S) {/*构造一个空栈S*/ S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(! S.base) exit(OVERFLOW);/*存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnOK; } StatusStackEmpty(SqStack&S) {/*若栈S为空栈,则返回TRUE,否则返回FALSE*/ if(S.top==S.base) returnTRUE; else returnFALSE; } StatusPush(SqStack&S,SElemTypee) {/*插入元素e为新的栈顶元素*/ if(S.top-S.base>=S.stacksize)/*栈满,追加存储空间*/ { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(! S.base) exit(OVERFLOW);/*存储分配失败*/ S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *(S.top)++=e; returnOK; } StatusPop(SqStack&S,SElemType&e) {/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/ if(S.top==S.base) returnERROR; e=*--S.top; returnOK; } voidDFSTraverse2(MGraphG,intv) {//对图G作深度优先遍历(非递归算法) SqStacks; InitStack(s); for(inti=0;i visited[i]=FALSE;//访问标志数组初始化 Push(s,v); while(! StackEmpty(s))//对尚未访问的顶点调用DFS { intflag=0; Pop(s,v); if(! visited[v]) { cout< visited[v]=TRUE; } for(intj=0;j if((! visited[j])&&(G.arcs[v][j].adj! =INFINITY)) { Push(s,j); flag=1; break; } if(! flag) { visits(G,v); if(v>=0&&v Push(s,v); else break; } } } typedefintQElemType;/*队列类型*/ /*单链队列--队列的链式存储结构*/ typedefstructQNode { QElemTypedata; structQNode*next; }QNode,*QueuePtr; typedefstruct { QueuePtrfront,rear;/*队头、队尾指针*/ }LinkQueue; StatusInitQueue(LinkQueue&Q) {/*构造一个空队列Q*/ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(! Q.front) exit(OVERFLOW); Q.front->next=NULL; returnOK; } StatusQueueEmpty(LinkQueue&Q) {/*若Q为空队列,则返回TRUE,否则返回FALSE*/ if(Q.front==Q.rear) returnTRUE; else returnFALSE; } StatusEnQueue(LinkQueue&Q,QElemTypee) {/*插入元素e为Q的新的队尾元素*/ QueuePtrp=(QueuePtr)malloc(sizeof(QNode)); if(! p)/*存储分配失败*/ exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK; } StatusDeQueue(LinkQueue&Q,QElemType&e) {/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/ QueuePtrp; if(Q.front==Q.rear) returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); returnOK; } intLocateVex(ALGraphG,VertexTypeu) {/*初始条件: 图G存在,u和G中顶点有相同特征*/ /*操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/ inti; for(i=0;i if(strcmp(u,G.vertices[i].data)==0) returni; return-1; } VertexType*GetVex(ALGraphG,intv) {/*初始条件: 图G存在,v是G中某个顶点的序号。 操作结果: 返回v的值*/ if(v>=G.vexnum||v<0) exit(ERROR); return&G.vertices[v].data; } intFirstAdjVex(ALGraphG,VertexTypev) {/*初始条件: 图G存在,v是G中某个顶点*/ /*操作结果: 返回v的第一个邻接顶点的序号。 若顶点在G中没有邻接顶点,则返回-1*/ ArcNode*p; intv1; v1=LocateVex(G,v);/*v1为顶点v在图G中的序号*/ p=G.vertices[v1].firstarc; if(p) returnp->adjvex; else return-1; } intNextAdjVex(ALGraphG,VertexTypev,VertexTypew) {/*初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点*/ /*操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */ /*若w是v的最后一个邻接点,则返回-1*/ ArcNode*p; intv1,w1; v1=LocateVex(G,v);/*v1为顶点v在图G中的序号*/ w1=LocateVex(G,w);/*w1为顶点w在图G中的序号*/ p=G.vertices[v1].firstarc; while(p&&p->adjvex! =w1)/*指针p不空且所指表结点不是w*/ p=p->nextarc; if(! p||! p->nextarc)/*没找到w或w是最后一个邻接点*/ return-1; else/*p->adjvex==w*/ returnp->nextarc->adjvex;/*返回v的(相对于w的)下一个邻接顶点的序号*/ } voidBFSTraverse(ALGraphG,void(*Visit)(char*)) {/*按广度优先非递归遍历图G。 使用辅助队列Q和访问标志数组visited。 算法7.6*/ intv,u,w; VertexTypeu1,w1; LinkQueueQ; for(v=0;v visited[v]=FALSE;/*置初
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图的存储结构与遍历 数据结构实验 存储 结构 遍历 数据结构 实验