C语言实现哈夫曼树
本文实例为大家分享了C语言实现哈夫曼树的具体代码，供大家参考，具体内容如下
//哈夫曼树C语言实现 #include#include typedefstructHuffmanNode { charletter;//存储的字符，叶节点为字母，非叶节点为# structHuffmanNode*parent;//父亲结点 intcode;//如果为父亲结点的左孩子，则为0，右孩子为1 }HuffmanNode; typedefstructHeapNode { intrate;//出现频率 HuffmanNode*node;//对应于哈夫曼树中的结点 }HeapNode; /*------------------全局变量----------------------*/ intheapSize;//堆大小 intnum;//记录字符数量 HeapNode*heap;//堆数组 char*letter;//字符数组 int*rate;//字符出现频率 HuffmanNode**array;//记录叶节点的数组，打印编码的时候可以从叶结点回溯向上 charch; /*----------------------函数声明-------------------------*/ voidinit(intnumOfLetters);//初始化变量 voidinput();//输入数组 intparent(inti);//求父节点 intleft(inti);//求左孩子 intright(inti);//求右孩子 voidswap(inti,intj);//交换函数 voidheapIfy(inti,intlocalHeapSize);//维持堆性质函数，使用前提为左右子树均为最小堆 voidbuildHeap();//初始化堆 HeapNode*extractMin();//去掉并返回堆中最小的元素 voidheapInsert(intrate,HuffmanNode*p);//向堆中插入数据（前提：堆已经初始化） HuffmanNode*buildTree();//构造哈夫曼树 voiddisplay();//显示函数 voidbackPrint(HuffmanNode*p,HuffmanNode*root);//从叶节点回溯打印编码code /*----------------------函数实现-------------------------*/ voidinit(intnumOfLetters) { 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));//记录叶节点的数组，打印编码的时候可以从叶结点回溯向上 } voidinput() { inti=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++; } } intparent(inti) { returni/2; } intleft(inti) { return2*i; } intright(inti) { return2*i+1; } voidswap(inti,intj)//交换结构体数组，需要交换结构体内数据 { intrate; 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; } voidheapIfy(inti,intlocalHeapSize)//维持堆性质函数，使用前提为左右子树均为最小堆 { intl=left(i); intr=right(i); intleast=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); } } voidbuildHeap()//初始化堆 { inti=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); returnmin; } else { printf("堆中没有元素"); returnNULL; } } voidheapInsert(intrate,HuffmanNode*p) { ++heapSize; inti=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;//用于临时存储次小堆结点 intcount=heapSize; inti; 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);//插入堆中 } returnextractMin()->node; } voiddisplay() { HuffmanNode*p=buildTree();////哈夫曼树的根节点地址 inti=1; while(i<=num) { printf("%c:",array[i]->letter); backPrint(array[i],p); printf("\n"); i++; } } voidbackPrint(HuffmanNode*p,HuffmanNode*root) { if(p!=root) { backPrint(p->parent,root); printf("%d",p->code);//printf("++++");//测试 } } intmain(intargc,char*argv[]) { intnumber; printf("输入的字符个数为：\n"); scanf("%d",&number); ch=getchar(); init(number); input(); display(); system("PAUSE"); return0; }
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。