图形大数据结构实验

淮海工学院计算机科学系

实验报告书

课程名： 《数据结构》

题 目： 图形数据结构实验

班 级： 学 号： 姓 名：

评语： 成绩： 指导教师： 批阅时间： 年 月 日 文案大全

实用标准文档

图形数据结构实验报告要求

1目的与要求:

1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；

2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现（预习）； 3）掌握AOV-网普里姆构造最小生成树算法的数据结构和算法实现（待学）； 4）掌握AOE-网关路经的生成算法和实现（待学）；

5）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）； 6）认真书写实验报告,并按时提交（第12周周一提交）。

2 实验内容或题目

题目： 一、图形数据结构实验——图的建立与遍历。 内容：

1） 使用邻接矩阵和邻接表储表示分别实现如下给定的图1和或图2所示图的物理存储结

构。

2） 在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并

给出遍历结果（序列）。

V1 V2 V3 V4 V5 V6 V7 V8 图1 无向图

文案大全

实用标准文档

V1 V2 V3 V4 V5 V6 V7 V8 例2 有向图

题目：二、连通网的最小生成树及其应用实验（暂不做）

内容：对下图所示通信连通网，按照普里姆算法实现其最小生成树。

V1

6 V2

5 1 v4

5 v3

5 4 6 2

v6

3 v5

6 通信连通网（权值单位：百万元）

文案大全

实用标准文档

3 实验步骤与源程序 邻接矩阵

#include #include

#define MAX_VERTEX_NUM 8 #define OK 1 #define FALSE 0 #define Error -1 #define AdjType int #define OtherInfo int

int visited[MAX_VERTEX_NUM]; #define TRUE 1 #define MAXSIZE 6

typedef struct {

int element[MAXSIZE]; int front; int rear; }SeqQueue;

typedef enum{DG,DN,UDG,UDN} GraphKind; typedef char VertexData; typedef struct ArcNode {

AdjType adj; OtherInfo info; }ArcNode;

typedef struct {

VertexData vexs[MAX_VERTEX_NUM];

ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vernum,arcnum; GraphKind kind; }AdjMatrix;

int LocateVertex(AdjMatrix *G,VertexData v) {

int j=Error; int k;

for(k=0;kvernum;k++) if(G->vexs[k]==v) {

j=k; break; }

return (j);

文案大全

实用标准文档

}

int CreatUDG(AdjMatrix * G) {

int i,j,k;

VertexData v1,v2;

cout<<\"输入无向图的顶点数和边数：\"<>G->vernum; cin>>G->arcnum;

for(i=0;ivernum;i++) for(j=0;jvernum;j++) G->arcs[i][j].adj=0; cout<<\"输入图的顶点：\"<vernum;i++) {

cin>>G->vexs[i]; }

for(k=0;karcnum;k++) {

cout<<\"输入一条边的两顶点:\"<>v1; cin>>v2;

i=LocateVertex(G,v1); j=LocateVertex(G,v2); G->arcs[i][j].adj =1;

G->arcs[j][i].adj=G->arcs[i][j].adj ; }

return (OK); }

