数据结构实验指导书(2016)(7)

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;

第28页 /共58页

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;

第29页 /共58页

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．能够独立完成带权图的存储和最小生成树的生成

四、实验内容

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

2．现在某电信公司要对如下图的几个城市之间进行光纤连接布线，请用合适的存储结构将下图存储到计算机中方便进行处理。

3．现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用普里姆算法和克鲁斯卡尔算法实现本图的最小生成树。

第30页 /共58页

#include \#include \#include \#define INFINITY 32767

typedef enum{FALSE,TRUE}panduan_hc;

typedef struct {int fromvex; int endvex ; int weight ; int tags ; }arclist_hc; typedef struct {char *vexs; int **vexlist; arclist_hc *gelist; int **arcs;

int vexnum, edgnum; }stgraph_hc;

int locatevex_hc(stgraph_hc*st,char v) {int i,k=0;

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

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

stgraph_hc *creategraph_hc () {stgraph_hc *st;int i,j,x,y;char a,b;

if(!(st=(stgraph_hc*)malloc(sizeof(stgraph_hc)))){printf(\出错!\printf(\输入图的顶点数和边数:\

scanf(\

if(!(st->vexs=(char*)malloc(st->vexnum*sizeof(char)))){printf(\出错!\

if(!(st->gelist=(arclist_hc*)malloc(st->edgnum*sizeof(arclist_hc)))){printf(\出错!\if(!(st->arcs=(int**)malloc(st->vexnum*sizeof(int*)))){printf(\出错!\if(!(st->vexlist=(int**)malloc(st->vexnum*sizeof(int*)))){printf(\出错!\for(i=0;ivexnum;i++)

{if(!(st->arcs[i]=(int*)malloc(st->vexnum*sizeof(int)))){printf(\出错!\if(!(st->vexlist[i]=(int*)malloc(st->vexnum*sizeof(int)))){printf(\出错!\printf(\输入顶点:\

for(i=0;ivexnum;i++)scanf(\printf(\输入边及权值:\\n\for(i=0;iedgnum;i++)

{flushall();scanf(\x=locatevex_hc(st,a);y=locatevex_hc(st,b);

第31页 /共58页

if(xgelist[i].fromvex=x,st->gelist[i].endvex=y; else st->gelist[i].fromvex=y,st->gelist[i].endvex=x; st->gelist[i].tags=0;} for(i=0;ivexnum;i++)

for(j=0;jvexnum;j++)st->arcs[i][j]=0; for(i=0;ivexnum;i++) {st->vexlist[i][0]=i;

for(j=1;jvexnum;j++)st->vexlist[i][j]=-1;} return(st);}

int minweight_hc(stgraph_hc*st) {int i,min;

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

if(!st->gelist[i].tags){min=i;i=st->edgnum;} for(i=0;iedgnum;i++)

if(!st->gelist[i].tags&&st->gelist[min].weight>st->gelist[i].weight)min=i; st->gelist[min].tags=1;return(min);}

panduan_hc samegraph_hc(stgraph_hc *st,int a,int b) {int i,j,k;panduan_hc f=FALSE; for(i=0;st->vexlist[a][i]!=-1&&!f;i++) for(j=0;st->vexlist[b][j]!=-1&&!f;j++) if(st->vexlist[a][i]==st->vexlist[b][j])f=TRUE; if(!f)

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

{for(j=0;jvexnum&&st->vexlist[i][j]!=-1;j++) {if(st->vexlist[i][j]==a)

{k=+j;while(st->vexlist[i][k]!=-1)k++;st->vexlist[i][k]=b;j=st->vex …… 此处隐藏：3287字，全部文档内容请下载后查看。喜欢就下载吧 ……