哈夫曼樹課程設計報告

Ⅰ 哈夫曼樹的構造 編碼 解碼（數據結構的設計報告）

Huffman 編碼

一、實驗目的
熟悉Huffman編碼方法。
了解並弄懂Huffman編碼實現信息的無損壓縮原理。

二、實驗要求
熟悉C語言編程。

三、實驗內容
1.根據給定的n個權值(w1, w2, …, wn)構成n棵二叉樹的集合F={T1, T2, …, Tn}，其中每棵二叉樹Ti中只有一個帶樹為Ti的根結點
2.在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置其根結點的權值為其左右子樹權值之和
3.在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中
4.重復2, 3，直到F只含一棵樹為止

四、實驗步驟
1．用C語言實現二叉樹的說明
2．輸入n個權值，並生成n個二叉樹
3．對n個二叉樹逐步生成Huffman樹
4．對Huffman樹的每個葉子結點生成編碼

附：實驗程序
#include <stdio.h>
#define M 10
#define MAX 100

typedef struct
{
int data;
int pa,lc,rc;
}JD;

void huffman(int n,int w[],JD t[])
{ int i,j,k,x1,x2,m1,m2;
for(i=1;i<(2*n);i++)
{ t[i].pa=t[i].lc=t[i].rc=0;
if(i<=n)
t[i].data=w[i-1];
else
t[i].data=0;
}
for(i=1;i<n;i++)
{ m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{ if((t[j].data<m1)&&(t[j].pa==0))
{ m2=m1; x2=x1;
m1=t[j].data; x1=j;
}
else if((t[j].data<m2)&&(t[j].pa==0))
{ m2=t[j].data; x2=j; }
}
k=n+i;
t[x1].pa=t[x2].pa=k;
t[k].data=m1+m2;
t[k].lc=x1;
t[k].rc=x2;
}
}

void main()
{ int i,j,n=4;
static int w[]={7,5,2,4};
JD t[M];
huffman(n,w,t);
for(i=1;i<=2*n-1;i++)
printf("%d ,%d ,%d ,%d \n",t[i].lc,t[i].data,t[i].rc,t[i].pa);
printf("\n\n");
getch();
}

Ⅱ 數據結構課程設計 哈夫曼樹的應用

我在做軟體工程的課程設計 酒店管理系統的開發

Ⅲ 哈夫曼樹,赫夫曼樹...數據結構課程設計........如果正確....再追加分

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

#define MAX_INT 99999

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

typedef struct f
{
char a;
int count;
}ZHI_F;

typedef char **HuffmanCode;

int min(HuffmanTree &t,int i)
{
int j,flag;
int k=MAX_INT;
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=min(t,i);
s2=min(t,i);
}

void PrintHuffmanTree(HuffmanTree &HT,HuffmanCode &HC, int n)
{
int i, c, cdlen;
char *cd;
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));
c=2*n-1;
cdlen=0;
for(i=1; i<=c; ++i) HT[i].weight=0;
while(c) {
if(HT[c].weight==0) {
HT[c].weight=1;
if(HT[c].lchild==0 && HT[c].rchild==0) {
HC[c]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[c],cd);
}
if(HT[c].lchild!=0) {
c=HT[c].lchild;
cd[cdlen++]='0';
}
}
else if(HT[c].weight==1) {
HT[c].weight=2;
if(HT[c].rchild!=0) {
c=HT[c].rchild;
cd[cdlen++]='1';
}
}
else {
HT[c].weight=0;
c=HT[c].parent;
--cdlen;
}
}
free(cd);
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,i,s1,s2;

HuffmanTree p;

if(n<=1) return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1; i<=n; ++i,++p,++w) {
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(; i<=m; ++i,++p) (*p).parent=0;
for(i=n+1; i<=m; ++i) {
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;
}
PrintHuffmanTree(HT, HC, n);
}

void TongJ( ZHI_F *&T,int &num)
{
ZHI_F *t;
int i,n,m,r;
char ch,str[1500];
num=0;
t=(ZHI_F*)malloc(27*sizeof(ZHI_F));
scanf("%d",&n);
for(i=0;i<n;)
{
ch=getchar();
if(isalpha(ch))
{
str[i++]=ch;
}
}
for(i=1;i<27;i++)
{
t[i].a='A'+i-1;
t[i].count=0;
}
for(i=0;i<n;i++)
{
if(isalpha(str[i]))
{
m=(str[i]-'A')%32+1;
t[m].count++;
}
}

for(i=1;i<=26;i++)
if(t[i].count!=0)num++;
//printf("%d",num);
T=(ZHI_F*)malloc(num*sizeof(ZHI_F));
for(i=1,r=0;i<=26;i++)
if(t[i].count!=0)
{
T[r].a=t[i].a;
T[r].count=t[i].count;
r++;
}
//for(i=0;i<num;i++)
//printf("%c %d ",T[i].a,T[i].count);
}
void Sort(ZHI_F *&T,int &n)
{
int i,j,t;
char ch;

for(i=0;i<n;i++)
for(j=0;j<n-1;j++)
{
if(T[j].count<T[j+1].count)
{
t=T[j].count;
ch=T[j].a;
T[j].count=T[j+1].count;
T[j].a=T[j+1].a;
T[j+1].count=t;
T[j+1].a=ch;
}
}

}
int main()
{
ZHI_F *M;
int i,n,*a;
HuffmanTree HT;
HuffmanCode HC;

TongJ( M,n);
Sort(M,n);
a=(int*)malloc(n*sizeof(int));

for(i=0;i<n;i++)
{
*(a+i)=M[i].count;
}

HuffmanCoding(HT,HC,a,n);
for(i=1;i<=n;i++)
printf("%c %d %s\n",M[i-1].a,M[i-1].count,HC[i]);
return 0;
}
這個是統計個數然後再建哈夫曼樹。。。你改改，可能對你有幫助