void Print(AdjMatrix * G) {

int i,j;

for(i=0;ivernum;i++) {

for(j=0;jarcnum;j++)

cout<arcs[i][j].adj<<\" \"; cout<void DepthFirstSearch(AdjMatrix * G,int v0) {

cout<vexs[v0]<for(int vi=1;vivernum;vi++) {

if(!visited[vi] && G->arcs[v0][vi].adj==1) DepthFirstSearch(G,vi);

文案大全

实用标准文档

} }

void InitQueue(SeqQueue * Q) {

Q->front=Q->rear=0; }

int Empty(SeqQueue * Q) {

if(Q->front=Q->rear=0) return (TRUE); else

return (Error); }

int EnterQueue(SeqQueue * Q,int x) {

if((Q->rear+1)%MAXSIZE==Q->front) {

cout<<\"队已满。\"<Q->element[Q->rear]=x;

Q->rear=(Q->rear+1)%MAXSIZE; return (TRUE); }

int DeleteQueue(SeqQueue * Q,int * x) {

if(Q->front=Q->rear) {

cout<<\"队空\"<*x=Q->element[Q->front];

Q->front=(Q->front+1)%MAXSIZE; return(*x); }

int FirstAdj(AdjMatrix * G,int v) {

int j,p=-1;

for(j=0;j<=G->vernum;j++) if(G->arcs[v][j].adj==1) {

p=j; break; }

return(p); }

文案大全

实用标准文档

int NextAdj(AdjMatrix * G,int v,int w) {

int j,p=-1;

for(j=w+1;jvernum;j++) if(G->arcs[v][j].adj==1) {

p=j; break; }

return(p); }

void BreadthFirstSearch(AdjMatrix * G,int v0) {

SeqQueue * Q;

Q=(SeqQueue *)malloc(sizeof(SeqQueue)); InitQueue(Q);

for(int i=0;ivernum;i++) visited[i]=FALSE; cout<vexs[v0]<while(!Empty(Q)) {

v=DeleteQueue(Q,&v);

for(w=0;wvernum;w++) {

if((G->arcs[v][w].adj!=0) &&(visited[w]==0)) {

cout<vexs[w]<void main() {

AdjMatrix * G;

G=(AdjMatrix *)malloc(sizeof(AdjMatrix)); CreatUDG(G); Print( G);

cout<<\"打印邻接矩阵\"<cout<<\"广度优先搜索：\"<文案大全

实用标准文档

BreadthFirstSearch(G,0); }

邻接表

#include #include #include #include #define OK 1 #define ERROR -1 #define TRUE 1 #define FALSE 0

#define maxvernum 10

#define maxsize (maxvernum+1) #define infinity 32768 typedef struct {

int element[maxsize]; int front; int rear; }Seqqueue;

int Enterqueue(Seqqueue *q,int x) {

if((q->rear+1)%maxsize!=q->front ) {

q->element [q->rear ]=x;

q->rear =(q->rear +1)%maxsize; return(TRUE); }

else {

return(FALSE); } }

int Deletequeue(Seqqueue *q,int *x) {

if(q->front==q->rear) {

return(FALSE); }

*x=q->element[q->front];

q->front =(q->front +1)%maxsize; return(TRUE); }

int visited[maxvernum]; typedef struct Arcnode {

文案大全

实用标准文档

int adjvex;

struct Arcnode *nextarc; }Arcnode;

typedef struct vexnode {

int data;

Arcnode *firstarc; }vexnode;

typedef struct {

vexnode vexs[maxvernum]; int vexnum,arcnum; }Adjlist;

int Locate(Adjlist *g,int v) {

int k;

for(k=0;kvexnum;k++) {

if(g->vexs[k].data==v) {

return k; } }

return -1; }

void Create(Adjlist *g) {

int i,j,k,v1,v2;

cout<<\"请输入顶点数和弧数:\"<>g->vexnum>>g->arcnum; for(i=0;ivexnum;i++) {

g->vexs[i].data=i+1;

g->vexs[i].firstarc=NULL; }

cout<<\"打印顶点数据:\"<vexnum;i++) {

cout<<\"a\"<vexs[i].data<<\" \"; }

cout<for(k=0;karcnum;k++) {

cout<<\"请输入第\"<>v1>>v2;

文案大全

实用标准文档

i=Locate(g,v1); j=Locate(g,v2); if(i>=0&&j>=0) {

Arcnode *p,*q;

p=(Arcnode *)malloc(sizeof(Arcnode)); p->adjvex=j; p->nextarc=NULL;

if(!g->vexs[i].firstarc) g->vexs[i].firstarc=p; else {

q=g->vexs[i].firstarc; while(q->nextarc) {

q=q->nextarc; }

q->nextarc=p; } } }

cout<<\"打印邻接表：\"<vexnum;i++) {

if(g->vexs[i].firstarc) {

Arcnode *p;

cout<vexs[i].data<<\"--->\"; p=g->vexs[i].firstarc; while(p->nextarc) {

cout<<(p->adjvex)+1<<\"--->\"; p=p->nextarc ; }

cout<<(p->adjvex)+1<else cout<vexs[i].data<int First(Adjlist g,int v) {

if(g.vexs[v].firstarc)

return g.vexs[v].firstarc->adjvex; else

return -1; }

文案大全

实用标准文档

int Next(Adjlist g,int v,int w) {

int flag=0; Arcnode *p;

p=g.vexs[v].firstarc; while(p) {

if(p->adjvex==w) {

flag=1; break; }

p=p->nextarc; }

if(flag && p->nextarc)

return p->nextarc->adjvex; else

return -1; }

void DFS(Adjlist g,int v0) {

if(g.vexs[v0].firstarc) {

Arcnode *p;

cout<p=g.vexs[v0].firstarc; while(p!=NULL) {

if(!visited[p->adjvex]) {

DFS(g,(p->adjvex)); }

p=p->nextarc; } } else {

cout<void BFS(Adjlist g,int v0) {

Seqqueue *q;

文案大全

实用标准文档

q=(Seqqueue *)malloc(sizeof(Seqqueue)); q->rear=q->front=0; int v; int w;

for(;v0if(!visited[v0]) {

cout<while(q->rear!=q->front) {

Deletequeue(q,&v); w=First(g,v); while(w!=-1) {

if(!visited[w]) {

cout<w=Next(g,v,w); } } } } }

void main() {

Adjlist g; Create(&g);

for(int i=0;ifor(int v0=0;v0if(!visited[v0]) DFS(g,v0); }

cout<for(i=0;i文案大全

实用标准文档

cout<<\"广度优先遍历：\"; for(v0=0;v0if(!visited[v0]) BFS(g,v0); }

cout<4 测试数据与实验结果（可以抓图粘贴） 邻接矩阵

文案大全

实用标准文档

邻接表

5 结果分析与实验体会

做这次试验我感觉很吃力，邻接表，邻接矩阵都运用的不是很熟练，在书本上没有找到相应的算法，只能硬着头皮自己想办法，跟同学交流了很久才渐渐有了头绪，一开始做起来还是遇到了很多的困难。之后在图书馆查阅了很多的资料，找了很多的实例才写出最终的算法，希望老师可以给我们一些算法实例，我们结合书本上的理论知识也许会有更好，更深刻的理解.

文案大全