西安工业大学数据结构课程设计实验报告(赫夫曼编码)

《西安工业大学数据结构课程设计实验报告(赫夫曼编码)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计赫夫曼编码院系：计算机科学与工程学院专业：计算机科学与技术姓名：林煌东学号：110601111指导教师：潘煜112013年01月03日11目录一、实验目的3二、题目——赫夫曼编码31.问题描述42.基本要求43.测试要求4三、概要设计41.分析赫夫曼树的定义42.所实现的功能函数43.系统结构图（功能模块图）5四、赫夫曼编码源代码5五、调试分析101.输入102.建立赫夫曼树103.编码10六、实验心得与体会1111一、实验目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主

2、要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为

3、计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：1.了解并掌握数据结构与算法的设计方法，

4、具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。11二、题目——赫夫曼编码1.问题描述利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，因此需要一个完整的赫夫曼编码系统。试为发送端编写一个赫夫曼码的编码系统。2.基本要求一个完整的系统应

5、具有以下功能：（1）初始化（Initialization）：从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，输出结果。（2）编码（Encoding）：利用已建好的赫夫曼树，对赫夫曼树进行编码，输出结果。3.测试要求已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。三、概要设计1.分析赫夫曼树的定义（1）赫夫曼树节点的数据类型定义为：typedefstruct{intweight;//节点权值intparent,lch

6、ild,rchild;//左右孩子的节点}htnode,*huffmantree;typedefchar**huffmancode;112.所实现的功能函数（1）voidhuffmancoding(huffmantreeht,huffmancodehc,int*w,intn)//初始化赫夫曼树，处理函数得到的数据按照赫夫曼规则建立2叉树。此函数块调用了Select()函数。（2）voidselect(huffmantreeht,intn,int*s1,int*s2)//Select()函数，选出赫夫曼树到n为止，权值最小且pare

7、nt为0的2个节点。（3）intmain()主函数//让用户利用已建好的赫夫曼树对输入的数据进行编码，输出结果。使用数组存储，然后分别调用排序函数，建立赫夫曼函数，编码函数等来实现功能。3.系统结构图（功能模块图）赫夫曼编码初始化赫夫曼树打印编码编码打印赫夫曼树四、赫夫曼编码源代码#include#include#includetypedefstruct{intweight;//节点权值intparent,lchild,rchild;//双亲、左右孩子的节点}htnode,

8、*huffmantree;typedefchar**huffmancode;voidselect(huffmantreeht,intn,int*s1,int*s2)//挑选权值较小的两个节点{11inti,j,temp;for(i=1;i<=n;i