Hi
I am trying to generated a Huff man code.
i am trying to arrange a vector<info> (info is a structure) to get a binary tree.
0. Read a txt file containing about 10 to 20 different symbols.and store it in a vector (vector <info>);
1. First sort the vector according to occur (occur is an interger value in info).
2. Pick up the last two elements of vector <info> and attach it to a new info type structure.
3. Remove last two elements form the vector mentioned above.
4. append the new formed info type structure at the end and repeat the same.
I doubt my append function (given in the code below).
And the Code_fun function(given below) gives a segmentation fault.
Pleas help
My code is given Below.
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct info {
char ch;
int occur;
info *Right;
info *Left;
info *Head;
};
struct Code{
char Ch;
string Co;
};
vector<Code> Store_code;
vector<Code> ::iterator it1;
Code nw_code;
vector<info> Read_txt()
{
ifstream infi;
ofstream onfi;
char c;
vector<info> letter;
info n_letter;
vector<info>::iterator it;
infi.open("hi1.txt");
while(!infi.eof()){
infi>>c;
it = letter.begin();
while(it != letter.end()) {
if ((*it).ch==c){
(*it).occur ++;
break;
}
else
it++;
}
if (it==letter.end()){
n_letter.ch = c;
n_letter.occur = 1;
letter.push_back(n_letter);
}
}
infi.close();
// for(it=letter.begin(); it!=letter.end(); it++)
// cout<<(*it).ch<<"\t"<<(*it).occur<<endl;
return letter;
}
void Sort(vector<info> &letter)
{
vector<info>::iterator it1, it2, it3;
for(it1=letter.begin(); it1!=letter.end()-1; it1++)
for(it2=it1; it2!=letter.end(); it2++) {
if((*it2).occur > (*it1).occur){
swap((*it1).occur,(*it2).occur);
swap((*it1).ch, (*it2).ch);
}
}
}
void Append(vector<info> &letter)
{
info *nw_node;
int x,y;
while(letter.begin() != letter.end()-1){
Sort(letter);
nw_node = new info;
x=letter.back().occur;
// letter.back().Head = nw_node;
nw_node->Left = &letter.back();
letter.pop_back();
y=letter.back().occur;
// letter.back().Head = nw_node;
nw_node->Right = &letter.back();
letter.pop_back();
nw_node->occur = x+y;
nw_node->ch = 'x';
letter.push_back(*nw_node);
cout<<letter.back().Left->ch<<"\t"<<letter.back().Left->occur<<endl;
cout<<letter.back().Right->ch<<"\t"<<letter.back().Right->occur<<endl;
}
}
/*
void Code_fun(info &letter)
{
string str;
cout<<endl<<letter.Left->ch<<endl;
if(letter.ch == 'x') {
cout<<endl<<letter.Left->ch<<endl;
letter=*letter.Left;
cout<<endl<<letter.Left->ch<<endl;
cout<<endl<<letter.Right->ch<<endl;
}
str.push_back('1');
Code_fun(*letter.Left);
nw_code.Ch = letter.Left->ch;
nw_code.Co = str;
Store_code.push_back(nw_code);
str.erase(str.end());
str.push_back('0');
exit(0);
Code_fun(*letter.Right);
nw_code.Ch = letter.Right->ch;
cout<<letter.Right->ch<<"\t";
nw_code.Co = str;
cout<<"str"<<endl;
Store_code.push_back(nw_code);
str.erase(str.end());
}
}
*/
int main()
{
vector<info> tter;
info tter1;
vector<info>::iterator it;
// vector<Code>::iterator it1;
tter = Read_txt();
Sort(tter);
for(it=tter.begin(); it!=tter.end(); it++)
cout<<(*it).ch<<"\t"<<(*it).occur<<endl;
// init(tter.back());
Append(tter);
for(it=tter.begin(); it!=tter.end(); it++)
cout<<(*it).ch<<"\t"<<(*it).occur<<endl;
tter1 = tter[0];
// Code_fun(tter1);
for(it1=Store_code.begin(); it1!=Store_code.end(); it1++)
cout<<(*it1).Ch<<"\t"<<(*it1).Co<<endl;
return 0;
}