数 据 结 构
实验报告
目的要求
１．掌握图的存储思想及其存储实现。
２．掌握图的深度、广度优先遍历算法思想及其程序实现。
３．掌握图的常见应用算法的思想及其程序实现。
实验内容
１．键盘输入数据，建立一个有向图的邻接表。
２．输出该邻接表。
3．在有向图的邻接表的基础上计算各顶点的度，并输出。
4．以有向图的邻接表为基础实现输出它的拓扑排序序列。
5．采用邻接表存储实现无向图的深度优先递归遍历。
6．采用邻接表存储实现无向图的广度优先遍历。
7．在主函数中设计一个简单的菜单，分别调试上述算法。
源程序：
主程序的头文件：队列
#include <stdio.h>
#include <stdlib.h>
#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 <stdio.h>
#include<stdlib.h>
#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",&G->vexnum,&G->arcnum);
for (i=0;i<G->vexnum;i++)
{ G->vertices[i].data='A'+i;
G->vertices[i].firstarc=NULL;
}
for (i=0;i<G->vexnum;)
{ printf("请输入顶点的数组坐标(若退出，请输入-1)：");
scanf("%d",&i);
if(i==-1) break;
printf("请输入顶点所指向下一个顶点的数组坐标：");
scanf("%d",&j);
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","NO","data","adjvexs of arcs");
for (i=0;i<G.vexnum;i++)
{
printf("%4d%5c ",i,G.vertices[i].data);
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
printf("%3d",p->adjvex);
printf("\n");
}
}
// 计算各顶点的度及入度
void cacu(ALGraph *G)
{
ArcNode *p;
int i;
for (i=0;i<G->vexnum;i++)
{G->vertices[i].degree=0;G->vertices[i].indegree=0;}//度与初度初始化为零
for (i=0;i<G->vexnum;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;i<G.vexnum;i++)
printf("\n%4d%5c%7d%8d",i,G.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;i<G.vexnum;i++)
if(!G.vertices[i].indegree) stack[top++]=i;
count=0;
while(top!=0)
{
i=stack[--top];
if (count==0) printf("%c",G.vertices[i].data);
else printf("-->%c",G.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.vexnum)return(FALSE); else return(TRUE);
}
//在图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->",i);
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;i<G.vexnum;i++) visited[i]=False; //访问标志数组初始化
for(i=0;i<G.vexnum;i++)
if(!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<G.vexnum;i++) visited[i]=False; //访问标志数组初始化
InitQueue(Q); //初始化队列
for(i=0;i<G.vexnum;i++)
if(!visited[i])
{visited[i]=True; //访问顶点i
printf("%d->",i);
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->",w);
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",&select);
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）
实验总结
这次的图的操作实验，与树的操作类似，但又比树复杂，包含更多的存储结构和遍历方法的操作，而且图的遍历需要沿着弧进行，以便输出弧上的信息。本实验中图的遍历采用邻接表的存储结构，在输入图的信息时，首先要画出图的邻接表信息。图有两种遍历的形式，一种为深度优先搜索，另一种为广度优先搜索。由于能力有限，没能实现图的深度非递归优先搜索，而是实现了图的深度递归优先搜索。本实验基本完成了图的操作，也学到了很多关于图的知识和算法。