|
- // /Users/zhangzhiqi/Library/Mobile Documents/M6HJR9W95L~com~textasticapp~textastic/Documents/CLionProjects/TouGe-Huffman-Tree/SY1.cpp
- // Copyright (c) 2022.
- // @Time : 2022/4/30 16:27:25
- // @Author : 张稚琦
- // @Address: 湖北理工学院腾龙公寓 5620
- // @Email : zhang@zhang.mba / zhangzhiqi828@gmail.com / zhangzhiqi@lh83.onmicrosoft.com / 2272358828@qq.com
- // @File : SY1.cpp
- // @LastModified: 2022/4/30 下午4:25
- // @ProjectName : TouGe_Huffman_Tree
-
- # include <stdio.h>
- # include <iostream>
- # include <string.h>
- using namespace std;
-
-
- typedef struct //define structure HuffmanTree
- { int weight;
- int parent,lchild,rchild;
- }HTNode,*HuffmanTree;
-
- typedef char ** HuffmanCode;
-
- void Select(HuffmanTree HT,int end,int &s1,int &s2) ;//选出HT树到i为止,权值最小且parent为0的2个节点
- void HuffmanTreeing(HuffmanTree &HT,int *w,int n);//构建哈夫曼树函数
-
- void output(HuffmanTree HT,int m);//输出哈夫曼树
-
- int main()
- {
- HuffmanTree HT;
- HuffmanCode HC;
- int n,i;
- int *w;
- scanf("%d",&n);
- w=(int *)malloc(n*sizeof(int));
- for(i=0;i<n;i++)
- {
- scanf("%d",&w[i]);
- }
- HuffmanTreeing( HT , w ,n );
- cout<<"哈夫曼树:"<<endl;
- output(HT,2*n-1);
- return 0;
- }
-
- void Select(HuffmanTree HT,int end,int &s1,int &s2)
- { //选出HT树到i为止,权值最小且parent为0的2个节点
- //s1 is the least of HT[].weight
- //s2 is the second least of HT[].weight
- /********** Begin **********/
- int min1, min2;
- //遍历数组初始下标为 1
- int i = 1;
- //找到还没构建树的结点
- while(HT[i].parent != 0 && i <= end){
- i++;
- }
- min1 = HT[i].weight;
- s1 = i;
-
- i++;
- while(HT[i].parent != 0 && i <= end){
- i++;
- }
- //对找到的两个结点比较大小,min2为大的,min1为小的
- if(HT[i].weight < min1){
- min2 = min1;
- s2 = s1;
- min1 = HT[i].weight;
- s1 = i;
- }else{
- min2 = HT[i].weight;
- s2 = i;
- }
- //两个结点和后续的所有未构建成树的结点做比较
- for(int j=i+1; j <= end; j++)
- {
- //如果有父结点,直接跳过,进行下一个
- if(HT[j].parent != 0){
- continue;
- }
- //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
- if(HT[j].weight < min1){
- min2 = min1;
- min1 = HT[j].weight;
- s2 = s1;
- s1 = j;
- }
- //如果介于两者之间,min2赋值为新的结点的位置下标
- else if(HT[j].weight >= min1 && HT[j].weight < min2){
- min2 = HT[j].weight;
- s2 = j;
- }
- }
- /********** End **********/
- }
-
-
- void HuffmanTreeing(HuffmanTree &HT,int *w,int n) //构建哈夫曼树函数
- { // w存放n个字符的权值(均>0),构造赫夫曼树HT
- /********** Begin **********/
- if(n<=1) return; // 如果只有一个编码就相当于0
- int m = 2*n-1; // 哈夫曼树总节点数,n就是叶子结点
- HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode)); // 0号位置不用
- HuffmanTree p = HT;
- // 初始化哈夫曼树中的所有结点
- for(int i = 1; i <= n; i++)
- {
- (p+i)->weight = *(w+i-1);
- (p+i)->parent = 0;
- (p+i)->lchild = 0;
- (p+i)->rchild = 0;
- }
- //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
- for(int i = n+1; i <= m; i++)
- {
- (p+i)->weight = 0;
- (p+i)->parent = 0;
- (p+i)->lchild = 0;
- (p+i)->rchild = 0;
- }
- //构建哈夫曼树
- for(int i = n+1; i <= m; i++)
- {
- int s1, s2;
- Select(HT, i-1, s1, s2);
- (HT)[s1].parent = (HT)[s2].parent = i;
- (HT)[i].lchild = s1;
- (HT)[i].rchild = s2;
- (HT)[i].weight = (HT)[s1].weight + (HT)[s2].weight;
- }
-
- /********** End **********/
- }
-
-
- void output(HuffmanTree HT,int m)
- { //输出哈夫曼树
- for(int i=1;i<=m;++i)
- {
- cout<<"HT["<<i<<"] ="<<HT[i].weight<<"\t"<<HT[i]. parent<<"\t";
- cout<<"\t" <<HT[i]. lchild <<"\t" <<HT[i]. rchild<<endl;
- }
- }
|