d.cd[ --d.start ] = _9__; c = f; ___10___; }
__11_____= d; }
printf( \输出huffman编码:\\n\ ); for( i = 0; i < n; i++ ) {
printf( \
for( k = hcd[i].start; k < n; k++ ) printf(\%c\ printf( \ ); } }
52
实验9 图的基本操作
四、参考程序
程序1：题1 与题2 图基本操作函数及其调用 #include
#include
/* 后继邻接顶点 */
/* 邻接表类型 */
}edgeNode;
typedef edgeNode *lgraph[MAX];
typedef int mgraph[MAX][MAX]; /* 邻接矩阵类型 */ int visited[MAX]; /* 访问标志 */ int queue[MAX]; /* 广度优先遍历存储队列 */
int creat_graph( lgraph lg, mgraph mg ) /* 输入无向图的边, 建立图的邻接表, 邻接矩阵 */ {
int vn, en, k, i, j;
edgeNode *p;
printf( \邻接表方式建图\\n\ while( 1 ) { /* 输入图的顶点数, 边数 */
vn = en = 0;
printf( \输入图的顶点数[1-30]\\n\ );
fflush( stdin );
scanf( \%d\if( ____1_____ ) continue;
printf( \输入图的边数[0-%d]\\n\scanf( \%d\
if( en >= 0 &&___2______ ) break; }
for( k = 0; k < vn; k++ ) lg[k] =__3___; /* 置空邻接表 */
53
for( k = 0; k < vn; k++ ) /* 置空邻接矩阵 */
for( i = 0; i < vn; i++ ) _____4___; for( k = 0; k < en; ) { /* 构造邻接表, 邻接矩阵的各条边 */ i = j = -1; printf( \输入第[%d]对相连的两条边[1-%d]: \, k+1, vn ); scanf( \%d%d\, &j );
if( i < 1 || j < 1 || i > vn || j > vn ) {
printf( \输入错误, 边范围为[1-%d]\\n\, vn );
continue;
} k++; i--;
j--; p = (edgeNode *)malloc( sizeof(edgeNode) ); ____5_____; p->next = lg[i];
lg[i] =___6__; /* 将新结点插入到第i行邻接表行首 */ p = (edgeNode *)malloc( sizeof(edgeNode) ); p->vno = i; __7_____; lg[j] = p; /* 将新结点插入到第j行邻接表行首 */ mg[i][j] =__8____ = 1; /* 置邻接矩阵的值 */
}
return vn; }
void ldfs( lgraph g, int i ) /* 邻接表表示的图的递归深度优先遍历 */
{ edgeNode *t;
printf( \ /* 访问顶点i */
visited[_9_] = 1;
/* 置i顶点已被访问 */
t = g[i];
while( t != NULL ) { /* 检查所有与顶点i相邻接的顶点 */ if( ___10____ ) /* 如果该顶点未被访问过 */
ldfs( g, t->vno ); /* 从邻接顶点出发深度优先搜索 */
_____11____; /* 考察下一个邻接顶点 */
} }
54
void mdfs( mgraph g, int i, int vn ) /* 邻接矩阵表示的图的递归深度优先遍历 */ { int j; printf( \ /* 访问顶点i */ visited[i] = 1; /* 置i顶点已被访问 */ for( j = 0; j < vn; j++ ) { /* 检查所有与顶点i相邻接的顶点 */ if( ___12____ &&__13_____ ) /* 如果该顶点有边且未被访问过 */
mdfs( g, j, vn ); /* 从邻接顶点出发深度优先搜索 */
}
}
void lbfs( lgraph g, int s, int n ) /* 邻接表表示的图的广度优先遍历 */ { int i, v, w, head, tail; edgeNode *t; for( i = 0; i < n; i++ ) visited[i] = 0; /* 置全部顶点为未访问标志 */ head = tail = 0; /* 队列置空 */ printf( \/* 访问出发顶点 */ visited[s] = 1; /* 置该顶点已被访问标志 */ queue[ __14____ ] = s; /* 出发顶点进队 */ while( head < tail ) { /* 队不空循环 */ v = queue[__15___ ]; /* 取队列首顶点 */ for( t = g[v]; t != NULL; t = t->next ) { /* 按邻接表, 顺序考察与顶点v邻接的各顶点w */ w =__16___;
if( visited[w] == 0 ) { /* 顶点w未被访问过 */ printf( \/* 访问顶点w */ __17_____; /* 置顶点w已被访问标志 */ queue[tail++] = w; /* 顶点w进队 */
}
}
} }
void mbfs( mgraph g, int s, int n ) /* 邻接矩阵表示的图的广度优先遍历 */ { int i, j, v, head, tail; for( i = 0; i < n; i++ )
visited[i] = 0;
/* 置全部顶点为未访问标志 */
55