自适应哈弗曼编码c++实现zzia.doc

///用数组array存放自适应哈弗曼树 ///通过各元素的下标指针构建哈弗曼树 #includeiostream #includestring using namespace std; struct node { char elem; //字符元素 int weight; //字符的权重 int flag; //标记，判断是否是字符节点，编码使用 int rparent; //字符是否为父节点的右孩子判别标志，是的话该值为1 否则为0 编码用 int parent; //父结点的序号 int lchild; //节点的左孩子下标 int rchild; //节点的右孩子下标 }; node array[200]; int n=2; string str; int count=0; int exchange(int m, int k) //两节点交换函数，对应下标分别为m，k { // cout交换结点开始endl; int p = array[m].rparent; int q = array[k].rparent; int a = array[m].parent; if(q p)//都是右结点 { array[array[m].parent].rchild = k; array[m].parent = array[k].parent; array[array[k].parent].rchild = m; array[k].parent = a; // cout交换节点完毕endl; return 0; } else if(!q !p)//都是左结点 { array[array[m].parent].lchild = k; array[m].parent = array[k].parent; array[array[k].parent].lchild = m; array[k].parent = a; // cout交换节点完毕endl; return 0; } else if(!q p) { array[array[m].parent].rchild = k; array[m].parent = array[k].parent; array[array[k].parent].lchild = m; array[k].parent = a; array[m].rparent = 0; array[k].rparent = 1; // cout交换节点完毕endl; return 0; } else if(q !p) { array[array[m].parent].lchild = k; array[m].parent = array[k].parent; array[array[k].parent].rchild = m; array[k].parent = a; array[m].rparent = 1; array[k].rparent = 0; // cout交换节点完毕endl; return 0; } else { return -1; } } void coding() //对生成的哈弗曼树编码 { // cout开始编码endl; for(int i=0; icount; i++) //输出当前录入的字符串 coutstr.at(i); coutendl; int* code=new int[20]; int k,l; for(i=1;i=n;i++) { if(array[i].flag==0) {continue; } //该节点不是叶子节点，对下一节点编码 k=i; l=0; while(array[k].parent != -1) { code[l]=array[k].rparent; k=array[k].parent; l++; } cout.setf(ios::left); cout.width(3); coutarray[i].weight; //输出该节点字符的权重 if(array[i].weight==0) coutnew:; else cout array[i].elem:; for(l=l-1;l=0;l--) //输出字符编码 coutcode[l]; coutendl;