Ⅳ 哈夫曼問題課程設計

#define MAXSIZE 100 /*結點允許的最大數量*/
#define MAXWEIGHT 32767 /*權值允許的最大值*/
#define n 6

typedef char elemtype;
typedef struct
{
char data; /*用戶自定義類型，存放結點的值*/
int weight; /*存放權值*/
int parent; /*父結點信息*/
int lchild; /*左孩子信息*/
int rchild; /*右孩子信息*/
}huffnode; /*哈夫曼樹結點類型*/
typedef struct
{
char cd[MAXSIZE];
int start;
}huffcode; /*自定義存放哈夫曼編碼的數據類型*/

void creathuffmamtree(huffnode ht[])
{
/*構造一棵哈夫曼樹*/
int i,k,l,r,min1,min2;

for (i=0;i<2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
for (i=n;i<2*n-1;i++) /*構造哈夫曼樹*/
{

min1=min2=MAXWEIGHT; /*為最小和次最小的權賦初值*/
l=r=0; /*L和R為最小權重的兩個結點位置*/
for (k=0;k<=i-1;k++)

if (ht[k].parent==0) /*選擇parent為零結點*/
if (ht[k].weight<min1) /*選擇最小和次最小的兩個結點*/
{
min2=min1;
r=l;
min1=ht[k].weight;
l=k;
}
else if (ht[k].weight<min2)
{
min2=ht[k].weight;
r=k;
}
printf("\n");

ht[l].parent=i;
printf(" lp%d",ht[l].parent);
ht[r].parent=i;
printf(" rp%d",ht[r].parent);
ht[i].weight=ht[l].weight+ht[r].weight;

printf(" lw%d",ht[l].weight);
printf(" rw%d",ht[r].weight);
printf(" iw%d",ht[i].weight=ht[l].weight+ht[r].weight);
ht[i].lchild=l;
printf(" il%d",l);
ht[i].rchild=r;
printf(" ir%d\n",r);

}

}
void creatHuffmancode (huffnode ht[],huffcode hcd[])
{
/*根據哈夫曼樹求哈夫曼編碼的演算法*/
int i,f,c;
huffcode d;
for (i=0;i<n;i++) /*逐個字元求哈夫曼編碼*/
{
d.start=n+1; /*編碼結束的位置*/
c=i;
ht[0].parent=6;
f=ht[i].parent;

while (f!=0) /*從葉子到根逆向求哈夫曼編碼*/
{
if (ht[f].lchild==c)
{/* printf("thenf:%d",f);*/

d.cd[--d.start]='1';
}
else
{ /*printf("elseF:%d",f);*/

d.cd[--d.start]='0';
}
c=f;
/*printf("ht[f].parent:%d",ht[f].parent);*/
f=ht[f].parent;
/* printf("F$%d",f); */
}
hcd[i]=d;
/* printf("hcd[i]:%d\n",hcd[i]);*/
}
}

void printhuffmancode(huffnode ht[],huffcode hcd[])
{
/*輸出哈夫曼編碼*/
int i,k;
printf ("shu chu ha fu man bian ma:\n");
for (i=0;i<n;i++) /*逐個字元依次輸出*/
{

printf(" %c:",ht[i].data); /*輸出結點數據域的值*/
for (k=hcd[i].start;k<=n;k++)
printf("%4c:",hcd[i].cd[k]); /*輸出字元編碼*/
printf("\n");
}
}

main()
{
huffnode ht[50];
huffcode hcd[50];
int j;
int w;
int g;
w=7;
while(w!=4)
{
printf("\n 哈夫曼\n");
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printf("| |");
printf("\n");
printf("| 1.構造一棵哈夫曼樹. |\n");
printf("| 2.根據哈夫曼樹求哈夫曼編碼的演算法. |\n");
printf("| 3.輸出哈夫曼編碼. |\n");
printf("| 4.退出. |\n");
printf("| |");
printf("\n");
printf("-------------------------------------------------------------\n");
printf("請輸入您的選擇(1,2,3,4)：");
scanf("%d",&w);
switch(w)
{
case 1:
{
for(j=0;j<n;j++)
{
printf("請輸入");
scanf("%d",&ht[j].weight);
}
creathuffmamtree (ht);break;
}
case 2: creatHuffmancode(ht,hcd);break;
case 3:
{/*for(g=0;g<6;g++)
{printf("ht[g].data:");
scanf("%c",&ht[g].data);} */
printhuffmancode(ht,hcd);break;}

default:break;
}
}
}

Ⅳ 哈夫曼樹 求詳細的設計報告

http://www.csdn.net/
這個網站有很多，超詳細的內...呵呵！容~