C语言如何实现哈夫曼树
小编这次要给大家分享的是C语言如何实现哈夫曼树,文章内容丰富,感兴趣的小伙伴可以来了解一下,希望大家阅读完这篇文章之后能够有所收获。
站在用户的角度思考问题,与客户深入沟通,找到钟山网站设计与钟山网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:网站设计、成都网站建设、企业官网、英文网站、手机端网站、网站推广、国际域名空间、虚拟空间、企业邮箱。业务覆盖钟山地区。
//哈夫曼树C语言实现 #include#include typedef struct HuffmanNode { char letter;//存储的字符,叶节点为字母,非叶节点为# struct HuffmanNode *parent;//父亲结点 int code;//如果为父亲结点的左孩子,则为0,右孩子为1 }HuffmanNode; typedef struct HeapNode { int rate;//出现频率 HuffmanNode *node;//对应于哈夫曼树中的结点 }HeapNode; /*------------------全局变量----------------------*/ int heapSize;//堆大小 int num;//记录字符数量 HeapNode *heap;//堆数组 char *letter;//字符数组 int *rate;//字符出现频率 HuffmanNode **array; //记录叶节点的数组,打印编码的时候可以从叶结点回溯向上 char ch; /*----------------------函数声明-------------------------*/ void init(int numOfLetters);//初始化变量 void input();//输入数组 int parent(int i);//求父节点 int left(int i);//求左孩子 int right(int i);//求右孩子 void swap(int i,int j);//交换函数 void heapIfy(int i,int localHeapSize);//维持堆性质函数,使用前提为左右子树均为最小堆 void buildHeap();//初始化堆 HeapNode* extractMin();//去掉并返回堆中最小的元素 void heapInsert(int rate,HuffmanNode *p);//向堆中插入数据(前提:堆已经初始化) HuffmanNode* buildTree();//构造哈夫曼树 void display();//显示函数 void backPrint(HuffmanNode *p,HuffmanNode *root);//从叶节点回溯打印编码code /*----------------------函数实现-------------------------*/ void init(int numOfLetters) { heapSize=numOfLetters;//堆大小初始化为字母数 num=numOfLetters;//记录字符数量 heap=(HeapNode*)malloc((numOfLetters+1)*sizeof(HeapNode));//分配堆空间,最多只需要字符的个数,因为合并过程中删除两个,插入一个 letter=(char*)malloc((numOfLetters+1)*sizeof(char));//用于存储字符 rate=(int *)malloc((numOfLetters+1)*sizeof(int));//用于存储字符出现频率 array=(HuffmanNode **)malloc((numOfLetters+1)*sizeof(HuffmanNode));//记录叶节点的数组,打印编码的时候可以从叶结点回溯向上 } void input() { int i=1; while(i<=heapSize) { printf("输入第%d个字符\n",i); scanf("%c",&letter[i]);ch=getchar(); printf("输入第%d个字符的频度\n",i); scanf("%d",&rate[i]);ch=getchar(); //向堆中插入各个结点 heap[i].rate=rate[i]; heap[i].node=(HuffmanNode *)malloc(sizeof(HuffmanNode)); array[i]=heap[i].node; heap[i].node->parent=NULL; heap[i].node->letter=letter[i]; i++; } } int parent(int i) { return i/2; } int left(int i) { return 2*i; } int right(int i) { return 2*i+1; } void swap(int i,int j) //交换结构体数组,需要交换结构体内数据 { int rate; HuffmanNode *p; rate=heap[i].rate; p=heap[i].node; heap[i].rate=heap[j].rate; heap[i].node=heap[j].node; heap[j].rate=rate; heap[j].node=p; } void heapIfy(int i,int localHeapSize)//维持堆性质函数,使用前提为左右子树均为最小堆 { int l=left(i); int r=right(i); int least=i; //找出heap成员rate 的i,left(i),right(i)的最小值 if(l<=localHeapSize&&heap[least].rate>heap[l].rate) { least=l; } if(r<=localHeapSize&&heap[least].rate>heap[r].rate) { least=r; } if(least!=i) { swap(i,least); heapIfy(least,localHeapSize); } } void buildHeap()//初始化堆 { int i=0; for(i=heapSize/2;i>=1;i--) { heapIfy(i,heapSize); } } HeapNode* extractMin() { if(heapSize>=1) { HeapNode *min; swap(1,heapSize); min=&heap[heapSize]; --heapSize; heapIfy(1,heapSize); return min; } else { printf("堆中没有元素"); return NULL; } } void heapInsert(int rate,HuffmanNode *p) { ++heapSize; int i=heapSize; while(i>1&&heap[parent(i)].rate>rate) { heap[i].rate=heap[parent(i)].rate; heap[i].node=heap[parent(i)].node; i=parent(i); } heap[i].rate=rate; heap[i].node=p; } HuffmanNode* buildTree() { buildHeap();//初始化堆 HeapNode *p;//用于临时存储最小堆结点 HeapNode *q;//用于临时存储次小堆结点 int count=heapSize; int i; for(i=1;i<=count-1;i++) { HuffmanNode *tree=(HuffmanNode*)malloc(sizeof(HuffmanNode));//生成内结点 tree->letter='#';//内结点的字符记作#,没有实际意义 p=extractMin(); q=extractMin(); p->node->parent=tree; p->node->code=0; q->node->parent=tree; q->node->code=1; //printf("%c:%d",p->node->letter,p->node->code); //printf("\n"); printf("%c:%d",q->node->letter,q->node->code); printf("\n");//测试 heapInsert(p->rate+q->rate,tree);//插入堆中 } return extractMin()->node; } void display() { HuffmanNode*p=buildTree();////哈夫曼树的根节点地址 int i=1; while(i<=num) { printf("%c:",array[i]->letter); backPrint(array[i],p); printf("\n"); i++; } } void backPrint(HuffmanNode *p,HuffmanNode *root) { if(p!=root) { backPrint(p->parent,root); printf("%d",p->code);//printf("++++");//测试 } } int main(int argc ,char* argv[]) { int number; printf("输入的字符个数为:\n"); scanf("%d",&number); ch=getchar(); init(number); input(); display(); system("PAUSE"); return 0; }
看完这篇关于C语言如何实现哈夫曼树的文章,如果觉得文章内容写得不错的话,可以把它分享出去给更多人看到。
本文标题:C语言如何实现哈夫曼树
链接分享:http://pwwzsj.com/article/ihsejp.html