赫夫曼殊的自我学习与思考

// HuffmanTree.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include<stdlib.h> #include <iostream> using namespace std; #define MAXVALUE 0xFFFF #pragma region HuffmanTree的结构定义 typedef int datatype; typedef struct HuffmanTree { int weight;/*权重*/ datatype data; int parent; int leftchild; int rightchild; }HTNode; typedef HuffmanTree* HuffTree; #pragma endregion #pragma region 初始化HuffmanTree HuffTree InitHuffTree(int TreeNum) { /*初始化树：首先创建存放2*TreeNum的存储空间的树，然后0下标位置不存放数据，从1位置开始赋值权重以及数据。*/ HuffTree HT = NULL; HT = (HuffTree)malloc(sizeof(HTNode)*(2 * TreeNum));/*下标为0的HuffmanTree的结点是不用的*/ for (int i = 1; i < 2*TreeNum; i++) { HT[i].leftchild = -1; HT[i].rightchild = -1; HT[i].parent = -1;/*首先将双亲以及左右孩子置为-1*/ } cout << "请输入权重" << endl; for (int i = 1; i <= TreeNum; i++) { cin >> HT[i].weight;/*对每个结点赋值权重*/ } char c = getchar(); cout << "请输入数据" << endl; for (int i = 1; i <=TreeNum; i++) { cin >> HT[i].data; } return HT; } #pragma endregion #pragma region 创建HuffmanTree void minvalue_select(HuffTree HT, int& minloction1, int& minloction2, int loc) { int minvalue1 = MAXVALUE, minvalue2 = MAXVALUE; for (int i = 1; i < loc; i++) { if ((minvalue1 > HT[i].weight)&&(HT[i].parent == -1)) { minloction2 = minvalue1; minloction2 = minloction1; minvalue1 = HT[i].weight; minloction1 = i; } else { if ((HT[i].weight <minvalue2)&&(HT[i].parent == -1)) { minvalue2 = HT[i].weight; minloction2 = i; } } } } HuffTree CreatHuffmanTree(HuffTree HT,int TreeNum) { /*最终的parent为-1的结点代表根结点 没有双亲*/ if (HT == NULL) { cout << "HuffmanTree的数据为空 请重新输入" << endl; return NULL; } HuffTree tmpTree = NULL; tmpTree = HT; int minlocation1, minlocation2; for (int i = TreeNum+1; i <= TreeNum*2-1; i++) { minvalue_select(tmpTree, minlocation1, minlocation2, i-1);/*找出两个最小的值*/ HT[minlocation1].parent = HT[minlocation2].parent = i; HT[i].leftchild = minlocation1; HT[i].rightchild = minlocation2;/*其中location2大于location1*/ HT[i].weight = HT[minlocation1].weight + HT[minlocation2].weight; } /*此时i也就是最后一个根结点 它的左右孩子已经确定 但是它的parent为-1 表示它为根结点*/ return HT; } #pragma endregion #pragma region 从叶子结点到根结点逆向求HuffmanTree编码 typedef char** HuffmanCode; void HuffmanCoding(HuffTree HT, HuffmanCode& HC, int TreeNum) { HC = (HuffmanCode)malloc(sizeof(char*)*TreeNum);/*表明HC是一个指针类型的变量，同时每一个指针存放的位置为一个char*类型的数据，也就表示HC是一个存放指针类型数据的指针数组*/ if (HT==NULL) { return; } char* tmpcode = (char*)malloc(sizeof(char)*TreeNum); if (tmpcode == NULL) { return; } tmpcode[TreeNum -1 ] = '\0'; HuffTree tmpHTree = NULL; tmpHTree = HT; for (int i = 1; i <= TreeNum; i++) { int location = TreeNum - 1; int parentIndex = tmpHTree[i].parent; int currentIndex = i; while (parentIndex !=-1)/*未到达根结点*/ { if (tmpHTree[parentIndex].leftchild == currentIndex) { tmpcode[--location] = '0'; } else { tmpcode[--location] = '1'; } currentIndex = parentIndex; parentIndex = tmpHTree[parentIndex].parent; } /*完成编码*/ HC[i] = (char*)malloc(sizeof(char)*(TreeNum- location)); if (HC[i]!=NULL) { strcpy(HC[i], tmpcode + currentIndex); } cout << HC[i] << endl; } delete tmpcode; } #pragma endregion #pragma region 基于 根结点编码赫夫曼树 HuffmanCode EnCodeRootHuffmantree(HuffTree HT, HuffmanCode& EnCode, int capacity) { if (HT == NULL|| capacity == 0) { return NULL; } HuffTree tmptree = NULL; tmptree = HT; /*编码与权重无光 所以通过设置设置weight = 0/1/2代表未遍历左右子树/遍历左子树/遍历右子树*/ int location = 2 * capacity - 1; int current = 0; for (int i = 1; i <= location; i++) { tmptree[i].weight = 0;/*将HT所有的赫夫曼树结点都标记为未访问过*/ } EnCode = (HuffmanCode)malloc(capacity*(sizeof(char*)));/*为即将存入的编码指针向量创建可供存储的空间*/ char* tmpnode = (char*)malloc(sizeof(char)*capacity);/*用于存储临时字符串的编码信息*/ while (location!=-1)/*我要实现的目的是：如果该结点的左右子树分别遍历完成 那么我们将退回到该结点的父亲结点 但是对于根结点的叶子结点为-1 所以直到根节点的左右两边的结点分别遍历完成 我们将退出该循环*/ { if (tmptree[location].weight==0 ) { tmptree[location].weight = 1; if (tmptree[location].leftchild != -1) { tmpnode[current++] = '0'; location = tmptree[location].leftchild; } else/*到达左侧根结点*/ { tmpnode[current] = '\0'; EnCode[location] = (char*)malloc(sizeof(char)*(current+1)); if (EnCode[location] == NULL) { cout << "空间存储分配失败" << endl; return NULL; } else { strcpy(EnCode[location], tmpnode); } } } else if (tmptree[location].weight == 1)/*表明该结点已经遍历完成左子树*/ { tmptree[location].weight = 2; if (tmptree[location].rightchild != -1) { tmpnode[current++] = '1'; location = tmptree[location].rightchild; } } else/*左右两侧结点都放问过了*/ { tmptree[current].weight = 0; --current; location = tmptree[location].parent; } } } #pragma endregion int main() { std::cout << "Hello World!\n"; } // 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单 // 调试程序: F5 或调试 >“开始调试”菜单 // 入门使用技巧: // 1. 使用解决方案资源管理器窗口添加/管理文件 // 2. 使用团队资源管理器窗口连接到源代码管理 // 3. 使用输出窗口查看生成输出和其他消息 // 4. 使用错误列表窗口查看错误 // 5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目 // 6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件