数据结构实验指导书及答案（徐州工程学院）(6)

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验8”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某网络公司的光纤连接结点如下图所示，请分别用邻接矩阵和邻接表将图存储到计算机中方便进行处理。

3．现在公司想知道共有哪些结点及其名称，现在请你用深度优先和广度优先进行遍历。 4．完成如下图中没有实现的操作函数：

#include \#include \#include \#define INFINITY 32767 #define MAX_VERTEX_NUM 20

typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc;

typedef struct arccell_hc {int adj; int *info;

}arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc;

typedef struct arcnode_hc {int adjvex;

struct arcnode_hc *nextarc; int *info; }arcnode_hc;

typedef struct vnode_hc {char data;

arcnode_hc *firstarc;

}vnode_hc,adjlist_hc[MAX_VERTEX_NUM];

typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc;

int locatevex_hc(mgraph_hc*g,char v) {int i,k=0;

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

if(g->vexs[i]==v){k=i;i=g->vexnum;} return(k);}

mgraph_hc*createudg_hc() {mgraph_hc*g; char v1,v2; int i,j,incinfo;

g=(mgraph_hc*)malloc(sizeof(mgraph_hc)); g->kind=UDG;

printf(\请输入图顶点数、边数及该边相关信息:\scanf(\printf(\请输入顶点信息:\

for(i=0;ivexnum;++i)scanf(\for(i=0;ivexnum;++i) for(j=0;jvexnum;++j) g->arcs[i][j].adj=0;

printf(\输入一条边依附的顶点:\\n\flushall();scanf(\while(v1!='#'&&v2!='#')

{i=locatevex_hc(g,v1);j=locatevex_hc(g,v2); g->arcs[i][j].adj=1;

if(incinfo)g->arcs[i][j].info=&incinfo; g->arcs[j][i].adj=g->arcs[i][j].adj; g->arcs[j][i].info=g->arcs[i][j].info; flushall();scanf(\return(g);}

visited_hc vis[MAX_VERTEX_NUM];

int firstadjvex_hc(mgraph_hc*g,int v) {int i,k=-1;

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

if(g->arcs[v][i].adj==1){k=i;i=g->vexnum;} return(k);}

int nextadjvex_hc(mgraph_hc*g,int v,int w) {int i,k=-1;

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

if(g->arcs[v][i].adj==1&&i>w){k=i;i=g->vexnum;} return(k);}

void dfs_hc(mgraph_hc*g,int v) {int w;

vis[v]=TRUE; printf(\

for(w=firstadjvex_hc(g,v);w>=0;w=nextadjvex_hc(g,v,w)) if(!vis[w])dfs_hc(g,w);}

void dfstraverse_hc(mgraph_hc*g) {int v,i;char f;

for(v=0;vvexnum;v++)vis[v]=FALSE;

printf(\输入遍历开始顶点:\i=locatevex_hc(g,f);printf(\深度遍历结果为:\for(v=i;vvexnum;v++)if(!vis[v])dfs_hc(g,v);

for(v=0;v

int locatevexal_hc(algraph_hc*a,char v) {int i,k=0;

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

if(a->vertices[i].data==v){k=i;i=a->vexnum;} return(k);}

char createlist_hc(algraph_hc*a,arcnode_hc*firstl,char v) {arcnode_hc*nextl; if(v!='\\n')

{nextl=(arcnode_hc*)malloc(sizeof(arcnode_hc)); nextl->adjvex=locatevexal_hc(a,v);

nextl->nextarc=NULL;nextl->info=firstl->info; firstl->nextarc=nextl;

scanf(\return(v);}

algraph_hc*createaludg_hc() {algraph_hc*a;int i,incinfo;char v; a=(algraph_hc*)malloc(sizeof(algraph_hc)); a->kind=UDG;

printf(\请输入图顶点数、边数及该边相关信息:\scanf(\printf(\请输入顶点信息:\

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

{printf(\输入%c的邻接点:\flushall();scanf(\

a->vertices[i].firstarc=(arcnode_hc*)malloc(sizeof(arcnode_hc)); a->vertices[i].firstarc->adjvex=locatevexal_hc(a,v); a->vertices[i].firstarc->nextarc=NULL; if(incinfo)a->vertices[i].firstarc->info=&incinfo;

scanf(\return(a);}

visited_hc vis[MAX_VERTEX_NUM];

void dfsal_hc(algraph_hc*a,arcnode_hc*b,int k) {vis[k]=TRUE;

printf(\while(b) {k=b->adjvex;

if(!vis[k]){b=a->vertices[k].firstarc;dfsal_hc(a,b,k);}

else b=b->nextarc;}}

void dfstraverseal_hc(algraph_hc*a) {char f;int i=0,k;

for(i=0;ivexnum;i++)vis[i]=FALSE;

printf(\遍历开始顶点:\k=locatevexal_hc(a,f); printf(\深度遍历结果:\for(i=k;ivexnum;i++)

if(!vis[k])dfsal_hc(a,a->vertices[i].firstarc,i); for(i=0;i

if(!vis[k])dfsal_hc(a,a->vertices[i].firstarc,i);}

void main()

{algraph_hc*a;mgraph_hc*g; char c;

printf(\邻接矩阵(M)\\n\printf(\邻接表(A)\\n\printf(\请选择:\c=getchar(); while(c!='E')

{if(c=='M'){g=createudg_hc();dfstraverse_hc(g);} else if(c=='A'){a=createaludg_hc();dfstraverseal_hc(a);} printf(\请选择:\

实验九 图的最小生成树算法的实现

实验预备知识：

1．理解图最小生成树的意义和相应算法。 2．掌握带权图的存储结构。

一、实验目的

1．使学生熟悉最小生成树的算法实现。 2．掌握带权图的存储结构和处理方法。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．能够独立完成带权图的存储和最小生成树的生成