哈夫曼算法編碼26字母程序?qū)崿F(xiàn)C++-創(chuàng)新互聯(lián)

一、編程目的

10年積累的成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、外貿(mào)網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)后付款的網(wǎng)站建設(shè)流程，更有玉環(huán)免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

（1）學(xué)習(xí)和理解樹和二叉樹的概念、特點(diǎn)和相關(guān)知識(shí)，理解和掌握二叉樹的遍歷操作的原理和方法；掌握二叉樹的常用存儲(chǔ)結(jié)構(gòu)以及C++類的實(shí)現(xiàn)方法。

（2）學(xué)習(xí)最優(yōu)二叉樹的概念，理解和掌握哈夫曼算法的原理，掌握基于哈夫曼算法構(gòu)造最優(yōu)二叉樹的方法；學(xué)習(xí)和掌握基于最優(yōu)二叉樹的哈夫曼編碼方法。

（3）學(xué)會(huì)通過分析應(yīng)用需求，結(jié)合理論知識(shí)來設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)與有效的求解算法；能夠通過查找和學(xué)習(xí)技術(shù)資料、文檔來掌握需用到的編程知識(shí)、技術(shù)；能夠綜合運(yùn)用所學(xué)知識(shí)，利用開發(fā)環(huán)境提供的調(diào)試工具對(duì)程序進(jìn)行調(diào)試，完成程序的開發(fā)、測(cè)試和完善。

二、26字母頻率表

英文字母字符集及使用頻率

字母	英語中出現(xiàn)的頻率	字母	英語中出現(xiàn)的頻率	字母	英語中出現(xiàn)的頻率	字母	英語中出現(xiàn)的頻率
a	8.167%	h	6.094%	o	7.507%	u	2.758%
b	1.492%	i	6.966%	p	1.929%	v	0.978%
c	2.782%	j	0.153%	q	0.095%	w	2.360%
d	4.253%	k	0.772%	r	5.987%	x	0.150%
e	12.702%	l	4.025%	s	6.327%	y	1.974%
f	2.228%	m	2.406%	t	9.056%	z	0.074%
g	2.015%	n	6.749%

三、代碼實(shí)現(xiàn)

