不同排序算法的实现和性能比较
学院信息学院
专业计算机系统结构
姓名张凯歌
学号1201001179
指导教师岳昆（副教授）
一、引言 (3)
二、排序算法 (3)
三、算法实现及性能比较 (4)
附录 (9)
参考文献 (16)
一、引言
排序是日常生活和工作中的一个常见问题，其目的是将一组原本无序的数据元素（或记录）序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。
在现实生活中，人们要用到排序。如：学生成绩往往需要按照成绩高低或按学号从前到后排序；在图书馆众多的图书中，需要按照各个学科将书籍归类；排队时从高到低的顺序排队等问题。同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。
二、排序算法
排序是计算机内部经常进行的一种操作，其目的是将一组无序的记录序列调整为有序的记录序列，其可分为内部排序和外部排序（这里我们所说的排序只指前者）。下面我们将对这五中算法进行简单介绍和分析，然后通过实验数据给出五种中算法的性能比较。
(1) 插入排序（insertion sort）：插入排序的思想是将一组无序的元素（这里我们用正整数来代替）分别插入一个已经有序的的数组里，并保证插入后的数组也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组n[1…r]为初始的一个无序数组（为了直观起见，我们这里设定数组从1开始，而不是0），则n[1]默认为只有一个元素的有序数组，n[2]插入只有n[1]构成的有序数组中，则此时有序数组的元素数量变为2。以此类推，到第i个元素时，前i-1个元素已经是有序的，此时只需将第i个元素插入到有序数组中并使之保持有序。如此直至最后一个元素插入完毕，整个插入排序完成。
(2) 冒泡排序（bubble sort）：冒泡排序每遍历一次数组，便将最大的元素放到数组最后边。下次遍历将次大的元素放到数组倒数第二位，依次类推，直至将最小的元素放到最前边，此时冒泡排序完成。
(3) 堆排序（heap sort）：堆排序与其他排序算法最大的区别是它依靠一种特殊的数据结构——堆来进行排序。堆是一种完全二叉树，并且根节点不大于左右子树中的所有节点（这里描述的是小根堆，大根堆的话情况恰好相反），n[i]<=n[2*i]&&n[i]<=n[2*i+1]。因此堆排序算法首先要将给出的无序数组构造成一个堆，然后输出根节点（最小元素），将剩余元素重新恢复成堆，再次输出根节点。依次类推，直至最后一个节点输出，此时堆排序完成。
(4) 合并排序（merge sort）：这里的合并排序和下边要描述的快速排序都采用了分而治之的思想，但两者仍然有很大差异。合并排序是将一个无序数组n[1…r]分成两个数组n[1…r/2]与n[r/2+1…r]，分别对这两个小数组进行合并排序，然后再将这两个数组合并成一个大数组。由此我们看出合并排序时一个递归过程（非递归合并排序这里不做讨论）。合并排序的主要工作便是“合并”，两个小规模数组合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行的。
(5) 快速排序（quick sort）：如上所述，快速排序也是采用了分而治之的思想，但与合并排序有所不同的是快速排序先“工作”（这里是分割或partition），再递归。快速排序的主要思想是保证数组前半部分小于后半部分的元素，然后分别对前半部分和后半部分再分别进行排序，直至所有元素有序。
三、算法实现及性能比较
这里我们通过c++语言来实现各种排序算法（源码见附录），程序运行环境为windows xp，所用编译器为vc++ 6.0。如图1所示
图1 windows xp操作系统
在程序中我们根据数据规模的不同产生不同的随机整型数组，然后分别让不同
的排序算法来进行从小到大的排序。这里需要注意的是：每种排序算法在相同的输入规模中原始无序数据都是一样的。例如五种排序算法要对长度为100的无序数组进行排序，它们所要排序的无序数组都是一样的，我们以此来保证实验的公正性。在这里我们认为比较次数是排序算法的主要操作，因此我们在每个排序算法中加入计数器来记录排序过程中的比较次数，以此来作为对算法性能分析的主要参数（排序时间作为辅助参数）。表1为在输入规模分别为100,1000,2000,5000,10000,100000时各个算法的元素比较次数。
表1 排序算法比较次数性能比较
为了直观起见，我们根据实验数据画出各种排序算法在不同输入规模下比较次数的变化趋势图如图2所示：
图2排序算法性能趋势图
由上图我们基本上看出插入排序和冒泡排序的比较次数随输入规模的呈非线性增长，而后三种排序方法——堆排序，合并排序，快速排序的比较次数随输入规模的增长基本呈线性变化趋势。因此我们在这里暂且将前两种排序归类为低效排序算法，而将后三种归类为高效排序算法。图3和图4更加清楚地显示了这两类算法的变化趋势。
图4插入与冒泡排序性能比较图
图5高效排序算法性能分析图
实验结果与我们对这五种算法的性能理论分析基本吻合：插入排序与冒泡排序的时间复杂度为O(n*n)，而后三种排序算法的时间复杂度为O(nlogn)。图4还显示出虽然冒泡排序和插入排序的时间复杂度相同，但插入排序的性能仍然比冒泡排序好。
关于图5我们仍有一点要说明，就是从比较次数上看合并排序似乎是最高效
的算法，但我们知道快速排序才是排序算法中最快的算法，这里理论似乎和实验结果出现了矛盾。下面我们以算法执行的时间来进行辅助说明，如表2所示：
次数计数排序基数排序堆排序快速排序希尔排序直接插入排序冒泡排序
1 0.0000 0.0310 0.0470 0.0470 0.0310 14.7970 58.0930
2 0.0000 0.0470 0.0310 0.0470 0.0470 16.2500 53.3280
3 0.0000 0.0310 0.0310 0.0310 0.0310 14.4850 62.4380
4 0.0000 0.0320 0.0320 0.0470 0.0310 17.1090 61.8440
5 0.0000 0.0310 0.0470 0.0470 0.0310 16.9380 62.3280
6 0.0000 0.0310 0.0310 0.0470 0.0310 16.9380 57.7030
7 0.0000 0.0310 0.0470 0.0310 0.0310 16.8750 61.9380
8 0.0150 0.0470 0.0310 0.0470 0.0320 17.3910 62.8600
9 0.0000 0.0320 0.0470 0.0460 0.0310 16.9530 62.2660
10 0.0000 0.0470 0.0310 0.0470 0.0310 17.0160 60.1410
11 0.0000 0.0930 0.0780 0.0320 0.0310 14.6090 54.6570
12 0.0000 0.0310 0.0320 0.0310 0.0310 15.0940 62.3430
13 0.0000 0.0310 0.0310 0.0470 0.0310 17.2340 61.9530
14 0.0000 0.0320 0.0470 0.0470 0.0310 16.9060 61.0620
15 0.0000 0.0320 0.0320 0.0460 0.0320 16.7810 62.5310
16 0.0000 0.0470 0.0470 0.0620 0.0310 17.2350 57.1720
17 0.0150 0.0160 0.0320 0.0470 0.0310 14.1400 52.0320
18 0.0150 0.0160 0.0310 0.0310 0.0310 14.1100 52.3590
19 0.0000 0.0310 0.0320 0.0460 0.0320 14.1090 51.8750
20 0.0000 0.0310 0.0320 0.0460 0.0320 14.0780 52.4840
21 0.0150 0.0780 0.0470 0.0470 0.0310 16.3750 59.5150
22 0.0000 0.0310 0.0310 0.0470 0.0320 16.8900 60.3440
23 0.0000 0.0310 0.0310 0.0310 0.0310 16.3440 60.0930
24 0.0000 0.0310 0.0310 0.0470 0.0310 16.3440 60.5780
25 0.0000 0.0320 0.0470 0.0470 0.0470 16.3590 59.7810
26 0.0160 0.0470 0.0310 0.0470 0.0310 16.1250 61.0620
27 0.0000 0.0310 0.0470 0.0470 0.0310 16.7810 59.6100
28 0.0150 0.0320 0.0320 0.0470 0.0310 16.9220 56.8130
29 0.0000 0.0310 0.0310 0.0310 0.0310 15.0790 57.8120
30 0.0000 0.0310 0.0320 0.0460 0.0320 14.7810 58.8280
31 0.0000 0.0310 0.0310 0.0470 0.0310 15.8590 59.1400
32 0.0000 0.0470 0.0320 0.0310 0.0310 16.0940 59.1560
33 0.0000 0.0470 0.0310 0.0310 0.0310 15.9850 59.1400
34 0.0000 0.0310 0.0310 0.0470 0.0320 16.0150 59.2500
35 0.0000 0.0310 0.0470 0.0470 0.0310 16.7660 57.9840
36 0.0000 0.0310 0.0320 0.0470 0.0310 15.3750 59.0470
37 0.0000 0.0320 0.0460 0.0470 0.0320 16.0310 58.9060
38 0.0000 0.0310 0.0310 0.0470 0.0310 15.9530 57.2650
39 0.0160 0.0310 0.0470 0.0470 0.0310 15.9530 57.5160
40 0.0150 0.0310 0.0320 0.0470 0.0310 14.7030 56.6710
平均值0.0031 0.0360 0.0372 0.0437 0.0320 15.9946 58.7480 最小值0.0000 0.0160 0.0310 0.0310 0.0310 14.0780 51.8750 最大值0.0160 0.0930 0.0780 0.0620 0.0470 17.3910 62.8600
表2高效排序算法排序时间比较
表2中的数据位各种排序算法在一定规模的输入中所消耗的排序时间。该表显示快速在相同输入规模（上边说过相同的规模下三种排序算法原始数据是一样的）快速排序确实是最快的，而合并排序和堆排序所耗时间基本相同。如果我们深入研究合并排序算法会发现：合并排序最主要的工作是将两个有序的数组进行合并，这其中虽然连个数组合并过程中比较的次数并不是很多，但在合并的过程中除了比较之外仍然有许多额外的工作要做（保存合并结果，将合并结果返回给原数组等，），这也就导致了合并排序虽然比较最少，但执行时间却并不是最少的结果。
最后我们得出结论：
时间性能上，
Merge > Heap > Quick > BInsert > Insert > Simple Selection > Shell > Bubble 比较次数上，
Shell > Bubble = SimpleSelection > Insert > Heap > Quick > BInsert > Merge 数组元素的交换次数上，
Bubble > Quick > BInsert > Insert > Heap > Merge > Shell > SimpleSelection 内存的消耗上，
Merge > Heap > Quick = BInsert = Insert = SimpleSelection = Shell = Bubble
附录
插入排序源码：
int insert_sort(int data[],int size)
{
int i,j,tmp;
unsigned long count_i=0;
for (i=1;i<=size;i++)
{
j=i;
tmp=data[i];
while (j>1&&tmp {data[j]=data[j-1]; j--;count_i++; } if(j>1) count_i++; data[j]=tmp; } return count_i; } 冒泡排序源码： int buble_sort(int data[],int size) { int i,j,k,temp; long counter=0; for (i=size;i>1;i=k) {for (j=1,k=1;j { if (data[j]>data[j+1]) { temp=data[j];data[j]=data[j+1];data[j+1]=temp; k=j; } counter++; } } return counter; } 堆排序源码： heap_restor(int input[],int i,int m) //也就是sift-down操作，但这里用递归方式来实现 { int ma; if((i<=m/2)&&(input[i]>min(input[2*i],input[2*i+1]))) { /*printf("this is heap_restor!\n"); printf("i=%d\n",i);*/ if(input[2*i] { ma=input[i]; input[i]=input[2*i]; input[2*i]=ma; /* printf("input[i]=%d\n",input[i]); printf("input[2*i]=%d\n",input[2*i]);*/ heap_restor(input,2*i,m); } else { ma=input[i]; input[i]=input[2*i+1]; input[2*i+1]=ma; /* printf("input[i]=%d\n",input[i]); printf("input[2*i]=%d\n",input[2*i]);*/ heap_restor(input,2*i+1,m); } count_h=count_h+2; } else if(i<=m/2) count_h++; } void heap_creat(int input[],int m) { int num; for(num=m/2;num>=1;num--) heap_restor(input,num,m); } unsigned long heap_sort(int input[],int output[],int m) { int i,num,counter; num=m; heap_creat(input,m); for(i=1;i<=m;i++) { output[i]=input[1]; input[1]=input[num]; heap_restor(input,1,--num); } return count_h; } 合并排序： merge_list(int *input,int a,int b,int c,int d) { int start1,end1,start2,end2,i,j; /*int result_lqc[MAXLINE_S];*/ int *result_lqc; result_lqc=(int*)malloc((d-a+1)*sizeof(int)); start1=a; end1=b; start2=c; end2=d; i=0; /*printf("start1=%d,end1=%d,start2=%d,end2=%d",a,b,c,d);*/ while(start1<=end1&&start2<=end2) { /* printf("this is test!"); printf("test input[%d]:%d\n",i,input[i]);*/ if(input[start1] { result_lqc[i]=input[start1]; /* printf("result[%d]=%d\n",i,result_lqc[i]);*/ i++; start1++; } else { result_lqc[i]=input[start2]; /* printf("result[%d]=%d\n",i,result_lqc[i]);*/ i++; start2++; } count_m++; //printf("counter=%lu\n",count); } if(start1<=end1) for(j=start1;j<=end1;j++) { result_lqc[i]=input[j]; /* printf("result[%d]=%d\n",i,result_lqc[i]);*/ i++; else if(start2<=end2) { for(j=start2;j<=end2;j++) { result_lqc[i]=input[j]; /*printf("result[%d]=%d\n",i,result_lqc[i]);*/ i++; } } j=0; for(i=a;i<=d;i++) { input[i]=result_lqc[j]; /* printf("input[%d]=%d\n",i,input[i]);*/ j++; } free(result_lqc); } unsigned long merge_sort(int input[],int first,int last) { int middle; if(first { middle=(first+last)/2; merge_sort(input,first,middle); merge_sort(input,middle+1,last); merge_list(input,first,middle,middle+1,last); } return count_m; } 快速排序： partition(int input[],int low,int high) int key,i,p,r; p=low; r=high; key=input[p]; while(p { // printf("counter=%lu\n",count_q); for(i=r;i>p;i--) { if(input[i]<=key) { input[p]=input[r]; p++; count_q++; break; } r--; count_q++; } for(i=p;i { if(input[i]>key) { input[r]=input[p]; r--; count_q++; break; } p++; count_q++; } // printf("counter=%ul\n",count_q); } input[p]=key; for(i=low;i<=high;i++) /* printf("%d ",input[i]); printf("\n"); printf("partition=%d\n",p);*/ return p; } unsigned long quick_sort(int input[],int low,int high) { int i; if(low { i=partition(input,low,high); quick_sort(input,low,i-1); quick_sort(input,i+1,high); } return count_q; } 参考文献 [1]王卫东等算法设计与分析导论机械工业出版社2007..7 [2]陈先红基于vb的排序算法比较科技信息2009年第35期 [3]百度与谷歌等互联网工具 昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 程序流程图： 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include 软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为 一、实验目的 （1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树 代码： #include 实验报告 实验课名称：数据结构实验 实验名称：文件压缩问题 班级：20132012 学号：姓名：时间：2015-6-9 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 二、数据结构设计 首先定义一个结构体： struct head { unsigned char b; //记录字符 long count; //权重 int parent,lch,rch; //定义双亲，左孩子，右孩子 char bits[256]; //存放哈夫曼编码的数组 } header[512],tmp; //头部一要定设置至少512个,因为结 点最多可达256,所有结点数最多可 达511 三、算法设计 输入要压缩的文件读文件并计算字符频率根据字符的频率，利用Huffman 编码思想创建Huffman树由创建的Huffman树来决定字符对应的编码，进行文件的压缩解码压缩即根据Huffman树进行译码 设计流程图如图1.1所示。 图1.1 设计流程图 (1)压缩文件 输入一个待压缩的文本文件名称(可带路径)如:D:\lu\lu.txt 统计文本文件中各字符的个数作为权值,生成哈夫曼树；将文本文件利用哈夫曼树进行编码,生成压缩文件。压缩文件名称=文本文件名.COD 如:D:\lu\lu.COD 压缩文件内容=哈夫曼树的核心内容+编码序列 for(int i=0;i<256;i++) { header[i].count=0; //初始化权重 header[i].b=(unsigned char)i; //初始化字符 } ifstream infile(infilename,ios::in|ios::binary); while(infile.peek()!=EOF) { infile.read((char *)&temp,sizeof(unsigned char)); //读入一个字符 header[temp].count++; //统计对应结点字符权重 flength++; //统计文件长度 } infile.close(); //关闭文件 for(i=0;i<256-1;i++) //对结点进行冒泡排序,权重大的放在上面，编码时效率高 for(int j=0;j<256-1-i;j++) if(header[j].count #include 实验四 哈夫曼编码的贪心算法设计（4学时） [实验目的] １. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 核心源代码 #include //选择两个parent为0，且weight最小的结点s1和s2 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++) 数据结构实验报告 实验名称：实验3——哈夫曼编码 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月24日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 2. 程序分析 2.1存储结构： struct HNode { char c;//存字符内容 int weight; int lchild, rchild, parent; }; struct HCode { char data; char code[100]; }; //字符及其编码结构 class Huffman { private: HNode* huffTree; //Huffman树 HCode* HCodeTable; //Huffman编码表 public: Huffman(void); void CreateHTree(int a[], int n); //创建huffman树 void CreateCodeTable(char b[], int n); //创建编码表 void Encode(char *s, string *d); //编码 void Decode(char *s, char *d); //解码 void differ(char *,int n); char str2[100];//数组中不同的字符组成的串 int dif;//str2[]的大小 ~Huffman(void); }; 结点结构为如下所示： 三叉树的节点结构： struct HNode//哈夫曼树结点的结构体 { int weight;//结点权值 int parent;//双亲指针 int lchild;//左孩子指针 int rchild;//右孩子指针 char data;//字符 }; 示意图为： int weight int parent int lchild int rchild Char c 编码表节点结构： 嘉应学院计算机学院 实验报告 课程名称：数据结构课程设计 开课学期：2017-2018学年第2学期 班级： 指导老师： 实验题目：哈夫曼树 学号： 姓名： 上机时间： 一、实验目的 本实验的目的是通过对简单的哈夫曼编/译码系统的设计与实现来熟练掌握树形结构在实际问题中的应用。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此试验即设计这样的一个简单的编/译码系统。系统应该具备如下的几个功能。 1、求出各个叶子节点的权重值 输入一个字符串，统计其中各个字母的个数和总的字母个数。 2、构造哈夫曼树 统计出的字母种类为叶子结点个数，每个字母个数为相应的权值，建立哈夫曼树。 3、打印哈弗曼树的功能模块 按照一定形式打印出哈夫曼树。 4、编码 利用已经建立好的哈夫曼树进行编码。 5、译码 根据编码规则对输入的代码进行翻译并将译码。 三、实验步骤 1、实验问题分析 （1）设计一个结构体数组保存字母的类型和个数。 { ; 字母的种类 ; 字母的个数 }; （2）在构造哈夫曼树时，设计一个结构体数组保存哈夫曼树中各结点 的信息，根据二叉树的性质可知，具有n个结点的哈夫曼树共有21个结点，所以数组大小设置为21,描述结点的数据类型为： { ; 权值 ; 双亲 ; 左孩子 ; 右孩子 }; []; 定义此类型的数组 （3）求哈夫曼编码，实质上是在已经建立的哈夫曼树中，从叶子结点开始，沿着结点的双亲链表域退回到根节点，每退回一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼值，由于一个字符的哈夫曼编码是从根结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码，所以设计如下的数据类型： 10; { []; 每个结点的哈夫曼编码 ; 开始位置 }; （4）设置全局变量。 s; 为输入的字符串 0; 记录输入的字符串中字母的种类，即叶子结点个数 0; 记录字符串中字母的总个数 []叶子结点类型 2、功能（函数）设计 （1）统计字母种类和个数模块 此模块的功能为从键盘接受一个字符串，统计字符串中字母种类即结 点个数，每种字母出现次数即各叶子结点的权值。全局变量s保存输 入的字符串，将种类和个数保存到[]中。 函数原型：（） 如输入的字符串是“”则显示如下。 实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include 哈夫曼编码步骤： 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。） 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，直到集合F中只有一棵二叉树为止。 /*------------------------------------------------------------------------- * Name: 哈夫曼编码源代码。 * Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在Win-TC 下测试通过 * 实现过程：着先通过HuffmanTree() 函数构造哈夫曼树，然后在主函数main()中 * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在 * 父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。*------------------------------------------------------------------------*/ #include 实验六哈夫曼树的建立与操作 一、实验要求和实验内容 1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表 二、详细代码（内包含了详细的注释）： #include cout<<"输入第"< 一、问题描述 1.用户输入字母及其对应的权值，生成哈夫曼树； 2.通过最优编码的算法实现，生成字母对应的最优0、1编码； 3.先序、中序、后序遍历哈夫曼树，并打印其权值。 二、方法思路 1.哈夫曼树算法的实现 §存储结构定义 #define n 100 /* 叶子树*/ #define m 2*(n) –1 /* 结点总数*/ typedef struct { /* 结点型*/ double weight ; /* 权值*/ int lchild ; /* 左孩子链*/ int rchild ; /* 右孩子链*/ int parent; /* 双亲链*/ 优点？ }HTNODE ; typedef HTNODE HuffmanT[ m ] ; /* huffman树的静态三叉链表表示*/ 算法要点 1)初始化：将T[0]，…T[m-1]共2n-1个结点的三个链域 均置空( -1 ),权值为0； 2)输入权值：读入n 个叶子的权值存于T的前n 个单元 T[0]，…T[n], 它们是n 个独立的根结点上的权值； 3)合并：对森林中的二元树进行n-1次合并，所产生的新 结点 依次存放在T[i](n<=i<=m-1)。每次合并分两步： (1) 在当前森林中的二元树T [0]，…T[i-1]所有结点中 选取权值 最小和次最小的两个根结点T[p1]和T[p2]作为合并对象，这 里0<= p1，p2<= i –1; (2) 将根为T[p1]和T[p2]的两株二元树作为左、右子树 合并为一 株新二元树，新二元树的根结点为T[i]。即 T[p1].parent =T[p2].parent = i ,T[i].lchild= p1, #include if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s2 = min; } void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++) {/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++) { (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } /*非叶子结点初始化*/ /* ------------初始化完毕！对应算法步骤1---------*/ for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/ { /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; } }/*哈夫曼树建立完毕*/ void outputHuffman(HuffmanTree HT, int m) { if(m!=0) { 计算机科学与技术学院数据结构实验报告 班级2014级计算机1班学号20144138021 姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期2016.1.5 一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。 3、译码。 利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： ┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊ 目录 目录 (1) 1 课程设计的目的和意义 (2) 2 需求分析 (3) 3 系统设计 (4) (1)设计思路及方案 (4) (2)模块的设计及介绍 (4) (3)主要模块程序流程图 (6) 4 系统实现 (10) (1)主调函数 (10) (2)建立HuffmanTree (10) (3)生成Huffman编码并写入文件 (13) (4)电文译码 (14) 5 系统调试 (16) 小结 (18) 参考文献 (19) 附录源程序 (20) ┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊ 1 课程设计的目的和意义 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。 作为软件工程专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。 在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。 学生学号Xxx实验课成绩 学生实验报告书 实验课程名称数据结构与算法综合实验 开课学院计算机科学与技术学院 指导教师姓名xxx 学生姓名xxx 学生专业班级xxxx 2015--2016学年第2学期 实验课程名称：数据结构与算法综合实验 实验项目名称二叉树与赫夫曼图片压缩报告成绩 实验者xx专业班级xxx组别 同组者完成日期2016年5月 2日第一部分：实验分析与设计（可加页） 一、实验目的和要求 1.目的 掌握树的存储结构 掌握二叉树的三种遍历方法 掌握 Huffman树、Huffman编码等知识和应用 使用 C++、文件操作和 Huffman算法实现“图片压缩程序”专题编程。 2.要求 针对一幅 BMP 格式的图片文件，统计 256 种不同字节的重复次数，以每种字 节重复次数作为权值，构造一颗有 256 个叶子节点的哈夫曼二叉树。 利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。 压缩后的文件与原图片文件同名，加上后缀.huf （保留原后缀），如 pic.bmp 压 缩后 pic.bmp.huf 二、分析与设计 依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为： ① 读取图片文件、统计权值 ②生成 Huffman树 ③生成 Huffman编码 ④ 压缩图片文件 ⑤ 保存压缩的文件 1.数据结构的设计 记录统计 256种不同字节的重复次数使用整型数组。 int weight[256] = { 0 }; 二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方 式存储二叉树。 Huffman编码存储结构 struct HTNode { int weight;//权值 0023算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。 译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为d T(c)。d T(c)也是字符c的前缀码长。则平均码长定义为： 哈夫曼树描述文档 一、思路 通过一个argv[]数组存储从test文件中读取字母，然后利用ascal 码循环计算每个字母的权值，利用weight[]是否为零，确定叶子节点，节点个数为count，传入到构建哈夫曼树的子程序中，然后利用cd[]数组存储每一个叶子节点的哈夫曼代码.输出代码时，通过与argv[]数组的比对，扫描ht数组，进而读出所有的数据。 二、截图 三、代码 #include intrchild; }HTNode; typedefstruct { char cd[50]; int start; }HCode; using namespace std; int enter(char argv[])//进行读入操作 { fstream in; ofstream out; char c; int number=0;//字母个数置为0 in.open("test.txt",ios::in); //打开文件test.txt out.open ("code.txt",ios::trunc); //打开文件code.txt，如果不存在就新建一个，如果存在就清空 if(!in.eof()) in>>c; //从test.txt中读取一个字符存入c printf("原文本是:\n"); while(! in.eof()){ //文件不为空，循环读取一个字符 cout< 《数据结构与算法》课程设计（2009/2010学年第二学期第20周） 指导教师：王老师 班级：计算机科学与技术（3）班 学号： 姓名： 《数据结构与算法》课程设计 目录 一、前言 1．摘要 2．《数据结构与算法》课程设计任务书 二、实验目的 三、题目--赫夫曼编码/译码器 1．问题描述 2．基本要求 3．测试要求 4．实现提示 四、需求分析--具体要求 五、概要设计 六、程序说明 七、详细设计 八、实验心得与体会 前言 1．摘要 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。 算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 2．《数据结构与算法》课程设计任务书 《数据结构与算法》是计算机专业重要的核心课程之一，在计算机专业的学习过程中占有非常重要的地位。《数据结构与算法课程设计》就是要运用本课程以及到目前为止的有关课程中的知识和技术来解决实际问题。特别是面临非数值计算类型的应用问题时，需要选择适当的数据结构，设计出满足一定时间和空间限制的有效算法。 本课程设计要求同学独立完成一个较为完整的应用需求分析。并在设计和编写具有一定规模程序的过程中，深化对《数据结构与算法》课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使自己的程序设计与调试水平有一个明显的提高。中衡算法分析与【设计明细】-实验二-哈夫曼编码
贪心算法构造哈夫曼树
数据结构 哈夫曼编码实验报告
数据结构哈夫曼树的实现
实验三.哈夫曼编码的贪心算法设计
北邮数据结构实验3哈夫曼编码
数据结构课程设计-哈夫曼树
哈夫曼编码算法实现完整版
哈夫曼编码步骤
哈夫曼树的建立与操作
哈工大数据结构大作业——哈夫曼树生成、编码、遍历
哈夫曼树建立、哈夫曼编码算法的实现
哈夫曼树 实验报告
数据结构课程设计(哈夫曼编码)
武汉理工大学数据结构与算法综合实验哈夫曼树(1)
0023算法笔记——【贪心算法】哈夫曼编码问题
构建哈夫曼树及输出哈夫曼代码及算法思想
数据结构课程设计哈夫曼编码(DOC)
相关主题
文本预览