《算法设计与分析》--最优二叉排序树

《算法分析与设计》

实验报告

题目：

姓名： 班级：

学号：

指导教师：

完成时间：

一、 实验题目

给定一系列键值和权重，构造最优二叉排序树，使得总的查找次数最少。

二、 实验目的

1. 理解时间复杂度的概念。

2. 深入地掌握C语言编程。

3. 通过编程直观地理解算法分析的意义

三、 实验要求

给定一系列键值和权重，构造最优二叉排序树，使得总的查找次数最少。要求的输出格式为：第一行为最优的查找次数，第二行为最优二叉排序树的前序遍历得到的序列，然后一个空行，随后为源代码。算法的输入如下(冒号前为键值，冒号后为权重)：1:0 2:56 3:19 4:80 5:58 6:47 7:35 8:89 9:82 10:74 11:17 12:85 13:71 14:51 15:30 16:1 17:9 18:36 19:14 20:16 21:98 22:44 23:11 24:0 25:0 26:37 27:53 28:57 29:60 30:60 31:16 32:66 33:45 34:35 35:5 36:60 37:78 38:80 39:51 40:30 41:87 42:72 43:95 44:92 45:53 46:14 47:46 48:23 49:86 50:20 51:77 52:84 53:99 54:99 55:61 56:39 57:26 58:29 59:84 60:2 61:37 62:9 63:67 64:5 65:0 66:91 67:27 68:27 69:58 70:69 71:83 72:72 73:48 74:20 75:74 76:46 77:45 78:94 79:74 80:10 81:59 82:38 83:73 84:60 85:57 86:36 87:15 88:22 89:42 90:80 91:51 92:98 93:75 94:34 95:16 96:65 97:49 98:6 99:69 100:50 101:14 102:94 103:14 104:90 105:69 106:30 107:42 108:7 109:96 110:68 111:15 112:87 113:82 114:58 115:19 116:17

117:81 118:47 119:15 120:50 121:73 122:40 123:27

四、 程序流程图

五、 程序代码

#include<stdio.h>

#include<string.h>

struct node{

int key;

int v;

};

int sum[1000],c[1000][1000],y[1000][1000];

struct node a[10000];

int n,ans;

void df(int left,int right)

{

if(left>right) return ;

int k=y[left][right];

printf("%d ",k);

df(left,k-1);

df(k+1,right);

}

void fi(int left,int right,int t)

{

if(left>right) return ;

ans=ans+t;

int k=y[left][right];

fi(left,k-1,t+1);

fi(k+1,right,t+1);

}

void in()

{

char ch;

freopen("input.txt","r",stdin);

n=1;

while(1)

{

do{

if( scanf("%c",&ch) ==EOF) return ;

if(ch!=':') a[n].key=a[n].key*10+(ch-'0'); }while(ch!=':');

do{

if( scanf("%c",&ch) ==EOF) return ;

if(ch!=' ') a[n].v=a[n].v*10+(ch-'0'); }while(ch!=' ');

n++;

}

n--;

}

int main()

{

int i,j,k,u;

in();

sum[0]=0;

for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].v;

for(i=0;i<=n;i++)

for(j=0;j<=n;j++) c[i][j]=0;

for(i=1;i<=n;i++)

{

y[i][i]=i;

c[i][i]=0;

}

for(u=2;u<=n;u++)

{

for(i=1;i<=n-u+1;i++)

{

j=i+u-1;

c[i][j]=10000000;

for(k=i;k<=j;k++)

if(c[i][k-1]+c[k+1][j]+sum[j]-sum[i-1]-a[k].v<c[i][j])

{

c[i][j]=c[i][k-1]+c[k+1][j]+sum[j]-sum[i-1]-a[k].v;

y[i][j]=k;

}

}

}

ans=0;

fi(1,n,1);

printf("%d",ans);

df(1,n);

printf("\n");

return 0;

}

六、 实验结果

七、 实验体会

通过本次上机实验，我在编写算法的过程中，了解到了二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树可得到一个依据关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，