#include#include#includeusing namespace std;
struct huff
{
	double weight;
	int parent, lch, rch;
	char cha;
};
struct code
{
	char cd[25];
	int start;
};
void input(huff hufftree[],char alpha[],double weight[])//初始化哈夫曼樹，權(quán)值先全部賦0，再將頻率錄入
{
	for (int i = 0;i< 51;i++)
		hufftree[i].cha = '_';
	for (int i = 0;i< 26;i++)
		hufftree[i].cha= alpha[i];
	for (int i = 0;i< 51;i++)
		hufftree[i].weight = 0;
	for (int i = 0;i< 26;i++)
		hufftree[i].weight = weight[i];
	for (int i = 0;i< 51;i++)
	{
		hufftree[i].parent = -1;
		hufftree[i].lch = -1;
		hufftree[i].rch = -1;
	}
}
void buildtree(huff hufftree[])
{
	int i, k, lnode, rnode;double mina, minb;
	for (i = 26;i< 51;i++)//從第一個(gè)結(jié)點(diǎn)開始，確定其孩子結(jié)點(diǎn)
	{
		mina = minb = 100;lnode = rnode = 0;//100和0只是初始化值，無特殊含義，取100是確保高于任意字母的頻率，因?yàn)樗凶帜傅念l率和是100
		for (k = 0;k< 51&&hufftree[k].weight!=0;k++)//每一次遍歷整個(gè)hufftree，將已經(jīng)找到雙親結(jié)點(diǎn)的和尚未被使用的結(jié)點(diǎn)剔除，比較剩余結(jié)點(diǎn)
		{
			if (hufftree[k].parent == -1)//沒找到雙親結(jié)點(diǎn)
			{
				if (hufftree[k].weight< mina)//每一輪后mina都會(huì)變?yōu)?00，此時(shí)基本第一個(gè)進(jìn)來的k就會(huì)執(zhí)行這個(gè)if語句
				{
					minb = mina;//如果后續(xù)有更小的權(quán)，原先在mina的數(shù)據(jù)便會(huì)被移動(dòng)到minb，暫時(shí)變?yōu)榈诙?					rnode = lnode;
					mina = hufftree[k].weight;
					lnode = k;
				}
				else if (hufftree[k].weight< minb)//看看新的權(quán)值會(huì)不會(huì)替代成為第二小
				{
					minb = hufftree[k].weight;
					rnode = k;
				}//遍歷整個(gè)hufftree后，此時(shí)mina和minb上都已經(jīng)確定好這一輪的最小和次小，準(zhǔn)備賦值給這一輪對(duì)應(yīng)的未使用結(jié)點(diǎn)
			}
		}
		hufftree[lnode].parent = i;//確定雙親
		hufftree[rnode].parent = i;
		hufftree[i].weight = hufftree[lnode].weight + hufftree[rnode].weight;//確定未使用結(jié)點(diǎn)的權(quán)
		hufftree[i].lch = lnode;//確定未使用結(jié)點(diǎn)的孩子
		hufftree[i].rch = rnode;
	}//循環(huán)直到按照哈夫曼算法確定每個(gè)結(jié)點(diǎn)的值，構(gòu)造完成
	
}
void createcode(huff hufftree[],code alphac[])
{
	int i, f, c;
	code hc{};
	for(i=0;i<26;i++)//26次循環(huán)，確定26個(gè)字母
	{
		hc.start = 26;
		c = i;
		f = hufftree[i].parent;
		while (f != -1)
		{
			if (hufftree[f].lch == c)hc.cd[hc.start--] = '0';
			else hc.cd[hc.start--] =  '1';
			c = f;
			f = hufftree[f].parent;//向上再找一級(jí)，逆向從后向前儲(chǔ)存
		}
		hc.start++;//讀取時(shí)有用，確定長度
		alphac[i] = hc;//儲(chǔ)存
	}
}
void display(code alphac[],huff hufftree[])
{
	int i, j;
	cout<< "*********             歡迎使用哈夫曼編碼程序             *************"<< endl;
	cout<< "*********       26字母表字符集對(duì)應(yīng)哈夫曼編碼如下：       *************"<< endl;
	for(i=0;i<26;i++)
	{
		
		cout<< hufftree[i].cha<< " ";
		for (j = alphac[i].start;j<= 26;j++)
			cout<< alphac[i].cd[j];//正向讀取
		cout<< endl;
	}
	cout<< "*************   請(qǐng)輸入接下來的操作：         *************"<< endl;
	cout<< "************     1.將單詞翻譯為哈夫曼編碼         ********************"<< endl;
	cout<< "************     2.將哈夫曼編碼翻譯為單詞         ********************"<< endl;
	cout<< "請(qǐng)選擇："<< endl;
}
void fromwordstohuff(code alphac[], huff hufftree[])
{
	int eye = 0;
	cout<< "請(qǐng)輸入你想編譯的單詞："<< endl;
	char input[1000];
	cin >>input;
	cout<< input<< "的編碼為：" ;
	for (int i = 0;input[i] != '\0';i++)
	{
		char temp = input[i];
		for (int k = 0;k< 26;k++)
		{
			if (temp == hufftree[k].cha)
			{
				for (int j = alphac[k].start;j<= 26;j++)
					cout<< alphac[k].cd[j];//正向讀取
				    eye++;
				
			}
		}
	}
	if (eye< strlen(input))
	{
		cout<< endl;
		cout<< "您輸入的單詞中或含非法字符，已過濾，請(qǐng)您留意！"<< endl;//魯棒性容錯(cuò)
	}
	cout<< endl;
}
void fromhufftowords(code alphac[], huff hufftree[],char code[])
{
	cout<< "該編碼對(duì)應(yīng)單詞為：" ;
	int i, j;
	struct array { char storecode[10]; };
	array array1[26];
	for (i = 0;i< 26;i++)
	{
		int q = 0;
		for ( j = alphac[i].start;j<= 26;j++)
		{
			array1[i].storecode[q] = alphac[i].cd[j];
			q++;
		}
		array1[i].storecode[q] = '\0';
		//cout<< array1[i].storecode<< endl;（調(diào)試用）
	}
	int tt=0;//用于暫存i值
	char codecmp[1000];//構(gòu)造用于比較的字符串
	int z;
	int w = 0;
	for (int i = 0;code[i] != '\0';) 
	{
		int key=1;//用于判斷是否跳出for循環(huán)
		//cout<< w;w++;system("pause");（調(diào)試用）
		tt = i;
		for (z = 0;code[i] != '\0';z++)
		{
			codecmp[z] = code[i];
			i++;
		}//完成拷貝
		codecmp[z++] = '\0';//加入截止符號(hào)
		i = tt;
		int len=0;
		int k = 0;
		for (;k< 26&&key==1;k++)
		{    int d;
		     for (d = 0; codecmp[d] != '\0';) 
		     {   
				 if (codecmp[d] == array1[k].storecode[d])
				 {
					 d++;
					 if (array1[k].storecode[d] == '\0')//判斷哈夫曼代碼是否和字符集有相同的段落
					 {
						 cout<< hufftree[k].cha;//如果有，輸出該字符
						 key = 0;//調(diào)整key，使得對(duì)于該字符的循環(huán)停止，重新從k=0開始，避免k繼續(xù)往下加
						len = strlen(array1[k].storecode);
					 }
				 }
				 else break;
			 }
		}
		if (k == 26 && key == 1) 
		{
			cout<< "<——本條提示前為成功編譯的字母，但此后存在哈夫曼碼輸入錯(cuò)誤,請(qǐng)檢查后重新輸入"<< endl;
			break;
		}
		i = i + len;
		key = 1;//重調(diào)key值是下一次正常進(jìn)入循環(huán)
	}
	

}
int main()
{
	int w; int t;
	char alpha[26] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };
	double weight[26] = { 8.167,1.492, 2.782,4.253,12.702,2.228,2.015,6.094,6.966,0.153,0.772,4.025,2.406,6.749,7.507,1.929,0.095,5.987,6.327,9.056,2.758,0.978,2.360,0.150,1.974,0.074 };
	huff hufftree[51];
	code alphac[26];
	input(hufftree, alpha, weight);
	buildtree(hufftree);
	createcode(hufftree, alphac);
	display(alphac, hufftree);//字母表、權(quán)值表、哈夫曼樹和儲(chǔ)存哈夫曼碼的結(jié)構(gòu)數(shù)組的建立
	while(1)
	{ 
		cin >>t;
		w = t;
		int guard = 0;
	switch(w)
	{
	case 1: fromwordstohuff(alphac, hufftree);break;
	case 2:  cout<< "請(qǐng)輸入哈夫曼碼："<< endl;
		char code[1000];
	       	cin >>code;
			for (int check = 0;code[check] != '\0';check++)
			{
				if (code[check] != '0' && code[check] != '1')
				{
					cout<< "請(qǐng)輸入二進(jìn)制數(shù)字,請(qǐng)重試"<< endl;
					guard = 1;
					break;
				}
			}
			if (guard == 1) { break; }
			fromhufftowords(alphac, hufftree,code);cout<< endl;break;
	case 3: exit(1);
	default: cout<< "請(qǐng)輸入一個(gè)合理的選項(xiàng)"<< endl;
	 }
	cout<< endl;
	cout<< "*************   請(qǐng)輸入接下來的操作：         *************"<< endl;
	cout<< "************     1.將單詞翻譯為哈夫曼編碼         ********************"<< endl;
	cout<< "************     2.將哈夫曼編碼翻譯為單詞         ********************"<< endl;
	cout<< "************     3.退出程序                       ********************"<< endl;
	cout<< "請(qǐng)選擇："<< endl;
	}
 }

四、運(yùn)行結(jié)果

1、初始化

2、將單詞編碼為哈夫曼編碼

3、將哈夫曼碼編譯為單詞

五、結(jié)語

源代碼很少調(diào)用函數(shù)，編程習(xí)慣也很糟糕，因?yàn)楣P者對(duì)c++已經(jīng)非常生疏，但覺得這個(gè)功能很有意思，所以還是磕磕絆絆寫出來了一堆非常低效低級(jí)的代碼，有的地方甚至非常冗余，源代碼看著樂就好啦！

筆者過于小白，如果覺得有任何錯(cuò)漏和不足，懇請(qǐng)批評(píng)指正筆者，筆者感激不盡！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：哈夫曼算法編碼26字母程序?qū)崿F(xiàn)C++-創(chuàng)新互聯(lián)
文章地址：http://muchs.cn/article36/dgccsg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、用戶體驗(yàn)、營銷型網(wǎng)站建設(shè)、建站公司、網(wǎng)站設(shè)計(jì)公司、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)