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

四、实验内容

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

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

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

#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);

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->vexnum;} else if(st->vexlist[i][j]==b)

{k=+j;while(st->vexlist[i][k]!=-1)k++;st->vexlist[i][k]=a;j=st->vexnum;}}}}

return(f);}

stgraph_hc*minspandtree_hc(stgraph_hc*st) {int i,a,b,min;

for(i=0;ivexnum-1;i++) {min=minweight_hc(st);

a=st->gelist[min].fromvex;b=st->gelist[min].endvex; if(samegraph_hc(st,a,b))i--;

else st->arcs[a][b]=st->arcs[b][a]=st->gelist[min].weight;} free(st->vexlist);free(st->gelist); return(st);}

void printst(stgraph_hc*st) {int i,j;

printf(\最小生成树为:\\n\for(i=0;ivexnum;i++) {for(j=0;jvexnum;j++)

printf(\printf(\需要连通的点有:\for(i=0;ivexnum;i++) for(j=i;jvexnum;j++)

if(st->arcs[i][j])printf(\

void main() {stgraph_hc *st; st=creategraph_hc(); st=minspandtree_hc(st); printst(st);}

实验十 图的最短路径算法的实现

实验预备知识：

1．理解图最短路径的意义和相应算法。 2．掌握带权图的存储结构。

一、实验目的

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

二、实验环境

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

三、实验要求

1．能够独立完成带权图的存储和最短路径的生成。

四、实验内容

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

2．现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到计算机中方便进行处理。

3．现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra 算法实现我的要求的路径。

#include \#include \

typedef struct {int *vexs; int **arcs; int vexnum; }graph_hc;

typedef struct {int adjvex; int lowcost; }markedg_hc;

graph_hc*initgraph_hc() {int i,j;graph_hc*g;

g=(graph_hc*)malloc(sizeof(graph_hc)); g->vexnum=25;

g->vexs=(int*)malloc(g->vexnum*sizeof(int)); g->arcs=(int**)malloc(g->vexnum*sizeof(int*)); for(i=0;ivexnum;i++)

g->arcs[i]=(int*)malloc(g->vexnum*sizeof(int)); for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) {g->arcs[i][j]=0;} return g;}

void creategraph_hc(graph_hc *g) {int i,j;

for(i=0;ivexnum;i++)g->vexs[i]=i; g->arcs[0][9]=1892; g->arcs[1][3]=242; g->arcs[2][4]=668; g->arcs[2][9]=1145; g->arcs[3][5]=305; g->arcs[4][6]=137; g->arcs[4][11]=695; g->arcs[5][6]=704; g->arcs[5][7]=397; g->arcs[6][12]=674; g->arcs[8][9]=216; g->arcs[9][10]=676; g->arcs[10][11]=511;g->arcs[10][13]=842; g->arcs[11][12]=349;g->arcs[11][14]=534; g->arcs[12][15]=651;g->arcs[13][16]=110; g->arcs[13][17]=967;g->arcs[14][18]=409; g->arcs[15][19]=825;g->arcs[16][17]=639; g->arcs[17][18]=902;g->arcs[17][21]=607; g->arcs[18][19]=367;g->arcs[18][21]=672; g->arcs[18][23]=675;g->arcs[19][20]=622; g->arcs[21][22]=255;g->arcs[23][24]=140; for(i=0;ivexnum;i++) for(j=i;jvexnum;j++) if(g->arcs[i][j])

g->arcs[j][i]=g->arcs[i][j];}

void printgraph_hc(graph_hc*g) {int x,y;

printf(\城市间连通图为:\\n\for(x=0;xvexnum;x++) for(y=x;yvexnum;y++)

if(g->arcs[x][y])printf(\距离:%d\\t\

int selectnearvex_hc(markedg_hc*mark,int *flag,int num) {int j; int nearestv;