发布时间 : 星期三 文章数据结构实验报告（华夏）更新完毕开始阅读3b8bbc00ccbff121dd368354
for (p=ht+1 , i=1 ; i<=m ; ++i , ++p) { p->weight=0 ; p->parent=0 ; p->lchild=0 ; p->=rchild=0 } printf(“\\n input %d weight : “, n)
for (i=1 ;i<=n ; i++)
scanf(“%d”,&ht[i] .weight); for(i=n+1 ; i<=m ;++i)
{ s1=1 ; s2=1 ; w1=100; w2=100 ; for (j=1 ; j<=i-1 ;j++) if (ht[j].parent ==0) if (ht[j].weight w1=ht[j].weight ; s2=s1 ; s1=j ;} else if(ht[j].weight ht[s1].parent=i ; ht[s2].parent=i; ht[i.lchald=s1 ; ht[i].rchild=s2; ht[i].weight=ht[s1].weight+ht[s2].weight ; } /*for(I=n+1;I<=m;++I*/ /*求哈夫曼编码*/ ht=(Huffmantree ) malloc ((n+1)*sizeof(char*)) ; cd= (char* ) malloc (n*sizeof(char)) ; cd[n-1]=?\\0?; for (i=1 ;i<=n ; ++i ) { start=n-1 ; for(c=i,f=ht[i].parent ; f ; c=f , f=ht[f].parent) if(ht[f].lchild==c) cd[--start]=?0? ; else cd[--start]=?1? ; hc[i]=(char*)malloc((n-start)*sizeof(char)) ; strcpy(hc[i],&cd[start]) ; /*复制cd[start]到hc[i]中*/ } free(cd); /*释放cd*/ printf(“\\n output huffmancode : \\n”); for (i=1 ;i<=n ; i++) printf(“\\n -: %s”,ht[i].weight, hc[i]); } main() { printf(“\\n input n: “ ); scanf(“%d”,&n); huffmancoding(); getchar(); /*输入一个字符开始查阅*/ getchar(); /*输入一个字符结束*/ } 三、实验结果分析讨论 1． 输入的数据为： input n ：8 input 8 weight:5 29 7 8 14 23 3 11 对应的字符为：A B C D E F G H 输出的哈夫曼编码为： A 5 0001 B 29 10 C 7 1110 D 8 1111 E 14 110 F 23 01 G 3 0000 H 11 001 2． 分析上述程序的性能，提出改进算法。 四、巩固题 给出一个字符串序列{“aabcdabcddefdbcefaaabdddf”}用哈夫曼编码输出之。 实验五 单源最短路径的实现算法 一、预习报告 实验目的 1、掌握用Turbo C上机调试图结构的基本方法； 2、掌握图的基本存储方法，及有关图的操作算法在C语言上的程序实现； 3、了解实际问题的求解效率与采用何种存储结构及算法的密切关系； 基本原理与方法 采用dijkstra方法求单源最短路径用C语言编程实现 实验设备 PC机一台、配置Turbo C软件 二、实验内容 求单源最短路径 〔问题描述〕求下图从顶点V1到其它各顶点的最短路径 1 5 注意：各边权植（距离）自定； 2 3 4 〔基本要求〕 对上面给出的五个顶点的有向网络图，（各边距离自定；）求从V1到其它各 顶点的最短路径，并用清晰的界面输出V1到V2~V5的最短路径。 〔算法提示〕采用dijkstra方法实现 分析：1. 初始化：用邻接矩阵存储图； 2. 利用dijkstra方法求； 3. 输出结果 〔参考程序〕 # include “stdio.h” # include “string.h” # include “alloc.h” #defile MAX 10000 #defile Vextype int #defile Edgetype int #defile MAXLEN 100 typedef struct { Vextype VEXS[MAXLEN]; Edgetype edges[MAXLEN][ MAXLEN]; Int n,e ; } MGRAPH; MGRAPH create_mgraph() { int i ,j,k,h ; char b,t ; MGRAPH mg ; printf(“\\n 请输入顶点数和边数：“)； scanf(%d,%d”,&i,&j); mg.n=i ; mg.e=j ; for (i=0 ;i printf(“\\n 请输入第%d个顶点的信息：“，i+1)； scanf(“%d”,&mg.vexs[i]); ｝ for(i=0 ; i<=mg.n ; i＋＋) for (j=0 ; j printf(“\\n 请输入第%d条边的起始顶点编号和终止顶点编号：“，k)； scanf(“%d，％d”,& i，&j); while(i<1|| i>mg.n || j<1 || j>mg.n) ｛ printf(“\\n 编号超出范围，请重新输入“ )； scanf(“%d，％d”,& i，&j); ｝ printf(“\\n 输入此边的权值：“ )； scanf(“%d ”,& h); mg.adges[i-1][j-1]=h; } return mg ； ｝ main() ｛ MGRAPH mg ; int cost[MAXLEN][ MAXLEN]; int path[ MAXLEN]; int dist[ MAXLEN]; int i,j,n,v0,min,u;; mg＝create_mgraph(); /*建有向图的邻接矩阵*/ printf(“\\n 请输入起始顶点的编号“ )；/*有向图的编号从1开始*/ scanf(“%d ”,&v0); v0-- ； n＝mg.n ； for (i=0 ;i< n ; i＋＋ ) /* 邻接矩阵cost初始化*/ { for(j=0 ; f ; j cost[i][j]=mg.edges[i][j]; ; cost[i][i]=0; ｝