Huffman 인 코딩 (데이터 구조)
#include <iostream.h>
#include <fstream.h>
#include <string.h>
class Data {
public:
char ch;
Data(){
ch = NULL;
}
};
typedef class Huffman {
public:
Data data;
int weight;
int parent, lchild, rchild;
Huffman(){
weight = parent = lchild = rchild = NULL;
}
} * HuffmanTree;
typedef char ** HuffmanCode;
//
void Select(int *tw, int n, int &s1, int &s2)
{
// temp_w, weight
int temp_w, i = 1;
while(!tw[i])
{
i++;
}
temp_w = tw[i];
s1 = i;
// s1
for(; i<=n; i++)
{
if(temp_w > tw[i])
{
if(tw[i] != NULL)
{
temp_w = tw[i];
s1 = i;
}// ifin
}// if
}//for
i = 1;
while(!tw[i] || i == s1)
{
i++;
}
temp_w = tw[i];
s2 = i;
for(; i<=n; i++)
{
if(i == s1)
goto loop;
if(temp_w > tw[i])
{
if(tw[i])
{
temp_w = tw[i];
s2 = i;
}// ifin
loop:;
}// if
}// for
// s1
if(tw[s1]>tw[s2])
{
temp_w = s1;
s1 = s2;
s2 = temp_w;
}// if
// , temp_array_w ,
tw[s1] = tw[s2] = NULL;
tw[0] = tw[0]-2;
}
void Initialization (HuffmanTree &HT, HuffmanCode &HC, int n)
{
// , HT[0]
HT[0].weight = n;
HT[0].data.ch = 3;
int i;
//
int *temp_array_w = new int[2*n];
// 0
for(i = 1; i<=2*n -1; i++)
temp_array_w[i] = 0;
for(i = 1; i<=n; i++)
{
cout << " : ";
cin >> HT[i].data.ch;
if(HT[i].data.ch == '/32')
HT[i].data.ch = '|';
cout << " : ";
cin >> HT[i].weight;
//
temp_array_w[i] = HT[i].weight;
// 0
temp_array_w[0] = i;
}// for
// s1 s2
int s1, s2;
s1 = s2 = NULL;
// huffman
for(i = n + 1; i<=2*n - 1; i++)
{
Select(temp_array_w, i-1, s1, s2);
cout << s1 << "//" << s2 << endl;
HT[i].weight = temp_array_w[i] = HT[s1].weight + HT[s2].weight;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[s1].parent = HT[s2].parent = i;
HT[i].data.ch = '#';
}// for
cout << "/tData/tweight/tparent/tlchild/trchild" << endl;
for(i = 1; i<=2*n - 1; i++)
cout << "/t" << HT[i].data.ch << "/t" << HT[i].weight << "/t" << HT[i].parent << "/t" << HT[i].lchild << "/t" << HT[i].rchild << endl;
// humTree
ofstream HumTreeOut("humTree.dll");
//
HumTreeOut << HT[0].weight << endl;
for(i = 1; i<=2*n -1; i++)
{
HumTreeOut << HT[i].data.ch << "/n" << HT[i].weight << "/n" << HT[i].parent << "/n" << HT[i].lchild << "/n" << HT[i].rchild << endl;
}
HumTreeOut.close();
}// void
// , CodeFile
void Encoding (HuffmanCode &HC, HuffmanTree &HT, int n, ifstream &tobetranfile)
{
char *cd = new char[n];
cd[n-1] = '/0';
int i = 1;
for(; i<=n; i++)
{
int start = n -1;
int c, f;
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]);
}
delete cd;
char temp_file_ch;
ofstream CodeOut("CodeFile.txt", ios::ate); // ios::ate open ,
while(!tobetranfile.eof()) // ,eof()
{
tobetranfile.get(temp_file_ch);
for(i = 1; i<=n; i++)
{
if(temp_file_ch == HT[i].data.ch) // ,
CodeOut << HC[i];
}
}
CodeOut.close();
}
void Decoding (HuffmanTree &HT, ifstream &CodeFile, int n)
{
ofstream TextOut("TextFile.txt", ios::ate);
char temp_code_ch;
int temp_num = 2*n - 1;
while(!CodeFile.eof())
{
CodeFile.get(temp_code_ch);
if(temp_code_ch == '1')
if(!HT[temp_num].rchild)
{
TextOut << HT[temp_num].data.ch;
temp_num = 2*n - 1;
}
else
{
temp_num = HT[temp_num].rchild;
if(!HT[temp_num].rchild) //
{
TextOut << HT[temp_num].data.ch;
temp_num = 2*n - 1;
}
}
else
if(!HT[temp_num].lchild)
{
TextOut << HT[temp_num].data.ch;
temp_num = 2*n - 1;
}
else
{
temp_num = HT[temp_num].lchild;
if(!HT[temp_num].lchild) //
{
TextOut << HT[temp_num].data.ch;
temp_num = 2*n - 1;
}
}
}
TextOut.close();
cout << " Text.txt " << endl;
}
// humtree.dll
bool CreatNewHum(HuffmanTree &HT, int &n)
{
char *ch_name = new char[30];
//
int temp_n;
char temp_ch;
int i = 1;
cout << "Please Inputing the File name :";
cin >> ch_name;
ifstream HuffmanTreeIn(ch_name);
if(HuffmanTreeIn.fail())
{
HuffmanTreeIn.close();
cout << " " << endl;
return false;
}
// HuffmanTree HT_TEMP = HT;
// HuffmanTreeIn.getline(temp_line, 9);
HuffmanTreeIn >> temp_n; //
HuffmanTreeIn.get(temp_ch);
// HuffmanTreeIn.seekg(1);
HT = new Huffman[2*temp_n];
// delete HT_TEMP;
// HT
/*
for(;i<20;i++)
{
HuffmanTreeIn.get(temp_ch);
cout << temp_ch;
}
//*/
//*
int j = 1;
while(!HuffmanTreeIn.eof())
{
if(i%5 == 1)
{
HuffmanTreeIn >> HT[j].data.ch;
HuffmanTreeIn.get(temp_ch); //
i++;
}
if(i%5 == 2)
{
HuffmanTreeIn >> HT[j].weight;
HuffmanTreeIn.get(temp_ch);
i++;
}
if(i%5 == 3)
{
HuffmanTreeIn >> HT[j].parent;
HuffmanTreeIn.get(temp_ch);
i++;
}
if(i%5 == 4)
{
HuffmanTreeIn >> HT[j].lchild;
HuffmanTreeIn.get(temp_ch);
i++;
}
if(i%5 == 0)
{
HuffmanTreeIn >> HT[j].rchild;
HuffmanTreeIn.get(temp_ch);
i++;
}
// i 5 j++
if(i%5 == 1)
j++;
//
if(i > (2*temp_n -1)*5)
break;
}// while
//*/
//
HuffmanTreeIn.close();
n = temp_n;
return true;
}
void PrintCode ()
{
char *name_ch = new char[51];
ifstream FileIn("CodeFile.txt");
ofstream FileOut("CodePrin.txt", ios::ate);
if(FileIn.fail())
cout << " !" << endl;
while(!FileIn.eof())
{
FileIn.getline(name_ch, 51);
cout << name_ch << endl;
FileOut << name_ch << endl;
}
FileIn.close();
FileOut.close();
}
void TreePrint ()
{
}
void TitalPrinT() {
cout << "/t=========================================================" << endl;
cout << endl;
cout << "/t=/t/t/tHUFFMANTREE/t/t/t=" << endl;
cout << endl;
cout << "/t=/t/tI:INITIAL A HUFFMAN TREE/t/t=" << endl;
cout << endl;
cout << "/t=/t/tE:ENCODEING THE DATA/t/t/t=" << endl;
cout << endl;
cout << "/t=/t/tD:DECODEING THE DATA/t/t/t=" << endl;
cout << endl;
cout << "/t=/t/tQ:QUIT/t/t/t/t/t=" << endl;
cout << endl;
cout << "/t=========================================================" << endl;
}
// , main
void ComputeHuffman ()
{
//
char temp_input = NULL;
TitalPrinT();
//
int n = 0;
// Q
while(temp_input != 'Q')
{
//
char temp_choise = 0;
HuffmanTree HT;
HuffmanCode HC;
// switch/case
cout << "CHOOSE WHICH DO YOU SELECT..." << endl;
cin >> temp_input;
switch(temp_input)
{
case 'I':
cout << "How many numbers need to be initialized: ";
cin >> n;
//
HT = new Huffman[2*n];
Initialization (HT, HC, n);
break;
case 'E':
{
//*
cout << "Inputing the HumffmanTree from the (F)ile or (M)emory : ";
cin >> temp_choise;
switch(temp_choise)
{
case 'F':
if(!CreatNewHum(HT, n))
continue;
break;
case 'M':
//
break;
default:
cout << "Please Pess F or M..." << endl;
continue;
}// switch
//*/
cout << "Translating in (F)ile or (P)ressing: ";
cin >> temp_choise;
switch(temp_choise)
{
case 'F':
break;
case 'P':
{
cout << " , 80 " << endl;
char *temp_press_word = new char[81];
cin >> temp_press_word;
// ToBeTran.txt
ofstream CodeFileOut("ToBeTran.txt");
CodeFileOut << temp_press_word;
break;
}
}
HC = new char*[n+1];
ifstream ToBeTranFile("ToBeTran.txt");
Encoding(HC, HT, n, ToBeTranFile);
ToBeTranFile.close();
for(int i = 1; i<=n; i++)
cout << HT[i].data.ch << "<-->" << HC[i] << endl;
}
// huffman ( humTree ),
// ToBeTran , CodeFile.txt .
break;
case 'D':
{
//
cout << "Inputing the HumffmanTree from the (F)ile or (M)emory : ";
cin >> temp_choise;
switch(temp_choise)
{
case 'F':
{
if(!CreatNewHum(HT, n))
continue;
HC = new char*[n+1];
/*
ifstream ToBeTranFile("ToBeTran.txt");
Encoding(HC, HT, n, ToBeTranFile);
ToBeTranFile.close();
*/
}
break;
case 'M':
//
break;
default:
cout << "Please Pess F or M..." << endl;
continue;
}// switch
ifstream CodeFile("CodeFile.txt");
Decoding(HT, CodeFile, n);
CodeFile.close();
}
// haffman codefile . TextFile.txt
break;
case 'P':
PrintCode();
// ,50 , CodePrin
break;
case 'T':
// huffman , huffman , huffman
// TreePrint
break;
case 'Q':
return;
default:
cout << "Please inputing in /" I E D Q /"..." << endl;
continue;
}// switch
//
TitalPrinT();
}// while
}// ComputerHuffman
void main()
{
ComputeHuffman();
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.