《c++哈夫曼编码与译码.doc》由会员分享，可在线阅读，更多相关《c++哈夫曼编码与译码.doc（6页珍藏版）》请在三一办公上搜索。
1、#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); /
2、 返回指向第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
3、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-nex
4、t = 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 = po
5、sition; 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;HuffmanTree
6、Node: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; / 叶结点字符编码信息,Leaf
7、CharCodes0未用 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(c
8、har 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)
9、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未用
10、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.ri
11、ghtChild = 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 (nodespar
12、ent.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
13、() 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 Hu
14、ffmanTree: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 & nodescurP
15、os.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; HuffmanT
16、ree hmTree(ch, w, n); string strText,strCode; coutstrText; cout 文本串 strText.c_str() 编码为:; for (int pos = 0; pos strText.length(); pos+) string strTmp = hmTree.Encode(strTextpos); cout strTmp.c_str(); cout endl; system(PAUSE); coutstrCode; cout 编码串 strCode.c_str() 译码为:; LinkList lkText = hmTree.Decode(strCode); lkText.Traverse(); system(PAUSE); return 0;
