1、 + + 数据结构数据结构课程设计课程设计 题目：题目：赫夫曼编码赫夫曼编码 院、院、 系：系：滨江滨江学院学院 学科专业：学科专业：计算机科学与技术计算机科学与技术 学学 生：生： 学学 号：号： 指导教师：指导教师： 2010 年 12 月 22 日 目目 录录 1 1 课程设计的题目课程设计的题目-0 0 2 2 课程设计的目的（设计要解决的问题）课程设计的目的（设计要解决的问题）-1 1 3 3 概要设计 （函数划分、 总体设计）概要设计 （函数划分、 总体设计） -1 1 4 4 详细设计 （详细设计 （算法、算法、 流程图、 程序）流程图、 程序） -2 2 5 5 调试结果调试结
2、果- -3232 6 6 课程设计总结课程设计总结- -3333 7 7 心得体会心得体会-3434 二二课程设计的目的课程设计的目的 巩固构造赫夫曼树的算法巩固构造赫夫曼树的算法。 设计实验用程序实现赫夫曼树的构造设计实验用程序实现赫夫曼树的构造。 熟悉用先序、中序或后序的访问方法得到个叶子结点的赫夫曼编熟悉用先序、中序或后序的访问方法得到个叶子结点的赫夫曼编 码。码。 三三概要设计（函概要设计（函数划分、总体设计）数划分、总体设计） 总体设计总体设计 （1 1） 输入一个字符串用结构体链表存储字符串中出现的不同字符输入一个字符串用结构体链表存储字符串中出现的不同字符 及其出现的次数。及其出
3、现的次数。 （2 2） 定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出 现的次数作为叶子结点的元素及其权值，统计叶子结点的个数现的次数作为叶子结点的元素及其权值，统计叶子结点的个数 n n，开辟可以存储，开辟可以存储 2*n2*n 个结点的顺序表，来赫夫曼树的各个结个结点的顺序表，来赫夫曼树的各个结 点，然后按照一定的规则构造赫夫曼树。点，然后按照一定的规则构造赫夫曼树。 （3 3） 开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链 表的指针的顺序表，然后从叶子结点开始向上访问
4、，是左孩子表的指针的顺序表，然后从叶子结点开始向上访问，是左孩子 的把的把0 0接进链表是右孩子的把接进链表是右孩子的把1 1接进链表，直到根结点，接进链表，直到根结点， 然后把叶子结点的元素及存储其赫夫曼链表的然后把叶子结点的元素及存储其赫夫曼链表的头指针读入顺头指针读入顺 序表，直到把所有的叶子结点的元素及指向存储其赫夫曼编码序表，直到把所有的叶子结点的元素及指向存储其赫夫曼编码 链表的头指针读入顺序表，这样得到的赫夫曼编码是倒序的。链表的头指针读入顺序表，这样得到的赫夫曼编码是倒序的。 （4 4） 从存储其叶子结点及指向存储其赫夫曼编码链表头指针的顺从存储其叶子结点及指向存储其赫夫曼编码
5、链表头指针的顺 序表表头开始顺序访问各元素，在输出其赫夫曼编码之前，把序表表头开始顺序访问各元素，在输出其赫夫曼编码之前，把 链表中的编码顺序读入到等长的栈中，然后编码出栈就会得到链表中的编码顺序读入到等长的栈中，然后编码出栈就会得到 顺序的赫夫曼编码，直到把所有的叶子结点都访问到。顺序的赫夫曼编码，直到把所有的叶子结点都访问到。 （5 5） 用一个字符型的指针指向字符串的第一个字符，从存储叶子结用一个字符型的指针指向字符串的第一个字符，从存储叶子结 点元素及指向存储其赫夫曼编码链表的头指针的顺序表表头点元素及指向存储其赫夫曼编码链表的头指针的顺序表表头 开始访问顺序表中的各元素，直到找到叶子结点的元素和当前开始访问顺序表中的各元素，直到找到叶子结点的元素和当前 字符相等就结束访输出字符相等就结束访输出赫夫曼编码，回到表头
