Untitled
unknown
plain_text
a year ago
3.4 kB
5
Indexable
/* 分兩部分 1.每一個符號frequency (確認用) 2.huffman code (複製用) */ #include <iostream> #include <vector> #include <string> #include <cstring> #include<fstream> using namespace std; struct ch_n{ char chh; int ff=0; string code=""; }; typedef struct ch_n chn; struct Tree { int freq; // 出現頻率,即權重 char ch; struct Tree *left=nullptr; struct Tree *right=nullptr; }; typedef struct Tree tree; typedef struct Tree* ptree; vector<chn> storelist(128); vector<ptree> prior; int prior_n=0; void printin(ptree pt, string st) { if (pt==nullptr) return; //空節點 if (pt->left) st+='0'; // 訪問left,添加 "0" printin(pt->left, st); // last 節點 if (!(pt->left && pt->right)){ storelist[static_cast<int>(pt->ch)].code=st; } st.pop_back(); // 退一個字元 if (pt->right) st+='1'; // 訪問rifht,添加 "1" printin(pt->right, st); } void input(){ char ch; ifstream infile("HUFFMANtree.txt",ios::in); while(infile.get(ch)){ storelist[static_cast<int>(ch)].chh=ch; storelist[static_cast<int>(ch)].ff++; } //確認frequency cout<<endl<<"-----確認每一個char都有對應frequency-----"<<endl; for(int i=0;i<128;i++){ cout<<i<<"\t"; if(storelist[i].chh==' ') cout<<"space"; else if(storelist[i].chh=='\n') cout<<"line"; else cout<<storelist[i].chh; cout<<"\t"<<storelist[i].ff<<endl; } // for(int i=0;i<127;i++){ if(storelist[i].ff!=0){ ptree pt = new tree; pt->ch = storelist[i].chh; pt->freq = storelist[i].ff; prior.push_back(pt); prior_n++; } } } void output(){ chn cc; cout<<endl<<"-----HUFFMAN CODE-----"<<endl<<endl; for(int next=0;next<128;next++){ cc=storelist[next]; if(cc.ff!=0){ cout<<"code["<<next<<"]= 12'b "; if(cc.code.length()!=12) cout<<"x"; cout<<cc.code<<";"<<endl; } } } void lookmin(){ for(int i=0;i<prior_n-1;i++){ for(int j=0;j<prior_n-i-1;j++){ if(prior[j]->freq > prior[j+1]->freq){ ptree st; st=prior[j]; prior[j]=prior[j+1]; prior[j+1]=st; } } } } void examine2(){ char ch; string s=""; ifstream infile("HUFFMANtree.txt",ios::in); while(infile.get(ch)){ s+=storelist[static_cast<int>(ch)].code; } cout<<s.length(); } void struct_huffmantree(){ while (prior_n > 1){ lookmin(); ptree pt = new tree; ptree pleft, pright; pleft = prior[0]; prior.erase(prior.begin()); pright = prior[0]; prior.erase(prior.begin()); pt->left = pleft; pt->right = pright; pt->freq = pleft->freq + pright->freq; prior_n--; prior.push_back(pt); } } // 霍夫曼編碼 void huffman(){ string initial("");//initialize input(); struct_huffmantree(); printin(prior[0], initial); output(); examine2(); } int main(){ huffman(); return 0; }
Editor is loading...
Leave a Comment