一、实验目的
1. 掌握哈夫曼树的构造算法，理解二叉树的应用；
2. 掌握哈夫曼编码的构造算法。
二、实验内容
输入一串字符串，根据给定的字符串中字符出现的频率建立相应的哈夫曼树，构造哈夫曼编码表，在此基础上可以对压缩文件进行压缩（即编码）。
已知字符串中出现的字符为A、B、C、D、E、F、G、H，其相应的权值为
7、19、2、6、32、3、21、10。
头文件及宏定义：
/*CaptainUniverse_ 2022.4.25*/
#include
#include
#include
#define MAX_SZ 256
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;
typedef struct _pQueueNode
{
htNode *val;
unsigned int priority;
struct _pQueueNode *next;
}pQueueNode;
typedef struct _pQueue
{
unsigned int size;
pQueueNode *first;
}pQueue;
/*CaptainUniverse_ 2022.4.25*/ 子函数声明：
/*CaptainUniverse_ 2022.4.25*/
htTree * buildTree(char *);
hlTable * buildTable(htTree *);
void encode(hlTable *, char *);
void decode(htTree *, char *);
void initPQueue(pQueue **);
void addPQueue(pQueue **, htNode *, unsigned int);
htNode *getPQueue(pQueue **);
/*CaptainUniverse_ 2022.4.25*/子函数主体：
/*CaptainUniverse_ 2022.4.25*/
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));
aux->code = (char *)malloc(sizeof(char)*(strlen(code)+1));
strcpy(aux->code,code);
aux->symbol = treeNode->symbol;
aux->next = NULL;
if((*table)->first == NULL)
{
(*table)->first = aux;
(*table)->last = aux;
}
else
{
(*table)->last->next = aux;
(*table)->last = aux;
}
}
if(treeNode->left!=NULL)
{
code[k]='0';
traverseTree(treeNode->left,table,k+1,code);
}
if(treeNode->right!=NULL)
{
code[k]='1';
traverseTree(treeNode->right,table,k+1,code);
}
}
hlTable * buildTable(htTree * huffmanTree)
{
hlTable *table = (hlTable *)malloc(sizeof(hlTable));
table->first = NULL;
table->last = NULL;
char code[256];
int k=0;
traverseTree(huffmanTree->root,&table,k,code);
return table;
}
htTree * buildTree(char *inputString)
{
int i;
int * probability = (int *)malloc(sizeof(int)*256);
for(i=0; i<256; i++)
{
probability[i]=0;
}
for(i=0; inputString[i]!='<=(*queue)->'; i++)
{
probability[(unsigned char) inputString[i]]++;
}
pQueue * huffmanQueue;
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]);
}
}
free(probability);
while(huffmanQueue->size!=1)
{
int priority = huffmanQueue->first->priority;
priority+=huffmanQueue->first->next->priority;
htNode *left = getPQueue(&huffmanQueue);
htNode *right = getPQueue(&huffmanQueue);
htNode *newNode = (htNode *)malloc(sizeof(htNode));
newNode->left = left;
newNode->right = right;
addPQueue(&huffmanQueue,newNode,priority);
}
htTree *tree = (htTree *) malloc(sizeof(htTree));
tree->root = getPQueue(&huffmanQueue);
return tree;
}
void encode(hlTable *table, char *stringToEncode)
{
int i;
hlNode *traversal;
printf("输入的字符串为:\n");
printf("%s\n",stringToEncode);
printf("转换为哈夫曼编码为:\n");
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=0;
htNode *traversal = tree->root;
printf("要转化的哈夫曼编码为：\n");
printf("%s\n",stringToDecode);
printf("哈夫曼编码转化为字符串为：\n") ;
while(stringToDecode[i]!='\0')
{
if(stringToDecode[i]!='1'&&stringToDecode[i]!='0')
{
printf("你输入的哈夫曼编码有误！\n");
return;
}
i++;
}
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(traversal->left == NULL && traversal->right == NULL)
{
printf("%c",traversal->symbol);
traversal = tree->root;
}
printf("\n");
}
void initPQueue(pQueue **queue)
{
(*queue) = (pQueue *) malloc(sizeof(pQueue));
(*queue)->first = NULL;
(*queue)->size = 0;
return;
}
void addPQueue(pQueue **queue, htNode *val, unsigned int priority)
{
if((*queue)->size == MAX_SZ)
{
printf("队列已满！\n");
return;
}
pQueueNode *aux = (pQueueNode *)malloc(sizeof(pQueueNode));
aux->priority = priority;
aux->val = val;
if((*queue)->size == 0 || (*queue)->first == NULL)
{
aux->next = NULL;
(*queue)->first = aux;
(*queue)->size = 1;
return;
}
else
{
if(priority<=iterator->first->priority)
{
aux->next = (*queue)->first;
(*queue)->first = aux;
(*queue)->size++;
return;
}
else
{
pQueueNode * iterator = (*queue)->first;
while(iterator->next!=NULL)
{
if(prioritynext->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;
}
}
}
}
htNode *getPQueue(pQueue **queue)
{
htNode *returnValue;
if((*queue)->size>0)
{
returnValue = (*queue)->first->val;
(*queue)->first = (*queue)->first->next;
(*queue)->size--;
}
else
{
printf("队列已空！\n");
}
return returnValue;
}
/*CaptainUniverse_ 2022.4.25*/主函数：
/*CaptainUniverse_ 2022.4.25*/
int main(void)
{
printf(" ☆☆☆☆欢迎使用☆☆☆☆\n\n");
printf("请选择哈夫曼树：\n");
printf("1.预设“实验五”哈夫曼树\n");
printf("2.自行输入一串字符建立一棵哈夫曼树\n");
htTree *codeTree;
hlTable *codeTable;
int choice1;
char data[256]="AAAAAAABBBBBBBBBBBBBBBBBBBCCDDDDDDEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEFFGGGGGGGGGGGGGGGGGGGGGHHHHHHHHHH";
while(1)
{
fflush(stdin);
scanf("%d",&choice1);
if(choice1==1)
{
codeTree = buildTree(data);
codeTable = buildTable(codeTree);
printf("成功建立！\n");
break;
}
else if(choice1==2)
{
char *HuffmanTree=(char *)malloc(MAX_SZ*sizeof(char));
printf("请输入字符串：（上限256字符）\n");
fflush(stdin);
gets(HuffmanTree);
codeTree = buildTree(HuffmanTree);
codeTable = buildTable(codeTree);
printf("成功建立！\n");
break;
}
else
{
printf("输入有误！请重新输入！\n");
}
}
while(1)
{
printf("\n\n ☆☆☆☆继续 *** 作☆☆☆☆\n\n");
printf("请选择：\n");
printf("1.输入字符串转为哈夫曼编码\n");
printf("2.输入哈夫曼编码转为对应字符串\n");
printf("0.退出\n");
int choice2;
char *StoH=(char *)malloc(MAX_SZ*sizeof(char));
char *HtoS=(char *)malloc(MAX_SZ*sizeof(char));
fflush(stdin);
scanf("%d",&choice2);
switch(choice2)
{
case 1:
printf("请输入要转换的字符串:（上限256字符）\n");
printf("注意：字符要在哈夫曼树中已有！否则退出程序！\n");
fflush(stdin);
gets(StoH);
encode(codeTable,StoH);
break;
case 2:
printf("请输入要转换的哈夫曼编码:（上限256字符）\n");
fflush(stdin);
gets(HtoS);
decode(codeTree,HtoS);
break;
case 0:
goto END;
default:
printf("输入有误！请重新输入！\n");
break;
}
}
END: printf("感谢您的使用，再见！\n");
system("pause");
return 0;
}
/*CaptainUniverse_ 2022.4.25*/写在最后：
2022.4.27 1：58
data字符数组属实有点抽象
等我有空再回来写注释
就这样
2022.4.27 17：08
代码优化：
修改主函数 起初误解了题意 稍稍修改了一下 另外字符数组改为字符指针 *** 作更灵活
添加fflush(stdin)清空输入缓冲区 防止输入非数字造成无限循环 （实验二中也出现了）
修改decode函数 先判断输入是否合法（‘0’左 ‘1’右 其他皆为非法字符）再输出Huffman编码对应字符
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）