哈夫曼編碼編譯器

1、 一、 課題：哈夫曼編碼編譯器設(shè)計一個哈夫曼編碼/譯碼系統(tǒng)，對一個文本文件中的字符進(jìn)行哈夫曼編碼，生成編碼文件壓縮文件，后綴名.cod；反過來，可將一個壓縮文件譯碼復(fù)原為一個文本文件(.txt)。二、 功能1輸入一個待壓縮的英文文本文件，統(tǒng)計文本文件中各字符的個數(shù)作為權(quán)值，生成哈夫曼樹；2將文本文件利用哈夫曼樹進(jìn)行編碼，生成壓縮文件后綴名cod3輸入一個待解壓的壓縮文件名稱,并利用相應(yīng)的哈夫曼樹將編碼序列譯碼。三、程序結(jié)構(gòu)程序流程圖執(zhí)行程序選擇0退出選擇1編碼選擇2譯碼輸入要編碼文件輸入要譯碼文件名編碼譯碼保存編碼后的文件保存譯碼后的文件文字說明Main函數(shù)：Coding()編碼函數(shù)Trans

2、Code()譯碼函數(shù)Coding()編碼函數(shù)：clearscreen()清屏函數(shù)Open()翻開源碼文件SearchStr()查找字符串中不同的字符及其出現(xiàn)的次數(shù)CreatHFMTree()用每個字符出現(xiàn)的次數(shù)作為葉子節(jié)點的權(quán)值建立哈夫曼樹HFMCode()利用哈夫曼樹對每個葉子節(jié)點進(jìn)行編碼，存入編碼表中TotalCoding()利用編碼表對字符串進(jìn)行最終編碼Save()保存最終的哈夫曼編碼TransCode()譯碼函數(shù)：clearscreen()清屏函數(shù)Open()翻開編碼文件DeCoding(); /將編碼進(jìn)行解碼存入字符串?dāng)?shù)組中Save(); /保存譯碼后的字符串四、 算法說明1. 執(zhí)行

3、界面可供三個選擇（1） 編碼（2） 譯碼（3） 退出執(zhí)行1選擇需要輸入要編譯的文件名需要輸出編碼保存文件名選擇1執(zhí)行完畢執(zhí)行2選項輸入要譯碼的編碼文件名并輸入保存的文件名選擇(2)執(zhí)行完畢執(zhí)行0那么退出該程序五、報告總結(jié)該程序主要采用了哈夫曼編碼譯碼方法，對txt文件進(jìn)行編譯壓縮，同時也能對編碼后的文件進(jìn)行解碼，程序結(jié)構(gòu)清晰，主干分兩大局部：編碼局部與解碼局部，各局部通過調(diào)用函數(shù)合理清晰的實現(xiàn)其功能。程序中運用了一些文件的C語言根本操作，例如翻開文件open、保存文件save函數(shù)，但程序上對文件類型的處理還有一些缺點，不能實現(xiàn)文件類型的自動保存，需要輸入文件名字和類型。通過這次課程設(shè)計，不僅提

4、高了自己的編程能力，還讓我知道自己在編程方面的缺點，我以后會更加努力擴(kuò)大自己的知識面提高自己的編程能力。#include <stdio.h>#include <stdlib.h>#include <string.h>#define M 10000 /定義字符串最大長度#define N 128 /定義葉子節(jié)點個數(shù)typedef struct node /定義哈夫曼樹節(jié)點結(jié)構(gòu)體int weight;struct node *LChild,*RChild,*Parent; /分別指向該節(jié)點的左孩子，右孩子，和雙親節(jié)點struct node *next; /指向建

5、立的哈夫曼樹的下一個節(jié)點HFMNode,*HFMTree;typedef struct /定義哈夫曼編碼的結(jié)構(gòu)體char ch; /存儲對應(yīng)的字符char codeN+1; /存儲對應(yīng)字符的編碼int start; /存儲編碼的起始位置CodeNode;int n; /存儲真正葉子節(jié)點個數(shù)void clearscreen()system("cls");void Open(char s) /翻開存放字符或編碼的文件，將其存入字符串?dāng)?shù)組中char name10;FILE *fp;int i=0;printf("請輸入要翻開的文件名：");gets(name)

