哈夫曼树课程设计摘要

㈠ 哈夫曼问题课程设计

#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;
}
}
}

㈡ 求哈夫曼编译器的课程设计，主要想知道如何在TXT文件中存储哈夫曼树，又如何读取哈夫曼树。

主要是定义文件格式。这个不难。

㈢ 数据结构课程设计 哈夫曼树的应用

我在做软件工程的课程设计 酒店管理系统的开发

㈣ 紧急！数据结构课程设计 题目：哈夫曼树的建立（由键盘输入各个节点，并建立二叉树，能实现对二叉树的查询

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define N 20
#define M 2*N-1
char * cd;

typedef char *Huffmancode[N+1];
typedef struct
{
int weight;
int parent;
int LChild;
int RChild;
char c;
}HTNNOde,HuffmanTree[M+1];

void select(HuffmanTree p,int k,int *i,int *j)
{
int m,n=1;
while((n<=k)&&p[n].parent!=0) //寻找双亲节点为空的起始节点
{
++;
}
m=p[n].weight;
*i=n;
while(n<=k) //找最小的值
{
if(p[n].weight<m&&p[n].parent==0)
{
*i=n;
m=p[n].weight;
}
n++;
}
n=1;
while((n<=k&&p[n].parent!=0)||n==(*i))
{
n++;
}
m=p[n].weight;
*j=n;
while(n<=k) //找次小的值
{
if(p[n].weight<m&&n!=*i&&p[n].parent==0)
{
*j=n;
m=p[n].weight;

}
n++;
}
if(*i>*j)
{
n=*i;
*i=*j;
*j=n;
}

}

void creatHuffmanTree(HuffmanTree ht,int w[],int n)
{
int m=2*n-1,i,s1,s2;
for(i=1;i<=n;i++)
{
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}

for(i=n+1;i<=m;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
// printf("%d\n",ht[i].weight);
}
for(i=n+1;i<=m;i++)
{
select(ht,i-1,&s1,&s2); /*ht前i-1项选双亲为零且权最小的两结点*/
// 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[i].weight);
}
// i=1;

/* while(i<=9)
{printf("%d\n",ht[i].weight);
i++;}
*/
}

void CrtHuffmanCode(HuffmanTree ht,Huffmancode hc,int n,char w[N][20])
{
int i,p,c;
int start,j=1;
// char w[20][20];
cd=(char *)malloc(n*sizeof(char ));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{ start=n-1;
c=i;
p=ht[i].parent;
while ( p!=0)
{
--start;
if(ht[p].LChild == c)
cd[start]='0';
else cd[start]='1';
c=p;
p=ht[p].parent;
}

hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(hc[i],&cd[start]);
strcpy(w[j],hc[i]);
j++;
printf("%s\n",hc[i]);//实验性打印
}
}
void translationhuffman(char w[N][20],HuffmanTree ht,int n)
{
char litter[20];int i;char yes_no;
do
{
printf("输入哈夫曼编码编码\n");
scanf("%s",litter);

for(i=1;i<=n;i++)
if(strcmp(litter,w[i])==0)
{
printf("该密码对应的字母\n");
printf("%c",ht[i].c);
break;
}
if(i==n+1)
printf("无该密码对应字母\n");
printf(" \n要继续译码吗（Y/N）\n");
do
{
yes_no=getchar();
}while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');
}while(yes_no!='N'&&yes_no!='n');

}
main()
{

HuffmanTree ht;
Huffmancode hc;
int i,n;
int h[50];char w[N][20];
printf("请输入节点总个数");
scanf("%d",&n);
printf("请输入哈夫曼树权值和对应字母\n");
for(i=1;i<=n;i++)
scanf("%d %c",&h[i],&ht[i].c);
creatHuffmanTree(ht,h,n);
/* i=1;
while(i<=9)
{printf("%d\n",ht[i].weight);
i++;}*/
CrtHuffmanCode(ht,hc,n,w);
translationhuffman(w,ht,n);

}这是除过查询以外的所有功能都包含了，包括编码和译码，其余的你自己可以添加的，我调试过，没一点问题的

㈤ 求一个<哈夫曼编码>数据结构课程设计（C语言版）

我帮你测试了，这个可以满足你的要求！#include<stdio.h>
#include<stdlib.h>
#define max 50
struct a
{
int weight;
int parent,lchild,rchild;
};
struct b
{
char cd[max];
int start;
};
void main()
{
struct a ht[2*max];
struct b hcd[max],d;
int i,k,n,c,s1,s2,m1,m2,f;
printf("输入n:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("输入权值:");
scanf("%d",&ht[i].weight);
ht[i].parent=0;
}
for(;i<=2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
for(i=n+1;i<=2*n-1;i++)
{
m1=m2=30000;
s1=s2=0;
for(k=1;k<=i-1;k++)
{
if(ht[k].parent==0 && ht[k].weight<m1)
{
m2=m1;
s2=s1;
m1=ht[k].weight;
s1=k;
}
else if(ht[k].parent==0 && ht[k].weight<m2)
{
m2=ht[k].weight;
s2=k;
}
}
ht[s1].parent=ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
for(i=1;i<=n;i++)
{
d.start=n-1;
c=i;
f=ht[i].parent;
while(f)
{
if(ht[f].lchild==c)d.cd[--d.start]='0';
else d.cd[--d.start]='1';
c=f;
f=ht[f].parent;
}
hcd[i]=d;
}
printf("输出哈夫编码:");
for(i=1;i<=n;i++)
{
printf("%d ",ht[i].weight);
for(k=hcd[i].start;k<n-1;k++)
printf("%c",hcd[i].cd[k]);
printf(" ");
}
printf("\n");
}

㈥ 哈夫曼树,赫夫曼树...数据结构课程设计........如果正确....再追加分

#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;
}
这个是统计个数然后再建哈夫曼树。。。你改改，可能对你有帮助