haffmantree.c

程序通过构建一个haffman树

// HaffmanTree.c : Defines the entry point for the console application.
//

#include "stdafx.h"


/*=================================================*/
/*             哈夫曼树编码             */
/*用哈夫曼树算法对文本文件进行0-1化编码，并模拟文件*/
/*压缩与解压                           */
/*=================================================*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

#define MAX_SINGLECODE_LEN 10     //单个字符最大码长
#define MAX_STRING_LEN 1000         //要编码的字符串的最大长度
#define MAX_CODESTRING_LEN 10000         //产生的二进制码的最大长度
#define MAX_WORDS 1000         //要编码的字符串中字符种数最大值
#define END_TREE 30000         //树部分存储的结束符
#define PATH_LEN 50         //路径串最大长度

/*****哈夫曼树结构定义*****/
typedef struct Huffmantree
{
  char ch;           //字符部分
  int weight;           //结点权值
  int   mark;           //标记是否加入树中
  struct Huffmantree *parent,*lchild,*rchild,*next;
}HTNode,*LinkTree;

/*****编码字典结构定义*****/
typedef struct
{
  char ch;           //字符部分
  char code[MAX_SINGLECODE_LEN];   //编码部分
}CodeDictionary;

/*********函数声明*********/
LinkTree setWeight(char *);
LinkTree sortNode(LinkTree);
LinkTree createHTree(LinkTree);
void codeHTree(LinkTree,CodeDictionary *);
void decodeHTree(LinkTree,char *,char *);
void deleteNode(LinkTree);
void compressString(char *s,CodeDictionary *,char *);
void readFile(char *);
void writeFile(char *);
void readCode(LinkTree,char *);
void writeCode(LinkTree,char *);
void menu();

/**
*主函数
*输入：空
*返回：空
*/
void main(void)
{
  char choice;         //菜单选择变量
  char string[MAX_STRING_LEN];   //保存从文件中读取的内容
  LinkTree temp;         //保存赋了权值的表
  LinkTree ht;         //保存排序后的表
  LinkTree htcopy,tempcopy;     //表备份
  LinkTree htree;         //保存哈夫曼树
  LinkTree ptr=NULL;
  CodeDictionary codedictionary[MAX_WORDS];//编码字典
  char codestring[MAX_CODESTRING_LEN];   //保存0-1形的代码串
  char codestring2[MAX_CODESTRING_LEN];//保存0-1形的代码串
  LinkTree ht2;         //保存读取的树
  LinkTree htree2;         //保存排序后的表
  char filestring[MAX_STRING_LEN];   //解码后要写入文件中的内容

  if((ht2=(LinkTree)malloc(sizeof(HTNode)))==NULL)//创建链表的头结点
  {
    printf("内存不足！");
    getch();
    exit(0);
  }
  ht2->next=NULL;

  while(1)
  {
    menu();         //调入主菜单
    choice=getch();     //读入用户选项
    switch(choice)     //判断用户选择
    {
        case 'c':
        case 'C':
          printf("\n您选择了压缩文件模式:\n\n");
          readFile(string);   //读取要编码的文件（字符串）
          temp=setWeight(string);         //得到有权值的表
          tempcopy=setWeight(string);
    ht=sortNode(temp);           //按权值排序后的表
 
          htcopy=sortNode(tempcopy);     //用于记录解码树
          htree=createHTree(ht);         //得到哈夫曼树
          codeHTree(htree,codedictionary);//哈夫曼编码
          compressString(string,codedictionary,codestring);//压缩为0-1码
          writeCode(htcopy,codestring);   //将解码树和0-1码保存
          deleteNode(htree);           //释放空间*/
          break;
        case 'u':
        case 'U':
          printf("您选择了解压缩文件模式:\n\n");
          readCode(ht2,codestring2);     //读取要解码的0-1码
          htree2=createHTree(ht2);     //得到哈夫曼树
          codeHTree(htree2,codedictionary);//哈夫曼编码
          decodeHTree(htree2,codestring2,filestring); //解码
          writeFile(filestring);         //将解码文件保存
          deleteNode(htree2);           //释放空间
          break;
        case 'e':
        case 'E':
          exit(0);                 //退出程序
    }
  }
}