6、; /要翻開的文件名if(fp=fopen(name,"rt")=NULL) printf("翻開失?。"); /假設(shè)翻開失敗，那么直接退出exit(1); si+=fgetc(fp);while(si-1!=EOF) si+=fgetc(fp);si='0' /存取字符串結(jié)束fclose(fp);void Save(char s) /保存字符或編碼到文件中char name10;FILE *fp;printf("請輸入要保存的文件名：");gets(name);if(fp=fopen(name,"wt&q

7、uot;)=NULL) printf("存儲失??！");exit(1); fputs(s,fp);printf("n保存成功，文件名為:%s。n",name);printf("n按回車鍵繼續(xù).");getchar();fclose(fp);void SearchStr(char s,char str,int count) /查找字符串中字符的個數(shù)和每個字符出現(xiàn)的次數(shù)int i,j,k=0;for(i=0;i<N;i+) /初始化每個字符出現(xiàn)的次數(shù)counti=0;for(i=0;si;i+) for(j=0;j<k;j+)

8、 /在str中查找是否有該字符if(strj=si) countj+; break; if(j=k) /在str中無該字符，將其存入最后一個單元strk=si; countk+; strk='0' /將字符串結(jié)尾置0n=k; /將實際的字符個數(shù)作為葉子節(jié)點個數(shù)存入nvoid SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)/查找哈夫曼鏈表中兩個權(quán)值最小的節(jié)點int i,min;HFMTree p;min=32767;for(i=0,p=HT;i<k;i+,p=p->next) if(p->weight&

9、lt;min&&p->Parent=0) min=p->weight; *HT1=p; min=32767;for(i=0,p=HT;i<k;i+,p=p->next) if(p->weight<min&&p->Parent=0&&p!=*HT1) /令第二個最小的節(jié)點不等于第一個節(jié)點min=p->weight; *HT2=p; void CreatHFMTree(HFMTree *HT,int count)/創(chuàng)立哈夫曼樹int i;HFMTree p,HT1,HT2; /HT1，HT2分別存放權(quán)值

