// 最优二叉查找树的期望搜索代价.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#include<cmath>
#include<limits>
#define N 100
using namespace std;
const double MAX = numeric_limits<double>::max(); //double的最大值
int _tmain(int argc, _TCHAR* argv[])
{
//p[j]存储第j关键字的概率(j=1...n)
double p[N];
//存储第j虚拟键的概率(j=0...n)
double q[N];
//存储包含关键字ki....kj的最优子树的搜索代价
double c[N][N];
//存储包含关键字ki....kj和虚拟键的最优子树的概率和
double w[N][N];
//存储存储包含关键字ki....kj的最优子树的根
int root[N][N];
int cases;
cout<<"请输入案例的个数:"<<endl;
cin>>cases;
while(cases--)
{
int n;
double sum = 0;
int i,j,l;
cout<<"请输入关键字的个数:"<<endl;
cin>>n;
cout<<"请输入每个关键字的概率:"<<endl;
for(i=1;i<=n;i++)
{
cin>>p[i];
sum += p[i];
}
cout<<"请输入每个虚拟键的概率:"<<endl;
for(i=0;i<=n;i++)
{
cin>>q[i];
sum += q[i];
}
//
if(abs(sum-1)>0.01)
{
cout<<"输入的概率和不为1,请重新输入"<<endl;
cases++;
continue;
}
for(i=1;i<=n+1;i++)
{
c[i][i-1] = q[i-1];
w[i][i-1] = q[i-1];
}
for(l=1;l<=n;l++)
{
for(i=1;i<=n-l+1;i++)
{
j = l+i-1;
c[i][j] = MAX;
w[i][j] = w[i][j-1] + p[j] +q[j];
int r;
for(r=i;r<=j;r++)
{
double k = c[i][r-1] + w[i][j] + c[r+1][j];
if(k<c[i][j])
{
c[i][j] = k;
root[i][j] = k;
}
}
}
}
cout<<"最优二叉查找树的期望搜索代价为:"<<c[1][n]<<endl;
}
system("pause");
return 0;
}
---------------------------------------------测试程序----------------------------------------------
请输入案例的个数:
1
请输入关键字的个数:
5
请输入每个关键字的概率:
0.15 0.10 0.05 0.10 0.20
请输入每个虚拟键的概率:
0.05 0.10 0.05 0.05 0.05 0.10
最优二叉查找树的期望搜索代价为:2.75
请按任意键继续. . .
分享到:
相关推荐
用C++实现的最优二叉查找树,简单,明了,是数据结构里经典必学算法,初学者适用
c语言实现的用动态规划实现最优二叉查找树,,,具体参见附件,2.txt中的内容为: 5 0.15 0.10 0.05 0.10 0.20
使用C++实现最优二叉查找树,对正在学习算法的同学应该挺有帮助的
C++的课程作业,一个简单的程序,用dev就能直接运行,老师应该不会太仔细检查,糊弄一下肯定没事的,不过最好能自己看懂就是了
最优二叉搜索树,计算机算法设计与分析的一个题目
使用C#实现的动态规划算法 关键字序列:0.15,0.1,0.05,0.1,0.2 非关键字序列:0.05,0.1,0.05,0.05,0.05,0.1 以上的测试数据,输入数据可以得到结果
二叉查找树的C++实现
14.3 二叉搜索树的操作和实现 14.3.1 类binarySearchTree 14.3.2 搜索 14.3.3 插入 14.3.4 删除 14.3.5 二叉搜索树的高度 14.4 带有相同关键字元素的二叉搜索树 14.5 索引二叉搜索树 14.6 应用 14.6.1 直方图 14.6.2...
设S=(x1,x2,…,xn)是有序集,且x1…,已知键值和区间的存取概率分布为(a0,b1,a1,b2,…,bn,an),其中ai表示相应区间的搜索概率,bi表示相应键值的...在所有表示有序集的二叉树中找出一棵具有最小平均路长的二叉搜索树
使用二叉链表和c++来实现二叉搜索树,提供插入、删除、遍历、求最小节点、最大最节点等操作。
资源内容:完整的二叉查找树C++头文件,包括运算符重载,bst类构造器、bst类析构器、destroy()、size()、insert(),迭代器类的声明与实现,++运算符重载(前置、后置)、--运算符重载、*运算符重载、!=运算符重载、...
c++实现的二叉查找树,代码简陋,大家互相学习即可
这个程序实现了二叉查找树的删除,增加,先序遍历,后序遍历,中序遍历,还有一些非递归和层次遍历!
二叉查找树的常用操作,含C++代码,找工作的时候可以放在手机里看。
二叉查找树实现源码(C、C++、JAVA)
这是我自己用C++写的一个二叉查找树的链表实现。由于是老师突然布置的课程实验,时间比较匆忙,所以在写代码的过程中首先考虑的代码的功能的实现,而忽视了代码的可读性和健壮性,有的代码并不是最佳的功能实现。贴...
这里是二叉查找树的实现代码,如果有不明白的可以联系我,很多其他的C++代码我都有
1、 定义二叉查找树的类。 2、 实验验证如下算法的正确性、各种功能及指标: 1)实现二叉查找树结构; 2) 实现二叉查找树的查找、插入和删除等算法;
C++实现的二叉查找树,算是AVL树的雏形。