《数据结构实验与实训教程(第4版)》程序代码 下载本文

head = tail = 0; /* 队列置空 */ printf( \/* 访问出发顶点 */ visited[s] = 1; /* 置该顶点已被访问标志 */ queue[ tail++ ] = s; /* 出发顶点进队 */ while(_18_____ ) { /* 队不空循环 */ v = queue[ head++ ]; /* 取队列首顶点 */ for( j = 0; j < n; j++ ) { /* 按邻接矩阵, 顺序考察与顶点v邻接的各顶点w */ if(__19____ && visited[j] == 0 ) { /* 如果该顶点有边且未被访问过 */ printf( \/* 访问顶点j */ visited[j] = 1; /* 置顶点w已被访问标志 */

__20_____; /* 顶点j进队 */

}

} } }

void main() { lgraph lg; mgraph mg; int n, i; n = creat_graph( lg, mg ); for( i = 0; i < n; i++ ) visited[i] = 0; /* 置全部顶点为未访问标志 */ printf( \邻接表表示的图的递归深度优先遍历 \\n\ __21____; getch(); for( i = 0; i < n; i++ ) visited[i] = 0; /* 置全部顶点为未访问标志 */ printf( \邻接矩阵表示的图的递归深度优先遍历\\n\ ___22___; getch();

printf( \邻接表表示的图的广度优先遍历\\n\ ___23_____; getch();

printf( \邻接矩阵表示的图的广度优先遍历\\n\ ___24____; }

56

程序2:题3 求最少换车次数 #include #define M 20 #define N 50 int a[N+1]; /* 用于存放一条线路上的各站编号 */ int g[N][N]; /* 存储对应的邻接矩阵 */ int dist[N];

/* 存储站0到各站的最短路径 */

int m=0, n=0;

void buildG() /* 建图 */

{ int i, j, k, sc, dd; while( 1 ) { printf( \输入公交线路数[1-%d], 公交站数[1-%d]\\n\, M, N );

scanf( \%d%d\ if( m >= 1 && m <= M && n >= 1 && n <= N ) break; }

for( i = 0; i < n; i++ ) /* 邻接矩阵清0 */

for( j = 0; j < n; j++ ) g[i][j] = 0; for( i = 0; i < m; i++ ) { printf( \沿第%d条公交车线路前进方向的各站编号(0<=编号<=%d, -1结束):\\n\, i+1,

sc = 0;

/* 当前线路站计数器 */

n-1);

}

while( 1 ) { scanf( \%d\ if( dd == -1 ) break;

if( dd >= 0 && dd < n ) a[_1__] = dd; /* 保存站点编号 */

}

a[sc] = -1;

for( k = 1; a[k] >= 0; k++ )

for( j = 0; j < k; j++ ) g[__2_____] = 1;

/* 处理第i+1条公交线路 */

/* 该条线路所经过的两个站点置1 */

}

int minLen() /* 求从站点0开始的最短路径 */ {

57

int j, k;

for( j = 0; j < n; j++ ) dist[j] =__3__; dist[0] = 1; while(1) { for( k = -1, j = 0; j < n; j++ ) /* 找下一个最少上车次数的站 */

if( ____4__ && ( k == -1 ||__5____) ) k = j;

if( k < 0 || k == n-1 ) /* 找到最后一个站点, 或无最少上车站数 */ break;

dist[k] = -dist[k]; /* 设置k站已求得上车次数的标志 */

for( j = 1; j < n; j++ ) /* 调整经过k站能到达的其余各站的上车次数 */

if( g[k][j] == 1 && ( dist[j] == 0 || -dist[k] + 1 < dist[j] ) ) _____6____; }

j =__7____;

return ( k < 0 ? -1 :____8__ );

}

void main() { int t; buildG(); if( (t=______9_____ ) printf( \无解!\\n\ ); else printf( \从0号站到%d站需换车%d次\\n\, n-1, t );

}

58

实验10 排 序

四、参考程序

程序1:题1与题2 的(1) 选择排序 #include #include

#define N 10

int E[N] = { 213, 111, 222, 77, 400, 300, 987, 1024, 632, 555 };

void s_sort( int e[], int n )/* e:存储线性表的数组 n:线性表的结点个数 */

{

int i, j, k, t;

for( i = 0; i < n-1; i++ ) { /* 控制n-1趟的选择步骤 */

/* 在e[i], e[i+1],...,e[n-1]中选键值最小的结点e[k] */ for( k = i, j =__1__; j < n; j++ ) if( e[k] > e[j] ) _k=j; if(___2__ ) { /* e[i]与e[k]作交换 */ t = e[i]; e[i] = e[k]; e[k] = t;

}

} }

void main() { int i; printf( \顺序排序 初始数据序列为:\\n\ for( i = 0; i < N; i++ ) printf( \ __3____ printf( \排序后数据序列为:\\n\ for( i = 0; i < N; i++ ) printf( \ getch(); }

59