/**
*整理输入的字符串，求出每个字符在数组中出现的次数，作为权值
*输入：（字符型指针）字符串的地址
*返回：（哈夫曼结点指针）含权链表的首地址
*/
LinkTree setWeight(char *string)
{
    int i=0;         //文件字符串下标
    LinkTree tree;        //头指针
 LinkTree ptr,beforeptr;      //创建指针与其前驱
 HTNode *node;

    if((tree=(LinkTree)malloc(sizeof(HTNode)))==NULL)//创建链表的头结点
   return NULL;
    tree->next=NULL;

    for(i=0;string[i]!='\0';i++)
 {
        ptr=tree;
        beforeptr=tree;

        if((node=(HTNode *)malloc(sizeof(HTNode)))==NULL)
   return NULL;
        node->next=NULL;
        node->parent=NULL;
        node->lchild=NULL;
        node->rchild=NULL;
        node->mark=0;
        node->ch=string[i];
        node->weight=1;

        if(tree->next==NULL)     //如果是第一个非头结点
            tree->next=node;
        else
  {
            ptr=tree->next;
            while(ptr&&ptr->ch!=node->ch)  //查找相同字符
   {
    ptr=ptr->next;
                beforeptr=beforeptr->next;
            }
            if(ptr&&ptr->ch==node->ch)   //如果链表中某结点的字符与新结点的字符相同
   {
                ptr->weight++;     //将该结点的权加一
                free(node);
            }
            else        //将新结点插入链表后
   {
                node->next=beforeptr->next;
                beforeptr->next=node;
            }
        }
    }
    return tree;        //返回头指针
}


/**
*将整理完的字符串（带权链表）按出现次数从小到大的顺序排列
*输入：（哈夫曼结点指针）要排序的表头地址
*返回：（哈夫曼结点指针）排序后的表头地址
*/
LinkTree sortNode(LinkTree tree)
{
  LinkTree head;                     //头指针
  LinkTree ph,beforeph;                 //创建指针及其前驱
  LinkTree pt;

  if((head=(LinkTree)malloc(sizeof(HTNode)))==NULL)//创建新链表的头结点
    return NULL;
  head->next=NULL;

  ph=head;
  beforeph=head;

  while(tree->next)
  {
    pt=tree->next;                   //取被操作链表的头结点
    tree->next=pt->next;
    pt->next=NULL;

    ph=head->next;
    beforeph=head;

    if(head->next==NULL)
        head->next=pt;                 //创建当前操作链表头结点
    else
    {
        while(ph&&ph->weight<pt->weight)   //将被操作结点插入相应位置
        {
          ph=ph->next;
          beforeph=beforeph->next;
        }
        pt->next=beforeph->next;
        beforeph->next=pt;
    }
  }
  free(tree);
  return head;                     //返回排序后的头指针
}

/**
*用排完序的字符串建立哈夫曼树
*输入：（哈夫曼结点指针）要建立哈夫曼树的地址
*返回：（哈夫曼结点指针）建立后的哈夫曼树地址
*/
LinkTree createHTree(LinkTree tree)
{
  LinkTree p,q,beforep;
  HTNode *newnode;

  for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next)
                                //p、q初值为头结点后的两个结点，即最小权结点
  {
    tree->next=q->next;
    q->next=NULL;
    p->next=NULL;

    if((newnode=(HTNode *)malloc(sizeof(HTNode)))==NULL)
                                //申请新结点作为哈夫曼树的中间结点
        return NULL;
    newnode->next=NULL;
    newnode->mark=0;

    newnode->lchild=p;                 //取链表头结点后的两个结点作为新结点的左、右孩子
    newnode->rchild=q;
    p->parent=newnode;
    q->parent=newnode;
    newnode->weight=p->weight+q->weight;   //权值相加

    p=tree->next;
    beforep=tree;

    if(p!=NULL&&p->weight>=newnode->weight)
    {
        newnode->next=beforep->next;     //将新结点插入原链表的相应位置
        beforep->next=newnode;
    }
    else
    {
        while(p!=NULL&&p->weight<newnode->weight)
        {
          p=p->next;
          beforep=beforep->next;
        }
        newnode->next=beforep->next;
        beforep->next=newnode;
    }
  }
  return (tree->next);
}

/**
*对哈夫曼树进行编码
*输入：（哈夫曼结点指针）要编码的哈夫曼树地址
*     （编码字典类型指针）存放字典的首地址
*返回：空
*/
void codeHTree(LinkTree tree,CodeDictionary *codedictionary)
{
  int index=0,k=0;
  char code[MAX_SINGLECODE_LEN];           //用于统计每个字符的哈夫曼编码
  LinkTree ptr=tree;                   //从树的根结点开始

  if(ptr==NULL)
  {
    printf("要压缩的文件是空的!\n");
    exit(0);
  }
  else
  {
    while(ptr->lchild&&ptr->rchild&&ptr->mark==0)
    {
        while(ptr->lchild&&ptr->lchild->mark==0)
        {
          code[index++]='0';           //左支路编码为0
          ptr=ptr->lchild;
          if(!ptr->lchild&&!ptr->rchild)   //如果没有左右孩子，即叶子结点
          {
            ptr->mark=1;           //作标记，表明该字符已被编码
            code[index]='\0';         //编码0-1字符串结束
            codedictionary[k].ch=ptr->ch;//给字典赋字符值
            for(index=0;code[index]!='\0';index++)
                codedictionary[k].code[index]=code[index];//给字典赋码值
            codedictionary[k].code[index]='\0';
            k++;
            ptr=tree;             //指针复位
            index=0;
          }
        }
        if(ptr->rchild&&ptr->rchild->mark==0)
        {
          ptr=ptr->rchild;
          code[index++]='1';           //右支路编码为1