一個(gè)不知名大學(xué)生，江湖人稱(chēng)菜狗
original author: jacky Li
Email : 3435673055@qq.com
Last edited: 2022.11.20

目錄

數(shù)據(jù)結(jié)構(gòu)“基于哈夫曼樹(shù)的數(shù)據(jù)壓縮算法”的實(shí)驗(yàn)報(bào)告

一、實(shí)驗(yàn)?zāi)康?/p>

二、實(shí)驗(yàn)設(shè)備

三、實(shí)驗(yàn)內(nèi)容

1.【問(wèn)題描述】

2.【輸入要求】

3.【輸出要求】

4.【實(shí)驗(yàn)提示】

四、實(shí)驗(yàn)步驟

4.1

4.2編程和調(diào)試

五、實(shí)驗(yàn)結(jié)果

5.1程序完成后關(guān)鍵源碼及運(yùn)行結(jié)果截圖

六、實(shí)驗(yàn)總結(jié)

七、劃重點(diǎn)參考代碼

數(shù)據(jù)結(jié)構(gòu)“基于哈夫曼樹(shù)的數(shù)據(jù)壓縮算法”的實(shí)驗(yàn)報(bào)告

一、實(shí)驗(yàn)?zāi)康?/h3>

1.掌握哈夫曼樹(shù)的構(gòu)造算法。

2.掌握哈夫曼編碼的構(gòu)造算法。

二、實(shí)驗(yàn)設(shè)備

裝有Dev C++的計(jì)算機(jī)一臺(tái)

三、實(shí)驗(yàn)內(nèi)容

結(jié)合在頭歌上已完成的實(shí)訓(xùn)任務(wù)進(jìn)行填寫(xiě)

1.【問(wèn)題描述】

輸入一串字符串，根據(jù)給定的字符串中字符出現(xiàn)的頻率建立相應(yīng)的哈夫曼樹(shù)，構(gòu)造哈夫曼編碼表，在此基礎(chǔ)上可以對(duì)壓縮文件進(jìn)行壓縮（即編碼），同時(shí)可以對(duì)壓縮后的二進(jìn)制編碼文件進(jìn)行解壓（即譯碼）。

2.【輸入要求】

多組數(shù)據(jù)，每組數(shù)據(jù)1行，為一個(gè)字符串（只考慮26個(gè)小寫(xiě)字母即可）。當(dāng)輸入字符串為“0”時(shí)，輸入結(jié)束。

3.【輸出要求】

每組數(shù)據(jù)輸出2n+3行（n為輸入串中字符類(lèi)別的個(gè)數(shù)）。第1行為統(tǒng)計(jì)出來(lái)的字符出現(xiàn)頻率（只輸出存在的字符，格式為：字符：頻度），每?jī)山M字符之間用一個(gè)空格分隔，字符按照ASCII碼從小到大的順序排列。第2行至第2n行為哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)的終態(tài)（如主教材139頁(yè)表5.2（b），一行當(dāng)中的數(shù)據(jù)用空格分隔）。第2n+1行為每個(gè)字符的哈夫曼編碼（只輸出存在的字符，格式為：字符：編碼），每?jī)山M字符之間用一個(gè)空格分隔，字符按照ASCII碼從小到大的順序排列。第2n+2行為編碼后的字符串，第2n+3行為解碼后的字符串（與輸入的字符串相同）。

4.【實(shí)驗(yàn)提示】

此實(shí)驗(yàn)內(nèi)容即要求實(shí)現(xiàn)主教材的案例5.1，具體實(shí)現(xiàn)可參考算法5.10和算法5.11。首先，讀入一行字符串，統(tǒng)計(jì)每個(gè)字符出現(xiàn)的頻率；然后，根據(jù)字符出現(xiàn)的頻率利用算法5.10建立相應(yīng)的哈夫曼樹(shù)；最后，根據(jù)得到的哈夫曼樹(shù)利用算法5.11求出每個(gè)字符的哈夫曼編碼。

四、實(shí)驗(yàn)步驟

4.1

此部分可包含解題思路、最初填寫(xiě)的但沒(méi)有通過(guò)的程序，通過(guò)調(diào)試如何找到問(wèn)題并做出改正，可粘貼調(diào)整規(guī)范的截圖

