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

实 验 报 告

目的要求

１．掌握图的存储思想及其存储实现。

２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。

实验内容

１．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。

3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。

6．采用邻接表存储实现无向图的广度优先遍历。

7．在主函数中设计一个简单的菜单，分别调试上述算法。

源程序：

主程序的头文件：队列 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define OVERFLOW -2 typedef int QElemType;

typedef struct QNode{ //队的操作 QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue;

void InitQueue(LinkQueue &Q){ //初始化队列

Q.front =Q.rear =(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); //存储分配失败 Q.front ->next =NULL; }

int EnQueue(LinkQueue &Q,QElemType e) //插入元素e为Q的新的队尾元素 {

QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e;

p->next=NULL; Q.rear->next=p; Q.rear =p; return OK; }

int DeQueue(LinkQueue &Q,QElemType &e) //删除Q的队头元素，用e返回其值 { if(Q.front ==Q.rear ) return ERROR; QueuePtr p; p=Q.front ->next; e=p->data;

Q.front->next=p->next ;

if(Q.rear==p) Q.rear =Q.front ; free(p); return OK; }

主程序：

#include #include #include\"duilie.h\" #define TRUE 1 #define FALSE 0 #define Status int

#define MAX_VERTEX_NUM 8 /*顶点最大个数*/ #define VertexType char /*顶点元素类型*/ enum BOOlean {False,True};

BOOlean visited[MAX_VERTEX_NUM]; //全局变量——访问标志数组 typedef struct ArcNode {int adjvex;

struct ArcNode *nextarc; int weight; /*边的权*/ }ArcNode; /*表结点*/ typedef struct VNode { int degree,indegree;/*顶点的度，入度*/ VertexType data; ArcNode *firstarc;

}VNode/*头结点*/,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices;

int vexnum,arcnum;/*顶点的实际数，边的实际数*/ }ALGraph;

//建立图的邻接表

