c++哈夫曼编码与译码.doc

#include #include /系统自带的字符串库函数using namespace std;struct node char data; / 节点数据域为字符型 node *next; node() next = null; node(char item, node *link = null) data = item; next = link; ;class linklist/仅保留几个用得到的成员函数protected: node *head; node *curptr; int count,curposition; node *getelemptr(int position); / 返回指向第position个结点的指针 public: linklist(); int length() const; bool empty() const; void traverse() ; void insert(int position, const char &e); char getelem(int position) ;node * linklist:getelemptr(int position) if (curposition position) curposition = 0; curptr = head; for (; curposition next; return curptr;char linklist:getelem(int position) node *tmpptr; tmpptr = getelemptr(position); char e = tmpptr-data; return e; linklist:linklist() head = new node; / 构造头指针，带表头结点的链表 curptr = head; curposition =0; count = 0; int linklist:length() const return count;bool linklist:empty() const return head-next = null;void linklist:traverse() for (node *tmpptr = head-next; tmpptr != null; tmpptr = tmpptr-next) coutdata); void linklist:insert(int position, const char &e) node *tmpptr; tmpptr = getelemptr(position - 1); node *newptr; newptr = new node(e, tmpptr-next); tmpptr-next = newptr; curposition = position; curptr = newptr; count+; / 哈夫曼树结点类struct huffmantreenode int weight; unsigned int parent, leftchild, rightchild; / 双亲,左右孩子域 huffmantreenode(); huffmantreenode(int w, int p = 0, int lchild = 0, int rchild = 0); ;huffmantreenode:huffmantreenode() parent = leftchild = rightchild = 0;huffmantreenode:huffmantreenode(int w, int p, int lchild, int rchild) / 右孩子 weight = w; / 权 parent = p; / 双亲 leftchild = lchild; / 左孩子 rightchild = rchild; / 右孩子class huffmantreeprotected:/ huffmantreenode *nodes; / 存储结点信息,nodes0未用 char *leafchars; / 叶结点字符信息,leafchars0未用 string *leafcharcodes; / 叶结点字符编码信息,leafcharcodes0未用 int curpos; / 译码时从根结点到叶结点路径的当前结点 int num; / 叶结点个数/ 辅助函数: void select(int cur, int &r1, int &r2); / nodes1 cur中选择双亲为0,权值最小的两个结点r1,r2 void creathuffmantree(char ch, int w, int n); public: huffmantree(char ch, int w, int n); / 由字符,权值和字符个数构造哈夫曼树 virtual huffmantree(); / 析构函数 string encode(char ch); / 编码 linklist decode(string strcode); / 译码 ;void huffmantree:select(int cur, int &r1, int &r2) r1 = r2 = 0; / 0表示空结点 for (int pos = 1; pos = cur; pos+) if (nodespos.parent != 0) continue; / 只处理双亲为0的结点 if (r1 = 0) r1 = pos; else if (r2 = 0) r2 = pos; else if (nodespos.weight nodesr1.weight) r1 = pos; else if (nodespos.weight nodesr2.weight) r2 = pos; void huffmantree:creathuffmantree(char ch, int w, int n) num = n; / 叶结点个数 int m = 2 * n - 1; / 结点个数 nodes = new huffmantreenodem + 1; / nodes0未用 leafchars = new charn + 1; / leafchars0未用 leafcharcodes = new stringn + 1; / leafcharcodes0未用 int pos; / 临时变量 for (pos = 1; pos = n; pos+) / 存储叶结点信息 nodespos.weight = wpos - 1; / 权值 leafcharspos = chpos - 1; / 字符 for (pos = n + 1; pos = m; pos+) / 建立哈夫曼树 int r1, r2; select(pos - 1, r1, r2); nodesr1.parent = nodesr2.parent = pos; / r1,r2双亲为pos nodespos.leftchild = r1; / r1为pos的左孩子 nodespos.rightchild = r2; / r2为pos的右孩子 nodespos.weight = nodesr1.weight + nodesr2.weight;/pos的权为r1,r2的权值之和 for (pos = 1; pos = n; pos+) / 求n个叶结点字符的编码 linklist charcode; / 暂存叶结点字符编码信息 for (unsigned int child = pos, parent = nodeschild.parent; parent != 0; child = parent, parent = nodeschild.parent) if (nodesparent.leftchild = child) charcode.insert(1,0); else charcode.insert(1,1); for(int i=1;i=charcode.length();i+) leafcharcodespos.append(1, charcode.getelem(i);/没有直接可以从链表为字符串赋值的函数，只能一个字符一个字符的追加过去 curpos = m; huffmantree:huffmantree(char ch,int w, int n) creathuffmantree(ch, w, n); huffmantree:huffmantree() if (nodes != null) delete nodes; / 释放结点信息 if (leafchars != null) delete leafchars; / 释放叶结点字符信息 if (leafcharcodes != null) delete leafcharcodes; / 释放叶结点字符编码信息string huffmantree:encode(char ch) for (int pos = 1; pos = num; pos+) if (leafcharspos = ch) return leafcharcodespos;/ 找到字符,得到编码 linklist huffmantree:decode(string strcode)/ 操作结果：对编码串strcode进行译码,返回编码前的字符序列 linklist charlist; / 编码前的字符序列 for (int pos = 0; pos strcode.length(); pos+) / 处理每位编码 if (strcodepos = 0) curpos = nodescurpos.leftchild; / 0表示左分支 else curpos = nodescurpos.rightchild; / 1表示左分支 if (nodescurpos.leftchild = 0 & nodescurpos.rightchild = 0) / 译码时从根结点到叶结点路径的当前结点为叶结点 charlist.insert(charlist.length() + 1, leafcharscurpos); curpos = 2 * num - 1; return charlist; int main(void) char *ch; int *w,n,i; cout输入字符集中字符的个数：n; ch=new charn; w=new intn; cout输入字符集中的字符：endl; for(i=0;ichi; cout输入字符集中的字符的权值：endl; for(i=0;iwi; huffmantree hmtree(ch, w, n); string strtext,strcode; coutstrtext; cout 文本串 strtext.c_str() 编码为:; for (int pos = 0; pos st