有好几天没发表文章了。主要是这几天在搞多媒体的压缩算法。老师布置了四个算法(Huffman编码,自适应Huffman编码，算术编码，LZW编码算法），因为Huffman算法以前就实现过了，直接用上就OK。但是自适应Huffman我弄了好久，整整两天吧，也是断断续续的，因为这个周末我们有微机的课设，两天都呆在实验室了。我写这基本谈不上什么算法，只能说是勉强完成了基本功能，如果是在POJ上面的话。肯定是TLE。没办法，我实在不知道怎么写了额。凑合着吧，接下来还要完成剩下的两个算法。再接再励吧。加油。然后才能继续我的ACM刷题了。

Huffman：

//HuffmanTree#include
     
      #include
      
       #include
       
        #define UNIT_MAX 10000typedef struct{   unsigned int weight;   unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree; //动态分配数组存储HuffmanTreetypedef char **HuffmanCode;//动态分配数组存储HuffmanCodeint min1(HuffmanTree t,int i){
    //函数VOID select调用   int j,flag;   unsigned int k=UNIT_MAX;//取K为最小可能的值   for(j=1;j<=i;j++)     if(t[j].weight
        
         *s2)   {       j=*s1;      *s1=*s2;      *s2=j;   }}void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)   //这里也是必须用两个*,我开始以为不用的呢。。。{
   //w存放n个字符的权值（>0），构造哈弗曼树HT，并求出n个字符的哈弗曼编码HC、  int m,i;  HuffmanTree p; if(n<=1) return ;  m=2*n-1;  *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));  //0号单元未用 //初始化  for(p=*HT+1,i=1;i<=n;++i,++p,++w)  {    p->weight=*w;    p->parent=0;    p->lchild=0;    p->rchild=0;  }  for(;i<=m;++i,++p)  {    p->weight=0;    p->parent=0;    p->lchild=0;    p->rchild=0;  }  for(i=n+1;i<=m;++i)//建HuffmanTree  {
   //在HT[1..i-1]中选择parent为0且weight最小的两个节点，其序号分别为s1,s2.     int s1,s2;     select(*HT,i-1,&s1,&s2);    //选出最小的两个节点    (*HT)[s1].parent=i;(*HT)[s2].parent=i;    (*HT)[i].lchild=s1;(*HT)[i].rchild=s2;    (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;  }    //-------------从叶子到根逆向求每个字符的HuffmanCode--------    *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));  //分配n个字符编码的头指针向量     char *cd;    cd=(char*)malloc(n*sizeof(char));     cd[n-1]='\0';      //分配求编码的工作空间    for(i=1;i<=n;++i)    {     int start=n-1;       int f,c;       for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) //从叶子到根逆向求编码 从第一个节点开始遍历          if((*HT)[f].lchild==c)               cd[--start]='0';          else               cd[--start]='1';       (*HC)[i]=(char*)malloc((n-start)*sizeof(char));  //为第i个字符编码分配空间       strcpy((*HC)[i],&cd[start]);      //从cd复制编码串到HC  这个超经典啊 为什么要用个&！！    }     free(cd);}//HuffmaCodingint main(){   HuffmanTree HT;   HuffmanCode HC;   int *w,n,i;   printf("请输入权值的个数(>1)：");   scanf("%d",&n);   w=(int*)malloc(n*sizeof(int));//为数据开辟空间   printf("请依次输入%d个权值(整型)：\n",n);   for(i=0;i<=n-1;i++)     scanf("%d",w+i);   HuffmanCoding(&HT,&HC,w,n);   for(i=1;i<=n;i++)     puts(HC[i]);    return 0;}
        
       
      
     

 

自适应Huffman算法：

