《数据结构》课程设计报告--内部排序的性能化比较与哈弗曼编码.docVIP

《数据结构》 课程设计报告 题　　目：　　 内部排序的性能比较与哈弗曼编码　 学　　院：　　　 商学院　　　 专　　业：　　　　 信息管理与信息系统　　　　　　 班　　级：　　　　　　 信息092　　　　　　　 学　　号：　　　　 　 姓　　名：　　　　　 　　　　 同组成员：　 指导教师：　　　　　 　　　　　　　　 完成日期：　　　　　2010年01月13日　　　　　　　 目 录 目 录 2 一、问题描述 3 1.1哈弗曼编码 3 1.2内部排序性能分析 3 二、问题分析 3 三、数据结构描述 4 四、算法设计 5 4.1希尔排序流程图： 5 五、详细程序清单 7 六、程序运行结果 17 七、心得体会 19 一、问题描述 1.1哈弗曼编码 设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。 (1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树； (2)编码：利用建好的哈夫曼树生成哈夫曼编码； (3)输出编码； 1.2内部排序性能分析 设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序算法的关键字比较次数和移动次数以取得直观感受（待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动））。 二、问题分析 我负责的是内部排序之中希尔排序的性能比较，先设计出希尔排序的排序原理，框架结构，然后设计程序代码，合并到总程序中，修改总程序。 三、数据结构描述 typedef struct { int key; char otherinfo; }Elem; typedef struct { Elem r[N+1];//r[0]闲置或用作“哨兵” int length; }Sqlist; void ShellSort(int a[],int n) { int i,j,d; d=n/2; while(d0) { for(i=d+1;i=n;i++) { a[0]=a[i];j=i-d; while(j=0 a[0]a[j]) { a[j+d]=a[j]; j=j-d; a[j+d]=a[0]; } d=d/2; } } } 四、算法设计 4.1希尔排序流程图： 核心算法： //希尔排序 void ShellInsert(Sqlist *L,int dk, int *s,int *t) { int i,j; for(i=dk+1;i=L-length ;i++) { (*t)++; if(L-r [i].key L-r [i-dk].key ) { L-r [0].key =L-r [i].key ; (*s)++; j=i-dk; (*t)++; while(j0L-r [0].key L-r [j].key ) { L-r [j+dk].key =L-r [j].key ; (*t)++; (*s)++; j-=dk; } L-r [j+dk].key =L-r [0].key ; (*s)++; }//if }//for } void ShellSort(Sqlist *L) { int i,j,dk; int s=0,t=0; for(i=(int)log(L-length +1);i0;i--) //形成增量 for(j=i;j=(int)log(L-length +1);j++) { dk =(int)pow(2,j-i+1)-1; ShellInsert(L,dk, s,t); } printf(希尔排序 比较次数:%d,移动次数:%d\n,t,s); } 五、详细程序清单 内部排序与哈弗曼的总程序： #includestdio.h #includemalloc.h #includestring.h #includestdlib.h typedef struct { unsigned int weight; unsigned char ch; unsigned int parent,lchild,rchild; }HT