void creat_link(ALGraph *G) { int i,j;

ArcNode *s;

printf(\"请依次输入顶点数、边数：\");

scanf(\"%d%d\ for (i=0;ivexnum;i++) { G->vertices[i].data='A'+i; G->vertices[i].firstarc=NULL; }

for (i=0;ivexnum;) { printf(\"请输入顶点的数组坐标(若退出，请输入-1)：\"); scanf(\"%d\ if(i==-1) break; printf(\"请输入顶点所指向下一个顶点的数组坐标：\"); scanf(\"%d\

s=(ArcNode *)malloc(sizeof(ArcNode)); s->adjvex=j;

s->nextarc=G->vertices[i].firstarc; G->vertices[i].firstarc=s; } }

// 输出邻接表

void visit(ALGraph G) { int i;

ArcNode *p;

printf(\"%4s%6s%18s\\n\ for (i=0;inextarc) printf(\"%3d\ printf(\"\\n\"); } }

// 计算各顶点的度及入度 void cacu(ALGraph *G) { ArcNode *p; int i;

for (i=0;ivexnum;i++)

{G->vertices[i].degree=0;G->vertices[i].indegree=0;}//度与初度初始化为零 for (i=0;ivexnum;i++)

for(p=G->vertices[i].firstarc;p;p=p->nextarc) {G->vertices[i].degree++;

G->vertices[p->adjvex].degree++; G->vertices[p->adjvex].indegree++; }

}

void print_degree(ALGraph G) {

int i;

printf(\"\\n Nom data degree indegree\\n\"); for (i=0;iprintf(\"\\n%4d%5c%7d%8d\.vertices[i].data, G.vertices[i].degree,G.vertices[i].indegree); printf(\"\\n\"); }

// 拓扑排序

Status TopologiSort(ALGraph G) {int i,count,top=0,stack[50]; ArcNode *p; cacu(&G);

print_degree(G);

printf(\"\\nTopologiSort is \\n\"); for(i=0;iif(!G.vertices[i].indegree) stack[top++]=i; count=0; while(top!=0) {

i=stack[--top];

if (count==0) printf(\"%c\.vertices[i].data); else printf(\"-->%c\.vertices[i].data); count++;

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

if (!--G.vertices[p->adjvex].indegree)stack[top++]=p->adjvex; }

if (count//在图G中寻找第v个顶点的第一个邻接顶点 int FirstAdjVex(ALGraph G,int v) {

if(!G.vertices[v].firstarc) return 0;

else return(G.vertices[v].firstarc->adjvex); }

//在图G中寻找第v个顶点的相对于u的下一个邻接顶点 int NextAdjVex(ALGraph G,int v,int u) {

ArcNode *p;

p=G.vertices[v].firstarc;

while(p->adjvex!=u) p=p->nextarc; //在顶点v的弧链中找到顶点u if(p->nextarc==NULL) return 0; //若已是最后一个顶点，返回0

else return(p->nextarc->adjvex); //返回下一个邻接顶点的序号 }

//采用邻接表存储实现无向图的深度优先递归遍历 void DFS(ALGraph G,int i) { int w;

visited[i]=True; //访问第i个顶点 printf(\"%d->\

for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w))

if(!visited[w]) DFS(G,w); //对尚未访问的邻接顶点w调用DFS }

void DFSTraverse(ALGraph G) { int i;

printf(\"DFSTraverse:\");

for(i=0;iif(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS }

//按广度优先非递归的遍历图G，使用辅助队列Q和访问标志数组visited void BFSTraverse(ALGraph G) {

int i,u,w;

LinkQueue Q;

printf(\"BFSTreverse:\");

for(i=0;i{visited[i]=True; //访问顶点i printf(\"%d->\

EnQueue(Q,i); //将序号i入队列

while(!(Q.front ==Q.rear)) //若队列不空，继续 {DeQueue(Q,u); //将队头元素出队列并置为u

for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))

if(!visited[w]) //对u的尚未访问的邻接顶点w进行访问并入队列 { visited[w]=True; printf(\"%d->\ EnQueue(Q,w); } } } }

void main() {

ALGraph G;

int select; printf(\" 图的有关操作实验\\n \"); do{ printf(\"\\n1 创建一个有向图的邻接表 2 输出该邻接表\\n\"); printf(\"3.输出该有向图的度和入度 4.输出该有向图拓扑排序序列 \\n\"); printf(\"5.创建一个无向图的邻接表 6.深度优先递归遍历该无向图\\n\"); printf(\"7.广度优先遍历该无向图 0.退出 \\n\"); printf(\"请输入选择： \"); scanf(\"%d\ switch(select){ case 1: printf(\"\\n创建一个有向图的邻接表：\\n\"); creat_link(&G); break; case 2: printf(\"\\n输出该邻接表：\\n\"); visit(G); break; case 3: printf(\"\\n输出该有向图的度和入度：\\n\"); cacu(&G); print_degree(G); break; case 4: printf(\"\\n输出该有向图拓扑排序序列：\\n\");

if(!TopologiSort(G))printf(\"Toposort is not success!\"); break; case 5: printf(\"\\n创建一个无向图的邻接表: \\n\"); creat_link(&G); break; case 6: printf(\"\\n深度优先递归遍历该无向图: \\n\"); DFSTraverse(G); break; case 7: printf(\"\\n广度优先遍历该无向图：\\n\"); BFSTraverse(G); break; case 0: break; default: printf(\"输入选项错误！重新输入！\\n\"); }

}

}while(select);

运行结果截图：

1. 主菜单界面：

2.创建一个有向图的领接表

3.输出该邻接表

4. 在有向图的邻接表的基础上计算各顶点的度，并输出。

5. 输出它的拓扑排序序列

6. 输出所建无向图的邻接表

7. 深度优先递归遍历该无向图

8. 广度优先遍历该无向图

说明：

本实验用的有向图是课本182页图7.28，无向图为课本168页图（a）

实验总结

这次的图的操作实验，与树的操作类似，但又比树复杂，包含更多的存储

结构和遍历方法的操作，而且图的遍历需要沿着弧进行，以便输出弧上的信息。本实验中图的遍历采用邻接表的存储结构，在输入图的信息时，首先要画出图的邻接表信息。图有两种遍历的形式，一种为深度优先搜索，另一种为广度优先搜索。由于能力有限，没能实现图的深度非递归优先搜索，而是实现了图的深度递归优先搜索。本实验基本完成了图的操作，也学到了很多关于图的知识和算法。