哈夫曼樹課程設計摘要
㈠ 哈夫曼問題課程設計
#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;
}
這個是統計個數然後再建哈夫曼樹。。。你改改，可能對你有幫助