Graph.c

一是让学习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题来说，所要求实现的是：图的邻接表存贮结构，输出该图中的元素。

二是通过实习巩固并提高实习者的C语言知识，提高其编程能力与专业水平。 二．问题描述

以邻接表存储图，并对图进行遍历，根据提示从键盘输入相应的内容来实现相应的功能。 数据结构设计： typedef struct ArcNode {

int adjvex;

struct ArcNode *nextArc; }ArcNode;

adjvex

typedef struct VNode {

char data; ArcNode *firstArc;

}VNode, AdjList[MAX_VERTEXT_NUM];

nextArc nextArc

typedef struct {

AdjList verTices; int vexNum; int arcNum; }ALGraph;

verTices

三．功能（函数）设计

vexNum firstArc arcNum 1.void CreateGraph(ALGraph *G)//以邻接表存储一个图 2.void DisplayGraph(ALGraph *G)//输出图中的每一个元素 该程序的流程图为：

DisplayGraph（） CreateGraph（） Main（） 四、实验结果（程序）及分析 1.实验的的源代码及相关的注释：

//包含头文件 #include #include

#define MAX_VERTEXT_NUM 20 //宏定义

typedef struct ArcNode//边表结点 {

int adjvex;//邻接点域

struct ArcNode *nextArc;//链域 }ArcNode;

typedef struct VNode//顶点表结点 {

char data;//顶点域

ArcNode *firstArc;//边表头指针 }VNode, AdjList[MAX_VERTEXT_NUM];

typedef struct//定义了一个结构体，里面有三个成员 {

AdjList verTices;//相当于定义了一个元素类型为 struct VNode的

数组

int vexNum;//用来存输入的顶点数 int arcNum;//用来存输入的边数 //int kind; }ALGraph;

//函数声明

void CreateGraph(ALGraph *G);//建立图的邻接表 void DisplayGraph(ALGraph *G);//输出图中的每一个元素

void main() {

ALGraph *Graph = (ALGraph *)malloc(sizeof(ALGraph));//动态分配内存

CreateGraph(Graph); DisplayGraph(Graph); }

void CreateGraph(ALGraph *G)//以邻接表存储一个图 {

int i,j,k;

ArcNode *arcNode;//定义边表结点 printf(\"请输入顶点数和边数：\");

scanf(\"%d%d\

//建立顶点表

printf(\"建立顶点表\\n\"); for (i = 0; i < G->vexNum; i++) {

printf(\"请输入第%d个顶点:\

fflush(stdin);//刷新缓冲区，不能省略，省去可能会出错 G->verTices[i].data = getchar();//读入顶点信息 G->verTices[i].firstArc = NULL;//边表置为空表

}

//建立边表

printf(\"建立边表\\n\");

for (k = 0; k < G->arcNum; k++) {

printf(\"请输入（vi-vj）的顶点对序号\");

scanf(\"%d%d\读入边（Vi，Vj）的顶点对序号 arcNode = (ArcNode *)malloc(sizeof(ArcNode));//生成边表结点

arcNode->adjvex = j;//邻接点序号为j

arcNode->nextArc = G->verTices[i].firstArc;//插入表头 G->verTices[i].firstArc = arcNode;//将新结点插入顶点Vi的边表头部

arcNode = (ArcNode *)malloc(sizeof(ArcNode)); arcNode->adjvex = i;//邻接点序号为i

arcNode->nextArc = G->verTices[j].firstArc;//插入表头 G->verTices[j].firstArc = arcNode;//将新结点插入顶点Vj的边表头部 } }

void DisplayGraph(ALGraph *G)//输出图中的每一个元素 { int i;

for (i = 0; i < G->vexNum; i++) {

printf(\"%d->\

while (G->verTices[i].firstArc != NULL) {

printf(\"%d->\

G->verTices[i].firstArc G->verTices[i].firstArc->nextArc; }

printf(\"\\n\"); } }

2.测试数据

输入顶点数为4，边数为5，该图为：

经程序运行测试，结果如下：

2 1 3 0 =

五．实验总结

这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思想和大纲,让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。总之，在这实验中，自己的C语言以及数据结构知识得到提高，编程能力也得到了提高。