(c語言)Huffman Codes (30分)-有解無憂

關于資料結構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;
            }
            else
                break;
        }
        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]);
        else
            return 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");
      else
          printf("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
就只有那么一點點開心
可能是前面的思想路程太過難受了
導致現在的索然無味吧，，

嚕~（逃）

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/231549.html

標籤：其他

上一篇：3des加解密（+MD5） c++實作（附原始碼）

下一篇：普通程式員如何進階架構師？如何規劃自己的學習路線，P5到P8需要掌握的知識點是那些？