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#include "pQueue.h"
#include <stdlib.h>
#include <stdio.h>
void initPQueue(pQueue **queue){
(*queue) = (pQueue *) malloc(sizeof(pQueue));//(*queue):队列头指针的地址
(*queue)->first = NULL;
(*queue)->size = 0;
return;
}
void addPQueue(pQueue **queue, TYPE val, unsigned int priority){
if((*queue)->size == MAX_SZ){
printf("\n队列已经满了.\n");
return;
}
pQueueNode *aux = (pQueueNode *)malloc(sizeof(pQueueNode));//申请空间
aux->priority = priority;//赋值，出现次数
aux->val = val;//val：树结点
if((*queue)->size == 0 || (*queue)->first == NULL){//如果是空队列
aux->next = NULL;
(*queue)->first = aux;
(*queue)->size = 1;
return;
}
else{
if(priority <= (*queue)->first->priority){//优先级小于第一个结点,
aux->next = (*queue)->first;
(*queue)->first = aux;
(*queue)->size++;
return;
}
else{
pQueueNode * iterator = (*queue)->first;//iterator:迭代器
while(iterator->next!=NULL){
if(priority <= iterator->next->priority){
aux->next = iterator->next;
iterator->next = aux;
(*queue)->size++;
return;
}
iterator = iterator->next;
}
if(iterator->next == NULL){//是最大的。放在最后
aux->next = NULL;
iterator->next = aux;
(*queue)->size++;
return;
}
}
}
}
TYPE getPQueue(pQueue **queue){//从队列里面获取数据
TYPE returnValue;
if((*queue)->size > 0){//可以获取一个树结点
returnValue = (*queue)->first->val;
(*queue)->first = (*queue)->first->next;
(*queue)->size--;
}
else{
printf("\n已经空了.\n");
}
return returnValue;
}
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
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-12-25 21:39:46
置顶卡
千斤顶
显身卡
楼主![SZMOD@8XJI[3]LI9GQXDJK4.png](https://xxx.ilovefishc.com/forum/202212/27/112351dngwn5bbtdgcc11d.png "SZMOD@8XJI[3]LI9GQXDJK4.png")