最优二叉查找树 算法导论216

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10000
double e[102][101];
double w[102][101];
int root[101][101];
double p[101],q[101];
typedef struct
{
char word[20];
char key[20];
}datatype;

typedef struct bitnode
{
datatype data;
struct bitnode *lchild;
struct bitnode *rchild;
}BiTNode;

int cmp( const void *a,const void *b)
{
return strcmp(((*(BiTNode**)a)->data.word),((*(BiTNode**)b)->data.word));
}

BiTNode *queue[101];

void bst(int n)
{
int i,j,r,l;
double t;


for(i=1;i<=n+1;i++)
e[i][i-1]=w[i][i-1]=q[i-1];

for(l=1;l<=n;l++)
for(i=1;i<=n-l+1;i++)
{
j=i+l-1;
e[i][j]=MAX;
w[i][j]=w[i][j-1]+p[j]+q[j];
for(r=i;r<=j;r++)
{
t=e[i][r-1]+e[r+1][j]+w[i][j];
if(t<e[i][j])
{
e[i][j]=t;
root[i][j]=r;
}
}
}
}

BiTNode *printfroot(int i,int j ,BiTNode *bt)
{
if(i>j)
{ BiTNode *p;
p=(BiTNode *)malloc(sizeof(BiTNode));
p->lchild=NULL;
p->rchild=NULL;
strcpy(p->data.word,"No_this_word!");
strcpy(p->data.key,"空");
bt=p;
return bt;
}
else
{
bt=queue[root[i][j]];
bt->lchild=printfroot(i,root[i][j]-1,bt->lchild);
bt->rchild=printfroot(root[i][j]+1,j,bt->rchild);
}
return bt;
}

void preorder(BiTNode *bt)
{
if(bt->lchild==NULL)
{
printf("%s \n",bt->data.word);
return ;
}
else if(bt->lchild==NULL)
{
printf("%s \n",bt->data.key);
return ;
}
else
{
printf("%s->%s\n",bt->data.word,bt->data.key);
preorder(bt->lchild);
preorder(bt->rchild);
}
}

void translate(BiTNode *BT)
{
int find,c;
char word[20];
BiTNode *bt;

printf("请输入要查的单词 输入1: 退出\n");
while(scanf("%s",word)!=EOF)
{
if(word[0]=='1')
{
printf("谢谢使用\n");
break;
}
else
{
find=0;
bt=BT;
while(find==0)
{
c=strcmp(word,(bt->data.word));
if(c==0)
{
printf("%s->%s\n\n",bt->data.word,bt->data.key);
find=1;
}
else if(c<0)
{
if(bt->lchild)
bt=bt->lchild;
else
{
printf("%s:%s\n\n",word,bt->data.key);
find=2;
}
}
else
{
if(bt->rchild)
bt=bt->rchild;
else
{
printf("%s:%s\n\n",word,bt->data.key);
find=2;
}
}
}
}
}
}

void print(int n)
{
int i,j;
for(j=1;j<=n;j++)
printf(" %d ",j);
printf("\n");
for(i=1;i<=n+1;i++)
{
printf("%d ",i);
for(j=0;j<i-1;j++)
printf(" ");
for(j=i-1;j<=n;j++)
printf("%.2lf ",e[i][j]);
printf("\n");
}
printf("\n");

for(j=1;j<=n;j++)
printf(" %d ",j);
printf("\n");
for(i=1;i<=n+1;i++)
{
printf("%d ",i);
for(j=0;j<i-1;j++)
printf(" ");
for(j=i-1;j<=n;j++)
printf("%.2lf ",w[i][j]);
printf("\n");
}
printf("\n");

printf(" ");
for(j=1;j<=n;j++)
printf("%d ",j);
printf("\n");
for(i=1;i<=n;i++)
{
printf("%d ",i);

for(j=1;j<=i-1;j++)
printf(" ");
for(j=i;j<=n;j++)
printf("%d ",root[i][j]);
printf("\n");
}
printf("\n");
BiTNode *bt;
bt=printfroot(1,n,bt);
preorder(bt);
printf("\n");
translate(bt);
}

int main()
{ freopen("1.txt","r",stdin);
int n,i;
BiTNode *pp;

printf("请输入关键字的个数N:\n");
scanf("%d",&n);

printf("请输入单词word 相对中文key 应的概率p:\n");

for(i=1;i<=n;i++)
{
pp=(BiTNode *)malloc(sizeof(BiTNode));
scanf("%s %s %lf",&(pp->data.word),&(pp->data.key),&p[i]);
pp->lchild=pp->rchild=NULL;
queue[i]=pp;
}

for(i=1;i<=n;i++)
printf("%s %s\n",queue[i]->data.word,queue[i]->data.key);
printf("\n");
// qsort(queue+1,n,sizeof(queue[0]),cmp);
for(i=1;i<=n;i++)
printf("%s %s\n",queue[i]->data.word,queue[i]->data.key);
printf("\n");
printf("请输入虚拟键的概率q:\n");
for(i=0;i<=n;i++)
scanf("%lf",&q[i]);
bst(n);
print(n);
return 0;
}