edgenode * p; SETNULL(Q);
printf(\％c＼n\visited[k]＝TRUE; ENQUEUE(Q,k); while(! EMPTY(Q)); { i＝DEQUEUE(Q);
p＝g1[i].1ink /*取vi+l的边表头指针*/
while(p !＝NULL) /*依次搜索vi+l的邻接点*/
{ if( ! visited[p - >adjvex]) /*访问vi+l的未访问的邻接点*/ { printf{\％c＼n\ visited[p - >adjvex]＝TRUE;
ENQUEUE(Q,p - >adjvex); /*访问过的顶点入队*/ }
p＝p - >next; /*找vi+l的下一个邻接点*/ } }
} /*BFSL*/
P148 在对算法Prim求精之前，先确定有关的存储结构如下： typdef struct
{Int fromvex，endvex； /*边的起点和终点*/ float length； /*边的权值*/ } edge；
float dist[n][n]； /*连通网络的带权邻接矩阵*/ edgeT[n-1]； /*生成树*/
P149 抽象语句(1)可求精为：
for(j=1;j P149 抽象语句(3)所求的第k条最短紫边可求精为： min＝max; /*znax大于任何边上的权值*/ for (j＝k;j {min＝T[j].1ength;m＝j; /*记录当前最短紫边的位置*/ } P149 抽象语句（4）的求精： e＝T[m];T[m]＝T[k];T[k]＝e， /* T[k]和T[m]交换*/ v＝T[kl.Endvex]; /* v是刚被涂红色的顶点*/ P149 抽象语句(5)可求精为： for(j＝k+1;j if(d T[j].fromvex＝v; /*新紫边取代原最短紫边*/ } } P150 完整的算法： PRIM() /*从第一个顶点出发构造连通网络dist的最小生成树，结果放在T中*/ {int j , k , m , v , min , max＝l0000; float d; edge e; for(j=1;j {T[j-1].formvex＝1; /*顶点1是第一个加入树中的红点*/ T[j-1].endvex＝j+1; T[j-1].length＝dist[o][j]; } for(k＝0;k for(j＝k;j } /*T[m]是当前最短紫边*/ } e＝T[m];T[m]＝T[k];T[k]＝e; /*T[k]和T[m]交换后，T[k]是第k条红色树边*/ v＝T[k].endvex ; /* v是新红点*/ for(j＝k+1;j } /* PRIM */ P151 Kruskl算法的粗略描述： T＝(V,φ); While(T中所含边数 {从E中选取当前最短边(u,v); 从E中删去边(u,v); if((u,v)并入T之后不产生回路，将边(u,v)并入T中; } P153 迪杰斯特拉算法实现。算法描述如下： #define max 32767 /*max代表一个很大的数*/ void dijkstra (float cost[][n],int v) /*求源点v到其余顶点的最短路径及其长度*/ { v1=v-1; for (i=0;i { dist[i]=cost[v1][i]; /*初始化dist*/ if (dist[i] pre[v1]=0; for (i=0;i s[i]=0; /*s数组初始化为空*/ s[v1]=1; /*将源点v归入s集合*/ for (i=0;i for (j=0;j if (!s[j] && (dist[j] } /*选择dist值最小的顶点k+1*/ s[k]=1; /*将顶点k+1归入s集合中*/ for (j=0;j if (!s[j]&&(dist[j]>dist[k]+cost[k][j])) { dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各顶点的dist值*/ pre[j]=k+1; /*k+1顶点是j+1顶点的前驱*/ } } /*所有顶点均已加入到S集合中*/ for (j=0;j { printf(\ p=pre[p-1]; } } } P155 弗洛伊德算法可以描述为： A(0)[i][j]=cost[i][j]; //cost为图的邻接矩阵 A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]} 其中 k=1,2,...,n P155 弗洛伊德算法实现。算法描述如下： int path[n][n]; /*路径矩阵*/ void floyd (float A[][n],cost[][n]) { for (i=0;i { if (cost[i][j] else { path[i][j]=0; A[i][j]=cost[i][j]; } } for (k=0;k /*做n次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/ for (i=0;i if (A[i][j]>(A[i][k]+A[k][j])) /*修改长度和路径*/ { A[i][j]=A[i][k]+A[k][j]; path[i][j]=path[i][k]; } for (i=0;i { printf (\ /*输出最短路径的长度*/ next=path[i][j]; /*next为起点i的后继顶点*/ if (next==0) /*i无后继表示最短路径不存在*/ printf (\ else { printf (\/*最短路径存在*/ while (next!=j+1) /*打印后继顶点，然后寻找下一个后继顶点*/ { printf (\ next =path[next-1][j]; } printf (\ } } } 第八章 查找 P163 具体实现图8-1框图的程序段如下： Void seqsrch(struct node r[],int n,int k) { int i=1; r[n+1].key=k; /*设置边界*/ while (r[i].key!=k) i=i+1; if (i<=n) printf(\else printf(\} P164 设表的长度为n，表的被查找部分的头为low，尾为high，初始时，low=1,high=n,k为关键字的值。具体算法如下： Void binsrch(struct node r[ ],int n,int k) { int mid,low,high,find; low=1; high=n;find=0; /*置区间初值*/ while ((low<=high) && (!find)) { mid=(low+high)/2; /*求中点*/ if (k= = r[mid].key) find=1; /*已查到*/ else if(k>r[mid].key ) low=mid+1; /*在后半区间查找*/ else high=mid-1; /*在前半区间查找*/ } if (find) return (mid); /*查找成功，返回找到元素的位置*/ else return (0); /*查找不成功，返回0标记*/ } P170 下面是线性探测法的算法，请注意，算法中设立了一个查找的边界值i，当顺序探测已超过表长，则要翻转到表首继续查找，直到查到i位置才是真正的查完全表。为编程方便，令i=j-1。 Define m 100; /*哈希表的长度*/ Struct hash {int key; }HT[m]; Void linehash(struct hash HT[ ],int k,int p) {j=k%p;i=j-1; while ((HT[j].key!=NULL)&&(HT[j].key!=k)&&(j!=i)) j=(j+1)%m; /*解决冲突*/ if (HT[j].key==k) printf(\else if (j==i) printf(\ /*溢出*/