#include 
     
      #include 
      
         //C++#include 
       
        #include 
        
         using namespace std;#define N 27bool used[256]; //标志是否存在struct AHTNode{     unsigned int weight;     string code;     char data;     struct AHTNode *parent,*lchild,*rchild;     AHTNode(){}};bool first=true;   //是否是第一个字符bool flag=false;  //标记是否交换位置AHTNode *NYT;AHTNode *Tree;void get_code(AHTNode *&n)  //向上获取编码{      n->code="";      AHTNode *tem=n;   //只是必须的  不然n会变为Tree      stack
         
           s;    while(tem->parent!=NULL)    {          if(tem->parent->lchild==tem)              s.push('0');          else if(tem->parent->rchild==tem)              s.push('1');         tem=tem->parent;    }    while(!s.empty())    {        if(s.top()=='0')              n->code+="0";        else if(s.top()=='1')            n->code+="1";        s.pop();    }}void update_code(){  //更新节点code    queue
          
            q; q.push(Tree); AHTNode* tem; while(!q.empty()) { tem=q.front(); q.pop(); if(tem->data!='0') get_code(tem); if(tem->lchild) q.push(tem->lchild); if(tem->rchild) q.push(tem->rchild); }}AHTNode* BFST(int t){ queue
           
             q; q.push(Tree); AHTNode* tem; while(!q.empty()) { tem=q.front(); q.pop(); if(tem->weight==t && tem->data!='0') return tem; if(tem->lchild) q.push(tem->lchild); if(tem->rchild) q.push(tem->rchild); }}AHTNode* BFSC(char c){ queue
            
              q; q.push(Tree); AHTNode* tem; while(!q.empty()) { tem=q.front(); q.pop(); if(tem->data==c) return tem; if(tem->lchild) q.push(tem->lchild); if(tem->rchild) q.push(tem->rchild); }}void sibling_rule(AHTNode *T){ if(T->parent && T==T->parent->lchild && T->weight > T->parent->rchild->weight) //左孩子 并且大于兄弟节点 { //不满足兄弟规则 AHTNode *tem=T->parent->rchild; //暂存它的兄弟节点 T->parent->lchild=tem; T->parent->rchild=T; //交换位置 flag=true; }}void up_plus(AHTNode *T){ AHTNode *tem=T; flag=false; while(tem) { tem->weight++; sibling_rule(tem); tem=tem->parent; } if(flag) { update_code(); }}void update_tree(int flag,char c){ AHTNode *node,*maxnode; if(flag) //出现过 { node=BFSC(c); cout<
             
              code; //输出上次的结果 maxnode=BFST(node->weight); //搜索块最大的点 if(maxnode==node) //自身是最大的 { up_plus(node); } else //不是块内最大 交换 { AHTNode *tem=maxnode->parent; maxnode->parent=node->parent; node->parent=tem; maxnode->parent->rchild=maxnode; //肯定是右孩子 if(maxnode==tem->lchild) { //最大节点在左边 tem->lchild=node; } else { tem->rchild=node; } up_plus(node); get_code(node); //获取新节点的编码 用于下次输出 } } else //没出现 { //新建节点 AHTNode *New=new AHTNode(); New->weight=1; New->data=c; New->lchild=NULL; New->rchild=NULL; if(first) { New->parent=Tree; Tree->rchild=New; first=false; } else { AHTNode* tem=new AHTNode(); //代替原来的NYT NYT->parent->lchild=tem; tem->parent=NYT->parent; tem->weight=0; tem->lchild=NYT; tem->rchild=New; tem->data='0'; NYT->parent=tem; New->parent=tem; } up_plus(New->parent); printf("%c",c); get_code(New); //获取新节点的编码 用于下次输出 //printf("%s",New->code); 这为什么不行呢？ string是C++特有的？？只能这么解释了 }//else}int main(){ NYT=new AHTNode(); NYT->weight=0;NYT->parent=NULL; NYT->lchild=NULL; NYT->rchild=NULL; NYT->data='0'; //Root Tree=new AHTNode(); Tree->weight=-1;Tree->parent=NULL; Tree->lchild=NULL; Tree->rchild=NULL; Tree->data='0'; Tree->lchild=NYT; NYT->parent=Tree; freopen("in.txt","r",stdin); char c; while( (c=getchar())!=EOF ) { if(used[c]) { //出现过 update_tree(1,c); } else { //没出现过 update_tree(0,c); used[c]=true; } } printf("\n"); return 0;}