南郵データ構造実験2(2)ハフマン符号化とコンパイルシステム
ハフマン符号化とコンパイルシステム
1.設計されたシステムは、次のメニュー項目を繰り返し表示します.
B:ツリーを作る:文字セットと各文字の頻度を読み込んで、ハフマンツリーを作る.
T-遍歴:先序と中序は二叉木を遍歴する.
E-生成符号化:作成されたハフマンツリーに基づいて、各文字のハフマン符号化を生成する.
C-符号化:文字セット文字からなる任意の文字列を入力、生成したハフマン符号化により符号化し、符号化結果を表示し、入力文字列とその符号化結果をそれぞれディスクファイルtextfileに保存する.txtとcodefile.txtで.
D-デコード:codefileを読み込む.txtは、作成するハフマンツリーを用いて復号し、復号結果をディスクファイルresultに格納する.txt.
P-印刷:ファイルtextfileが画面に表示する.txt,codefile.txt,result.txt.
X-脱退.
このプログラムはVC++6.0上でコンパイルして実行して間違いがありません
1.設計されたシステムは、次のメニュー項目を繰り返し表示します.
B:ツリーを作る:文字セットと各文字の頻度を読み込んで、ハフマンツリーを作る.
T-遍歴:先序と中序は二叉木を遍歴する.
E-生成符号化:作成されたハフマンツリーに基づいて、各文字のハフマン符号化を生成する.
C-符号化:文字セット文字からなる任意の文字列を入力、生成したハフマン符号化により符号化し、符号化結果を表示し、入力文字列とその符号化結果をそれぞれディスクファイルtextfileに保存する.txtとcodefile.txtで.
D-デコード:codefileを読み込む.txtは、作成するハフマンツリーを用いて復号し、復号結果をディスクファイルresultに格納する.txt.
P-印刷:ファイルtextfileが画面に表示する.txt,codefile.txt,result.txt.
X-脱退.
このプログラムはVC++6.0上でコンパイルして実行して間違いがありません
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
using namespace std;
template<class T>
class PrioQueue //
{
public:
PrioQueue(int mSize = 20);
~PrioQueue(){ delete []q; }
bool IsEmpty() const{ return n == 0; }
bool IsFull() const{ return n == maxSize; }
void Append(const T&x);
void Serve(T&x);
private:
void AdjustDown(int r, int j);
void AdjustUp(int j);
T *q;
int n, maxSize;
};
template<class T>
PrioQueue<T>::PrioQueue(int mSize)
{
maxSize = mSize;
n = 0;
q = new T[maxSize];
}
template<class T>
void PrioQueue<T>::AdjustUp(int j)
{
int i = j;
T temp = q[i];
while (i > 0 && temp < q[(i - 1) / 2])
{
q[i] = q[(i - 1) / 2];
i = (i - 1) / 2;
}
q[i] = temp;
}
template<class T>
void PrioQueue<T>::Append(const T&x) //
{
if(IsFull())
{
cout << "Overflow" << endl;
return;
}
q[n++] = x;
AdjustUp(n-1);
}
template<class T>
void PrioQueue<T>::Serve(T&x) //
{
if(IsEmpty())
{
cout << "Underflow" << endl;
return;
}
x = q[0];
q[0] = q[--n];
AdjustDown(0, n-1);
}
template<class T>
void PrioQueue<T>::AdjustDown(int r,int j) //
{
int child = 2 * r + 1;
T temp = q[r];
while(child <= j)
{
if((child < j) && (q[child] > q[child+1]))
child++;
if(temp <= q[child])
break;
q[(child - 1) / 2] = q[child];
child = 2 * child + 1;
}
q[(child - 1) / 2] = temp;
}
template<class T>
struct BTNode //
{
BTNode(){lChild = rChild = NULL;}
BTNode(const T&x, const char &y)
{
element = x;
ch = y;
lChild = rChild = parent = NULL;
memset(z, -1, sizeof(z));
}
BTNode(const T&x, const char &y, BTNode<T>*l, BTNode<T>*r)
{
element = x;
ch = y;
lChild = l;
rChild = r;
parent = NULL;
memset(z, -1, sizeof(z));
}
T element;
BTNode<T> *lChild, *rChild, *parent;
char ch;
int val;
int z[100];
};
template<class T> //
class BinaryTree
{
public:
BinaryTree(){root = NULL; i = -1;}
~BinaryTree(){}
void MakeTree(const T&x, const char &y, BinaryTree<T>&left, BinaryTree<T>& right);
void PreOrder(void (*Visit)(T&x));
void InOrder(void (*Visit)(T&x));
void Create_code();
void Create_code_out();
void Code();
void Compile();
void Print();
BTNode<T>*root;
private:
int i;
void PreOrder(void (*Visit)(T&x), BTNode<T>*t);
void InOrder(void (*Visit)(T&x), BTNode<T>*t);
void Create_code(BTNode<T>*t);
void Create_code_out(BTNode<T>*t);
void Code(BTNode<T>*t);
void Make(BTNode<T>*t,char a);
void Compile(BTNode<T>*t);
};
template<class T>
void BinaryTree<T>::MakeTree(const T&x, const char &y, BinaryTree<T>&left, BinaryTree<T>& right) //
{
if(root || &left == &right)
return;
root = new BTNode<T>(x, y, left.root, right.root);
if(left.root != right.root)
{
left.root -> parent = root;
right.root -> parent = root;
left.root -> val = 0;
right.root -> val = 1;
}
left.root = right.root = NULL;
}
template<class T> //Visit
void Visit(T&x)
{
cout << x << " ";
}
template<class T>
void BinaryTree<T>::PreOrder(void (*Visit)(T&x)) //
{
cout << " : ";
PreOrder(Visit, root);
cout << endl;
}
template<class T>
void BinaryTree<T>::PreOrder(void (*Visit)(T&x), BTNode<T>*t)
{
if(t)
{
Visit(t -> element);
PreOrder(Visit, t -> lChild);
PreOrder(Visit, t -> rChild);
}
}
template<class T>
void BinaryTree<T>::InOrder(void (*Visit)(T&x)) //
{
cout << " : ";
InOrder(Visit, root);
cout << endl;
}
template<class T>
void BinaryTree<T>::InOrder(void (*Visit)(T&x), BTNode<T>*t)
{
if(t)
{
InOrder(Visit, t -> lChild);
Visit(t -> element);
InOrder(Visit, t -> rChild);
}
}
template<class T>
class HfmTree : public BinaryTree<T> //
{
public:
operator T() const{ return weight; }
T getW(){ return weight; }
void putW(const T&x){ weight = x; }
void SetNull(){ root = NULL; }
private:
T weight;
};
template<class T>
HfmTree<T> CreateHfmTree(T w[],char q[],int n) //
{
PrioQueue<HfmTree<T> > pq(n);
HfmTree<T> x, y, z, zero;
for(int i = 0; i < n; i++)
{
z.MakeTree(w[i], q[i], x ,y);
z.putW(w[i]);
pq.Append(z);
z.SetNull();
}
for(i = 1; i < n; i++)
{
pq.Serve(x);
pq.Serve(y);
z.MakeTree(x.getW() + y.getW(), 'e', x, y);
z.putW(x.getW() + y.getW());
pq.Append(z);
z.SetNull();
}
pq.Serve(z);
return z;
}
void menu()
{
cout<<"-------------- ------------------"<<endl;
cout<<"************** : *****************"<<endl;
cout<<"***************** B-- ************************"<<endl;
cout<<"***************** T-- ************************"<<endl;
cout<<"***************** E-- ************************"<<endl;
cout<<"***************** C-- ************************"<<endl;
cout<<"***************** D-- ************************"<<endl;
cout<<"***************** P-- ************************"<<endl;
cout<<"***************** X-- ************************"<<endl<<endl;
cout<<"--------------------- ----------------------------"<<endl;
}
HfmTree<int> Ht;
int num;
void Make_Ht()
{
char str[100];
int weight[100];
cout << " :";
cin >> num; //
cout << " :";
for(int i = 0; i < num; i++)
cin >> weight[i];
cout << " :";
cin >> str;
Ht = CreateHfmTree(weight, str, num);
}
void Traversal_Ht()
{
Ht.PreOrder(Visit);
Ht.InOrder(Visit);
}
template<class T>
void BinaryTree<T>::Create_code()
{
Create_code(root);
}
template<class T>
void BinaryTree<T>::Create_code(BTNode<T>*t)
{
if(t)
{
if(t -> parent)
{
for(int j = 0; j <= i; j++)
t -> z[j] = t -> parent -> z[j]; //
i++;
t -> z[i] = t-> val; //
}
Create_code(t -> lChild); // ， ，
Create_code(t -> rChild);
i--;
}
}
template<class T>
void BinaryTree<T>::Create_code_out() //
{
Create_code_out(root);
}
template<class T>
void BinaryTree<T>::Create_code_out(BTNode<T>*t)
{
if(t)
{
if(t -> lChild == t -> rChild) //
{
cout << t -> ch << ":"; //
int i = 0;
while(t -> z[i] != -1)
{
cout << t -> z[i]; //
i++;
}
cout << endl;
}
Create_code_out(t->lChild);
Create_code_out(t->rChild);
}
}
template<class T>
void BinaryTree<T>::Code()
{
Code(root);
}
template<class T>
void BinaryTree<T>::Code(BTNode<T>*t) //
{
ofstream outf("textfile.txt");
if(!outf)
{
cout << "Cannot open the file
";
return;
}
ofstream outs("codefile.txt",ios::trunc);
if(!outs)
{
cout << "Cannot open the file
";
return;
}
outs.close();
char str2[100];
cout << " : ";
cin >> str2;
outf << str2;
outf.close();
int l = strlen(str2);
cout << " :" << endl;
for(int i = 0; i < l; i++)
Make(root, str2[i]);
cout << endl;
}
template<class T>
void BinaryTree<T>::Make(BTNode<T> *t,char a)
{
int i = 0;
if(t)
{
if(t -> ch == a) //
{
ofstream outs("codefile.txt",ios::app);
while(t -> z[i] != -1)
{
cout << t -> z[i]; //
outs << t -> z[i]; //
i++;
}
outs.close();
return;
}
Make(t -> lChild, a);
Make(t -> rChild, a);
}
}
template<class T>
void BinaryTree<T>::Compile() //
{
Compile(root);
}
template<class T>
void BinaryTree<T>::Compile(BTNode<T> *t)
{
ifstream inf("codefile.txt");
if(!inf)
{
cout << "Cannot open the file
";
return;
}
ofstream outs("result.txt",ios::trunc);
if(!outs)
{
cout << "Cannot open the file
";
return;
}
outs.close();
char *re;
char tmp;
int n = 0;
while(inf.get(tmp) != '\0')
{
n++; //
}
inf.close();
re = new char[n+1];
int n2 = 0;
ifstream in("codefile.txt");
if(!in)
{
cout<<"Cannot open the file
";
return;
}
while(in.get(tmp) != '\0')
{
re[n2] = tmp; //
n2++;
}
BTNode<T> *c;
cout << " :";
int n3 = 0;
while(n3 < n)
{
while(t)
{
c = t;
if(re[n3] == '0') // 0 1 0 1
t = t -> lChild;
else
t = t -> rChild;
n3++;
}
ofstream outs("result.txt",ios::app);
if(!outs)
{
cout << "Cannot open the file
";
return;
}
cout << c -> ch; //
outs << c -> ch; //
outs.close();
t = root;
n3--;
}
cout << endl;
}
void Print()
{
char str;
ifstream a("textfile.txt");
ifstream b("codefile.txt");
ifstream c("result.txt");
if(!a)
{
cout << "Cannot open the file
";
return;
}
if(!b)
{
cout << "Cannot open the file
";
return;
}
if(!c)
{
cout << "Cannot open the file
";
return;
}
cout << "textfile.txt :";
while(a.get(str) != '\0')
cout << str;
cout << endl;
cout << "codefile.txt :";
while(b.get(str) != '\0')
cout << str;
cout << endl;
cout << "result.txt :";
while(c.get(str) != '\0')
cout << str;
cout << endl;
a.close();
b.close();
c.close();
}
int main()
{
char choose;
menu();
cin >> choose;
while(choose != 'X')
{
switch(choose)
{
case 'B':
Make_Ht();
Ht.Create_code();
break;
case 'T':
Traversal_Ht();
break;
case 'E':
cout << " :" << endl;
Ht.Create_code_out();
break;
case 'C':
Ht.Code();
break;
case 'D':
Ht.Compile();
break;
case 'P':
Print();
break;
case 'X':
break;
default:
cout << " ， ！"<<endl;
break;
}
system("PAUSE");
system("CLS");
menu();
cin >> choose;
}
return 0;
}