数据结构课程设计报告

信息与软件工程学院

课程名称：数据结构课程设计学院专业：信息与软件学院学生姓名：陈海松学 号：日 期：课程设计报告 XX专业 文书豪

黄震析 魏波 刘润卿 张英旭

2011223040024 2011029190009

2011223040004 2011029120029 2011223040016 2011223040020 指导教师：周益民

2012年06月08日

数据结构课程设计报告

目录

第一章

1.1. 1.2. 1.3. 第二章

2.1. 2.2. 2.3.

绪论 ....................................................................................................................... 1 数据结构课程设计概要 ....................................................................................... 1 训练要求 ............................................................................................................... 1 课程设计的基本内容 ........................................................................................... 2 约瑟夫生死者游戏 ............................................................................................... 3 游戏描述 ............................................................................................................... 3 需求分析 ............................................................................................................... 3 概要设计 ............................................................................................................... 4 2.3.1. 循环链表 ........................................................................................................ 4 2.3.2. 顺序表 ............................................................................................................ 4 详细设计 ............................................................................................................... 4 2.4.1. 循环链表解决方案 ........................................................................................ 4 2.4.2. 顺序表解决方案 ............................................................................................ 6 低复杂度求解进阶方案 ....................................................................................... 7 测试分析 ............................................................................................................... 8 小结 ..................................................................................................................... 10 哈夫曼压缩编码 ................................................................................................. 11 哈夫曼树和哈夫曼编码 ..................................................................................... 11 3.1.1. 哈夫曼树 ...................................................................................................... 11 3.1.2. 哈夫曼编码 .................................................................................................. 11 需求分析 ............................................................................................................. 12 概要设计 ............................................................................................................. 13 详细设计 ............................................................................................................. 14 测试分析 ............................................................................................................. 22 小结 ..................................................................................................................... 23 报告总结 ............................................................................................................. 26 参考文献 ............................................................................................................. 27

2.4.

2.5. 2.6. 2.7. 第三章

3.1.

3.2. 3.3. 3.4. 3.5. 3.6. 第四章 第五章

数据结构课程设计报告

第一章 绪论

计算机科学与技术专业强调四个方面的专业能力：计算思维能力、算法设计与分析能力、程序设计与实现能力和计算机系统的认知、分析、设计和运用能力。

1.1. 数据结构课程设计概要

《数据结构课程设计》是《数据结构》课程的深入与实践，是计算机科学与技术学科的核心课程。通过数据结构课程设计的学习.目的在于使学生：

1、 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。 3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

4．使学生学会自主学习，也学会以团队的形式思考问题，解决问题，培养学生的团队合作能力。

5．使学生在团队工作中培养良好的人际交流的能力，以及沟通能力„„ 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。

算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。

《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

1

数据结构课程设计报告

学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。

1.2. 训练要求

数据结构课程设计于具体的数据结构教科书，重点放在数据的存储及在存储结构上实现的相关典型算法上。以较多的应用实例来涵盖数据结构这门课程所要求的各类重要基础知识。

结合实际应用的要求，使课程设计既覆盖教学所要求的知识点，又接近工程的实际需要。训练了实际分析问题、解决问题及编程能力的整体提高。

通过详细的实例分析、循序渐进的描述，启发同学们顺利完成设计。课程设计将设计要求、需求分析、算法设计、编程和测试运行分开，为同学们创造分析问题、思考的条件。在充分理解要求和算法的前提下，完全可以不按教材中提供的参考程序，设计出具有特色的应用程序。

课程设计的内容基本上按照课程教学的顺序设计，可以让学生循序渐进地学习，以加深同学们对数据结构知识的理解。

课程设计的最后提出了几个比较大的综合课程设计题目，以进一步锻炼同学们的动手能力。

1.3. 课程设计的基本内容

主要内容包含有：

1．链表的应用：约瑟夫生死者游戏。 2．树结构的应用：赫夫曼编码的应用。

学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。

学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。课程设计按照教学要求需要16课时的时间完成，上机调试程序时间总共不少于16小时。

2

数据结构课程设计报告

第二章 约瑟夫生死者游戏

在这一次的课程中，将利用线性链表，特别是循环链表来实现约瑟夫生死问题。

2.1. 游戏描述

【其一】据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位臵，于是逃过了这场死亡游戏。

【其二】17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

