#include
#include
#include
using namespace std;
typedef struct HTNode{
unsigned int weight;
HTNode *lchild, *rchild;
}HTNode,*HuffmanTree;
typedef HuffmanTree *HuffmanCode;
typedef struct List{
HuffmanTree data;
List *next;
}List,*LinkList;
void sort(int elem,int n) {
int *p = elem;
for(int i=0;i<n-1;i++)
for (int j = 0; j < n - 1 - i; j++) {
if ((p + j) < *(p + j + 1)) {
int k = *(p + j);
*(p + j) = *(p + j + 1);
*(p + j + 1) = k;
}
}
}
void insert(LinkList L, HuffmanTree p) {
LinkList q = L;
bool triger = true;
while (q->next) {
if (p->weight < q->next->data->weight) {
LinkList t = (LinkList)malloc(sizeof(List));
t->data = p;
t->next = q->next;
q->next = t;
triger = false;
break;
}
q = q->next;
}
if (triger) {
LinkList t = (LinkList)malloc(sizeof(List));
t->data = p;
t->next = q->next;
q->next = t;
}
}
void CreateHuffman(HuffmanTree &P, int elem, int n) {
//
//最后一个元素为(elem+n-1)
HuffmanCode T;
T = (HuffmanCode)malloc(sizeof(HuffmanTree)*n);
LinkList L;
L = (LinkList)malloc(sizeof(List));
L->next = NULL;
for (int i = 0; i < n; i++) {
HuffmanTree q = (HuffmanTree)malloc(sizeof(HuffmanCode));
q->weight = *(elem + i);
cout << q->weight << endl;
q->lchild = NULL;
q->rchild = NULL;
LinkList p;
p = (LinkList)malloc(sizeof(List));
p->data = q;
p->next = L->next;
L->next = p;
}
for (int i = 0; i < n - 2; i++) {
HuffmanTree p;
p = (HuffmanTree)malloc(sizeof(HuffmanCode));
p->lchild = L->next->data;
p->rchild = L->next->next->data;
p->weight = L->next->data->weight + L->next->next->data->weight;
//cout << p->weight << endl;
L = L->next->next;
insert(L, p);
}
P = (HuffmanTree)malloc(sizeof(HuffmanCode));
P->lchild = L->next->data;
P->rchild = L->next->next->data;
P->weight = L->next->data->weight + L->next->next->data->weight;
//cout << P->weight << endl;
}
void print(HuffmanTree P,int n=0) {
if (P->rchild) print(P->rchild, n + 1);
for (int i = 1; i <= n; i++) cout << " ";
cout << P->weight << endl;
if (P->lchild) print(P->lchild, n + 1);
}
int main() {
int n;
int *elem;
cin >> n;//建立的哈夫曼数的节点个数
elem = (int *)malloc(sizeof(int)*n);
int *p = elem;
for (int i = 1; i <= n; i++) {
cin >> *p;
p++;
}
sort(elem, n);
//for (int i = 0; i < n; i++) cout << setw(4) << *(elem + i);
HuffmanTree P;
CreateHuffman(P, elem, n);
print(P);
system("pause");
}
把第62行注释掉就会报错