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

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

第33页 /共58页

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;}

第34页 /共58页

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; int lowcost=32767; for(j=0;j

{if(flag[j]!=1&&mark[j].lowcost

lowcost=mark[j].lowcost;}} flag[nearestv]=1; return nearestv;}

void markothervex_hc(graph_hc*g,markedg_hc*mark,int nearestv,int num,int*flag)

第35页 /共58页

{int j;

for(j=0;jarcs[nearestv][j]>0) {if(flag[j]!=1)

{if(mark[j].lowcost>(mark[nearestv].lowcost+g->arcs[nearestv][j])) {mark[j].lowcost= mark[nearestv].lowcost+g->arcs[nearestv][j]; mark[j].adjvex=nearestv;}}}}}

void shortestpath_hc(graph_hc*g,markedg_hc*mark,int start) {int i,num; int *flag; int nearestv; num=g->vexnum;

flag=(int *)malloc((num)*sizeof(int)); flag[start]=1;

for(i=0;ivexnum;i++) {mark[i].adjvex=start; if( g->arcs[start][i]>0)

{mark[i].lowcost=g->arcs[start][i];} else

{mark[i].lowcost=32767;}} for(i=1;ivexnum;i++)

{nearestv=selectnearvex_hc(mark,flag,num); markothervex_hc(g,mark,nearestv,num,flag);}}

void printshortpath_hc(graph_hc*g,markedg_hc*mark,int start) {int i,j,k,path[25]; for(i=0;ivexnum;i++) {if(i!=start)

{printf(\从%d到%d最短路径为:%d; \printf(\途经:\k=0;path[k]=i; j=mark[i].adjvex; while(j!=start) {path[++k]=j; j=mark[j].adjvex;} printf(\

for(j=k;j>=0;j--)printf(\printf(\ main() {int city;

graph_hc*g;markedg_hc*mark; g=initgraph_hc();

第36页 /共58页

creategraph_hc(g); printf(\城市名称/代号:\

printf(\乌鲁木齐/0, 哈尔滨/1, 呼和浩特/2, 长春/3, 北京/4, \printf(\沈阳/5, 天津/6, 大连/7, 西宁/8, 兰州/9, 西安/10, 郑州/11, \printf(\徐州/12, 成都/13, 武汉/14, 上海/15, 昆明/16, 贵阳/17, 株州/18,\printf(\南昌/19, 福州/20, 柳州/21, 南宁/22, 广州/23, 深圳/24.\\n\printgraph_hc(g);

mark=(markedg_hc*)malloc(g->vexnum*sizeof(markedg_hc)); printf(\输入起始城市:\shortestpath_hc(g,mark,city); printshortpath_hc(g,mark,city);

}

实验十一顺序表查找算法的实现

实验预备知识：

1．理解记录、关键字和查找的相关概念。 2．熟练掌握顺序表的存储结构。

一、实验目的

1．掌握排序算法及基本思想及实现的技术；能够根据实际问题特点的要求选择合理的排序方法；理解排序在数据处理中的重要性；

2．学会比较各种排序方法的稳定性分析以及在最好、最坏和平均情况的时间性能分析。 3．掌握顺序查找和折半查找两种查找的算法及实现技术；了解它们各自的优缺点。 4．熟悉各种查找方法的适用范围和条件；掌握顺序查找、折半查找的基本思想及效率分析。

二、实验环境

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

三、实验要求

1．本次实验较为简单，每个同学独立按时完成，通过实验掌握记录的概念，为以后数据库技术打好基础。

2．如果输入数据较为繁琐，可减低每个班的人数。 3．输入输出数据要有提示，方便用户操作。

第37页 /共58页