10、最小和次小的節(jié)點的位置p=*HT=(HFMTree)malloc(sizeof(HFMNode);p->next=p->LChild=p->RChild=p->Parent=NULL; /初始化哈夫曼鏈表且有2n-1個節(jié)點for(i=1;i<2*n-1;i+) p->next=(HFMTree)malloc(sizeof(HFMNode); p=p->next; p->next=p->LChild=p->RChild=p->Parent=NULL; for(i=0,p=*HT;i<n;i+) /將各個字符出現(xiàn)的次數(shù)作為權(quán)值

11、 /存入哈夫曼鏈表的前n個單元中p->weight=counti; p=p->next; for(i=n;i<2*n-1;i+) /將后n-1個節(jié)點賦權(quán)值，建樹SelectMin(*HT,i,&HT1,&HT2); /每次從前i個節(jié)點中選取權(quán)值最小的兩個節(jié)點HT1->Parent=HT2->Parent=p; p->LChild=HT1; p->RChild=HT2; p->weight=HT1->weight+HT2->weight; /將兩個節(jié)點的權(quán)值相加存入最后一個節(jié)點中p=p->next; /p指向下一個

12、沒有存儲權(quán)值的節(jié)點void HFMCode(HFMTree HT,CodeNode HC,char str)/從每個葉子節(jié)點開始，利用哈夫曼樹對每個字符進(jìn)行編碼，最終建立一個哈夫曼表int i;HFMTree q,p=HT;for(i=0;i<n;i+) /將字符存入哈夫曼編碼結(jié)構(gòu)體數(shù)組的字符單元中HCi.ch=stri; HCi.coden-1='0' /初始化編碼的最后一位for(i=0;i<n;i+) HCi.start=n-1; for(q=p;q->Parent;q=q->Parent) /判斷q所指向的節(jié)點，左孩子置0，右孩子置1 if(q=

13、q->Parent->LChild) HCi.code-HCi.start='0' else HCi.code-HCi.start='1' p=p->next; /判斷下一個葉子節(jié)點void TotalCoding(char s,CodeNode HC,char code)/利用哈夫曼編碼表對整個字符串進(jìn)行編碼int i,j;code0='0' /編碼數(shù)組初始化for(i=0;si;i+) /將每個字符在哈夫曼編碼表中對應(yīng)的編碼存入存放總編碼的數(shù)組中for(j=0;j<n;j+) if(si=HCj.ch) strcpy(

14、code+strlen(code),HCj.code+HCj.start);void DeCoding(char code,HFMTree HT,char str,char s)/對哈夫曼編碼進(jìn)行解碼，放入字符串s中int i,j,k=0;HFMTree root,p,q;for(root=HT;root->Parent;root=root->Parent); /用root指向哈夫曼樹的根結(jié)點for(i=0,p=root;codei;i+) /從根結(jié)點開始按編碼順序訪問樹 if(codei='0') p=p->LChild; else p=p->RChi

15、ld; if(p->LChild=NULL&&p->RChild=NULL) /到根節(jié)點時將該節(jié)點對應(yīng)的字符輸出for(j=0,q=HT;q!=p;q=q->next,j+); sk+=strj; p=root; /回溯到根結(jié)點 sk='0' /解碼完畢，在字符串最后一個單元存入'0'void Coding(char s,char str,char code,int count,HFMTree *HT,CodeNode HC)clearscreen();printf("n翻開存放字符串的文件.nn");Ope

16、n(s); /翻開源碼文件SearchStr(s,str,count); /查找字符串中不同的字符及其出現(xiàn)的次數(shù)CreatHFMTree(HT,count); /用每個字符出現(xiàn)的次數(shù)作為葉子節(jié)點的權(quán)值建立哈夫曼樹HFMCode(*HT,HC,str); /利用哈夫曼樹對每個葉子節(jié)點進(jìn)行編碼，存入編碼表中TotalCoding(s,HC,code); /利用編碼表對字符串進(jìn)行最終編碼printf("n讀入的字符串為:n");puts(s);printf("n最終的哈夫曼編碼是:n");puts(code);printf("n保存編碼,"

17、);Save(code); /保存最終的哈夫曼編碼void TransCode(char code,char str,char ss,HFMTree *HT,CodeNode HC)clearscreen();printf("n翻開編碼的文件.nn");Open(code); /翻開編碼文件DeCoding(code,*HT,str,ss); /將編碼進(jìn)行解碼存入字符串?dāng)?shù)組ss中printf("n得到的最終字符串為:n");puts(ss);printf("n保存譯碼，");Save(ss); /保存譯碼后的字符串int main()

18、/主函數(shù)char sM,ssM; /定義字符串?dāng)?shù)組，s存放將要編碼的字符串，ss存解碼后的字符串char strN; /存放輸入的字符串中n個不同的字符int countN; /存放n個不同字符對應(yīng)的在原字符串中出現(xiàn)的次數(shù)char codeM; /存放最終編碼完成后的編碼char choice;HFMTree HT; /定義一個哈夫曼樹的鏈表CodeNode HCN; /定義一個哈夫曼編碼表的數(shù)組，存放每個字符對應(yīng)的哈夫曼編碼do clearscreen(); printf("nn"); printf(" *哈夫曼樹*n"); printf(" * *n"); printf(" * 1.編碼。 *n"); printf(" * 2.譯碼。 *n"); printf(" * 0.退出。 *n"); printf(" * *n"); printf(" * *n"); printf(" * *n"); printf(" * 請輸入相應(yīng)操作的序號(0-2) *n"); printf(" *n")