《数据结构实验指导书》

第一部分 上机实践

-31-

第一部分 上机实践

（4）程序运行结果

省略创建图时的输入内容，只须画出预创建的无向图。然后给出程序的运行结果。

-32-

第一部分 上机实践

2．图的邻接表表示法的实现

（1）图的邻接表表示及相关操作的定义。将如下代码设计完整，并保存为“ALGraph.h”。

#define MaxVexNum 20 struct arcNode { int adjVex;

struct arcNode *nextArc; };

struct vexElem { VexType data;

struct arcNode *firstArc; };

typedef struct

{ struct vexElem vexs[MaxVexNum]; int vexNum,arcNum; int kind;

} ALGraph; //图的邻接表类型

int compareTo(VexType v1,VexType v2); //顶点元素的比较函数声明 int LocateVex(ALGraph &G, VexType v)

//在图G中查找顶点v，若存在返回位置，否则返回-1 { }

void InputVexInfo(VexType v); //顶点信息输入函数声明 void CreatDG(ALGraph &G) //有向图的创建 { //代码略 }

void findIndegree(ALGraph &G, int indegree[]) //求每个顶点的入度，存于indegree数组中 { int i;

struct arcNode *p;

for(i=0;i

{ indegree[p->adjVex]++; p=p->nextArc; } } }

-33-

第一部分 上机实践

（2）图的邻接矩阵表示的测试程序及应用

以下实现了对“ALGraph.h”中图的邻接矩阵表示及其操作的测试示例程序。并且程序还实现了有向图拓扑排序算法。

#include #include #include \

typedef char VexType[20]; //顶点类型为字符数组类型 #include \

typedef int SElemType; //定义栈中元素类型为int类型 #include \

int compareTo(VexType v1,VexType v2)//顶点元素的比较函数定义 { return strcmp(v1,v2); }

void InputVexInfo(VexType v) //顶点信息输入函数定义 { scanf(\}

void GraphOutput(ALGraph &G) //邻接表的输出 { int i;

struct arcNode *p;

printf(\.kind); for(i=0;i

{ printf(\ p=G.vexs[i].firstArc; while(p)

{ printf(\ } printf(\ } }

Status TopSort(ALGraph &G) /*利用栈和求入度函数对有向图G进行拓扑排序。若能够进行拓扑排序，则输出拓扑序列，函数返回TRUE；否则返回FALSE*/

{ //代码略 }

int main()

{ ALGraph G;

CreatDG(G); GraphOutput(G); printf(\拓扑序列：\

if( !TopSort(G) ) printf(\图中存在有向环路，拓扑序列不完整！\\n\ return 0; }

-34-