關于資料結構c語言版
哈夫曼樹的建立于select（）函數的實作
代碼如下：（具體注意事項已經在代碼注釋中表面，其中關鍵事項在最後表明）
//haffumanshu
//by wangjintao
typedef struct{
int weight;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree;
void CreateHuffmanTree(HuffmanTree *HT,int n);
void Select(HuffmanTree HT,int m,int *s1,int *s2);
void outHuffmanTree(HuffmanTree HT,int n);
#include<stdlib.h>
#include<stdio.h>
int main(){
int n;
HuffmanTree HT;
printf("下面進行huffmantree的建立\n請輸入你想要輸入的結點個數:\n");
scanf("%d",&n);
CreateHuffmanTree(&HT,n);
printf("建立Huffman tree完成\n");
//printf("%d",HT[4].lchild);
//printf("%d %d",4,HT[4].weight);測試發現應該是沒有create成功
//printf("%d %2d %6d %6d %6d",4,HT[4].weight,HT[4].parent,HT[4].lchild,HT[4].rchild);//說明這個create不一定成功
//intf("%d",HT[3].weight);
outHuffmanTree(HT,n);//HT裡邊的值就是那棵哈夫曼樹的位址，這樣就需要考慮之前的單連結清單，與2叉數的問題了
return 0;
}
void CreateHuffmanTree(HuffmanTree *HT,int n){
if(n<=1)
return;
int i;
int s1,s2;
*(HT)=(HTNode*)malloc(2*n*sizeof(HTNode));//huffmantree有其他輔助結點
for(i=0;i<=2*n;i++){
(*HT)[i].lchild=0;(*HT)[i].parent=0;(*HT)[i].rchild=0;
}
printf("請輸入這n個結點的weight：");
for(i=1;i<=n;i++)
scanf("%d",&(*HT)[i].weight);
for(i=n+1;i<2*n;i++){//進行n-1次的結合 //最後一個位置為2n-1
Select(*HT,i-1,&s1,&s2);//此時s1和s2裡邊就是那兩個下标了，在下面的函數裡邊都是用到s1和s2而不是*s2
//select注意(*HT)因為你這個是在create函數裡邊，隻有一個（*HT）它指向主程式裡邊一個變量，變量裡的值就是那棵哈夫曼樹的位址
//printf("%d,%d\n",s1,s2);//測試
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
(*HT)[s1].parent=i;
(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
//printf("%d\n",(*HT)[s1].parent);//測試
}
}
void Select(HuffmanTree HT,int m,int *s1,int *s2){//從這m個數裡邊選擇最小的2個//把第一個進行标記就ok
int i;//從下标為1的位置開始計數
//int min=HT[1].weight;這裡直接指派不合理，假如第一次那個1就是最小被選選中，那麼第2次還是被選中
int min1=1000;
int min2=1000;//規定一個特别大的數
for(i=1;i<=m;i++){
if(HT[i].parent==0&&min1>HT[i].weight){
min1=HT[i].weight;
*s1=i;
}
}
for(i=1;i<=m;i++){//注意這個I!=*s1标記min
if(i!=(*s1)&&HT[i].parent==0)
if(HT[i].weight<min2){
min2=HT[i].weight;
*s2=i;
}
}
}
void outHuffmanTree(HuffmanTree HT,int n){
if(HT==NULL)
printf("無huffmantree\n");
int i;
printf("輸出huffmantree表格\n");
printf("結點 weight parent lchild rchild\n");
//printf("%d %2d %6d %6d %6d",i,HT[4].weight,HT[4].parent,HT[4].lchild,HT[4].rchild);//ceshi
for(i=1;i<2*n;i++){//是2n-1個結點，申請了2n個位置0-2n-1（這是2n個用1-2n-1）
printf("%2d %6d %6d %6d %6d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
}
注意：1Select()函數在CreateHuffmanTree（）函數内部注意(*HT)因為你這個是在create函數裡邊，隻有一個（*HT）它指向主程式裡邊一個變量，變量裡的值就是那棵哈夫曼樹的位址
2 select（）函數裡邊不能用 //int min=HT[1].weight;這裡直接指派不合理，假如第一次那個1就是最小被選選中，那麼第2次還是被選中 這樣下面的for（i=2；）
3注意函數的指針部分。
運作結果
