哈夫曼樹的順序存儲形式

⑴ 哈夫曼樹，我這樣構造對不對，如果對，還有另外的一種形式嗎

八個權值是529781423311

(1)從小到大排序357811142329(這是有序序列)
(2)每次提取最小的兩個結點,取結點3和結點5,組成新結點N8,其權值=3+5=8,
取數值較小的結點作為左分支,結點3作為左分支,而結點5就作為右分支.
(3)將新結點N8放入有序序列,保持從小到大排序:
78N811142329[注意,新結點N8排在原結點8的後面]
(4)重復步驟(2),提取最小的兩個結點,結點7與結點8組成新結點N15,其權值=7+8=15,
結點7的數值較小,將結點7作為左分支,結點8就作為右分支.
(5)將新結點N15放入有序序列,保持從小到大排序:
N81114N152329
(6)重復步驟(2),提取最小的兩個結點,N8與結點11組成新結點N19,其權值=8+11=19,
N8的數值較小,作為左分支,結點11就作為右分支.
(7)將新結點N19放入有序序列,保持從小到大排序:
14N15N192329
(8)重復步驟(2),提取最小的兩個結點,結點14與N15組成新結點N29,其權值=14+15=29,
結點14的數值較小,作為左分支,N15就作為右分支.
(9)將新結點N29放入有序序列,保持從小到大排序:
N192329N29[注意,新結點N29排在原結點29的後面]
(10)重復步驟(2),提取最小的兩個結點,N19與結點23組成新結點N42,其權值=19+23=42,
N19的數值較小,作為左分支,結點23就作為右分支.
(11)將新結點N42放入有序序列,保持從小到大排序:
29N29N42
(12)重復步驟(2),提取最小的兩個結點,結點29與N29組成新結點N58,其權值=29+29=58,
結點29與N29的數值相同,將原結點29作為左分支,N29就作為右分支.
(13)將新結點N58放入有序序列,保持從小到大排序:
N42N58
(14)重復步驟(2),提取剩下的兩個結點,N42與N58組成新結點N100,其權值=42+58=100,
數值較小的N42作為左分支,N58就作為右分支.
最後得到"哈夫曼樹":

N100
/
N42N58
//
N192329N29
//
N81114N15
//
3578

帶權路徑長度(WPL):
根結點N100到結點29的路徑長度是2,結點29的帶權路徑長度是29*2
根結點N100到結點23的路徑長度是2,結點23的帶權路徑長度是23*2
根結點N100到結點14的路徑長度是3,結點14的帶權路徑長度是14*3
根結點N100到結點11的路徑長度是3,結點11的帶權路徑長度是11*3
根結點N100到結點8的路徑長度是4,結點8的帶權路徑長度是8*4
根結點N100到結點7的路徑長度是4,結點7的帶權路徑長度是7*4
根結點N100到結點5的路徑長度是4,結點5的帶權路徑長度是5*4
根結點N100到結點3的路徑長度是4,結點3的帶權路徑長度是3*4
所以,哈夫曼樹的帶權路徑長度(WPL)等於
29*2+23*2+14*3+11*3+8*4+7*4+5*4+3*4=271

哈夫曼編碼:
規定哈夫曼樹的左分支代表0,右分支代表1.
從根結點N100到結點29,先經歷右分支,再經歷左分支,結點29的編碼就是10
從根結點N100到結點23,先經歷左分支,再經歷右分支,結點23的編碼就是01
從根結點N100到結點14,經歷兩次右分支,再經歷左分支,結點14的編碼就是110
如此類推,得出所有結點的"哈夫曼編碼":
權值29:10
權值23:01
權值14:110
權值11:001
權值8:1111
權值7:1110
權值5:0001
權值3:0000


//C語言測試程序:

//輸入葉子結點的總個數:8
//連續輸入8個權值:529781423311
//Weight=5Code=0001
//Weight=29Code=10
//Weight=7Code=1110
//Weight=8Code=1111
//Weight=14Code=110
//Weight=23Code=01
//Weight=3Code=0000
//Weight=11Code=001
//huffman'sWPLis:271

#include<stdio.h>
#include<stdlib.h>

