#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#pragma warning(disable : 4996)
int n = 0;
typedef struct Heffuman {
char act;
float weight;
int parent; //双亲 //权值
int lt; //左孩子
int rt; // 右孩子
}Hefumanshu; //节点命名
Hefumanshu* HT;
char** HC;
void Select(int k, int* s1, int* s2) {
//在固定范围内找到权值最小的两个数,第一个最小的数
int min = 0;
for (int i = 1; i <= k; i++) {
if (HT[i].parent == 0) {
min = i;
break;
}
}
for (int i = min + 1; i <= k; i++) {
if (HT[i].parent == 0 && HT[i].weight <= HT[min].weight)
min = i;
}
*s1 = min;
//找第二个最小值
for (int i = 1; i <= k; i++) {
if (HT[i].parent == 0 && i != *s1) {
min = i;
break;
}
}
for (int i = min + 1; i <= k; i++) {
if (HT[i].parent == 0 && HT[i].weight <= HT[min].weight && i != *s1)
min = i;
}
*s2 = min;
}
void CreateHuff() {
int m = 2 * n - 1;
HT = (Hefumanshu*)malloc((m + 1) * sizeof(Hefumanshu));//开辟空间
if (!HT) exit(0);
for (int i = 0; i <= m + 1; i++) {
HT[i].parent = 0; HT[i].act = '#';
HT[i].lt = 0; HT[i].weight = 0.0;
HT[i].rt = 0;
}
HT[0].weight = INT_MAX;
printf("请输入编码符号和权值\n");
float a[100];
char s[100];
scanf("%s", s);
for (int i = 1; i <= n; i++) {
scanf("%f", &a[i]);
}
for (int j = 1; j <= n; j++) {
HT[j].act = s[j - 1];
HT[j].weight = a[j];
}
for (int i = n + 1; i <= m; i++) {
int s1 = 0, s2 = 0;
Select(i - 1, &s1, &s2);
HT[i].act = '#';
HT[i].weight = HT[s1].weight + HT[s2].weight;
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lt = s1;
HT[i].rt = s2;
}
printf("哈夫曼树\n");
for (int i = 0; i <= m; i++) {
printf("%c %1.2lf %d %d %d\n", HT[i].act, HT[i].weight, HT[i].parent, HT[i].lt, HT[i].rt);
}
printf("\n");
}
void HuffCoding() {
HC = (char**)malloc(sizeof(char*) * (n + 1));
//if(!HC) exit(0);
char* code = (char*)malloc(sizeof(char) * n);
//if(!code) exit(0);//开辟储存空间
code[n - 1] = '\0';
for (int i = 1; i <= n; i++) {
int start = n - 1;
int c = i;
int p = HT[c].parent;
while (p) {
if (HT[p].lt == c)
code[--start] = '0';
else
code[--start] = '1';
c = p;
p = HT[c].parent;
}
HC[i] = (char*)malloc(sizeof(char)*(n - start));
strcpy(HC[i], &code[start]);
}
free(code);
}
int main() {
printf("请输入字符集大小\n");
scanf_s("%d", &n);
CreateHuff();
printf("成功构建哈夫曼树\n");
HuffCoding();
printf("成功编码\n");
for (int i = 1; i <= n; i++) {
printf("数据:%s\n", HC[i]);
}
}
0x00007FF9BB3EF199 (ntdll.dll) (hufumanshu.exe 中)处有未经处理的异常: 0xC0000374: 堆已损坏。 (参数: 0x00007FF9BB4577F0)。
仅供参考：
#include <iostream>
#include <string>
using namespace std;
struct huffTree {
int parent;
int lchild;
int rchild;
int weight;
string flag;
};
struct Lowest_node {
char ch;
int ch_num;
};
void coding(int length,huffTree *tree,int n,int &a,int &b) {
int i;
int r,s;
r=s=length;
for (i=0;i<n;i++) {
if (tree[i].weight<r
&& tree[i].parent==-1) {
r=tree[i].weight;
a=i;
}
}
for (i=0;i<n;i++) {
if (tree[i].weight<s
&& i!=a
&& tree[i].parent==-1) {
s=tree[i].weight;
b=i;
}
}
}
void frequency(string str) {
int i,j;
int length=str.length();
Lowest_node *node=new Lowest_node[length];
for (i=0;i<length;i++) node[i].ch_num=0;
int char_type_num=0;
for (i=0;i<length;i++) {
for (j=0;j<char_type_num;j++)
if (str[i]==node[j].ch
|| ('a'<=node[j].ch && node[j].ch<='z'
&& str[i]+32==node[j].ch))
break;//
if (j<char_type_num) node[j].ch_num++;
else {
if ('A'<=str[i] && str[i] <= 'Z') node[j].ch=str[i]+32;
else node[j].ch=str[i];
node[j].ch_num++;
char_type_num++;
}
}
for (i=0;i<char_type_num;i++) {
for (j=i;j<char_type_num;j++) {
if (node[j].ch_num<node[j+1].ch_num) {
int temp;
char ch_temp;
temp=node[j].ch_num;
ch_temp=node[j].ch;
node[j].ch_num=node[j+1].ch_num;
node[j].ch=node[j+1].ch;
node[j+1].ch_num=temp;
node[j+1].ch=ch_temp;
}
}
}
for (i=0;i<char_type_num;i++)
cout<<"字符"<<node[i].ch<<"出现了"<<node[i].ch_num<<"次"<<endl;
huffTree *huff=new huffTree[2*char_type_num-1];
huffTree temp;
string *code=new string[2*char_type_num-1];
for (i=0;i<2*char_type_num-1;i++) {
huff[i].lchild=-1;
huff[i].parent=-1;
huff[i].rchild=-1;
huff[i].flag=-1;
}
for (j=0;j<char_type_num;j++) huff[j].weight=node[j].ch_num;
int min1,min2;
for (int k=char_type_num;k<2*char_type_num-1;k++) {
coding(length,huff,k,min1,min2);
huff[min1].parent=k;
huff[min2].parent=k;
huff[min1].flag="0";
huff[min2].flag="1";
huff[k].lchild=min1;
huff[k].rchild=min2;
huff[k].weight=huff[min1].weight+huff[min2].weight;
}
for (i=0;i<char_type_num;i++) {
temp=huff[i];
while (1) {
code[i]=temp.flag+code[i];
temp=huff[temp.parent];
if (temp.parent==-1) break;//
}
}
cout<<"字符串的每个字符huffman编码为："<<endl;
for (i=0;i<char_type_num;i++) cout<<node[i].ch<<" "<<code[i]<<endl;
cout<<"整个字符串的huffman编码为："<<endl;
for (i=0;i<length;i++) { //S?
for (j=0;j<char_type_num;j++) {
if (str[i]==node[j].ch)
cout<<code[j];
}
}
delete[] node;
node=NULL;
delete[] huff;
huff=NULL;
delete[] code;
code=NULL;
}
int main() {
int length=0;
string str;
cout<<"请输入一个字符串：";
cin>>str;
frequency(str);
return 0;
}
//请输入一个字符串：2333abcde
//字符3出现了3次
//字符2出现了1次
//字符a出现了1次
//字符b出现了1次
//字符c出现了1次
//字符d出现了1次
//字符e出现了1次
//字符串的每个字符huffman编码为：
//3 11
//2 000
//a 001
//b 010
//c 011
//d 100
//e 101
//整个字符串的huffman编码为：
//000111111001010011100101