《数据结构》(C语言版)实验(8)

if(flag==1)

g->arcs[j][i]=w;

scanf(\ } }

void prim(graph *g,int u)/*出发顶点u*/ {

int lowcost[N],closest[N],i,j,k,min;

for(i=0;ivexnum;i++) /*求其他顶点到出发顶点u的权*/ {

lowcost[i]=g->arcs[u][i]; closest[i]=u; }

lowcost[u]=0;

for(i=1;ivexnum;i++) /*循环求最小生成树中的各条边*/ { min=INFIN;

for(j=0;jvexnum;j++) /*选择得到一条代价最小的边*/ if(lowcost[j]!=0&&lowcost[j]

min=lowcost[j]; k=j; }

printf(\/*输出该边*/

lowcost[k]=0; /*顶点k纳入最小生成树 */

for(j=0;jvexnum;j++) /*求其他顶点到顶点k 的权*/ if(g->arcs[k][j]!=0&&g->arcs[k][j]

lowcost[j]=g->arcs[k][j]; closest[j]=k; } } }

void printPath(graph g,int startVex,int EndVex) {

int stack[N],top=0; /*堆栈*/ int i,k,j;

int flag[N]; /*输出路径顶点标志*/ k=EndVex;

for (i=0;i

36

printf(\ flag[j]=1;

stack[top++]=k;

while (top>0) /*找j到k的路径*/ {

for (i=0;i

if (path[k][i]==1 && flag[i]==0) /*j到k的路径含有i顶点*/ {

if (g.arcs[j][i]!=INF ) /*j到i的路径含有中间顶点*/ {

printf(\ /*输出j到k的路径的顶点i*/ flag[i]=1; j=i;

k=stack[--top]; break; } else {

if (i!=k) stack[top++]=i; /*break;*/ } } } }

void dijkstra(graph g,int v){ /*dijkstra算法求单源最短路径*/ int path[N][N],dist[N],s[N]; int mindis,i,j,u,k;

for(i=0;i

for(j=0;j

dist[v]=0; s[v]=1;

for(i=0,u=1;i

for(j=0;j

37

if(s[j]==0)

if(dist[j]

mindis=dist[j]; } s[u]=1;

for(j=0;j

if((s[j]==0)&&dist[u]+g.arcs[u][j]

printf(\顶点%c->到各顶点的最短路径\\n\ for(i=0;i

printf(\顶点%c->顶点%c：\ if(dist[i]==INF||dist[i]==0) printf(\无路径\ else{

printf(\

printf(\经过顶点：\

printPath(g,v,i); /*输出v到i的路径*/ } } }

void showprim()/*最小生成树prim算法演示*/ {

graph ga;

createGraph_w(&ga,1); prim(&ga,0); }

void showdij(){ /*dijstra算法演示*/ graph ga;

createGraph_w(&ga,0); dijkstra(ga,0); }

int main(){

showprim(); /*prim算法演示*/ getchar();

showdij(); /*dijstra算法演示*/

38

return 0; }

? 下面的输入分别验证prim算法和dijstra算法。输入实例的第一部分为无向图，求

其最小生成树；输入的第二部分为有向图，求其最短路径。 最小生成树 最短路径 ABCDEF# 0,1,6 0,2,1 0,3,5 1,2,5 1,4,3 2,3,5 2,4,6 2,5,4 3,5,2 4,5,6 -1,-1,-1 ? 运行结果：（并画出两个图）

最小生成树

四、实验小结

五、教师评语

ABCDEF# 0,2,10 0,5,100 0,4,30 1,2,5 2,3,50 3,4,20 3,5,10 4,3,20 4,5,60 -1,-1,-1 最短路径 39

实验六 查找

一、实验目的

1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。

3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。

二、实验预习

说明以下概念 1、顺序查找：

2、折半查找：

3、哈希函数：

4、冲突及处理：

三、实验内容和要求

1. 静态查找表技术

依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：

查找表1 ： { 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 } ，查找key = 41 查找表2 ： {12 ，76 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 } ，查找key =35 查找key=41的算法： 比较次数： 查找key=35的算法： 比较次数： ? 顺序查找算法算法实现代码

40

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构》(C语言版)实验(8)在线全文阅读。