第一篇：數(shù)據(jù)結(jié)構(gòu) 吳亞峰 第二次作業(yè)

哈夫曼編碼與解碼的實(shí)現(xiàn)

一、設(shè)計(jì)思想

首先構(gòu)建哈夫曼樹(shù)，再去進(jìn)行哈夫曼的譯碼，接著設(shè)計(jì)函數(shù)進(jìn)行字符串的編碼過(guò)程，最后進(jìn)行哈夫曼編碼的譯碼。

定義一個(gè)結(jié)構(gòu)體，用于存放構(gòu)建哈夫曼樹(shù)所需要的所有變量，開(kāi)辟一塊地址空間，用于存放數(shù)組，數(shù)組中每個(gè)元素為之前定義的結(jié)構(gòu)體。輸入n個(gè)字符及其權(quán)值。

構(gòu)建哈夫曼樹(shù)：在上述存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的哈夫曼算法可大致描述為：

第一步:初始化。將ht[ ]中2n-1個(gè)結(jié)點(diǎn)里的三個(gè)指針均置為空，權(quán)值置為0。

第二步:輸入。讀入n個(gè)葉子的權(quán)值存于向量的前n個(gè)分量中。它們是初始森林中n個(gè)孤立的根結(jié)點(diǎn)上的權(quán)值。

第三步:合并。對(duì)森林中的樹(shù)共進(jìn)行n-1次合并，所產(chǎn)生的新結(jié)點(diǎn)依次放入向量ht的第i個(gè)分量中。每次合并分兩步： 在當(dāng)前森林ht[0．．i-1]的所有結(jié)點(diǎn)中，選取權(quán)最小和次小的兩個(gè)根結(jié)點(diǎn)[s1]和 [s2]作為合并對(duì)象，這里0≤s1，s2≤i-1。將根為ht[s1]和ht[s2]的兩棵樹(shù)作為左右子樹(shù)合并為一棵新的樹(shù)，新樹(shù)的根是新結(jié)點(diǎn)ht[i]。具體操作：

將ht[s1]和ht[s2]的parent置為i，將ht[i]的lchild和rchild分別置為s1和s2。新結(jié)點(diǎn)ht[i]的權(quán)值置為ht[s1]和ht[s2]的權(quán)值之和。

哈夫曼的編碼：約定左子為0，右子為1，則可以從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上的字符組成的字符串作為該葉子結(jié)點(diǎn)的編碼。

當(dāng)用戶(hù)輸入字母時(shí)。就在已經(jīng)找好編碼的編碼結(jié)構(gòu)體中去查找該字母。查到該字母就打印所存的哈夫曼編碼。接著就是完成用戶(hù)輸入0、1代碼時(shí)把代碼轉(zhuǎn)成字母的功能。這是從樹(shù)的頭結(jié)點(diǎn)向下查找，如果當(dāng)前用戶(hù)輸入的0、1串中是0則就走向該結(jié)點(diǎn)的左子。如果是1這就走向該結(jié)點(diǎn)的右結(jié)點(diǎn)，重復(fù)上面步驟。直到發(fā)現(xiàn)該結(jié)點(diǎn)屬于輸入了字母的結(jié)構(gòu)體則打印該結(jié)構(gòu)體的字母。重復(fù)上面步驟。直到找完用戶(hù)輸入0、1串為止。則就完成了程序所有的譯碼過(guò)程。

哈夫曼編碼與解碼的實(shí)現(xiàn)

三、源代碼

#include #include

/* 數(shù)組頭文件 */ #include #define MAX 999

/* 定義長(zhǎng)度 */ typedef struct{

/* 定義哈夫曼編碼的結(jié)構(gòu)數(shù)組 */

char data;

int weight;

/* 定義權(quán)值 */

int parent;

int lchild;

int rchild;}huffmannode;typedef struct{

/* 定義保存哈夫曼結(jié)構(gòu)體 */

char bits[50];

int start;}huffmancode;void main(){

huffmannode ht[100];

/* 定義儲(chǔ)存權(quán)值的空間 */

huffmancode cd[100];

char string[100];

/* 定義數(shù)組存儲(chǔ)空間 */

char hcd[100];

int i,j,x,y,s1,s2,m1,m2,n,c,f,k;

printf(“please input the n=”);

/* 輸入字符的個(gè)數(shù) */

scanf(“%d”,&n);

printf(“n===============================n”);

for(i=0;i

{

getchar();

/* 獲得輸入的字符 */

printf(“please input the value :”);

scanf(“%c”,&ht[i].data);

/* 輸入字符函數(shù) */

printf(“please input the weight:”);

scanf(“%d”,&ht[i].weight);

}

printf(“n=============================n”);

for(i=0;i<2*n-1;i++)

{

ht[i].parent=ht[i].lchild=ht[i].rchild=-1;/* 初始化父結(jié)點(diǎn)，左右子結(jié)點(diǎn) */

}

for(i=n;i<2*n-1;i++)

{

s1=s2=0;

/* 初始化變量 */

m1=m2=MAX;

哈夫曼編碼與解碼的實(shí)現(xiàn)

}

printf(“n=============================n”);

printf(“nPlease input the message:n”);

scanf(“%s”,string);

/* 輸入字符串 */

for(i=0;string[i]!='