c/c++语言开发共享C语言：数据结构、哈夫曼编码、Huffman-源代码

1. 目标

读取一段字符，生成哈夫曼编码，并输出。如下所示：

2. 代码结构

2.1 统计各个字符出现的次数，并排序；

2.2 根据生成的哈夫曼树，生成哈夫曼编码；

3. 源代码

  #include   #include   #include   #define title  #define queuesize_max 256 //队列的最大长度  #define code_max 256 //编码的最大长度    /**************************************/  /*定义huffman tree节点                */  /*其中symbol记录节点存储的字符        */  /*left, right指向左右子节点           */  /**************************************/  typedef struct hfmtreenode{      int symbol;      struct hfmtreenode *left;      struct hfmtreenode *right;  } hfmtreenode, *phtreenode;    /**************************************/  /*定义一个指向huffman tree的根节点    */  /**************************************/  typedef struct hhfmtreenode{      hfmtreenode* rootnode;  } hhfmtreenode;    /**************************************/  /*定义队列的节点                      */  /*ptr是一个指向phtreenode的指针，     */  /*主要是方便后续建立huffman treee     */  /*count记录字符出现的频次，           */  /*next指向下一个节点                  */  /**************************************/  typedef struct queuenode{      phtreenode ptr;      int count;      struct queuenode *next;  } queuenode, *ptrqueue;    /**************************************/  /*定义指向queuenode的头节点           */  /*其中size记录节点的数量              */  /*first指向queuenode的第一个节点      */  /**************************************/  typedef struct hqueuenode{      int size;      ptrqueue first;  } hqueuenode;    /**************************************/  /*定义指向记录编码的table节点         */  /*symble为字符，code指向对应的编码    */  /*next用来指向下一个节点              */  /**************************************/  typedef struct tablenode{      char symbol;      char* code;      struct tablenode *next;  } tablenode;    /**************************************/  /*定义指向tablenode的头节点           */  /*first标记第一个节点                 */  /*last指向最后一个节点                */  /**************************************/  typedef struct hdtablenode{      tablenode *first;      tablenode *last;  } hdtablenode;    /**************************************/  /*对队列进行初始，添加一个头节点      */  /*其中size记录节点的数量              */  /*first指向queue节点                  */  /**************************************/  void initqueue(hqueuenode** hqueue)  {      *hqueue=(hqueuenode*)malloc(sizeof(hqueuenode));      (*hqueue)->size=0;      (*hqueue)->first=null;  }    void addqueuenode(hqueuenode **hqueue,hfmtreenode *hnode,int count)//新建一个队列节点并按统计的结果从小到大的顺序加入队列  {      queuenode *qnode=null;        if((*hqueue)->size==queuesize_max)//队列规模检查，正常情况下不会出现      {          printf("nerr: the queue is full!!!");      }      else    //如果正常，则按照从小到大的顺序，寻找正确的位置插入节点      {          if(0==(*hqueue)->size)//如果是添加的第一个节点，直接添加即可          {              qnode=(queuenode*)malloc(sizeof(queuenode));              (*hqueue)->first=qnode;              qnode->count=count;              qnode->ptr=hnode;              qnode->next=null;              (*hqueue)->size++;          }          else if(count<(*hqueue)->first->count)//如果要添加的字符的统计数量小于现有最小的，则直接放在第一个节点处          {              qnode=(queuenode*)malloc(sizeof(queuenode));              qnode->next=(*hqueue)->first;              (*hqueue)->first=qnode;              qnode->count=count;              qnode->ptr=hnode;              (*hqueue)->size++;          }          else    //对于第三类情况，则需要遍历队列，直到寻找到合适的位置          {              queuenode* p=(*hqueue)->first;              qnode=(queuenode*)malloc(sizeof(queuenode));              qnode->count=count;              qnode->ptr=hnode;              (*hqueue)->size++;                while(p->next!=null && count>=p->next->count)                  p=p->next;              qnode->next=p->next;              p->next=qnode;          }      }  }    hfmtreenode* gethfmtreenode(hqueuenode* hqueue)  {      hfmtreenode* getnode;      if(hqueue->size>0)      {          getnode=hqueue->first->ptr;          hqueue->first=hqueue->first->next;          hqueue->size--;      }      else      {          printf("nerr: can't get a noden");      }      return getnode;  }      hhfmtreenode* crthfmtree(hqueuenode** hqueue)  {      int count=0;      hfmtreenode *left, *right;        while((*hqueue)->size>1)      {          count=(*hqueue)->first->count+(*hqueue)->first->next->count;          left=gethfmtreenode(*hqueue);          right=gethfmtreenode(*hqueue);            hfmtreenode *newnode=(hfmtreenode*)malloc(sizeof(hfmtreenode));            newnode->left=left;          newnode->right=right;            addqueuenode(hqueue,newnode,count);      }        hhfmtreenode* tree=(hhfmtreenode*)malloc(sizeof(hhfmtreenode));      tree->rootnode=gethfmtreenode(*hqueue);      return tree;  }    hhfmtreenode* creattree(void)  {      file *ifile;      int *countarray;      char c;      int i;        countarray=(int*)malloc(sizeof(int)*256);//分配空间用于存储各字符出现的次数,并初始化为零      for(i=0;i<256;i++)      {          countarray[i]=0;      }        ifile=fopen("d://1.txt","r");      if(!ifile)  //检查文件是否打开成功          printf("can't open the filen");      else          {              while((c=getc(ifile))!=eof)              {                  countarray[(unsigned int)c]++;                  printf("%c", c);              }              fclose(ifile);          }      hqueuenode *hqueue;      initqueue(&hqueue);      for(i=0;i<256;i++)      {          if(countarray[i])          {              //printf("%c %dn",i, countarray[i] );              hfmtreenode *hnode=(hfmtreenode*)malloc(sizeof(hfmtreenode));//创建一个树节点，并初始化（用来对应队列queuenode中的ptr）                hnode->symbol=(char)i;              hnode->left=null;              hnode->right=null;                addqueuenode(&hqueue,hnode,countarray[i]);//将该节点插入队列中的适当位置（按统计的结果，从小到大排列）          }      }      free(countarray);//释放不用的内存        queuenode* q=hqueue->first;      printf("n");      do      {          printf("n%c %d",q->ptr->symbol, q->count);          q=q->next;      }    while(q!=null);      //printf("%d",hqueue->size);        hhfmtreenode *tree=crthfmtree(&hqueue);      return tree;  }    void traversetree( hdtablenode** table, hfmtreenode* tree, char* code, int k)  {      if(tree->left==null && tree->right==null)   //递归结束检查，即找到叶子节点      {          code[k]='';   //添加字符串结束标记          tablenode *tnode=(tablenode*)malloc(sizeof(tablenode)); //创建一个节点，并将其添加到table链表中          tnode->code=(char*)malloc(sizeof(char)*256+1);          strcpy(tnode->code,code);          tnode->symbol=tree->symbol;          tnode->next=null;            if((*table)->first==null)   //如果是第一个节点，直接添加即可， 否则添加到尾部即可          {              (*table)->first=tnode;              (*table)->last=tnode;          }          else          {              (*table)->last->next=tnode;              (*table)->last=tnode;          }      }        if(tree->left!=null)    //向左边递归，并记录编码为0      {          code[k]='0';          traversetree(table,tree->left, code, k+1);      }        if(tree->right!=null)   //向右边递归，并记录编码为1      {          code[k]='1';          traversetree(table, tree->right, code, k+1);      }  }    hdtablenode* crttable(hhfmtreenode* hfmtree)  {      hdtablenode* hdtable=(hdtablenode*)malloc(sizeof(hdtablenode));      hdtable->first=null;      hdtable->last=null;        char code[code_max];      int k=0; //记录树的层级        traversetree(&hdtable, hfmtree->rootnode, code, k);      return hdtable;  }        int main(void)  {      hhfmtreenode* tree;      hdtablenode* table;        printf("%snnn",title);      tree=creattree();      table=crttable(tree);      int i=0, j=0;      tablenode* t=table->first;      char* s=t->code;      printf("nn*************************************************************************************n");      printf("the huffman code is:n");      while(t!=null)      {            for(i=0;i<257;i++)          {              if((*s)!='')              {                  printf("%c",*s);                  s++;              }          }              printf("%8cn",t->symbol);              t=t->next;              if(t)                  s=t->code;        }  }