《数据结构》
课程设计报告
专业：计算机科学与技术
姓名：钱昉
学号：19110321
指导教师：吉根林
二O一三年九月五日
一、必做题。
1、题目：
编程实现希尔、快速、堆排序、归并排序算法。要求随机产生10000个数据存入磁盘文件，然后读入数据文件，分别采用不同的排序方法进行排序，并将结果存入文件中。
2、算法思想：
利用rand()函数与文件流向文件中读入10000个数据，再将数据分别读入4个数组中，在对数组分别进行希尔、快速、堆排序、归并排序。希尔排序的基本思想：想将整个待排序列划分成若干个子序列，在子序列内分别进行直接插入排序；
然后重复上述的分组和排序；分组方式按着d=[n/2],d=2/d,来进行，最后对整个序列进行直接插入排序。快速排序的基本思想：从待排序中选取一个记录（通常是第一个）放到temp 中，然后将比temp小的放到temp之前，比temp大的放到temp之后。便分成了2个序列，再对2个序列进行相同操作。
堆排序的基本思想：首先创建小顶堆（大），将小顶堆（大）的堆顶作为最小值（大），然后对堆进行操作，使堆再次成为小顶堆（大），依次同上步骤，便是堆排序。归并排序：将若干序列逐步归并，最终归并成一个有序序列。
3、程序结构：
4、测试结果：
（1）希尔排序生产文件
（2）快速排序文件
10000随机 数的文件 数组str1 数组str4
数组str3 数组str2 希尔排序 归并排序 堆排序 快速排序 写入文件1 写入文件4
写入文件3 写入文件2
（3）堆排序文件
（4）归并排序文件
5、收获与体会：
（1）、不同的情况要选择适当的排序方法。
6、参考文献：数据结构教程（c++版）电子工业出版社
二、选做题。
1、题目：
压缩软件：设有一个文本文件A（可以是C源程序），统
计该文件中个字符的频率，对个字符进行Huffman编码，将该文件翻译成Huffman编码文件B，再将Huffman编码文件译码成文件C，并对文件A与C进行比较。
2、算法思想：
生产一个文件，并在文件中写入字符；字符的ascII范围是-128-127，倘若字符定义为无符号类型的，也就是unsigned char，那它的的范围就是0-255，可以定义一个大小为256的int数组str[256]。从文件中读入字符ch,读入一次则str[ch]++，最后便求出文件中字符的频数，再除以文件中字符总数，就求出字符出现的频率。现在就可以创建HuffmanTree的一个对象。接着就可以对文件进行编码与译码。
3、程序结构：
创建文件写入字符
求文件字符
出现的频率
创建对象
对原文件进
行编码
编码结果写
入文件
对编码进行
译码
译码结果写入文件
4、测试结果：（1）、源文件
（2）、编码后文件
（3）、译码后文件
5、收获与体会：
（1）、要有明确的思路才能很好地解决问题。
（2）、对字符的编码与操作有了一定的了解。
6、参考文献：数据结构教程（c++版）电子工业出版社
