当前位置： 代码迷 >> 综合 >> (c语言)Huffman Codes (30分)
  详细解决方案

(c语言)Huffman Codes (30分)

热度：96   发布时间：2023-11-17 20:57:56.0

文章目录

    • 题目大意
    • 大致思路
    • 哈曼树的建立
    • 鉴定是否是最优代码
    • 心路历程
    • 噜~（逃）

关于数据结构Mooc后的每一道答案
基本我都已经给出了详解
希望能对大家有所帮助
收藏一下也是方便大家查找吧
希望大家一起进步！

浙大Mooc数据结构的解题集

这道题成功提交截图
(博客的最后有我做这个题的心路历程)
在这里插入图片描述

下面是关于这道题的谷歌翻译

在这里插入图片描述

题目大意

–
首先这道题 题目我们就能看出来是要用 哈夫曼树的
我们先来看一下 中文的题目
题目的大意就是
第一行给出我们有几个字符
第二行我们先给出 我们的标准用来对比的字符和频率
然后第三行给出我们需要测试几个同学的代码
是满足最优代码
之后就是机器给出的代码了

大致思路

先一部分一部分分析吧

哈曼树的建立

一看到这道题 我就知道肯定需要建立哈曼树
也许有其他的算法可以不建树
但是我估计正常思路也是需要建立的
首先哈曼树的建立是需要 一个最小堆 每个新建立的
哈曼树节点都是由最小堆提出来两个结点
然后再把新节点插入最小堆
然后又从最小堆提出来 如果最小堆有N个元素
那么提取操作就需要N-1次（不包括最后一次提取）

哈曼树的基本结构是包括了 当前权值和左右两节点
我们的字符需要单独存储 哈曼树里面只存储我们的权值

鉴定是否是最优代码

1、WPL 就是根节点到有权值结点的总路程值相等 最短编码长度
2、不允许其中有结点是其他结点的前缀，就是判断前缀是否重复

1、WPL的计算

（细节） WPL总值等于 所有度为2的结点上面的值之和
也是等于除了叶节点外的所有结点值之和
证明过程略了 大家可以自己手画一个哈曼树
来看一下是不是这样的
然后通过上面的思路就不难想出下面的函数

void CalculateWPL(HuffmanTree T)
{
    if(T){
    HuffmanTree Temp = T;//这里就是筛选节点 度为2的结点//realWPL是我设置的全局变量 就是用来记录WPL的if(Temp->Left != NULL && Temp->Right != NULL)realWPL += T->weight;//这里使用了很简单的递归CalculateWPL(T->Left);CalculateWPL(T->Right);}return;
}

2、前缀重复

这里我是这样理解的
我们来通过重新建立一个树来判断是否前缀重复

当出现一个字符的落点位不为空结点的时候
说明前缀重复
落点位就是最后一位数决定他是向左结点还是右节点的位置

思路就是上面的思路 可以结合一下代码和注释来理解一下

	//转为了Judge创立的节点typedef struct JudgeNode{
    struct JudgeNode *Left,*Right;} *JNode;//新建立结点函数JNode NewNode(){
    JNode T;T = (JNode)malloc(sizeof(struct JudgeNode));T->Left = NULL;T->Right = NULL;return T;}int Judge(int numbers)
{
    JNode T,Position;//新建立一个头结点T = NewNode();for(i=0;i<numbers;i++){
    //Position负责确认当前结点位置Position = T;for(j=0;j<strlen(tempstring[i]);j++){
    //当字符为0 时if(tempstring[i][j] == '0'){
    //我们只需要确认最后的一位落点位是否是空结点//不是空结点就说明 要不是重复的 要不是前缀的if(j == strlen(tempstring[i]) -1 && Position->Left != NULL)return 0;//这里就是基本情况 把每一位数走一遍else{
    //这里有两层意思 当是空结点就新创立一个//不是的话 就不管 直接跳到那个节点去if(Position->Left == NULL)Position->Left =NewNode();Position = Position->Left;}}//下面同理else{
    if(j == strlen(tempstring[i]) -1 && Position->Right != NULL)return 0;else{
    if(Position->Right == NULL)Position->Right =NewNode();Position = Position->Right;}}}//当上面的循坏都执行完了 都没有跳出 说明没有前缀重叠//就可以return 1了return 1;
}

下面就是全代码实现了