#defineMaxValue10000//初始設定的權值最大值
#defineMaxBit10//初始設定的最大編碼位數
#defineMaxN10//初始設定的最大結點個數
structHuffNode//哈夫曼樹的結點結構
{
intweight;//權值
intflag;//標記
intparent;//雙親結點下標
intleftChild;//左孩子下標
intrightChild;//右孩子下標
};
structCode//存放哈夫曼編碼的數據元素結構
{
intbit[MaxBit];//數組
intstart;//編碼的起始下標
intweight;//字元的權值
};

//建立葉結點個數為n權值為weight的哈夫曼樹huffTree
voidHuffman(intweight[],intn,structHuffNodehuffTree[])
{
inti,j,m1,m2,x1,x2;
//哈夫曼樹huffTree初始化。n個葉結點的哈夫曼樹共有2n-1個結點
for(i=0;i<2*n-1;i++)
{
if(i<n)
{
huffTree[i].weight=weight[i];
}
else
{
huffTree[i].weight=0;
}
huffTree[i].parent=0;
huffTree[i].flag=0;
huffTree[i].leftChild=-1;
huffTree[i].rightChild=-1;
}
//構造哈夫曼樹huffTree的n-1個非葉結點
for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;//Maxvalue=10000;(就是一個相當大的數)
x1=x2=0;//x1、x2是用來保存最小的兩個值在數組對應的下標

for(j=0;j<n+i;j++)//循環找出所有權重中，最小的二個值
{
if(huffTree[j].weight<m1&&huffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=huffTree[j].weight;
x1=j;
}
elseif(huffTree[j].weight<m2&&huffTree[j].flag==0)
{
m2=huffTree[j].weight;
x2=j;
}
}
//將找出的兩棵權值最小的子樹合並為一棵子樹
huffTree[x1].parent=n+i;
huffTree[x2].parent=n+i;
huffTree[x1].flag=1;
huffTree[x2].flag=1;
huffTree[n+i].weight=huffTree[x1].weight+huffTree[x2].weight;
huffTree[n+i].leftChild=x1;
huffTree[n+i].rightChild=x2;
}
}
//由n個結點的哈夫曼樹huffTree構造哈夫曼編碼huffCode
voidHuffmanCode(structHuffNodehuffTree[],intn,structCodehuffCode[])
{
structCode*cd=(structCode*)malloc(sizeof(structCode));
intchild,parent;
inti,j;
//求n個葉結點的哈夫曼編碼
for(i=0;i<n;i++)
{
cd->start=0;//從0開始計數
cd->weight=huffTree[i].weight;//取得編碼對應權值的字元
child=i;
parent=huffTree[child].parent;
//由葉結點向上直到根結點
while(parent!=0)
{
if(huffTree[parent].leftChild==child)
{
cd->bit[cd->start]=0;//左孩子結點編碼0
}
else
{
cd->bit[cd->start]=1;//右孩子結點編碼1
}
cd->start++;//編碼自增
child=parent;
parent=huffTree[child].parent;
}
//重新修改編碼，從根結點開始計數
for(j=cd->start-1;j>=0;j--)
{
huffCode[i].bit[cd->start-j-1]=cd->bit[j];
}
huffCode[i].start=cd->start;
huffCode[i].weight=cd->weight;//保存編碼對應的權值
}
}
intmain()
{
inti,j;
intm=0;
intn=0;
intweight[20];

printf("輸入葉子結點的總個數:");
scanf("%d",&n);
printf("連續輸入%d個權值:",n);
for(i=0;i<n;i++)
{
scanf("%d",&weight[i]);
}
structHuffNode*myHuffTree=(structHuffNode*)malloc((2*n-1)*sizeof(structHuffNode));
structCode*myHuffCode=(structCode*)malloc(n*sizeof(structCode));
if(n>MaxN)
{
printf("
定義的n越界，修改MaxN!
");
exit(0);
}
Huffman(weight,n,myHuffTree);
HuffmanCode(myHuffTree,n,myHuffCode);
//輸出每個葉結點的哈夫曼編碼
for(i=0;i<n;i++)
{
printf("Weight=%-4dCode=",myHuffCode[i].weight);
for(j=0;j<myHuffCode[i].start;j++)
{
printf("%d",myHuffCode[i].bit[j]);
}m=m+myHuffCode[i].weight*myHuffCode[i].start;

printf("
");
}
printf("huffman'sWPLis:%d
",m);

	getchar();

return0;
}

⑵ 哈夫曼樹

這是我們的作業題，自己寫 的……（可能輸入的格式跟你要的不一致，自己改一下）

如果有什麼不懂的就問我，我可以把其中所有相關的文件發給你 ^^

註：1、 初始化創建哈夫曼樹有三種選擇，其中選擇編譯課本測試數據時和編譯源文件是，調用的輸入文件分別是：test.txt和input.txt；字母的哈夫曼編碼都保存在文件：hmfTree.txt；
2、 用戶自定義模式下，需要編碼的文件內容保存在ToBeTran.txt中；課本測試數據和源文件代碼分別保存在course.txt和sorse.txt中，在（1）中選擇不同的選項，則在編碼時調用相應的文件進行編碼，編碼結果保存在文件CodeFile.txt中。
3、 文件解碼時，調用文件CodeFile.txt進行解碼，得到的結果保存在文件TextFile.txt中。
4、 列印代碼文件：調用CodeFile.txt，結果顯示在終端並保存在文件CodePrin.txt中。
5、 列印哈夫曼樹：用凹入表形式把哈夫曼樹顯示在終端，同時將它保存在文件TreePrint..txt中。

#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;

typedef struct {
unsigned int weight;
char ch1;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

typedef struct {
char ch;
char code[7];
}codenode,*code;

void select(HuffmanTree HT,int n,int & s1,int &s2){ //從哈夫曼樹中選擇出最小的兩個節點
for(int i=1;i<=n;i++)
if(!HT[i].parent){
s1=i; break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i; break;
}
if(HT[s1].weight-HT[s2].weight){
int temp; temp=s1; s1=s2; s2=temp;
}
for(i=1;i<=n;i++) //對數組進行遍歷，尋找最小的兩個節點
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}

void prin(){ //終端輸出選擇菜單
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---創建哈夫曼樹 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件編碼 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件解碼 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---列印代碼文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼樹 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼樹的存儲結構 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("選擇菜單功能選項：");
}

void output (HuffmanTree th,int n){ //輸出哈夫曼樹的存儲結構
int i=0;
cout<<"序號"<<" "<<"字元"<<" "<<"雙親"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"權值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight <<endl;
}
}

void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //創建哈夫曼樹
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定義 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 2---編碼課本測試數據 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 3---編碼源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("選擇菜單功能選項：");
scanf("%d",&k);
if(k==1){
printf("輸入需要編碼的字元總數: ");
scanf("%d",&n);
printf("\n輸入需要編碼字元的權值:\n");
for(int d=0;d<n;d++) {
scanf("%d",&w[d]);
}
printf("\n輸入需要編碼的字元串: ");
scanf("%s",ch);
}
else if(k==2){
ifstream fin2 ("test.txt");
fin2>>n;
for(int d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else if(k==3){
ifstream fin1 ("input.txt");
fin1>>n;
for(int d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int s1,s2,i,num=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
}
for(i=n+1;i<=num;i++){
select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1;
HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
char * temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int start=n-1;
for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream fout ("hfmTree.txt");
fout<<ch<<endl;
for(int j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}

void encoding(int n,int select){ //編碼：對文件TobeTran.txt進行解碼
char a[100],b[100][20];
ifstream fin ("hfmTree.txt");
fin>>a;
for(int j=0;j<n;j++) fin>>b[j];
fin.close();
ifstream fin1 ("course.txt");
ifstream fin2 ("sorse.txt");
ifstream fin3 ("ToBeTran.txt");
char s[1000];
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
ofstream fout ("CodeFile.txt");
while(s[0]!='\0'){
for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
for(int g=0;a[g]!=s[i];g++) ;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}

void decoding(HuffmanTree ht,int n){ //解碼：對CodeFile.txt文件進行解碼
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
char s[500];
fin>>s;
HuffmanTree head=ht+2*n-1;
int i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild;
else if(s[i]=='0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<' ' ;
i=0;
fin>>s;
}
fin.close();
fout.close();
}

void Print(){ //列印代碼文件，顯示在終端，每行50個代碼
ifstream fin ("CodeFile.txt");
char s[2000];
int j=0;
int i=1;
fin>>s;
ofstream fout ("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}

void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //列印哈夫曼樹形（在參數的傳遞上，是文科給自己提出的意見才很好的解決了之後的操作難題^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//這個挺有用的：在文件末尾加入內容
for( int i = 0; i < level; i++ ) {
fout<<"|……";
printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}

void main(){
int select;
int n;
char ch[100];
int w[100];
HuffmanTree HT=NULL;
HuffmanCode hc=NULL;
prin();
char c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case 'E':
encoding(n,select);
prin();
break;
case 'D':
decoding(HT,n);
prin();
break;
case 'P':
Print();
prin();
break;
case 'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case 'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}

}

註：
input.txt文件中保存一下數據：
88
56
26
89
45
62
78
61
13
20
29
89
46
51
25
86
123
20
10
9
57
6
1
57
62
2
37
61
15
19
89
91
2
8
19
49
67
18
19
64
35
67
61
61
84
20
30
50
84
19
28
84
67
31
67
29
20
10
56
56
12
23
56
23
45
85
16
29
94
68
35
97
58
21
29
3
94
58
16
21
64
29
84
64
59
19
48
37
186
!,./;':[]\1234567890-=+)(*&%$#<>"|{}

⑶ 哈夫曼樹HT存儲結構的初態和末態怎麼寫

定義哈夫曼樹與編碼的存儲結構與數據類型
typedef struct
{
char data;//節點值
int weight; //權重
int parent; //雙親節點
int lchild; //左孩子節點
int rchild; //右孩子節點
} HTNode;

typedef struct
{
char cd[N]; //存放哈夫曼碼
int start;
} HCode;
void CreateHT(HTNode ht[],int n) //創建哈夫曼樹
void CreateHCode(HTNode ht[],HCode hcd[],int n) //根據哈夫曼樹計算每個元素的哈夫曼編碼
void DispHCode(HTNode ht[],HCode hcd[],int n) //輸出每個元素的哈夫曼編碼

⑷ 數據結構-構造哈夫曼樹

填空題
1.2的k-1次冪
2.根
3.中續
4.(log2n)+1
5.鏈式存儲
6.最小
7.n-1
8.5
9.每個頂點的訪問次數
10.任意
單選
1.B
2.D
3.C
4.B
5.A
6.A
7.B
8.B
9.B
10.C
判斷
1.對
2.對
3.對
4.錯
5.對
6.對
7.對
8.錯
9.對
10.對
綜合
36
有的不確定啊！

⑸ 哈夫曼編碼

/* algo6-1.c 求哈夫曼編碼。實現演算法6.12的程序 */
//------------------- 公用的常量和類型 ----------------------------
#include<stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
//函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define UINT_MAX 1000
typedef int Status;

/* c6-7.h 哈夫曼樹和哈夫曼編碼的存儲表示 */
typedef struct HTNode
{
char leaf;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 動態分配數組存儲哈夫曼編碼表 */

typedef char **HuffmanCode; /* 動態分配數組存儲哈夫曼編碼表 */
typedef struct Node
{
char leaf;
unsigned int weight;
struct Node * next;
}LeafNode,*LeafLink;

typedef struct
{
LeafLink head;
unsigned len;
}LeafLinkList;

int min1(HuffmanTree t,int i)
{ /* 函數void select()調用 */
int j,flag;
unsigned int k=UINT_MAX; /* 取k為不小於可能的值 */
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* s1為最小的兩個值中序號小的那個 */
int j;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1>*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, LeafLinkList L) /* 演算法6.12 */
{ /* w存放n個字元的權值(權值均需大於0),構造哈夫曼樹HT,並求出n個字元的哈夫曼編碼HC*/
int m,i,s1,s2,start;
int n=L.len;
unsigned c,f;
LeafLink ptr;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
printf("表長為%d\t哈夫曼樹含節點數為%d\n",n,m);
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0號單元未用 */
ptr=L.head->next;
for(p=HT+1,i=1;i<=n;++i,++p,ptr=ptr->next)
{
(*p).leaf=ptr->leaf;
printf("%d\t",(*p).leaf);
(*p).weight=ptr->weight;
printf("%d\n",(*p).weight);
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
{
(*p).parent=0;
(*p).leaf=0;
}
for(i=n+1;i<=m;++i) /* 建哈夫曼樹 */
{ /* 在HT[1~i-1]中選擇parent為0且weight最小的兩個結點,其序號分別為s1和s2 */
select(HT,i-1,&s1,&s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/* 從葉子到根逆向求每個字元的哈夫曼編碼 */
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/* 分配n個字元編碼的頭指針向量([0]不用) */
cd=(char*)malloc(n*sizeof(char)); /* 分配求編碼的工作空間 */
cd[n-1]='\0'; /* 編碼結束符 */
for(i=1;i<=n;i++)
{ /* 逐個字元求哈夫曼編碼 */
start=n-1; /* 編碼結束符位置 */
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
/* 從葉子到根逆向求編碼 */
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
/* 為第i個字元編碼分配空間 */
strcpy(HC[i],&cd[start]); /* 從cd復制編碼(串)到HC */
}
free(cd); /* 釋放工作空間 */
for(i=1;i<=n;i++)
{
printf("%c編碼為%s:\n",HT[i].leaf,HC[i]);
}
}

void InitLeafList(LeafLinkList &L)
{
L.head=(LeafLink)malloc(sizeof(LeafLink));
L.head->next=NULL;
L.len=0;
}
void PrintList(LeafLinkList L)
{
LeafLink p;
p=L.head->next;
printf("列印鏈表\n");
printf("表長為%d\n",L.len);
while(p!=NULL)
{
printf("%c or %d,%u\t",p->leaf,p->leaf,p->weight);
printf("列印一個節點\n");
p=p->next;
}
printf("列印結束\n");
printf("\n");
}

void EnLeafList(LeafLinkList &L,char ch)
{
LeafLink p,pre,temp;
int flag=0;
pre=p=L.head;
printf("%d即為%c******\n\n",ch,ch);
if(p->next==NULL) //p->next=NULL則為第一次插入操作
{
printf("第一次插入\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
p->next=temp;
L.len++;
}

else
{

p=p->next;
while(p!=NULL)
{

if(ch==p->leaf)
{
p->weight++;
printf("加權\n");
p=NULL;
flag=1;
} //權重加一
else if(ch<p->leaf) //插入
{
printf("插入A\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=p;
pre->next=temp;
L.len++;
flag=1;
p=NULL;
}
else //繼續尋找插入點
{
pre=p;
p=p->next;
}
}

if(p==NULL&&flag!=1) //若p=NULL則插到鏈尾
{
printf("插入B\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
pre->next=temp;
L.len++;
}
}

}
void EnCoding()
{
FILE *fp,*fr,*fc;
HuffmanTree HT;
HuffmanCode HC;
int i,n;
LeafLinkList L;
InitLeafList(L);
char filename[15];
char ch;
printf("請輸入文件名:\n ");
scanf("%s",filename);
if( !(fp=fopen(filename,"r")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
ch=getchar(); //接收執行scanf語句時最後輸入的回車符
printf("文件已經打開\n");
while(!feof(fp))
{

ch=fgetc(fp);
if(ch==-1)
{
printf("結束統計\n");
}
else
{
EnLeafList(L,ch);
}
}
PrintList(L);
HuffmanCoding(HT,HC, L);
n=L.len;
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
char TreeName[15];
printf("把哈夫曼樹存入文件，請輸入文件名:\n ");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"wb")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
ch=getchar(); //接收執行scanf語句時最後輸入的回車符
printf("文件已經打開\n");
//把哈夫曼樹存入文件
printf("%d\n",n);
printf("把樹的長度先存入\n");
putw(n,fr); //把樹的長度先存入
for(i=1;i<=2*n-1;i++)
if(fwrite(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件寫入出錯\n");
fclose(fr);

printf("列印原來的樹\n");
for(i=1;i<=2*n-1;i++)
printf("%c %u %u %u %u\n",HT[i].leaf ,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild );
fclose(fr);

printf("把編碼結果存入文件，請輸入文件名:\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"wb")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
ch=getchar(); //接收執行scanf語句時最後輸入的回車符

printf("待編碼的文件位置指針重新指向開始位置\n");
printf("對待編碼文件進行編碼，編碼同步顯示，並將結果存入指定的文件\n");
rewind(fp);
while(!feof(fp))
{

ch=fgetc(fp);
printf("%c\n",ch);
if(ch==-1)
{
printf("結束編碼\n");
}
else
{
for(int tap=0,i=1;tap==0&&i<=n;) //查找，該葉子對應的編碼串
{
if(ch==HT[i].leaf) //找到，列印出對應的編碼，並存入文件
{
printf("%s\n",HC[i]);
fputs(HC[i],fc); //將編碼字元串存入文件

tap=1;
}
else
{
i++;
}
}
}
}
fclose(fp); //關閉文件
fclose(fc); //關閉文件
}
int decode(FILE *fc,HuffmanTree HT,int n)
{
while(!feof(fc))
{
char ch=fgetc(fc);
if(ch=='0')
{
n=HT[n].lchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else if(ch=='1')
{

n=HT[n].rchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else return OK;
}
return ERROR;
}

void Decoding() //解碼文件，並將結果顯示出來
{
FILE *fc,*fr;
char CodeFileName[15],ch,TreeName[15];
int i;
printf("解碼文件，請輸入文件名(如*.dat):\n ");
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
ch=getchar(); //接收執行scanf語句時最後輸入的回車符
printf("存放編碼結果文件已經打開\n");

//讀入哈夫曼樹

HuffmanTree HT;
printf("取出對應的哈夫曼樹文件，請輸入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打開存放哈夫曼樹的文件
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
int n=getw(fr); //將葉子數目取出
printf("葉子數目%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然後分配空間，0號單元未用 */

for(i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件讀出出錯\n");
int length=2*n-1; //總長度
printf("總結點數目為：%d\n",n);
printf("該文件解碼後得到的源文件為：\n");
printf("**************************************\n");
while(!feof(fc))
{
decode(fc,HT,length);
}
printf("**************************************\n");
printf("\n\n");
}

int PreOrderPrint(HuffmanTree HT,int n,int count)
{
if(HT[n].lchild)
{
for(int i=0;i<count;i++)
printf(" ");
printf("%u\n",HT[n].weight);
if( PreOrderPrint(HT,HT[n].lchild, ++count) )
if (PreOrderPrint(HT,HT[n].rchild, ++count))
return OK;
return ERROR;
}
else return OK;
}
void PrintTree()
{
//讀入哈夫曼樹
FILE *fr;
char TreeName[15];
HuffmanTree HT;
printf("取出對應的哈夫曼樹文件(如*.dat)，請輸入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打開存放哈夫曼樹的文件
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}
int n=getw(fr); //將葉子數目取出
printf("含葉子數%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然後分配空間，0號單元未用 */

for(int i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件讀出出錯\n");
int count=0;
n=2*n-1;
printf("總結點數目為；%d\n",n);
printf("哈夫曼樹的存儲形式為：\n");
for(i=1;i<=n;i++)
{
printf("%c,%u,%u,%u,%u\n",HT[i].leaf,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
printf("哈夫曼樹的凹入表形式為：\n");
PreOrderPrint(HT,n,count);
}
void PrintCodeFile()
{
FILE *fc;
printf("列印編碼後的文件，請輸入文件名(如*.dat):\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);

if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打開文件失敗，請輸入正確的文件名!! ");
exit(0);
}

char ch=getchar(); //接收執行scanf語句時最後輸入的回車符
printf("列印編碼後的文件，列印方法一\n");
int flag=1;
while(!feof(fc))
{

ch=fgetc(fc);
if(ch==-1)
{
printf("結束列印\n");
}
else
{
printf("%c",ch);
if(flag<=49)
flag++;
else
{
flag=1;
printf("\n");
}
}
}
printf("列印編碼後的文件，列印方法二\n");
rewind(fc);
char str[50];
while(!feof(fc))
{
fgets(str,51,fc);
puts(str);
}
fclose(fc); //關閉文件
}

void Initialization() //系統初始化
{
printf("**************************************\n");
printf("*編碼文件請輸入e\n*解碼文件請輸入d\n*列印編碼後的文件請輸入p\n*列印哈夫曼樹請輸入t\n*結束請輸入q \n");
printf("**************************************\n");
printf("\n\n\t\t字元:\n\n\n");
printf("**************************************\n");
printf("* 輸入一個字元:e,d,p,t or q *\n");
printf("**************************************\n");
}

int read(char cmd)
{
int i,flag=0;
char choice[10]={'e','E','d','D','p','P','T','t','Q','q'};
for(i=0;i<10;i++)
{
if(cmd==choice[i]) flag++;
}
if(flag==1) return FALSE;
else return TRUE;
}
void ReadCommand(char &cmd) // 讀入操作命令符
{
do
{
cmd=getchar();
}
while(read(cmd));
}
void Interpret(char cmd) //解釋執行操作命令
{
switch(cmd)
{
case 'e':case'E':
EnCoding();
Initialization();
break;
case 'd':case'D':
Decoding();
Initialization();
break;
case 'p':case'P':
PrintCodeFile();
Initialization();
break;
case't':case'T':
PrintTree(); // Print();
Initialization();
break;
case 'q': case'Q': exit(0);
break;
default: printf("Error\n");break;
}
}
void main() //用戶驅式
{
char cmd;
Initialization(); //初始化
do
{
ReadCommand(cmd); //讀入一個操作命令符
Interpret(cmd); //解釋執行操作命令符
}
while(cmd!='q'&&cmd!='Q');
EnCoding();
Decoding();

}

⑹ 什麼是哈夫曼樹呢

夫曼樹是帶權路徑長度最小的二叉樹，用途是平均查找信息的代價最小。
普通二叉樹的用途也普通，比較通用，就是信息存儲和查找。
普通二叉樹可能有的只有一個子節點，而哈夫曼樹一定有兩個。

⑺ 「哈夫曼樹」的建立方法是什麼

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 k1、k2、…、kn，則哈夫曼樹的構造規則為：

(1) 將k1、k2、…，kn看成是有n 棵樹的森林(每棵樹僅有一個結點)；

(2) 在森林中選出兩個根結點的權值最小的樹合並，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；

(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

⑻ 哈夫曼樹是什麼求解

哈夫曼編碼是哈夫曼樹的一個應用。哈夫曼編碼應用廣泛，如JPEG中就應用了哈夫曼編碼。
首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
哈夫曼在上世紀五十年代初就提出這種編碼時，根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。（註：碼字即為符號經哈夫曼編碼後得到的編碼，其長度是因符號出現的概率而不同，所以說哈夫曼編碼是變長的編碼。）
一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現演算法，一般還要求以Ti的權值Wi的升序排列。）
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。
用C語言實現上述演算法，可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構： struct tree{
float weight; /*權值*/union{char leaf; /*葉結點信息字元*/
struct tree *left; /*樹的左結點*/};struct tree *right; /*樹的右結點*/};struct forest{ /*F集合，以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/};例：若字母A，B，Z，C出現的概率為：0.75,0.54,0.28,0.43；則相應的權值為：75，54，28，43。
構造好哈夫曼樹後，就可根據哈夫曼樹進行編碼。例如：上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼，即任一個字元的編碼都不是另一個字元的編碼的前綴，否則，編碼就不能進行翻譯。例如：a,b,c,d的編碼為：0，10，101，11，對於編碼串：1010就可翻譯為bb或ca，因為b的編碼是c的編碼的前綴。剛才進行哈夫曼編碼的規則是從根結點到葉結點（包含原信息）的路徑，向左孩子前進編碼為0，向右孩子前進編碼為1，當然你也可以反過來規定。
這種編碼方法是靜態的哈夫曼編碼，它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。 靜態哈夫曼編碼方法有一些缺點：一、對於過短的文件進行編碼的意義不大，因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間；二、進行哈夫曼編碼，存儲編碼信息時，若用與通訊網路，就會引起較大的延時；三、對較大的文件進行編碼時，頻繁的磁碟讀寫訪問會降低數據編碼的速度。
因此，後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與演算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼，並不是說JPEG就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟後得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。

⑼ 【問題描述】

nan