|
60鱼币
huffman.c
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
- #include "huffman.h"
- #include "pQueue.h"
- void traverseTree(htNode *treeNode, hlTable **table, int k, char code[256]){
- if(treeNode->left == NULL && treeNode->right == NULL){//目前位于叶结点
- code[k] = '\0';//结束字符串
- hlNode *aux = (hlNode *)malloc(sizeof(hlNode));//hlNode存放字符和对应的编码值;code存放编码值;symbol存放字符
- aux->code = (char *)malloc(sizeof(char)*(strlen(code)+1));
- strcpy(aux->code,code);//将编码拷贝到结点里
- aux->symbol = treeNode->symbol;
- aux->next = NULL;
- if((*table)->first == NULL){//aux是table的第一个结点
- (*table)->first = aux;//first指向第一个结点
- (*table)->last = aux;//last指向最后一个
- }
- else{
- (*table)->last->next = aux;
- (*table)->last = aux;
- }
- }
-
- if(treeNode->left != NULL){//左指针不为空,向左编码为0
- code[k]='0';//确定当前层数的编码值
- traverseTree(treeNode->left,table,k+1,code);//递归到最底层
-
- }
- if(treeNode->right != NULL){//向右编码为1
- code[k]='1';
- traverseTree(treeNode->right,table,k+1,code);
-
- }
- }
- hlTable * buildTable(htTree * huffmanTree){
- hlTable *table = (hlTable *)malloc(sizeof(hlTable));
- table->first = NULL;//malloc获取hlTable大小的空间,存放字符对应的编码
- table->last = NULL;
-
- char code[256];
- int i, k = 0;
- traverseTree(huffmanTree->root, &table, k, code);//huffmanTree->root:霍夫曼树的根结点;table:存放编码的指针;k:目前位于第几层;code:存放每一层得到的0和1
- return table;
- }
- htTree * buildTree(char *inputStr){//生成霍夫曼树,返回htree结点,指向根结点
- int i;
- int * probability = (int *)malloc(sizeof(int)*256);//Ascll码一共有八位;存放256个Ascll码,记录每一个字符出现的次数
-
- for(i = 0; i < 256; i++)//初始化每一项为0
- probability[i]=0;
- for(i = 0; inputStr[i] != '\0'; i++)//统计带编码的字符串中各个字符出现的次数
- probability[(unsigned char) inputStr[i]]++;//(unsigned char)进行强调,没有也可以
- pQueue * huffmanQueue;//huffmanQueue是pQueue类型的变量,队列的头指针
- initPQueue(&huffmanQueue);//给头指针分配了空间
- for(i = 0; i < 256; i++){//按优先级,出现次数,进行插入
- if(probability[i] != 0){//有出现过
- htNode *aux = (htNode *)malloc(sizeof(htNode));///分配一个树的结点
- aux->left = NULL;
- aux->right = NULL;
- aux->symbol = (char) i;
-
- addPQueue(&huffmanQueue, aux, probability[i]);//插入队列;huffmanQueue:头指针;aux:代插入的结点;probability[i]:(char)i出现的次数
- }
- }
- free(probability);//出现次数,使用完,没有了,释放掉
- while(huffmanQueue->size!=1){//真正的生成一个霍夫曼树
- int priority = huffmanQueue->first->priority;//出现次数;权值
- priority += huffmanQueue->first->next->priority;//priority:前2个结点,权值相加
- htNode *left = getPQueue(&huffmanQueue);//声明一个left树结点
- htNode *right = getPQueue(&huffmanQueue);//getPQueue:从列表中获取
- htNode *newNode = (htNode *)malloc(sizeof(htNode));//前面2个结点
- newNode->left = left;//成为newNode的左右孩子结点
- newNode->right = right;//权值小的放左边
- addPQueue(&huffmanQueue, newNode, priority);//插入列表
- }
- htTree *tree = (htTree *) malloc(sizeof(htTree));//htTree:指向根结点
- tree->root = getPQueue(&huffmanQueue);//huffmanQueue:根结点
-
- return tree;
- }
- void encode(hlTable *table, char *stringToEncode){//把字符串变为对应的编码,打印
- int i;
- hlNode *traversal;
-
- printf("\n输入的字符串 : \n%s\n编码后 : \n", stringToEncode);
- for (i = 0; stringToEncode[i] != '\0'; i++){//对于字符串的每个元素遍历列表
- traversal = table->first;//一旦找到符号,我们就输出它的代码
- while (traversal->symbol != stringToEncode[i])
- traversal = traversal->next;
- printf("%s", traversal->code);
- }
- printf("\n");
- }
- void decode(htTree *tree, char *stringToDecode){
- int i;
- htNode *traversal = tree->root;
- printf("\n输入字符串 : \n%s\n解码后 : \n",stringToDecode);
- for(i = 0; stringToDecode[i] != '\0'; i++){
- if(traversal->left == NULL && traversal->right == NULL){
- printf("%c",traversal->symbol);
- traversal = tree->root;
- }
-
- if(stringToDecode[i] == '0')
- traversal = traversal->left;
- if(stringToDecode[i] == '1')
- traversal = traversal->right;
- if(stringToDecode[i]!='0'&&stringToDecode[i]!='1'){
- printf("The input string is not coded correctly!\n");
- return;
- }
- }
- if(traversal->left == NULL && traversal->right == NULL)
- {
- printf("%c",traversal->symbol);
- traversal = tree->root;
- }
- printf("\n");
- }
复制代码
pQueue.c
main.c
- #include <stdio.h>
- #include <stdlib.h>
- #include "huffman.c"
- #include "pQueue.c"
- typedef char ElemType;
- typedef struct BiTNode{
- ElemType data;
- int code;//权值
- struct BiTNode *lchild, *rchild;
- } BiTNode, *BiTree;
- int main(void){
- htTree *codeTree = buildTree("I 1ove FishC.com");//返回htree结点,指向霍夫曼树的根结点
- hlTable *codeTable = buildTable(codeTree);//根据树生成各个字符的编码,存放在codeTable里面
- encode(codeTable, "I love FishC.com!");//把字符变为codeTable中对应的编码,打印出来
- decode(codeTree, "0011111000111");//解码;把编码变为codeTable中对应的字符
- return 0;
- }
复制代码
huffman.h
- #pragma once
- #ifndef _HUFFMAN_H
- #define _HUFFMAN_H
- typedef struct _htNode {//树的结点
- char symbol;
- struct _htNode *left, *right;
- }htNode;
- typedef struct _htTree {//指向根结点
- htNode *root;
- }htTree;
- typedef struct _hlNode {//编码
- char symbol;//字符
- char *code;//编码
- struct _hlNode *next;
- }hlNode;
- typedef struct _hlTable {
- hlNode *first;//指向第一个
- hlNode *last;//指向最后一个
- }hlTable;
- htTree * buildTree(char *inputString);
- hlTable * buildTable(htTree *huffmanTree);
- void encode(hlTable *table, char *stringToEncode);
- void decode(htTree *tree, char *stringToDecode);
- #endif
复制代码
pQueue.h
- #pragma once//pragma once或者ifdef防止重定义冲突
- #ifndef _PQUEUE_H
- #define _PQUEUE_H
- #include "huffman.h"
- #define TYPE htNode *//htNode:树的结点
- #define MAX_SZ 256
- typedef struct _pQueueNode{
- TYPE val;
- unsigned int priority;//优先级;大于0
- struct _pQueueNode *next;//指向下一个结点
- }pQueueNode;
- typedef struct _pQueue{
- unsigned int size;
- pQueueNode *first;
- }pQueue;
- void initPQueue(pQueue **queue);
- void addPQueue(pQueue **queue, TYPE val, unsigned int priority);
- TYPE getPQueue(pQueue **queue);
- #endif
复制代码
|
|