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
/* 存储站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
#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