数据结构试验实验程序代码下载.docx
《数据结构试验实验程序代码下载.docx》由会员分享，可在线阅读，更多相关《数据结构试验实验程序代码下载.docx（9页珍藏版）》请在冰点文库上搜索。
数据结构试验实验程序代码下载
第一个程序，未运行验证
#include
#include
#include
#include
#defineletter
#defineN2400
#defineMAX100
typedefstruct{
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode;
voidSelect（HTNode*HT,inti,int&s1,int&s2）
{
//在HT[1,...,i-1]选择parent为0且weight最小的2个结点，序号分别为s1,s2
intj;
s2=0;
for（j=1;j<=i;j++）
if（HT[j].parent==0）
{s1=j;break;}
for（j=s1+1;j<=i;j++）
if（HT[j].parent==0）
{
if（HT[j].weight{s2=s1;s1=j;}
elseif（s2==0||HT[j].weight}
}
voidHuffumanCoding（HTNode*HT,char**HC,intw[],intn）
{
//w存放的是n个字符的权值（>0），构造最优树HT
//HC用于存放n个字符的编码。
inti,m,f,c,j,s1,s2,start;
char*cd=0;
HTNode*p=0;
if（n<=1）return;
m=2*n-1;
for（p=HT+1,i=1;i<=n;i++,p++）
{p->weight=w[i-1];p->parent=0;p->lchild=0;
p->rchild=0;}
for（;i<=m;i++,p++）
{p->weight=0;p->parent=0;p->lchild=0;
p->rchild=0;}
for（i=n+1;i<=m;i++）
{
Select（HT,i-1,s1,s2）;//注意：
值传递的形参并不能用来改变实参的值
//在HT[1,...,i-1]选择parent为0且weight最小的2个结点，序号分别为s1,s2
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
#ifdefletter//预编译
//无栈非递归遍历最优数，求最优编码
intp1=m;
intcdlen=0;
cd=newchar[n];
for（i=1;i<=m;i++）HT[i].weight=0;
while（p1）
{
if（HT[p1].weight==0）
{
//向左遍历
HT[p1].weight=1;
if（HT[p1].lchild!
=0）
{p1=HT[p1].lchild;cd[cdlen++]='0';}
elseif（HT[p1].rchild==0）{
//对于最优树，这个条件可以去掉
HC[p1]=newchar[cdlen+1];
cd[cdlen]='\0';
strcpy（HC[p1],cd）;
}
}
elseif（HT[p1].weight==1）
{
//向右遍历
HT[p1].weight=2;
if（HT[p1].rchild!
=0）
{p1=HT[p1].rchild;cd[cdlen++]='1';}
}
else
{
//从结点向上退
HT[p1].weight=0;
p1=HT[p1].parent;
cdlen--;
}
}
delete[]cd;
cout<<"无栈非递归求霍夫曼编码"<}
#else
//从叶子到根逆向求每个字符的最优编码
cd=newchar[n];
cd[n-1]='\0';
for（i=1;i<=n;i++）
{
start=n-1;
for（c=i,f=HT[i].parent;f!
=0;c=f,f=HT[f].parent）
if（HT[f].lchild==c）cd[--start]='0';
elsecd[--start]='1';//为了区分权值比较小的2个字符
HC[i]=newchar[n-start];
for（j=start;jHC[i][j-start]=cd[j];
//把cd[start,...,n-1]复制给HC[i]
}
delete[]cd;
cout<<"从叶子到根求霍夫曼编码"<}
#endif
intmain（）
{
inti;
HTNodeHT[2*N];
char*HC[N+1];
intw[N];//每个符号对应的出现几率，根据它写出每个符号的编码
srand（time（NULL））;
for（i=0,w[0]=1,w[1]=2;i//w[i]=w[i-1]+w[i-2]+1;
//当w数组满足w[i]>=w[i-1]+w[i-2]+1时，编码的情况最坏，即此时树最深
w[i]=rand（）%MAX+1;
HuffumanCoding（HT,HC,w,N）;
for（i=1;iprintf（"%d'shuffumancodeis%s\n",w[i-1],HC[i]）;
printf（"\n"）;
/*
for（i=1;i<2*N;i++）
printf（"%d--%d--%d--%d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild）;*/
printf（"\n"）;
return1;
}
/*
voidtranslate（charcode[],intn,char*parentcode）
{
//译码
p=m;
k=0;
for（i=0;i{
if（str[i]=='0'）
{
p=HT[p].lchild;
if（p==0）
{
str[k,...,i]->译成原来的字符//即在HC中查找与之相匹配的字符串
k=i+1;
p=m;
}
}
else//即str[i]=='1'
{
p=HT[p].lchild;
if（p==0）
{
str[k,...,i]->译成原来的字符//即在HC中查找与之相匹配的字符串
k=i+1;
p=m;
}
}
}
}
第二个程序未运行
C语言的
#include
#definemax500
typedefstruct
{
chardata;
intweight;
intparent;
intleft;
intright;
}huffnode;
typedefstruct
{
charcd[max];
intstart;
}huffcode;
charelem[1000];
charinput[1000];
intweight[1000]={0};
intm=0;
intfind_char（chara[],charc,intn）
{
inti;
for（i=0;i<=n;i++）
{
if（a[i]==c）returni;
}
return-1;
}
intget_elem_weight（）
{
inti,n=-1;
for（i=0;i<100;i++）
elem[i]='';
charc;
while
（1）
{
c=getchar（）;
input[m++]=c;
if（c==10）break;
elseif（c!
=''）
{
if（find_char（elem,c,n）==-1）
{n++;
elem[n]=c;
weight[n]=1;
}
elseweight[find_char（elem,c,n）]+=1;
}
}
printf（"除空格和回车之外各字符的出现频率如下：
\n"）;
for（i=0;i<=n;i++）
{
printf（"%c%d",elem[i],weight[i]）;
printf（"\n"）;
}
returnn+1;
}
main（）
{
huffnodeht[2*max];
huffcodehtd[max],d;
inti,k,f,l,r,n,c,m1,m2,j;
printf（"请输入一个字符串，以回车结束\n"）;
n=get_elem_weight（）;
for（i=1;i<=n;i++）
{
ht[i].data=elem[i-1];
ht[i].weight=weight[i-1];
}
for（i=1;i<=2*n-1;i++）
ht[i].parent=ht[i].left=ht[i].right=0;
for（i=n+1;i<=2*n-1;i++）
{
m1=m2=32767;
l=r=0;
for（k=1;k<=i-1;k++）
if（ht[k].parent==0）
if（ht[k].weight{
m2=m1;
r=l;
m1=ht[k].weight;
l=k;
}
elseif（ht[k].weight{
m2=ht[k].weight;
r=k;
}
ht[l].parent=i;
ht[r].parent=i;
ht[i].weight=ht[l].weight+ht[r].weight;
ht[i].left=l;
ht[i].right=r;
}
for（i=1;i<=n;i++）
{
d.start=n+1;
c=i;
f=ht[i].parent;
while（f!
=0）
{
if（ht[f].left==c）
d.cd[--d.start]='0';
else
d.cd[--d.start]='1';
c=f;
f=ht[f].parent;
}
htd[i]=d;
}
printf（"输出编码\n"）;
for（i=1;i<=n;i++）
{
printf（"%c:
",ht[i].data）;
for（k=htd[i].start;k<=n;k++）
printf（"%c",htd[i].cd[k]）;
printf（"\n"）;
}
printf（"你所输入的字符串为\n"）;
for（i=0;iprintf（"\n"）;
printf（"经过编码之后\n"）;
for（i=0;i{
if（input[i]!
=''）
{
for（k=1;k<=n;k++）
if（ht[k].data==input[i]）break;
for（j=htd[k].start;j<=n;j++）
printf（"%c",htd[k].cd[j]）;
}
elseprintf（"%c",input[i]）;
}
printf（"\n"）;
}
升级会员 