#include <stdio.h>
#include <stdlib.h>//malloc需要
#include <string.h>//strlen需要
#define MAX 63//哨兵哈
#define MIN -1001//哈曼树结点
typedef struct TreeNode
{
    int weight;struct TreeNode *Left,*Right;
} *HuffmanTree;//Judge树结点
typedef struct JudgeNode
{
    struct JudgeNode *Left,*Right;
} *JNode;//储存字符
char character[MAX];//储存频率
int frequence[MAX];//这里有地方需要注意 这里的堆是以指针数组
HuffmanTree H[MAX+1];//下面的size就是储存堆当前有多少的 
//numbers就是一共有几个字符的
int realWPL = 0;
int size;
int numbers;void InitHeap();//初始化堆
void CreateMinHeap();//创造最小堆
HuffmanTree CreateHuffmanTree();//哈曼树创造
void Insert(HuffmanTree T);//插入 （最小堆）
HuffmanTree Delete(); //删除（最小堆）
void CalculateWPL(HuffmanTree T);
JNode NewNode();
int Find(char tempcharacter); //寻找是否有无效字符void InitHeap()
{
    HuffmanTree T;T = (HuffmanTree)malloc(sizeof(struct TreeNode));T->weight =MIN;T->Left = NULL;T->Right = NULL;H[0] = T;size = 0;
}//创造最小堆 没地方看不懂吧。。。
void CreateMinHeap()
{
    int i;int temp;char c;HuffmanTree T;for(i=0;i<numbers;i++){
    T = (HuffmanTree)malloc(sizeof(struct TreeNode));scanf(" %c %d",&c,&temp); //空格把缓冲区读走character[i] = c;frequence[i] = temp;T->weight = temp;T->Left = NULL;T->Right = NULL;Insert(T);}return;
}//基操 插入最小堆操作
void Insert(HuffmanTree T)
{
    int i = size+1;for( ;H[i/2]->weight > T->weight; i/=2 )H[i] = H[i/2];H[i] = T;size++;
}//这里细看一下吧
//但还是就基本操作 这里就代码就很直接
//没有parent child那些 更应该很快理解
HuffmanTree Delete()
{
    if(!size)exit(0);else{
    HuffmanTree T = H[size];int item = H[size--]->weight;int i;HuffmanTree minH = H[1];for(i=1 ; i*2 <= size; ){
    if(H[i*2]->weight <= H[i*2+1]->weight && item > H[i*2]->weight){
    H[i] = H[i*2];i*=2;}else if(H[i*2+1]->weight < H[i*2]->weight && item > H[i*2+1]->weight){
    H[i] = H[i*2+1];i = i*2 + 1;}elsebreak;}H[i] = T;return minH;}
}HuffmanTree CreateHuffmanTree()
{
    HuffmanTree T;int i;InitHeap();CreateMinHeap();//这里解释过了 是N-1次操作for(i=1;i<numbers;i++){
    T = (HuffmanTree)malloc(sizeof(struct TreeNode));T->Left = Delete();T->Right = Delete();T->weight = T->Left->weight + T->Right->weight;//累加权值Insert(T);}//把最后新生成的提走 就是我们的头结点了T = Delete();return T;
}void CalculateWPL(HuffmanTree T)
{
    if(T){
    HuffmanTree Temp = T;//这里就是筛选节点 度为2的结点//realWPL是我设置的全局变量 就是用来记录WPL的if(Temp->Left != NULL && Temp->Right != NULL)realWPL += T->weight;//这里使用了很简单的递归CalculateWPL(T->Left);CalculateWPL(T->Right);}return;
}JNode NewNode()
{
    JNode T;T = (JNode)malloc(sizeof(struct JudgeNode));T->Left = NULL;T->Right = NULL;return T;
}int Find(char tempcharacter)
{
    //筛查无效字符的 顺带找到字符后把频率返回回去int i;for(i=0;i<numbers;i++){
    if(character[i] == tempcharacter)return frequence[i];}return 0;
}//这里的Judge包含了1、WPL的核对是否相同
//2、前缀重复
int Judge()
{
    int i,j,sum = 0,tempfre;char tempcharacter[MAX],tempstring[MAX][MAX];for(i=0;i<numbers;i++){
    scanf(" %c %s",&tempcharacter[i],&tempstring[i]);//上面Find找到是否存在我们输入的字符 找到了//tempfre就是找到的字符的频率 if(tempfre = Find(tempcharacter[i]))sum += tempfre * strlen(tempstring[i]);elsereturn 0;}if(sum != realWPL)return 0;//else 之后就是我上面思路分析的地方else{
    JNode T,Position;T = NewNode();for(i=0;i<numbers;i++){
    //回到头结点Position = T;for(j=0;j<strlen(tempstring[i]);j++){
    if(tempstring[i][j] == '0'){
    //我们只需要确认最后的一位落点位是否是空结点//不是空结点就说明 要不是重复的 要不是前缀的if(j == strlen(tempstring[i]) -1 && Position->Left != NULL)return 0;else{
    if(Position->Left == NULL)Position->Left =NewNode();Position = Position->Left;}}else{
    if(j == strlen(tempstring[i]) -1 && Position->Right != NULL)return 0;else{
    if(Position->Right == NULL)Position->Right =NewNode();Position = Position->Right;}}}}}//当上面的循坏都执行完了 都没有跳出 说明没有前缀重叠//就可以return 1了return 1;
}int main()
{
    int i,checknumbers,ret;HuffmanTree T;scanf("%d",&numbers);T = CreateHuffmanTree();CalculateWPL(T);scanf("%d",&checknumbers);do{
    ret = Judge();if(!ret)printf("No");elseprintf("Yes");if(--checknumbers)printf("\n");} while(checknumbers);return 0;
}

终于写完了思路分析了
最重要的地方我都已经做了注释
希望能对像我一样刚上手的小白们有些许帮助
确实创造不易 但是重在坚持
也是对自己的一个思路回顾吧
在这里插入图片描述

心路历程

晚上20：17 12月5日
现在在写这篇博客的我
此时这道题还没有解出来 一个下午的心闷 一个晚上的难受
因为此时的我真的很想去学下一章了
到现在这道题我的思路还没有理清
还是坚持做一下吧

中午11：33 12月6日
我因为一个等号 因为一个等号 一个等号 等号
忽略了最小堆有可能就几个数字是相等的
我调试了整整一个上午 一直再找问题
刚刚吃饭都吃的不愉快 一直在想 我的思路没有错啊 我的代码没有错啊
怎么就是WPL算不对呢
方法也没问题啊 从8点调试到中午快12点了
就把哈曼树的构建调试成功了
我真的是一个小天才

下午13:11 12月6日
竟然大部分思路都完整了
而且大部分的代码都已经完工了
但是检查点只有三个是正确的
还需要再继续打磨一下
还有一些情况考虑的还不是很多

下午14：02 12月6日
这道题成功完工
但是做出来的喜悦竟然没有那么强hhh
就只有那么一点点开心
可能是前面的思想路程太过难受了
导致现在的索然无味吧。。

噜~（逃）

  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.