4.2編程和調(diào)試

此部分可包含解題思路、最初填寫(xiě)的但沒(méi)有通過(guò)的程序，通過(guò)調(diào)試如何找到問(wèn)題并做出改正，可粘貼調(diào)整規(guī)范的截圖

五、實(shí)驗(yàn)結(jié)果

5.1程序完成后關(guān)鍵源碼及運(yùn)行結(jié)果截圖

可以將最終完成的代碼及運(yùn)行結(jié)果在此展示。

六、實(shí)驗(yàn)總結(jié)

用簡(jiǎn)介、準(zhǔn)確的語(yǔ)言描述本次實(shí)驗(yàn)重點(diǎn)解決了什么問(wèn)題，學(xué)習(xí)了什么知識(shí)，自己掌握的如何等等

七、劃重點(diǎn)參考代碼

#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>

#define IOS std::ios::sync_with_stdio(false)

using namespace std;

typedef struct
{
	int weight;
	int parent, lchild, rchild;
}HTNode, *HuffmanTree;

typedef char **HuffmanCode;

char ch[10];

void Select(HuffmanTree HT,int len,int &s1,int &s2)
{
    int i, min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f;
    
    for(i = 1; i <= len; i ++)
    	if(HT[i].parent == 0 && min1 > HT[i].weight)
    		min1 = HT[i].weight, s1 = i;
    		
    for(i = 1; i <= len; i ++)
    	if(i != s1 && HT[i].parent == 0)
    		if(HT[i].weight < min2)
        		min2 = HT[i].weight, s2 = i;
}
 
void CreatHuffmanTree(HuffmanTree &HT, int n, int s[])
{
    if(n <= 1) return;
    int m = 2 * n - 1;
    HT = new HTNode[m + 1];
    for(int i = 1; i <= m; i ++)
        HT[i].parent = 0, HT[i].lchild = 0, HT[i].rchild = 0;
        
    for(int i = 1; i <= 26; i ++) 
		if(s[i] != 0) 
			HT[i].weight = s[i];
    
    for(int i = n + 1; i <= m; i ++)
	{
        int s1, s2;
        Select(HT, i - 1, s1, s2);
        HT[s1].parent = i;
		HT[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}
 
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
	char *cd;
    HC = new char*[n + 1], cd = new char[n];
    
    cd[n - 1] = '\0';
    for(int i = 1; i <= n; i ++)
	{
        int start = n - 1;
        int c = i, f = HT[i].parent;
        while(f != 0)
		{
            -- start;
            if(HT[f].lchild == c) cd[start] = '0';
            else cd[start] = '1';
            c = f, f = HT[f].parent;
        }
        HC[i] = new char[n - start];
        strcpy(HC[i], &cd[start]);
    }
    delete cd;
}

void show(HuffmanCode HC, int h)
{
	for(int i = 1; i <= h; i ++)
		cout << HC[i] << endl;
}

void init()
{
	IOS;
	for(int i = 0; ; i ++)
	{
		char a; cin >> a;
		if(a != '0') ch[i] = a;
		else break;
	}
}

int main()
{
	IOS; init();
	int s[27], t = strlen(ch), h = 0;
	memset(s, 0, sizeof s);
	
	for(int i = 0; i <= t; i ++) s[ch[i] - 'a' + 1] ++;
	
	for(int i = 0; i <= 26; i ++)
		if(s[i] != 0) h ++;
	cout << h << endl;
	
	for(int i = 1; i <= 26; i ++)
		if(s[i] != 0)
			cout << (char)(i + 'a' - 1) << ":" << s[i] << ' ';
	cout << endl;
	
	
	HuffmanTree HT;
	HuffmanCode HC;

	CreatHuffmanTree(HT, h, s);
	CreatHuffmanCode(HT, HC, h);
	show(HC, h);
 
    return 0;
}

如果感覺(jué)博主講的對(duì)您有用，請(qǐng)點(diǎn)個(gè)關(guān)注支持一下吧，將會(huì)對(duì)此類(lèi)問(wèn)題持續(xù)更新……文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-490790.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)“基于哈夫曼樹(shù)的數(shù)據(jù)壓縮算法”的實(shí)驗(yàn)報(bào)告的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！