《哈夫曼树实验报告》由会员分享，可在线阅读，更多相关《哈夫曼树实验报告（13页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告 实验名称：实验三哈夫曼树 学生姓名： 班 级： 班内序号： 学 号： 日 期： 程序分析：2.1 存储结构：二叉树2.2 程序流程：template class BiTreepublic: BiTree();/构造函数，其前序序列由键盘输入 BiTree(void);/析构函数 BiNode* Getroot();/获得指向根结点的指针protected: BiNode *root;/指向根结点的头指针;/声明类BiTree及定义结构BiNodeData： 二叉树是由一个根结点和两棵互不相交的左右子树构成 二叉树中的结点具有相同数据类型及层次关系示意图： root lchil
2、d parent rchild 哈夫曼树类的数据域，继承节点类型为int的二叉树class HuffmanTree:public BiTreedata:HCode* HCodeTable;/编码表int tSize; /编码表中的总字符数二叉树的节点结构template struct BiNode /二叉树的结点结构T data; /记录数据T lchild; /左孩子T rchild; /右孩子T parent; /双亲;示意图：T dataT lchildT rchildT parent编码表的节点结构struct HCodechar data; /编码表中的字符char code100;
3、 /该字符对应的编码;示意图：char datachar code100待编码字符串由键盘输入，输入时用链表存储，链表节点为struct Nodechar character; /输入的字符unsigned int count;/该字符的权值bool used; /建立树的时候该字符是否使用过Node* next; /保存下一个节点的地址 ;Node* nextbool usedunsigned int countchar character示意图： 2.3 关键算法分析： 1.初始化函数（void HuffmanTree:Init(string Input)）算法伪代码：1.初始化链表的头结
4、点2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表中字符的个数)3.从字符串第2个字符开始，逐个取出字符串中的字符 3.1 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。 3.2 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到链表尾部，同时n+4.tSize=n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数)5.创建哈夫曼树6.销毁链表 源代码： void HuffmanTree:Init(string Input) Node *front=new Node; /
5、初始化链表的头结点if(!front)throw exception(堆空间用尽); front-next=NULL;front-character=NULL;front-count=0;Node *pfront=front;char ch=Input0; /获得第一个字符 Node* New1=new Node;if(!New1) throw exception(堆空间用尽);New1-character=ch; /将第一个字符插入链表New1-count=1;New1-next=pfront-next;pfront-next=New1;bool replace=0; /判断在已经写入链表的
6、字符中是否有与当前读出的字符相同的字符int n=1; /统计链表中字符个数for(int i=1;inext; if(int)pfront-character = (int)ch) /如果在链表中有与当前字符相同的字符，该字符权值加1pfront-count+;replace=1;break;while(pfront-next); if(!replace) /如果在链表中没找到与当前字符相同的字符，则将该字符作为新成 员插入链表Node* New=new Node;if(!New)throw exception(堆空间用尽);New-character=ch;New-count=1;New-
7、next=pfront-next;pfront-next=New;n+;pfront=front; /重置pfront和replace变量为默认值replace=0;tSize=n; /tSize记录的是编码表中字符个数CreateHTree(front,n); /创建哈夫曼树pfront=front;while(pfront) /销毁整个链表front=pfront;pfront=pfront-next;delete front; 时间复杂度： 若输入的字符串长度为n，则时间复杂度为O(n)2.创建哈夫曼树（void HuffmanTree:CreateCodeTable(Node *p)）
8、 算法伪代码：1. 创建一个长度为2*tSize-1的三叉链表2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点的data域，并将对应结点的孩子域和双亲域赋为空3. 从三叉链表的第tSize个结点开始，i=tSize3.1 从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。3.2 将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点3.3 将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4. 根据哈夫曼树创建编码表 源代码： void HuffmanTre
9、e:CreateHTree(Node *p,int n) root= new BiNode2*n-1; /初始化哈夫曼树Node *front=p-next;if(n=0)throw exception(没有输入字符);for(int i=0;icount;rooti.lchild=-1;rooti.rchild=-1;rooti.parent=-1;front=front-next;front=p; int New1,New2; for(i=n;i2*n-1;i+) SelectMin(New1,New2,0,i); /从0i中选出两个权值最小的结点rootNew1.parent=rootN
10、ew2.parent=i; /用两个权值最小的结点生成新结点， 新节点为其双亲 rooti.data=rootNew1.data+rootNew2.data;/新结点的权值为其孩子的权值的和 rooti.lchild=New1; rooti.rchild=New2;rooti.parent=-1;CreateCodeTable(p); /创建编码表 时间复杂度： 在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数的时间复杂度为O（n2）3创建编码表（void HuffmanTree:CreateCodeTable(Node *p)） 算法伪代码： 1.初始化编码表 2.
11、初始化一个指针，从链表的头结点开始，遍历整个链表 2.1 将链表中指针当前所指的结点包含的字符写入编码表中 2.2 得到该结点对应的哈夫曼树的叶子结点及其双亲 2.3 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0 2.4 如果不止一个叶子结点，从当前叶子结点开始判断2.4.1 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否则为12.4.2 child指针指向叶子结点的双亲，parent指针指向child指针的双亲，重复2.4.1的操作 2.5 将已完成的编码倒序 2.6 取得链表中的下一个字符 3输出编码表 源代码： void HuffmanTree:CreateCodeTable(Node *p) HCodeTable=new HCodetSize; /初始化编码表 Node *front=p-
