数据结构实验报告（华夏）

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; ｝