陕西华泰建设陈安相片:哈夫曼问题课程设计

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>a
#include<graphics.h>
#define MAXVALUE 200 /*权值的最大值*/
#define MAXBIT 30 /*最大的编码位数*/
#define MAXNODE 30 /*初始的最大的结点数*/
struct haffnode
{char data;
int weight;
int flag;
int parent; /*双亲结点的下标*/
int leftchild; /*左孩子下标*/
int rightchild; /*右孩子下标*/
};
struct haffcode
{int bit[MAXNODE];
int start; /*编码的起始下标*/
char data;
int weight; /*字符权值*/
};

/*函数说明*/
/************************************************************************/
void pprintf(struct haffcode haffcode[],int n);
/*输出函数*/
void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[]);
/*建立哈夫曼树*/
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[]);
/*求哈夫曼编码*/
void test(struct haffcode haffcode[],int n);
/*测试函数*/
void end();
/*结束界面函数*/
/************************************************************************/

void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[])
/*建立叶结点个数为n，权值数组为weight[]的哈夫曼树*/
{int i,j,m1,m2,x1,x2;
/*哈夫曼树hafftree[]初始化，n个叶结点共有2n-1个结点*/
for(i=0;i<2*n-1;i++)
{if(i<n) {hafftree[i].data=data[i];
hafftree[i].weight=weight[i]; /*叶结点*/
}
else {hafftree[i].weight=0; /*非叶结点*/
hafftree[i].data='\0';
}
hafftree[i].parent=0; /*初始化没有双亲结点*/
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
hafftree[i].rightchild=-1;
}
for(i=0;i<n-1;i++) /*构造哈夫曼树n-1个非叶结点*/
{m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{if(hafftree[j].weight<m1&&hafftree[j].flag==0)
{m2=m1;
x2=x1;
m1=hafftree[j].weight;
x1=j;
}
else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
{m2=hafftree[j].weight;
x2=j;
}
}
hafftree[x1].parent=n+i;
hafftree[x2].parent=n+i;
hafftree[x1].flag=1;
hafftree[x2].flag=1;
hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
hafftree[n+i].leftchild=x1;
hafftree[n+i].rightchild=x2;

}
}
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[])
{/*由n个结点的哈夫曼树hafftree[]构成的哈夫曼编码haffcode[]*/
int i,j,child,parent;
struct haffcode newcode;
struct haffcode *cd;
cd=&newcode;
for(i=0;i<n;i++) /*求n个结点的哈夫曼编码*/
{cd->start=MAXBIT-1; /*不等长编码的最后一位是n-1*/
cd->weight=hafftree[i].weight;
cd->data=hafftree[i].data; /*取得编码对应值的字符*/
child=i;
parent=hafftree[child].parent;
while(parent!=0)
{if(hafftree[parent].leftchild==child)
cd->bit[cd->start]=0; /*左孩子编码为0*/
else
cd->bit[cd->start]=1; /*右孩子编码为1*/
cd->start--;
child=parent;
parent=hafftree[child].parent;
}
for(j=cd->start+1;j<MAXBIT;j++) /*保存每个叶结点的编码和等长编码的起始位*/
haffcode[i].bit[j]=cd->bit[j];
haffcode[i].data=cd->data;
haffcode[i].start=cd->start;
haffcode[i].weight=cd->weight;
}
}
void pprintf(struct haffcode myhaffcode[],int n)
{int i,j,count=0;
clrscr();
for(i=0;i<n;i++)
{textcolor(YELLOW);
cprintf("字符=%c",myhaffcode[i].data);
printf(" ");
textcolor(YELLOW);
cprintf("weight=%3d",myhaffcode[i].weight);
printf(" ");
textcolor(YELLOW);
cprintf("haffcode=");
for(j=myhaffcode[i].start+1;j<MAXBIT;j++)
cprintf("%d",myhaffcode[i].bit[j]);
printf("\n");
count++;
if(count==21)
getch();

}
}
void test(struct haffcode haffcode[],int n)
{int i,j,k,s;
char sstring[MAXNODE];
struct haffcode newhaffcode[MAXNODE];
j=0;
clrscr();
textcolor(YELLOW);
cprintf("请输入哈夫曼编码测试数据，在此建议为'this programme is my favorite'");
printf("\n");
cprintf("注意小写,空格由大写字母T代替，并且字符数小于27.\n");
scanf("%s",sstring);
if(strlen(sstring)>=MAXNODE)
{printf("you input the data number >=MAXNODE.");
exit(1);
}
for(i=0;i<strlen(sstring);i++)
{
for(j=0;j<MAXBIT;j++)
if(sstring[i]==haffcode[j].data)
{
k=j;
break;
}
if(k<0||k>MAXNODE-1)
{printf("在系统中找不到与第个%d字符相匹配的编码\n",i+1);
continue;
}
newhaffcode[i].start=haffcode[k].start;
newhaffcode[i].weight=haffcode[k].weight;
newhaffcode[i].data=haffcode[k].data;
for(s=haffcode[k].start+1;s<MAXBIT;s++)
newhaffcode[i].bit[s]=haffcode[k].bit[s];
}

pprintf(newhaffcode,strlen(sstring));
}
void end()
{int driver,mode;
driver=VGA;
mode=VGAHI;
initgraph(&driver,&mode," ");
setlinestyle(0,0,2);
setfillstyle(1,9);
bar(120,60,520,80);
setfillstyle(1,9);
bar(90,100,550,350);
moveto(121,65);
settextstyle(5,0,6);
setcolor(7);
outtext("This programme is designed by Dou Zheren");
settextstyle(3,0,3);
setcolor(7);
moveto(150,200);
outtext("thank you use this programme.");
moveto(100,300);
settextstyle(3,0,2);
setcolor(7);
outtext("please press anykey to end this programme.");
}
void main()
{
int i,j,n=27;
int driver=VGA,mode=VGAHI;
char ch;
int weight[27]={186,64,13,22,32,103,21,15,47,
57,1,5,32,20,57,63,15,1,48,
51,80,23,8,18,1,16,1};
char data[28]={'T','a','b','c','d','e','f','g','h',
'i','j','k','l','m','n','o','p','q',
'r','s','t','u','v','w','x','y','z'};
struct haffnode newhaffnode[2*MAXNODE-1];
struct haffcode newcode[MAXNODE];
struct haffnode *myhafftree=newhaffnode;
struct haffcode *myhaffcode=newcode;
if(n>MAXNODE)
{printf("you input the haffnode > MAXNODE,so you input the data is wrong");
printf("\n");
exit(1);
}
clrscr();
textcolor(YELLOW);
cprintf("WELCOME!这是一个求哈夫曼编码的问题");
printf("\n");
cprintf("即对所有的字母进行编码后，在根据用户的需要，对用户的要求进行编码。");
printf("\n");
cprintf("注意：本程序只支持小写字母，空格用大写字母T代替! ");
printf("\n");
getch();
textcolor(YELLOW);
cprintf("Ready?Enter,if you want to begin!\n");
printf("\n");
getch();
cprintf("Now，开始演示哈夫曼编码.");
getch();
haffmantree(weight,n,myhafftree,data);
haffmancode(myhafftree,n,myhaffcode);
pprintf(myhaffcode,n);
clrscr();
printf("若执行自定义编译，请输入y继续。否则程序将结束.");
if((ch=getch())=='y'||ch=='Y')
test(myhaffcode,n);
getch();
clrscr();
end();
getch();
exit(1);
}

我已经编好了,只是在这不支持,我又不想让我的心血白流,所以我上串到了我网络硬盘了
http://klyun50.ys168.com
你看我上串上来的就是这些了

0 1

0 1 0 1

0 1

0 1

所以 A 为0110
B 为0111
C 为010
D 为00
E 为10
F为 11
WPL=2*22+12*3+7*4+9*4+23*2+27*2=44+36+28+36+46+54=242
编码你自己就可以根据它们对应的代码去写了。

我在共享里面放着呢。没有密码！