课设要求
(1)初始化 (Initialization):从终端读入n个字符,建立哈夫曼树;
(2)编码 (Coding):利用已建好的哈夫曼树,对字符进行编码,然后将正文编码结果存入文件codefile中;
(3)译码 (Decoding):利用已建好的哈夫曼树将文件codefile中的代码进行译码,结果存入文件textfile中。
上代码
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedef char * * HuffmanCode;
//Select 2 smallest-weight nodes for merging
void Select(HuffmanTree &HT, int n, int& s1){
int maxx = inf;
for(int i = 0; i <= n; i++){
if(HT[i].weight<=maxx && HT[i].parent == 0){
maxx = HT[i].weight;
s1 = i;
}
}
HT[s1].parent = -1;
return;
}
//construct Huffman Tree
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){
if(n<1) return;
int m = 2*n-1;
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
HuffmanTree p = HT; int i;
for(i = 0; i < n; i++, p++, w++){
*p = {*w, 0, 0,0}; //存入初始权重
}
for(;i< m; i++,p++) *p={0, 0, 0, 0}; //初始化
for(i = n; i < m; i++){
//1-i-1中找到最小两个合并
int s1 = -1, s2 = -1;
Select(HT, i-1,s1);
Select(HT, i-1,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;
}
/*for(int k = 0; k < m; k++){
printf("%d : parent: %d\n", k, HT[k].parent);
printf("lcc: %d rcc: %d\n", HT[k].lchild, HT[k].rchild);
}*/
//从叶到根求每个字符编码
char * cd = new char[n];
cd[n-1]='\0'; int start;
for(i=0; i < n; i++){
start = n-1; //最长也就n-1条边
int f, c;
for(c = i, f = HT[i].parent; f!= 0; c = f, f = HT[f].parent){
if(HT[f].lchild == c) cd[--start] = '0';
else cd[--start] = '1';
}
HC[i] = new char[n-start];
strcpy(HC[i], &cd[start]);
//printf("Code; %s", HC[i]);
}
delete cd;
}
void Menu(){
int opt;
printf("*****************************************************\n");
printf("| Huffman编/译码系统 |\n");
printf("|-----------------*系统执行步骤:*------------------|\n");
printf("| 1. 读入文本字符,建HuffmanTree |\n");
printf("| 2. 编码存档 |\n");
printf("| 3. 译码读出 |\n");
printf("*****************************************************\n");
printf("\n请输入字符文本:('*'为结束符)\n");
string ss,s1;ss="";
while(getline(cin, s1) && s1!="*"){ss+=s1;ss+='\n';}
//getline(cin, ss);
int len = ss.size();
int t[len+1];memset(t, 0, sizeof(t));
char w[len+1]; //w存字符,t计权重
int cnt = 0;
for(int i = 0; i<len; i++){
bool flag = false;
for(int j = 0; j < cnt; j++){
if(ss[i]==w[j]){
t[j]++;
flag = true;
break;
}
}
if(!flag){
w[cnt] = ss[i];
t[cnt++] = 1;
}
}
//printf("cnt %d\n",cnt);
printf("字符与权值信息:\n");
for(int i = 0; i < cnt; i++){
printf("%c : %d\n", w[i],t[i]);
}
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(HT, HC, t, cnt);
//cout<<ss<<endl;
printf("\n请输入正文编码的文件地址:\n");
string fn;
cin>>fn;
ofstream out(fn.c_str());
//cout<<ss<<endl;
for(int i = 0; i < len;i++){
for(int j = 0; j < cnt; j++){
if(ss[i]==w[j]){
//cout<<"! "<<ss[i]<<endl;
out<<HC[j]<<endl;
break;
}
}
}
out.close();
printf("\n请输入译码文档的文件地址:\n");
string s2;
cin>>s2;
ofstream out2(s2.c_str());
ifstream in(fn.c_str());
string buff;
if(in.is_open()){
while(in>>buff){
for(int i = 0; i < cnt; i++){
if(!strcmp(buff.c_str(), HC[i])){
out2<<w[i];
break;
}
}
}
}
in.close();
out2.close();
return ;
}
int main(){
Menu();
return 0;
}
/*
..\课程资料\数据结构课程设计\课程设计四\课设4
*/
/*
hi,this is your first huffman-test.
Nobody grows old merely by living a number of years;
people grow old only by deserting their ideals.
*/
运行结果
更多推荐
课程设计四之Huffman编译码器
发布评论