哈弗曼树课程设计.doc.doc

1 09 计算机课程设计哈夫曼编码/ 译码器(树的应用) 2094021444 09 计算机科学与技术刘小青 2 一. 题目哈弗曼树编码/ 译码(树的应用) 二. 目的 1. 巩固数据结构基础知识, 了解并初步掌握设计、实现较大系统的完整过程,包括系统分析、编码设计、系统集成、以及调试分析,从而提高分析问题、解决问题的能力,提高编程技能,培养理论结合实践的能力。 2. 熟练掌握数据结构的线性表、树、图等结构的应用的设计实现以及操作方法, 为进一步的应用开发打好基础。 3. 培养查阅文献和撰写文档的能力。三. 要求 1. 课程设计题目可从指导老师提供的题目列表中选择或自行提出。从实际情况出发选择工作量适当、难度适中的题目。自选题目必须要得到指导老师的同意才能开题,否则不予承认,要求课题能够体现学生综合运用所学知识的能力。 2. 课程设计可参考已有的成果,但必须在功能、数据结构及算法上体现自己的独到之处。 3. 程序源代码和课程设计说明书必须按照相关要求和格式完成。:简述算法实现的过程。 1. 定义哈弗曼树。 2. 设计算法 CrtHuffmanTree 存放哈弗曼树的各个权值,建立哈弗曼树。 3. 设计算法 CrtHuffmanCode 从叶子结点到根, 逆向求每个叶子结点对应的哈夫曼编码,即“密文”。 4. 设计算法 TrsHuffmanTree 求哈弗曼编码对应的“明文”。 5 .设计 main 函数,利用以上函数实现建立哈弗曼函数、求编码和译文的目的。#include <> #include <> #include <> typedef char* HuffmanCode;/* 动态分配数组,存储哈夫曼编码*/ typedef struct { unsigned int weight ; /* 用来存放各个结点的权值*/ unsigned int parent, LChild,RChild ; /* 指向双亲、孩子结点的指针*/ }HTNode, * HuffmanTree; /* 动态分配数组,存储哈夫曼树*/ 3 void select(HuffmanTree *ht,int n, int *s1, int *s2) { int i; int min; for(i=1; i<=n; i++) { if((*ht)[i].parent == 0) { min = i; i= n+1; }} 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++) { if((*ht)[i].parent ==0 && i!=(*s1)) { min = i; i= n+1; }} for(i=1; i<=n; i++) { if((*ht)[i].parent ==0 && i!=(*s1)) { if((*ht)[i].weight < (*ht)[min].weight) min = i; }} *s2 = min; } void CrtHuffmanTree(HuffmanTr