文章目錄
前言
一、問(wèn)題描述：
二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：
1、課設(shè)要求：
2、具體實(shí)現(xiàn)：
三、功能（函數(shù)）設(shè)計(jì)
1、課設(shè)要求
2、具體實(shí)現(xiàn)：
四、界面設(shè)計(jì)
五、程序設(shè)計(jì)
?1、流程圖/程序思想詳細(xì)介紹：
2、函數(shù)功能說(shuō)明如下：
六、運(yùn)行與測(cè)試
1、課設(shè)要求
2、具體實(shí)現(xiàn)：
（1）測(cè)試的數(shù)據(jù)及其結(jié)果：
?（2）程序的空間復(fù)雜度與時(shí)間復(fù)雜度分析：
七、編寫代碼及運(yùn)行時(shí)遇到的問(wèn)題及解決方法
1、編寫代碼期間遇到的問(wèn)題及其解決辦法
2、運(yùn)行與測(cè)試期間遇到的問(wèn)題及其解決辦法
前言
本文主要介紹在結(jié)合文件基礎(chǔ)操作上進(jìn)行哈夫曼編/譯碼器的設(shè)計(jì)與實(shí)現(xiàn)，其中主要實(shí)現(xiàn)接收原始數(shù)據(jù)、編碼、譯碼、打印編碼規(guī)則這幾個(gè)功能。同時(shí)將詳細(xì)介紹本人對(duì)這一程序的設(shè)計(jì)思想與過(guò)程，以及自己在編寫程序與運(yùn)行與測(cè)試時(shí)遇到的問(wèn)題即解決方法。
一、問(wèn)題描述：
利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼。系統(tǒng)應(yīng)該具有如下的幾個(gè)功能：接收原始數(shù)據(jù)、編碼、譯碼、打印編碼規(guī)則。
二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：
1、課設(shè)要求：
（1）構(gòu)造哈夫曼樹時(shí)使用順序表作為哈夫曼樹的存儲(chǔ)結(jié)構(gòu)。
（2）求哈夫曼編碼時(shí)使用一維結(jié)構(gòu)數(shù)組作為哈夫曼編碼信息的存儲(chǔ)。
2、具體實(shí)現(xiàn)：
我主要定義了三種數(shù)據(jù)結(jié)構(gòu)。
（1）定義了動(dòng)態(tài)分配的二維數(shù)組來(lái)存儲(chǔ)哈夫曼樹，每個(gè)結(jié)點(diǎn)都有五個(gè)域，分別是權(quán)值域、字符域、雙親域與左孩子和右孩子域。結(jié)構(gòu)如下
//哈夫曼樹存儲(chǔ)結(jié)構(gòu)定義
typedef struct
{
int weight;//權(quán)值
char ch;//結(jié)點(diǎn)對(duì)應(yīng)字符
int parent, lchild, rchild;//結(jié)點(diǎn)的雙親和左右孩子
}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹
（2）?定義了動(dòng)態(tài)分配的指針數(shù)組來(lái)存儲(chǔ)哈夫曼編碼，數(shù)組內(nèi)存儲(chǔ)的指針?lè)謩e指向?qū)?yīng)存儲(chǔ)編碼的一維字符數(shù)組。結(jié)構(gòu)如下：
typedef char** Huffmancode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼
HC = (Huffmancode)malloc((n + 1) * sizeof(char*));
HC[i] = (char*)malloc((n - start) * sizeof(char));（3）?定義了存放字符及其權(quán)值的結(jié)構(gòu)體。結(jié)構(gòu)如下：
//存放字符及其權(quán)值的結(jié)構(gòu)體
struct Data_type
{
char c;
int weight;
}Data[50];三、功能（函數(shù)）設(shè)計(jì)
1、課設(shè)要求
（1）初始化功能模塊模塊的功能為從鍵盤接收字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值。
（2）建立哈夫曼樹的功能模塊此模塊功能為使用1中得到的數(shù)據(jù)按照構(gòu)造哈夫曼樹的算法構(gòu)造哈夫曼樹，即將HuffNode數(shù)組中的各個(gè)位置的各個(gè)域都添上相關(guān)的值，并將這個(gè)結(jié)構(gòu)體數(shù)組存于文件中。
（3）建立哈夫曼編碼的功能模塊此模塊功能為從文件中讀入相關(guān)的字符信息進(jìn)行哈夫曼編碼，然后將結(jié)果存入，同時(shí)將字符與0、1代碼串的一一對(duì)應(yīng)關(guān)系打印到屏幕上。
（4）譯碼的功能模塊此模塊功能為接收需要譯碼的0、1代碼串，按照3中建立的哈夫曼編碼規(guī)則將其翻譯成字符集中的字符所組成的字符串形式，存入文件，同時(shí)將翻譯的結(jié)果在屏幕上打印輸出。
2、具體實(shí)現(xiàn)：
本人根據(jù)設(shè)計(jì)內(nèi)容設(shè)計(jì)了五個(gè)功能模塊，模塊圖如下：
以下為每個(gè)模塊所用到的函數(shù)以及函數(shù)功能描述：
（1）建立/讀取Data與ToBeCode文件功能模塊：
case 1://建立/讀取Data與ToBeCode文件
{
printf("1、鍵盤輸入字符及其權(quán)值建立Data.txt文件\n");
printf("2、直接讀取文件中存儲(chǔ)的字符與權(quán)值\n");
printf("請(qǐng)選擇以上兩種方式中的一種：");
int c;
scanf_s("%d", &c);
getchar();
switch (c)
{
case 1:
{
printf("請(qǐng)建立文件Data用以存放字符及其權(quán)值：\n");
InitData(n);//建立文件Data與ToBeCode并輸出字符及其對(duì)應(yīng)權(quán)值
printf("建立文件成功，請(qǐng)選擇下一步操作：\n");
printf("\n\n");
break;
}
case 2:
{
if ((fp = fopen("Data.txt", "r")) == NULL)
{
printf("文件讀取失敗\n");
exit(0);
}
printf("各個(gè)字符及其對(duì)應(yīng)的權(quán)值如下:\n");
//從文件中讀取字符及其權(quán)值存入Data數(shù)組
for (int i = 0; i < n; i++)
{
fscanf(fp, "%c%d", &Data[i].c, &Data[i].weight);
printf("%c--%d\t", Data[i].c, Data[i].weight);
}
InitToBeCode(n);///創(chuàng)建ToBeCode文件存儲(chǔ)要進(jìn)行編碼的字符
printf("讀取成功，請(qǐng)選擇下一步操作：\n");
printf("\n\n");
break;
}
default:
{
printf("輸入錯(cuò)誤請(qǐng)重新輸入：\n");
break;
}
}
break;
}（2）根據(jù)Data文件中的數(shù)據(jù)建立哈夫曼樹并存儲(chǔ)到hfmTree文件功能模塊：?
case 2://從文件Data中讀取數(shù)據(jù)來(lái)建立哈夫曼樹并將數(shù)組存于文件hfmTree中
{
CreateTree(HT, n);//建立哈夫曼樹函數(shù)
printf("建立哈夫曼樹成功，請(qǐng)選擇下一步操作：\n");
printf("\n\n");
break;
}（3）?讀取ToBeCode文件進(jìn)行哈弗曼編碼并將編碼存入Code文件功能模塊：
case 3://對(duì)文件ToBeCode中的字符進(jìn)行編碼再寫入Code文件中，并輸出字符對(duì)應(yīng)編碼
{
HuffmanCoding(HT, HC, n);//哈夫曼編碼函數(shù)
printf("編碼成功，請(qǐng)選擇下一步操作：\n");
printf("\n\n");
break;
}（4）?對(duì)所輸入字符串/報(bào)文進(jìn)行譯碼并寫入TransFile文件功能模塊：
case 4://對(duì)文件CodeFile譯碼再寫入TransFile中，并輸出譯碼結(jié)果
{
printf("請(qǐng)選擇以下兩種操作中的其中一個(gè):\n");
printf("1、輸入字符串并對(duì)其進(jìn)行譯碼\n");
printf("2、輸入報(bào)文對(duì)其進(jìn)行編碼后進(jìn)行譯碼\n");
printf("請(qǐng)輸入您的選擇：");
int b;
scanf("%d", &b);
getchar();
switch (b)
{
case 1:
{
InitCode(n);//輸入字符串并存入CodeFile函數(shù)
TranslateTree(HT, n);//哈夫曼譯碼函數(shù)
printf("譯碼成功，請(qǐng)選擇下一步操作：\n");
printf("\n\n");
break;
}
case 2:
{
Trans(HT, HC, n);//輸入報(bào)文并進(jìn)行編碼函數(shù)
TranslateTree(HT, n);//哈夫曼譯碼函數(shù)
printf("譯碼成功，請(qǐng)選擇下一步操作：\n");
printf("\n\n");
break;
}
default:
{
printf("輸入錯(cuò)誤請(qǐng)重新輸入：\n");
break;
}
}
break;
}（5）?退出程序功能模塊：
case 5://退出程序
{
return 0;
}四、界面設(shè)計(jì)
界面設(shè)計(jì)主要包括主菜單與子菜單。主菜單主要是對(duì)五個(gè)功能模塊的展示，而子菜單則分別是由于用戶選擇輸入Data的方式不同以及進(jìn)行譯碼的數(shù)據(jù)不同而出現(xiàn)的，對(duì)應(yīng)的就是操作一與操作四的子菜單。菜單如下所示：
?
五、程序設(shè)計(jì)
?1、流程圖/程序思想詳細(xì)介紹：
①主程序的流程是首先讓用戶輸入葉子結(jié)點(diǎn)個(gè)數(shù)之后調(diào)用while函數(shù)進(jìn)入循環(huán)，接著調(diào)用mean函數(shù)輸出主菜單，接著再根據(jù)用戶的選擇調(diào)用switch函數(shù)進(jìn)入對(duì)應(yīng)的功能模塊。
②操作一為建立/讀取Data和ToBeCode文件功能模塊，擁有子菜單，讓用戶可以以兩種途徑去建立Data與ToBeCode文件，一比較適用于字符個(gè)數(shù)較少手動(dòng)輸入較快的情況，二比較適用于字符個(gè)數(shù)過(guò)多直接存入文件較快的情況。一主要通過(guò)調(diào)用InitCode函數(shù)去根據(jù)輸入數(shù)據(jù)建立Data文件，在InitData函數(shù)里面又調(diào)用了InitToBeCode函數(shù)建立ToBeCode文件，并將要進(jìn)行編碼的字符存入文件；二主要是調(diào)用fopen和fscanf函數(shù)去打開文件，并將文件數(shù)據(jù)存入Data數(shù)組，接著調(diào)用InitToBeCode函數(shù)建立ToBeCode文件，并將要進(jìn)行編碼的字符存入文件。
③操作二為根據(jù)Data文件中的數(shù)據(jù)建立哈夫曼樹并存儲(chǔ)到hfmTree文件功能模塊。首先調(diào)用CreateTree函數(shù)從Data文件中讀取數(shù)據(jù)來(lái)建立哈夫曼樹，在CreateTree函數(shù)里面又調(diào)用Select函數(shù)選擇權(quán)值最小的兩個(gè)結(jié)點(diǎn)來(lái)建立雙親結(jié)點(diǎn)。
④操作三為讀取ToBeCode文件進(jìn)行哈弗曼編碼并將編碼存入Code文件功能模塊。主要是通過(guò)調(diào)用HuffmanCoding函數(shù)對(duì)ToBeCode文件中的字符進(jìn)行編碼并存入Code文件。
⑤操作四為對(duì)輸入的字符串/報(bào)文進(jìn)行譯碼并寫入TransFile文件功能模塊，擁有子菜單，用戶可以選擇操作一直接輸入字符串存入CodeFile文件，也可以選擇操作二輸入報(bào)文對(duì)報(bào)文進(jìn)行編碼存入CodeFile文件，這個(gè)可以根據(jù)用戶的需求自行選擇。操作一是調(diào)用InitCode函數(shù)輸入要進(jìn)行譯碼的字符串并存入CodeFile文件，接著調(diào)用TranslateTree函數(shù)對(duì)CodeFile中的字符串進(jìn)行譯碼并輸出譯碼結(jié)果；操作二；是調(diào)用Trans函數(shù)輸入要進(jìn)行編碼和譯碼的報(bào)文并對(duì)其進(jìn)行編碼存入CodeFile文件，接著調(diào)用TranslateTree函數(shù)對(duì)CodeFile中的字符串進(jìn)行譯碼并輸出譯碼結(jié)果。
⑥操作五為退出程序功能模塊。通過(guò)return 0退出程序。
2、函數(shù)功能說(shuō)明如下：
（1）選擇無(wú)雙親且權(quán)值最小的兩個(gè)結(jié)點(diǎn)以建立新結(jié)點(diǎn)函數(shù)：
//在HT[1...n]中選擇無(wú)雙親即parent為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn)
void Select(HuffmanTree HT, int n, int& s1, int& s2)
{
//HT不進(jìn)行改變故無(wú)需引用,s1,s2需要作為序號(hào)返回
int i=1,min=0;
//先找到第一個(gè)雙親為0的結(jié)點(diǎn)的權(quán)值暫時(shí)作為最小值與其他結(jié)點(diǎn)進(jìn)行比較
for (i = 1; i <= n; i++)//時(shí)間復(fù)雜度O(n)
{
if (HT[i].parent == 0)
{
min = i;
break;
}
}
//將上個(gè)循環(huán)找到的暫時(shí)的最小值與每個(gè)結(jié)點(diǎn)的權(quán)值進(jìn)行比較從而找出權(quán)值最小的結(jié)點(diǎn)
for (i = 1; i <= n; i++)//時(shí)間復(fù)雜度O(n)
{
if (HT[i].parent == 0)
{
if (HT[i].weight < HT[min].weight)
{
min = i;
}
}
}
s1 = min;//s1為權(quán)值最小的結(jié)點(diǎn)
//排除s1，尋找另一個(gè)權(quán)值最小的結(jié)點(diǎn)
for (i = 1; i <= n; i++)//同樣尋找一個(gè)結(jié)點(diǎn)的權(quán)值作為比較
{
if ((HT[i].parent == 0) && (i != s1))
{
min = i;
break;
}
}
//將暫時(shí)的最小值與所有結(jié)點(diǎn)的權(quán)值進(jìn)行比較，找出權(quán)值最小的結(jié)點(diǎn)
for (i = 1; i <= n; i++)
{
if ((HT[i].parent == 0) && (i != s1))
{
if (HT[i].weight < HT[min].weight)
{
min = i;
}
}
}
s2 = min;//s2為第二個(gè)權(quán)值最小的結(jié)點(diǎn)
}?（2）建立并將要編碼的字符出入ToBeCode文件函數(shù)：
void InitToBeCode(int n)
{
FILE* fp;
if ((fp = fopen("ToBeCode.txt", "w")) == NULL)
{
printf("文件打開失敗\n");
exit(0);
}
for (int i = 0; i < n; i++)
{
//將n個(gè)字符的字符輸送到存入文件
fprintf(fp, "%c", Data[i].c);
}
fprintf(fp, "#");
fclose(fp);
}?（3）建立并輸入字符與權(quán)值存入文件Data函數(shù)：
//初始化功能模塊
//從鍵盤輸入字符和權(quán)值到文件Data中并輸出
void InitData(int n)
{
FILE* fp,*fp1;
//w--可讀可寫，打開一個(gè)文本文件，如果出錯(cuò)則會(huì)建立一個(gè)新文件
//如果原來(lái)已存在該命名文件則刪去原來(lái)的文件重新建立一個(gè)文件
if ((fp = fopen("Data.txt", "w")) == NULL)
{
printf("文件打開失敗\n");
exit(0);
}
printf("請(qǐng)依次輸入字符及其權(quán)值：\n");
for (int i = 0; i < n; i++)
{
scanf("%c%d", &Data[i].c, &Data[i].weight);
}
for (int i = 0; i < n; i++)
{
//將n個(gè)字符的字符及其權(quán)值輸送到存入文件
fprintf(fp, "%c%d", Data[i].c, Data[i].weight);
}
fprintf(fp, "#");
fclose(fp);
//輸出字符及其對(duì)應(yīng)權(quán)值
printf("各個(gè)字符及其對(duì)應(yīng)的權(quán)值如下:\n");
for (int i = 0; i < n; i++)
{
printf("%c--%d\t", Data[i].c, Data[i].weight);
}
InitToBeCode(n);//創(chuàng)建ToBeCode文件存儲(chǔ)要進(jìn)行編碼的字符
}（4）?創(chuàng)建CodeFile文件并將要進(jìn)行譯碼的字符串存入文件函數(shù)：
//創(chuàng)建存放即將要進(jìn)行譯碼的字符串
void InitCode(int n)
{
FILE* fp;
char s[50];
printf("請(qǐng)輸入要進(jìn)行譯碼的字符串：\n");
gets_s(s);
//w--可讀可寫，打開一個(gè)文本文件，如果出錯(cuò)則會(huì)建立一個(gè)新文件
//如果原來(lái)已存在該命名文件則刪去原來(lái)的文件重新建立一個(gè)文件
if ((fp = fopen("CodeFile.txt", "w")) == NULL)
{
printf("文件打開失敗\n");
exit(0);
}
fprintf(fp, "%s",s);
fprintf(fp, "#");
fclose(fp);
printf("\n");
}（5）初始化并建立哈夫曼樹與hfmTree文件函數(shù)：
//初始化并建立哈夫曼樹
void CreateTree(HuffmanTree& HT, int n)
{
FILE* fp;
if ((fp = fopen("Data.txt", "r")) == NULL)
{
printf("文件讀取失敗\n");
exit(0);
}
if (n < 1)//判斷結(jié)點(diǎn)字符個(gè)數(shù)
exit(-1);
int m, i,s1,s2;
//已知字符均為葉子結(jié)點(diǎn)
//由二叉樹的性質(zhì)3：度為2的結(jié)點(diǎn)數(shù)+1=葉子節(jié)點(diǎn)數(shù)可得總結(jié)點(diǎn)個(gè)數(shù)
m = 2 * n - 1;
//申請(qǐng)m+1個(gè)結(jié)點(diǎn)的存儲(chǔ)空間，其中0號(hào)單位不用
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));//空間復(fù)雜度為O(n)
//利用for循環(huán)將哈夫曼樹中所有結(jié)點(diǎn)的權(quán)值、雙親和左右孩子賦值為0
for (i = 1; i <= m; i++)
{
HT[i].ch = 0;
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
//利用for循環(huán)從文件中讀取數(shù)據(jù)為葉子結(jié)點(diǎn)賦權(quán)值和字符
for (i = 1; i <= n; i++)
{
fscanf(fp, "%c%d", &HT[i].ch, &HT[i].weight);
}
fclose(fp);
//建立哈夫曼樹
for (i = n + 1; i <= m; i++)
{
Select(HT, i - 1, s1, s2);//在HT[1...i-1]中選擇無(wú)雙親即parent為0且權(quán)值最小的兩個(gè)結(jié)點(diǎn)
HT[s1].parent = i;//s1和s2結(jié)合，將i賦給它們的雙親域
HT[s2].parent = i;
HT[i].lchild = s1;//將s1與s2賦給i的左孩子域和右孩子域
HT[i].rchild = s2;
//i的權(quán)值等于左右兩個(gè)孩子的權(quán)值相加
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
FILE* fp1;
//w--只寫，打開一個(gè)文本文件，如果出錯(cuò)則會(huì)建立一個(gè)新文件
if ((fp1 = fopen("hfmTree.txt", "w")) == NULL)
{
printf("文件打開失敗\n");
exit(0);
}
//將這個(gè)結(jié)構(gòu)體數(shù)組存于文件中
for (i = 1; i <=m; i++)
{
fprintf(fp1, "%c %d %d %d %d\n", HT[i].ch, HT[i].parent, HT[i].lchild, HT[i].rchild, HT[i].weight);
}
fclose(fp1);
}（6）?求對(duì)應(yīng)字符的哈夫曼編碼函數(shù)：
//求哈夫曼編碼函數(shù)
void HuffmanCoding(HuffmanTree& HT, Huffmancode& HC, int n)
{ //HC實(shí)際為存儲(chǔ)每個(gè)編碼的頭指針數(shù)組
//分配n個(gè)字符編碼的頭指針存儲(chǔ)數(shù)組空間，0號(hào)單元不用
HC = (Huffmancode)malloc((n + 1) * sizeof(char*));//空間復(fù)雜度為O(n*n)
int i, start,c,f;
char* cd;//分配暫時(shí)存儲(chǔ)求編碼的工作空間
cd = (char*)malloc(n * sizeof(char));
cd[n - 1] = '\0';//編碼結(jié)束符
printf("每個(gè)字符及其對(duì)應(yīng)編碼如下：\n");
for (i = 1; i <= n; i++)
{
//因?yàn)槭菑娜~子結(jié)點(diǎn)逆序進(jìn)行編碼，所以start指向存儲(chǔ)編碼的結(jié)束符位置
start = n - 1;
//從葉子結(jié)點(diǎn)到根逆向求編碼
f = HT[i].parent;
c = i;
while (f != 0)
{
--start;
if (HT[f].lchild == c)//如果目前結(jié)點(diǎn)是f的左孩子則編碼為0
cd[start] = '0';
else//如果目前結(jié)點(diǎn)是f的右孩子則編碼為1
cd[start] = '1';
//接著讓c指向目前結(jié)點(diǎn)的雙親，f指向目前結(jié)點(diǎn)的雙親的雙親不斷進(jìn)行編碼
//直至f=0即f指向根結(jié)點(diǎn)
c = f;
f = HT[f].parent;
}
//對(duì)每個(gè)葉子結(jié)點(diǎn)進(jìn)行編碼結(jié)束之后便 將對(duì)應(yīng)的編碼存儲(chǔ)到HC中
//為第i個(gè)字符的編碼分配空間
HC[i] = (char*)malloc((n - start) * sizeof(char));
strcpy(HC[i], &cd[start]);//從cd復(fù)制到HC
printf("%c--%s\t", HT[i].ch, HC[i]);//輸出字符及其對(duì)應(yīng)編碼
}
free(cd);//釋放暫時(shí)存儲(chǔ)編碼的工作空間
FILE* fp, * fp1;
//建立Code.txt文件用于存放字符與編碼
if ((fp1 = fopen("Code.txt", "w")) == NULL)
{
printf("文件打開失敗\n");
exit(0);
}
//判斷ToBeCode.txt文件是否存在
if ((fp = fopen("ToBeCode.txt", "r")) == NULL)
{
printf("文件讀取失敗\n");
exit(0);
}
c = fgetc(fp);
while (c != '#')
{
for (i = 1; i <= n; i++)
{
if (c == HT[i].ch) //找到字符編號(hào)
//將對(duì)應(yīng)的哈夫曼編碼寫入文件Code中
fprintf(fp1, "%s",HC[i]);
}
c = fgetc(fp);
}
fprintf(fp1, "#");
fclose(fp);
fclose(fp1);
}（7）譯碼函數(shù)：
//譯碼函數(shù)
//基本思想：從根出發(fā)，按字符'0'/'1'來(lái)尋找左孩子或者右孩子直至葉子結(jié)點(diǎn)
void TranslateTree(HuffmanTree HT, int n)
{
int m;
char b;
FILE* fp, * fp1,*fp2,*fp3;
//CodeFile.txt文件需要提前輸入，也就是要進(jìn)行譯碼的代碼串
if ((fp = fopen("CodeFile.txt", "r")) == NULL)
{//打開文件只讀
printf("文件打開失敗\n");
exit(0);
}
//w--只寫，打開一個(gè)文本文件，如果出錯(cuò)則會(huì)建立一個(gè)新文件
if ((fp1 = fopen("TransFile.txt", "w")) == NULL)
{//打開文件只寫
printf("文件打開失敗\n");
exit(0);
}
printf("字符串進(jìn)行譯碼的結(jié)果為：\n");
b = fgetc(fp); //從文件中一個(gè)一個(gè)讀取字符
m = 2 * n - 1;//初始化讓m指向根結(jié)點(diǎn)，從根結(jié)點(diǎn)出發(fā)
while (b != '#')
{
if (b == '0')//如果為'0'，則指向其左孩子
{
m = HT[m].lchild;
}
else if (b == '1')//如果為'1'，則指向其右孩子
{
m = HT[m].rchild;
}
//一直到根結(jié)點(diǎn)則將該結(jié)點(diǎn)表示的字符存入文件中并讓m重新指向根結(jié)點(diǎn)進(jìn)行查找
if (HT[m].lchild == 0)
{
fprintf(fp1, "%c", HT[m].ch);
m = 2 * n - 1;
}
printf("%c", b);
b = fgetc(fp);//再讀下一個(gè)字符
}
printf("——");
fprintf(fp1, "#"); //將‘#’寫入文件
fclose(fp);
fclose(fp1);
if ((fp2 = fopen("TransFile.txt", "r")) == NULL)
{//打開文件只讀
printf("文件打開失敗\n");
exit(0);
}
char k = fgetc(fp2);
while (k != '#')
{
printf("%c", k);
k = fgetc(fp2);
}
printf("\n\n");
fclose(fp2);
}
（8）?對(duì)給定的報(bào)文進(jìn)行編碼函數(shù)：
//對(duì)給定的報(bào)文進(jìn)行編碼
void Trans(HuffmanTree HT, Huffmancode HC, int n)
{
FILE* fp;
int i,j;
char s[50];//存放報(bào)文
if ((fp = fopen("CodeFile.txt", "w")) == NULL)
{
printf("文件打開失敗\n");
exit(0);
}
printf("請(qǐng)輸入要進(jìn)行編碼的報(bào)文:\n");
gets_s(s);
//時(shí)間復(fù)雜度為O(len*n)
for (i = 0; s[i] != '\0'; i++)
{
for (j = 1; j <= n + 1; j++)
{
if (s[i] == HT[j].ch)
{
fprintf(fp, "%s", HC[j]);
}
}
}
fprintf(fp, "#");
fclose(fp);
printf("\n");
}（9）主菜單函數(shù)：
void mean()
{
printf("--------哈夫曼編譯碼操作系統(tǒng)------\n");
printf("1.建立/讀取Data與ToBeCode文件\n");
printf("2.從文件Data中讀取數(shù)據(jù)來(lái)建立哈夫曼樹并將數(shù)組存于文件hfmTree中\(zhòng)n");
printf("3.對(duì)文件ToBeCode中的字符進(jìn)行編碼再寫入Code文件中，并輸出字符對(duì)應(yīng)編碼\n");
printf("4.對(duì)輸入字符串/報(bào)文進(jìn)行譯碼再寫入TransFile中，并輸出譯碼結(jié)果\n");
printf("5.退出程序\n");
printf("----------------------------------\n");
printf("輸入你的選擇：");
}六、運(yùn)行與測(cè)試
1、課設(shè)要求
（1）利用下列數(shù)據(jù)調(diào)試程序：令葉子結(jié)點(diǎn)個(gè)數(shù)n為4，權(quán)值集合為{1,3,5,7}，字符集合為{A,B,C,D}，并有如下對(duì)應(yīng)關(guān)系，A——1、B——3、C——5、D——7，調(diào)用初始化功能模塊可以正確接收這些數(shù)據(jù)；調(diào)用建立哈夫曼樹的功能模塊，構(gòu)造靜態(tài)鏈表HuffNode的存儲(chǔ)；調(diào)用建立哈夫曼編碼的功能模塊，在屏幕上顯示如下對(duì)應(yīng)關(guān)系：A——111、B——110、C——10、D——0；調(diào)用譯碼的功能模塊，輸入代碼串“111110100”后，屏幕上顯示譯碼結(jié)果：111110100——ABCD
（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THE PROGRAM IS MY FAVORITE”。
| 字符 | A | B | C | D | E | F | G | H | I | J | K | L | M | |
| 頻度 | 186 | 64 | 13 | 22 | 32 | 103 | 21 | 15 | 47 | 57 | 1 | 5 | 32 | 20 |
| 字符 | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | |
| 頻度 | 57 | 63 | 15 | 1 | 48 | 51 | 80 | 23 | 8 | 18 | 1 | 16 | 1 |
2、具體實(shí)現(xiàn)：
（1）測(cè)試的數(shù)據(jù)及其結(jié)果：
（一）結(jié)點(diǎn)個(gè)數(shù)n=4，字符及其權(quán)值A(chǔ)-1,B-3,C-5,D-7,譯碼字符串：100101110,結(jié)果如下：
?(二)結(jié)點(diǎn)個(gè)數(shù)與字符及其權(quán)值與（一）相同，譯碼報(bào)文為：ACDBDBCA，結(jié)果如下：
?（三）結(jié)點(diǎn)個(gè)數(shù)n=27，字符及其權(quán)值為-186，A-64，B-13，C-22，D-32，E-103，F(xiàn)-21，G-15，H-47，I-57，J-1，K-5，L-32，M-20，N-57，O-63，P-15，Q-1，R-48，S-51，T-80，U-23，V-8，W-18，X-1，Y-16，Z-1,譯碼報(bào)文：THE PROGRAM IS MY FAVORITE,結(jié)果如下：
?(四)結(jié)點(diǎn)個(gè)數(shù)與字符及其權(quán)值與（二）相同，譯碼字符串為1010001110111，結(jié)果如下：
?（2）程序的空間復(fù)雜度與時(shí)間復(fù)雜度分析：
空間復(fù)雜度為O（n）
當(dāng)要進(jìn)行譯碼的是報(bào)文時(shí)，時(shí)間復(fù)雜度為O(len*n),其中l(wèi)en為報(bào)文的長(zhǎng)度；當(dāng)要進(jìn)行譯碼的是字符串時(shí)，時(shí)間復(fù)雜度為O(n)。
七、編寫代碼及運(yùn)行時(shí)遇到的問(wèn)題及解決方法
1、編寫代碼期間遇到的問(wèn)題及其解決辦法
問(wèn)題（一）：定義Data數(shù)組中的權(quán)值域時(shí)定義類型先為字符數(shù)組char[50]，因此導(dǎo)致空間復(fù)雜度高了一些以及字符數(shù)組在輸入的時(shí)候很容易受到回車鍵/空格的影響。
解決方法：先是將50改成了10，最后為了更加適用，改成了int類型。
問(wèn)題（二）：在寫入文件的時(shí)候，運(yùn)用fwrite/fprintf這兩個(gè)函數(shù)的時(shí)候，不明確兩者的區(qū)別，所以隨意選擇而導(dǎo)致在人工檢查生成文件內(nèi)的數(shù)據(jù)的時(shí)候有些文件內(nèi)容為亂碼，因而無(wú)法判斷。
解決方法：弄清楚fprintf是將格式化的數(shù)據(jù)寫入文件，文件中的數(shù)據(jù)計(jì)算機(jī)與人都可讀；fwrite是以二進(jìn)制內(nèi)容寫入文件，除非數(shù)據(jù)能夠表示為字符，不然計(jì)算機(jī)可讀，人工不可讀。為了方便檢驗(yàn)，統(tǒng)一使用fprintf函數(shù)寫入文件。
問(wèn)題（三）：在運(yùn)用scanf輸入字符及其權(quán)值或者字符串與報(bào)文時(shí)，在定義格式類型時(shí)不夠統(tǒng)一，使得用戶在輸入的時(shí)候很容易出錯(cuò)。
解決方法：輸入字符與權(quán)值時(shí)統(tǒng)一“%c%d”的形式，而輸入字符串與報(bào)文則利用gets函數(shù)讀取。
問(wèn)題（四）：輸出字符及其對(duì)應(yīng)權(quán)值或編碼時(shí)如何進(jìn)行輸出，存入文件后再讀取文件存入數(shù)組再輸出的話不僅顯得很復(fù)雜。
解決方法：字符及其權(quán)值存放于Data數(shù)組，因而直接輸出數(shù)組數(shù)據(jù)就可以，而輸出字符及其編碼時(shí)則輸出哈夫曼樹HT中結(jié)點(diǎn)的字符及對(duì)應(yīng)HC中的編碼。但同時(shí)可能需要人工檢查寫入文件中的數(shù)據(jù)是否正確。
問(wèn)題（五）：將哈夫曼樹存入hfmTree文件如何操作。
解決方法：調(diào)用fprintf函數(shù)，用for循環(huán)依次存入。
2、運(yùn)行與測(cè)試期間遇到的問(wèn)題及其解決辦法
問(wèn)題（一）：利用fwrite函數(shù)將數(shù)據(jù)寫入文件時(shí)打開文件檢查出現(xiàn)亂碼以及不匹配的情況。
解決方法：均利用fprintf函數(shù)將數(shù)據(jù)寫入，以進(jìn)行人工核對(duì)數(shù)據(jù)，注意輸入數(shù)據(jù)的格式，避免多加空格使得數(shù)據(jù)不對(duì)。
問(wèn)題（二）：在輸入較多字符及其權(quán)值時(shí)手動(dòng)輸入很容易出錯(cuò)而導(dǎo)致結(jié)果出錯(cuò)以及無(wú)法將空格字符存入。
解決方法：提前建立一個(gè)數(shù)據(jù)文件，將要進(jìn)行輸入的較多字符提前存儲(chǔ)到其中，在用到時(shí)從數(shù)據(jù)文件中復(fù)制并存入Data文件中以減少出錯(cuò)的可能并且提高效率。
問(wèn)題（三）：由于需要用戶多次輸入自己的選擇，而每一個(gè)選擇對(duì)應(yīng)的下一步如果要輸入數(shù)據(jù)一般都為字符型，因而很容易將回車吃進(jìn)入導(dǎo)致數(shù)據(jù)存儲(chǔ)失敗從而導(dǎo)致哈夫曼樹建立失敗。
解決方法：對(duì)每一個(gè)scanf后面的操作進(jìn)行考慮，如果接下來(lái)涉及到字符型數(shù)據(jù)輸入則加一個(gè)getchar讀取回車鍵，以防止其影響數(shù)據(jù)輸入。
問(wèn)題（四）：由于手動(dòng)輸入空格字符作為結(jié)點(diǎn)時(shí)輸入失敗但未察覺(jué)而導(dǎo)致輸入“THE PROGRAM IS MY FAVORITE”時(shí)輸出結(jié)果為分段的字符串，與實(shí)際要求輸出結(jié)果不同。
解決方法：?jiǎn)栴}出現(xiàn)在輸入字符及其權(quán)值時(shí)，未按照規(guī)定的形式輸入數(shù)據(jù)，即未選擇合適記憶并且普遍使用的輸入格式，規(guī)定好輸入字符及其權(quán)值以%c%d的形式輸入。
問(wèn)題（五）：在對(duì)輸入的報(bào)文進(jìn)行編碼時(shí)，查找存儲(chǔ)編碼的指針數(shù)組HC時(shí)，無(wú)法轉(zhuǎn)化成對(duì)應(yīng)的編碼字符串。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-783628.html
解決方法：慣性思維認(rèn)為i,j都是從0開始，但是在HC數(shù)組中0號(hào)單元不存儲(chǔ)編碼，將j的初始值改成1即可。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-783628.html
到了這里，關(guān)于哈夫曼編/譯碼器的設(shè)計(jì)與實(shí)現(xiàn)（結(jié)合文件）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
