哈夫曼树课程设计报告

Ⅰ 哈夫曼树的构造 编码 译码（数据结构的设计报告）

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/
这个网站有很多，超详细的内...呵呵！容~