【其三】N个人，编号0..N1，从0开始报数，报到M1的退出，通常取MN。剩下的人继续从0开始报数，报到M1的退出，如此往复。求最终胜利者的编号。

2.2. 需求分析

构建线性表，通过线性表循环地向后移动来模拟“约瑟夫生死问题”的进行,最后给出模拟结果。

分别用数组和链表来实现此次模拟。 并思考是否有其他更优解决方案。

程序提示使用者输入人数N，和每次报数个数M，输出淘汰序列和最后赢家。

3

数据结构课程设计报告

2.3. 概要设计 2.3.1. 循环链表

议定30个人围成一圈，由第1个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔到大海中，如此循环地进行，直到剩下最后一个乘客为止。

约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有最后一个人为止。

2.3.2. 顺序表

为了节省空间复杂度，我们提出了这样一种问题：能否采用线性表来实现？ 答案是肯定的。那么怎样实现呢？

以动态数组元素代替循环链表节点的算法实现。 考虑：动态数组的申请、使用、回收三原则。

用30个元素数组来存放结果，初始化全为1，如果这个人被丢到海里了，就把对应位臵的元素臵为0；用一个变量依次对数组里不为0的元素计数，数到9则把对应位臵的数组元素臵0；循环控制可以用乘客数量来控制；初始为30,每有一个元素被臵0，则乘客数量减1，直到1。

2.4. 详细设计

2.4.1. 循环链表解决方案

伪代码：

1.首先定义链表节点。数据域用整数表示人员编号。

2.然后将节点组成为30个节点的单循环链表。删除计数器臵0。

3.从指定位臵开始计数，移动计数器臵1，移动指针到下一个节点，移动计数器加1。计数器臵8时，将下一节点删除。删除计数器加1。

4是否只剩下最后一人？否则从删除节点的下一个节点开始作为起始位臵，跳至3。

4

数据结构课程设计报告

是则结束循环。

int JonesList(Jonse * Head, int N, int M) {

Jonse *p,*q; p=Head; q=p->next;

while(q->next!=p) {

q=q->next; }

while(p!=p->next) {

for(int i=1;kq=p;

p=p->next; }

q->next=p->next; free(p); p=q->next; }

return p->number; }

采用线性链表来解决约瑟夫问题必然使用到N个节点，节点中既要存储数据信息也需要存储位臵信息(即循环链表的指针)。存储空间使用较多，为O(N)。 构造线性循环链表

Jonse * Create(int n) {

Jonse *h,*p; int i;

h=(Jonse *)malloc(sizeof(Jonse)); p=h;

for(i=1;i<=n;i++) {

p->code=i; if(ip->next=(Jonse *)malloc(sizeof(Jonse)); p=p->next; } }

p->next=h; return h; }

输出遍历链表

void ShowList(Jonse *h) {

Jonse *p; 5

数据结构课程设计报告

} p=h; do {

printf(\"%d\\ p=p->next; } while(p!=h);

执行算法

void Out(Jonse *h,int i,int d,int num, int flag) {

Jonse *p,*q; int k; p=h;

for(q=h;q->next!=h;q=q->next); for(k=1;kq=p;p=p->next; }

while(p!=p->next) {

for(k=1;kq=p;p=p->next; }

printf(\"%d\\ q->next=p->next; free(p); p=NULL; p=q->next; flag++;

if(num-flag==2) break; }

printf(\"%d\\n\ free(p); p=NULL; }

2.4.2. 顺序表解决方案

int JonesArray(int N, int M) {

int *jones; int winner;

jones=new int(N); int i,j,t;

for(i=0;ifor(i=N;i>=1;i--) { 6

数据结构课程设计报告

t=(t+M-1)%i; cout<jones[j-1]=jones[j]; } }

winner=jones[0];

cout<<\"winner is \"<2.5. 低复杂度求解进阶方案

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(MN)，当N，M非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：N个人，编号0..N1，从0开始报数，报到M1的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人，编号一定是(M1)modN，出列之后，剩下的N1个人组成了一个新的约瑟夫环，以编号为kMmodN的人开始：

k,k1,k2,,N2,N1,0,1,2,,k2 k0并且从k开始报0。现在我们把他们的编号做一下转换： k11

变换后就完完全全成为了N1个人报数的子问题，假如我们知道这个子问题的解：k2N2(N1)1例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是N个人情况的

解吗？

变回去的公式很简单，相信大家都可以推出来：

x'(xk)modN

如何知道N1个人报数的问题的解？对，只要知道N2个人的解就行了。N2个人的解呢？当然是先求N3的情况——这显然就是一个倒推问题！

好了，思路出来了，下面写递推公式：

令f表示i个人玩游戏报M退出最后胜利者的编号，最后的结果自然是f(n)f[n]。递推公式

7

数据结构课程设计报告

f(1)0f(fM)modi,i1有了这个公式，我们要做的就是从1..N1顺序算出f的数值，最后结果是f(N)。因为实际生活中编号总是从1开始，我们输出f(N)1。由于是逐级递推，不需要保存每个f，程序也是异常简单。

int JonesWinner(int N, int M) {

int winner=0;

for(int i=2; i<=N; i++) winner=(winner+M)%i; winner+=1;

cout<<\"winner is \"<2.6. 测试分析

上面一共提到了可以使用3种方法来实现对约瑟夫问题的模拟，下面就对这三种方法的实现情况进行测试。对于每个实现方法的测试，输入为N、M，输入为胜利者编号。

下面附上一些程序运行结果：

8

数据结构课程设计报告

上面只是进行了简单的测试，从上面的测试我们可以看出至少这三种方案都正确的进行了模拟，得出了我们想要的结果。

关于效率问题，前面有提到过顺序表和链表的实现的时间复杂度都是O(MN)，但是在实际的程序运行还是存在差异。

顺序表每次淘汰一个数后还需要耗费时间将后续的数向前搬移1个单元；链表每次淘汰一个节点后需要耗费时间释放该节点的内存空间。

数学的模拟方法确实就比较高而稳定了，时间复杂度为O(N)。

其实本人还进行了很多的测试，想要总结一下它们之间的效率对比问题。但是最后发现测试结果不规律，主要是链表方法的结果不规律。由于未能分析得出非常确切的答案，所以下面只进行大致的描述，提出猜想，待以后进行验证。

顺序表实现和数学实现还是比较规律的，比较可以分析理解。

关于链表实现不规律的问题，我直接举一个例子就能看到了，如右图。都是N=10000，M=1的结果是M=2的结果的9倍左右，差距非常的大。再进行其他的一些测试，测试结果也是存在波动的。

下面是本人关于这个问题的一些猜想。

当M=1时，链表的处理比较特殊，链表不会往后移动，会直接淘汰当前的节点，释放（free）单元。从理论上来说，不管M为何值，最终N个节点都会释放的，也就是要free()N次，一般我们认为这N次释放的时间花销应该是一样的，那么当M=1时，时间花销应该是最小的，因为它节约了向后移动的时间花销。但是我们实际结果，不仅不是最小的，反而效率非常低下，当M=2时，每次向后移动一个节点，效率马上又不那么低下了。

从此，我们可以推断：释放内存操作不能够连续高效地进行，操作之间存在一些间隔反而能更加高效。这里面就应该设计到内存池的实现机制的问题了。

在此，我们可以猜想：链表实现方法的效率的不规律受内存池的机制（内存分配与释放等）影响较大。比如：free()之后内存可能不会立即归还系统，下次malloc时也许会重用，那么这个时间间隙是多久呢？在时间间隙中有要释放内存单元呢？

该问题需进一步研究后得出结论，在此就简单描述了。

9

数据结构课程设计报告

2.7. 小结

通过上面的实验，验证了用3种方法实现约瑟夫的模拟。另外，有趣的是在分析实验数据的时候发现了链表实现的不规律问题，猜想原因是与内存池机制有关，留待后续处理。

通过遇到的问题，真正让我感受到，很多时候实践确实是很有价值的，能发现问题，也只有通过实践后才能去肯定我们的理论技术。

当我们只有真正去动手做时，就会发现该游戏程序中很多问题，在发现问题的过程中，也伴随着大家培养解决问题的能力，促进这个团队的工作力与协作性，在诸多问题的一个个解决过程中，每一位队员都学习了良好的经验与纠错能力。

总之，一句话，我们正在成长。

10

数据结构课程设计报告

第三章 哈夫曼压缩编码

3.1. 哈夫曼树和哈夫曼编码 3.1.1. 哈夫曼树

哈夫曼树。给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

哈夫曼树相关的基本术语：

（1）路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1；

（2）结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积；

（3）树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。 哈夫曼树的构造：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

3.1.2. 哈夫曼编码

霍夫曼编码(Huffman Coding)是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of

11

数据结构课程设计报告

Minimum-Redundancy Codes）一文。

在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。

为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。

3.2. 需求分析

利用哈夫曼编码算法压缩文件是一种无损压缩算法，它适用于文本压缩或者能够统计字符的文件，因为哈夫曼算法是一种基于字符统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码,对于使用频率越高的字符,其编码也越短。但要求编码属于前缀码,即任何 2个字符的编码,不能出现向前包含的关系,也就是说字符 A的编码的前段,不能为任意一个字符B的编码。

产生哈夫曼编码压缩需要对原始数据扫描两遍：第一遍是为了建立哈弗曼码表，扫描要精确地统计出原始数据中的每个字符出现的频率,然后用频率作为权重值建立哈哈弗曼树，在根据建立好的哈夫曼树进行哈夫曼编码，生成哈弗曼码表；第二遍就利用生成的码表将文本中的字符转换成码表中对应的编码,即进行压缩操作。

压缩生成的文件主要包含 2个部分：原始文本的字符统计和原始文本压缩转换后的内容。解压缩的时候 ,先把原始文本的字符统计取出,然后根据统计值为权重建立新的哈夫曼树，生成哈弗曼码表，然后使用这一码表对压缩内容部分各个字符进行逐一解码,还原为原始文件。

12

数据结构课程设计报告

哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。该算法不对重复子串统计编码 ,而且符号的出现频率不能预知,所以效率也是不能预知的。而且需要统计和编码两次处理 ,所以速度较慢 ,但简单有效 ,因而得到广泛的应用。

3.3概要设计

思路：

3.3.1统计ASCII编码各编码出现的字数，对个编码的权重赋值。因此需要打开目标文件，对目标文件进行遍历。此功能通过以下函数实现。 void character_count();

3.3.2对每个字符的权值赋值后，接着创建哈夫曼树，哈夫曼树的创建是从底向上的， 3.3.3取出权值最小的两个节点，作为新节点的左右孩子，新节点的权值赋值为左右孩子权值之和。

3.3.4删除原来的两个节点，并把新节点放入原节点的集合。

3.3.5重复1、2步直至剩下一个节点（即哈夫曼树的根节点）此功能需要通过下面三个函数实现

//创建哈夫曼树，返回根的地址 phuff huffman_tree_creat(); //找出权值最小的两个节点 void find_min();

//进行节点的合并、删除替换 void combine_replace();

3.3.6创建了哈夫曼树，需要建立256ASCII编码的哈夫曼编码码表，方便对下一步对字符压缩进行位运算操作。编码码表的建立通过遍历哈夫曼树确定，并将每个字符的编码储存与字符串指针数组中。此功能通过以下函数实现void huffman_code_hash();建立码表之后就可以对文本进行压缩。这里有三个问题需要注意，还有一点改进建议。 每个ASCII编码对应的哈夫曼编码由0、1的有序序列组成，但使用char 类型进行存储达不到压缩的文本的目的（一个字符的编码变成了多个0、1组成的字符串）。需要以位为单位记录编码信息。但是C语言允许的最小操作对象是一个字节，故存储的时候必须对每个字节进行位运算，使用char类型比较合适。

不建议把文件的哈夫曼编码写文本文件。文本文档以-1结尾，负数在计算机内存中以补码的形式存在，即-1是存储为11111111，在实际压缩字符是我们可能会连续写入多个1，这样的话可能造成在编码的存储文件中间加入文本结束符，后面的编码无法读取，信息丢失，而这是不允许的。解决方案有两个。一可以继续选择存储为文本模式，但是每个字节必须空出最高位，即最高位置0，避免在文本的中间写入11111111，使得后面的编码序列无法读取。但是这种方式首先造成了大量的浪费，每个字节8位，空出了1位，当压缩的文本巨大时造成存储空间的大量浪费，而这一点跟哈夫曼编码的压缩功能是相违背。再者，每个字节空出一位，那么对每个字节进行位运算是需要做特殊处理，虽然不是很麻烦，但是多余的而且必须的操作造成了时间上面的浪费。第二种解决方案比较简单，将哈夫曼编码存储位二进制文件，使用函数feof()判断文件时候读取到最后。 3.3.7对存储哈夫曼编码的最后一个字节必须做特殊处理，如果还有剩余k位没有操作，则必须填充哈夫曼树中深度最的的编码的前面k位。原因有两点，一是为了保证前

13

数据结构课程设计报告

面8-k位位于字符的高位，方便解码函数的编写，第二是为了保证不输出多余信息，实现文本的无损压缩（当指针到达不了叶子，那么就没有字符输出）。 3.3.8这一点是改进建议，在编写的程序中是每操作一个字符都对文件进行一次读写，这样在哈夫曼进程与系统进程的频繁切换造成了大量的时间浪费，降低了效率，为了提高程序的效率，可以采用缓冲技术，每次从源文件读取一定长度的数据，存储在源文件缓冲区，对源文件缓冲区的字符进行操作，并将存储了哈夫曼编码的char类型的数据存储在一个缓冲区。当源文件缓冲区或哈夫曼编码缓冲区满的时候对硬盘进行一次读取写入操作，减少哈夫曼进程与系统进程的切换次数，减少不必要的时间损耗。 3.3.9记录ASCII编码的权值，以便重新打开。

详细设计

#include #include #include #include

#define LENGTH 256 #define BUFFSIZE 512 #define CODE_BUFF #define ON 1 #define OFF 0

typedef struct HUFFMAN_TREE {

unsigned char character; struct HUFFMAN_TREE *left; struct HUFFMAN_TREE *right; }huff,*phuff;

typedef struct CHARACTER_COUNT {

unsigned char character; double num; }cher;

typedef struct HUFFMAN_STACK {

phuff node_add; char left_flag; char right_flag; }huff_stack;

void main(int ac,char *av[])

14

数据结构课程设计报告

{

FILE *fp_src=NULL; phuff root=NULL;

cher character[LENGTH]; char *huff_hash[LENGTH]; phuff huffman_tree_creat();

void huffman_code_hash(),character_count();

void huffman_encode(),character_record(),decode(); char *code_name,*key_name;

while(--ac) {

fp_src=fopen(*++av,\"rb\"); if(fp_src==NULL) exit(1);

code_name=(char *)malloc(sizeof(char)*(strlen(*av)+6)); strcpy(code_name,*av); strcat(code_name,\"_code\");

key_name=(char *)malloc(sizeof(char)*(strlen(*av)+5)); strcpy(key_name,*av); strcat(key_name,\"_key\");

character_count(fp_src,character);

root=huffman_tree_creat(character,LENGTH); huffman_code_hash(root,huff_hash);

character_record(key_name,character,LENGTH); huffman_encode(fp_src,huff_hash,code_name);

decode(code_name,key_name,*av); fclose(fp_src); free(code_name); free(key_name); }

return; }

void character_count(FILE *fp,cher character[LENGTH]) {

int i,j;

unsigned char buff; for(i=0;i15

数据结构课程设计报告

character[i].character=i; character[i].num=0; }

buff=fgetc(fp); do {

++character[buff].num; if(feof(fp)) break; buff=fgetc(fp); }while(1); return; }

phuff huffman_tree_creat(cher character[],int len) {

phuff leaves[LENGTH];

double leaves_wight[LENGTH]; int i;

void find_min(),combine_replace(); for(i=0;ileaves[i]=(phuff)malloc(sizeof(huff));

leaves[i]->character=character[i].character; leaves_wight[i]=character[i].num;

leaves[i]->left = leaves[i]->right =NULL; }

for(i=LENGTH;i!=1;--i) {

int m,n;

find_min(&m,&n,leaves_wight,i);

combine_replace(leaves,leaves_wight,m,n,i); }

return *leaves; }

void find_min(int *m,int *n,double leaves_wight[],int lenth) {

double temp1=leaves_wight[0],temp2=leaves_wight[1]; int i;

*m=0,*n=1;

for(i=2;iif(temp1 >leaves_wight[i]) {

if(temp116

数据结构课程设计报告

{ temp2=temp1; *n=*m; temp1=leaves_wight[i]; *m=i; } else { temp1=leaves_wight[i]; *m=i; } }

else if(temp2 >leaves_wight[i]) {

temp2=leaves_wight[i]; *n=i; } else

continue; }

return; }

void combine_replace(phuff leaves[],double leaves_wight[],int m,int n,int len) { int i;

phuff node=(phuff)malloc(sizeof(huff)); node->character='\\0'; node->left=leaves[m]; node->right=leaves[n]; if(mphuff temp_huff=leaves[len-1];

double temp_wight=leaves_wight[len-1]; leaves[len-1]=leaves[n];

leaves_wight[len-1]=leaves_wight[n]; leaves[n]=temp_huff;

leaves_wight[n]=temp_wight; leaves[m]=node;

leaves_wight[m]+=leaves_wight[len-1]; }

else if(m>n) {

phuff temp_huff=leaves[len-1];

double temp_wight=leaves_wight[len-1];

17

数据结构课程设计报告

leaves[len-1]=leaves[m];

leaves_wight[len-1]=leaves_wight[m]; leaves[m]=temp_huff;

leaves_wight[m]=temp_wight; leaves[n]=node;

leaves_wight[n]+=leaves_wight[len-1]; }

return; }

void huffman_code_hash(phuff root,char *hash[]) {

phuff temp=root;

huff_stack stack[3*LENGTH]={NULL}; char code[512]={'\\0'}; int i,j;

for(i=j=0;j!=LENGTH;) {

if(temp->left!=NULL && temp->right!=NULL) {

stack[i].node_add=temp; stack[i].left_flag=ON;

stack[i++].right_flag=OFF; temp=temp->left; strcat(code,\"0\"); } else {

char *route_correct=code; while(*route_correct) ++route_correct;

hash[temp->character]=(char *)malloc(sizeof(char)*(strlen(code)+1)); hash[temp->character][strlen(code)]='\\0'; strcpy(hash[temp->character],code); ++j;

while(stack[--i].right_flag!=OFF && j!=LENGTH) { *(--route_correct)='\\0'; stack[i].node_add=NULL; stack[i].right_flag=OFF; stack[i].left_flag=OFF; }

*(--route_correct)='1';

18

数据结构课程设计报告

temp=stack[i].node_add->right; stack[i++].right_flag=ON; } } }

void huffman_encode(FILE *fp,char *hash[],char *code_name) {

unsigned int k=0;

unsigned char c='\\0';

unsigned char buff_code='\\0'; FILE *fp_des=NULL; char *hash_point=NULL; fp_des=fopen(code_name,\"wb\"); rewind(fp); c=fgetc(fp); for(k=8;1;) {

if(feof(fp)) break;

hash_point=hash[c]; while(*hash_point) {

if(k==0) { fwrite(&buff_code,sizeof(char),1,fp_des); buff_code='\\0'; k=8; }

if(*hash_point=='0') buff_code<<=1; else { buff_code<<=1; buff_code|=1; } --k;

++hash_point; }

c=fgetc(fp); }

if(k!=0) {

int m;

19

数据结构课程设计报告

for(m=0;m<256;++m) if(strlen(hash[m])>8) { hash_point=hash[m]; break; }

while(k>0) {

if(*hash_point=='0') buff_code<<=1; else { buff_code|=1; buff_code<<=1; } --k;

if(hash_point=='\\0') hash_point=hash['\\0']; }

fwrite(&buff_code,sizeof(char),1,fp_des); }

fclose(fp_des); }

void character_record(char *key_name,cher character[],int len) {

FILE *key=NULL;

key=fopen(key_name,\"wb\"); rewind(key);

fwrite(character,sizeof(cher),len,key); fclose(key); return; }

void decode(char *code_name,char *key_name,char *av) {

FILE *fp_code=NULL; FILE *output_file=NULL; char *output_name=NULL; unsigned char c='\\0'; phuff root=NULL; phuff temp=NULL; phuff huffman_tree_creat(); FILE *key=NULL; int k=8; int i=0,dot_flag=0;

20

数据结构课程设计报告

cher character_arry[LENGTH];

while(av[i]) {

if(av[i]=='.') dot_flag=i; ++i; }

output_name=(char *)malloc(sizeof(char)*(2*strlen(av)-dot_flag+2)); for(i=0;i<2*strlen(av)-dot_flag+2;++i) output_name[i]='\\0';

strncpy(output_name,av,dot_flag); strcat(output_name,\"2\");

strcat(output_name,av+dot_flag);

output_name[2*strlen(av)-dot_flag+1]='\\0'; output_file=fopen(output_name,\"wb\");

key=fopen(key_name,\"rb\");

fread(character_arry,sizeof(cher),LENGTH,key); root=huffman_tree_creat(character_arry,LENGTH); fclose(key);

fp_code=fopen(code_name,\"rb\"); fread(&c,sizeof(char),1,fp_code); temp=root;

while(!feof(fp_code)) { k=8; do {

if(temp->left!=NULL) { if(c>=128) temp=temp->right; else temp=temp->left; --k; c<<=1; } else { fwrite(&(temp->character),sizeof(char),1,output_file); temp=root;

21

数据结构课程设计报告

}

}while(k>0);

fread(&c,sizeof(char),1,fp_code); }

fclose(fp_code); fclose(output_file); return; }

测试分析

我们前面提到过，哈弗曼编码的效率是不可预知的，它的效率与原文本的字符频率有关，所以我们没有必要去测试过多的数据来进行分析。下面的测试我们选取多种格式文件，每种文件测试一大一小两个文件。 文件格式 原文本大小 压缩后大小 压缩比 是否解压成功 .doc 1KB 383KB 1.412 成功 .doc 22KB 13KB 1.692 成功 .txt 275KB 217KB 1.267 成功 .txt 43KB 34KB 1.2 成功 .bmp KB KB 1.000 成功 .bmp 73KB 50KB 1.460 成功 22

数据结构课程设计报告

23

数据结构课程设计报告

24

数据结构课程设计报告

同理可操作得：

小结

通过四周的课程设计使我们对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我们更加明白哈夫曼编码译码在信息技术中的重要性和地位。

在调试过程中，许多的错误让我明白了一个道理---细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。

这次课程设计不但让我学们得了一些编程知识，还学会了系统的做一份课程设计报告，学会了如何更好的画流程图，明白了做事情只有认真，才能真正做得更好！

这段时间里，可谓是酸甜苦辣都尝过。有时，为了一个错误而焦头烂额；有时，编程熬夜到凌晨；有时，连吃饭都是匆匆了事；但一旦程序运行成功，总会让我兴奋不已。

通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，在以后的编程道路上，我们任重而道远！

路漫漫其修远兮，吾将上下而求索！

25

数据结构课程设计报告

报告总结

在此次课程设计中，我们确实觉得收获匪浅。收获最大的地方在于，我们团队的每一个人，在此次课程设计报告中，分工明确，各有责任，工作得到细化，又不失整体把握。使我们都充分利用了这一次机会，锻炼了自己的能力，也培养了我们的团队合作力，协作性„„

每一次的课程设计中的任务对我们来说都是一个不小的提高，在此任务上，我们解决了很多问题，有的经验如下：

一个一个功能模块分开进行调试，主要看调试的模块能否达到预期的结果，这样可以缩小排错的范围，便以纠错和提高编程的效率，当每个功能模块都调试好后，就把各个部分组合起来，再进行调试，主要检查各函数接口是否正确，当达到预期的结果，调试结束，编程部分完成，然后按实验要求完成实验报告。

由于写代码前做了充分的准备工作，所以写起代码来比较顺利，使编程的效率有不少的提高并且最终达到实验预期的结果。

哲学上说：“实践是检验真理正确性的唯一标准”，尤其是学编程，自己不动手操作，只看书永远都编不出像Windows之类的东西，正如老师说的那样，课程设计非常锻炼人，每完成一个项目，不仅是知识体系的完善和知识的验证，更是编程技术的提升，当自己编的多了，就会开始摸索编程的捷径，想着用更高效的方法去完成一个个项目，就这样在一次次的锻炼中自己会从一个菜鸟迅速的成长，终将成为一个优秀的软件工程师。

一个成功的项目必须在写代码前，先要对课题有充分的思考和规划，否则即使完成了项目也会浪费很多的时间和精力，我们认为科学合理的编程方法是我们这次课程设计的最大收获。

26

数据结构课程设计报告

第四章 参考文献

吴跃．数据结构与算法．北京：机械工业出版社，2010.03

苏仕华，魏韦巍．数据结构课程设计．北京：机械工业出版社，2010.03 严蔚敏，吴伟民．数据结构(c语言版)．北京：清华大学出版社，1997.04 王红梅，胡明．数据结构考研辅导．北京：清华大学出版社，2009,7 郑莉，董渊，何江舟．C++语言程序设计．北京：清华大学出版社，2010.07 Kenneth A. Peek．C和指针．北京：人民邮电出版社，2008.04

27

数据结构课程设计报告

28