`
shinepengwei
  • 浏览: 46022 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

动态规划之最优二叉查找树源代码——算法导论

阅读更多

此算法是根据《算法导论》里面的介绍编写的。数据也是。代码运行后,结果数据正确。

 

以《算法导论》P213中未测试数据:

p[6]={-100,0.15,0.1,0.05,0.1,0.2};

q[6]={0.05,0.1,0.05,0.05,0.05,0.1};

运行结果:


《算法导论》中的结果p216:


代码如下:

 

#include <iostream>
void main()
{
	float p[6]={-100,0.15,0.1,0.05,0.1,0.2};
	float q[6]={0.05,0.1,0.05,0.05,0.05,0.1};
	float e[7][6];
	float w[7][6];
	int root[6][6];

	for(int i=1;i<7;i++)
		e[i][i-1]=w[i][i-1]=q[i-1];//初始化d

	for(int l=0;l<6;l++)//求间隔距离为L的序列子最优二叉树
	{
		for(int i=1;i<6-l;i++)//序列从i开始
		{
			int j=i+l;//到j结束
			e[i][j]=1000;//初始化为-正无穷大
			//遍历序列中的节点作为子树的根结点,并找到最小搜索代价放入e,同时把此根结点存放入root
			w[i][j]=w[i][j-1]+q[j]+p[j];//这一个不太好理解。
			//w的物理意义是这个序列的所有k点和d点的概率和。
			//序列里面多了一个k点,同时,就要把这个Ki点和Di点加入到w里面。
			for(int k=i;k<=j;k++)//计算以k为根结点的子二叉树的搜索代价
			{
				float tmp=e[i][k-1]+e[k+1][j]+w[i][j];
				if(tmp<e[i][j])
				{
					e[i][j]=tmp;//如果搜索代价小于以前计算的,放入e(也就是说,e中一直存着目前最小的搜索代价)
					root[i][j]=k;
				}
					
			}
		}
	}
	printf("e:\n");
	for(int i=1;i<7;i++){
		for(int j=0;j<6;j++){
			if(e[i][j]>10||e[i][j]<0){
			printf("     ");
			}
			else{
			printf("%1.2f,",e[i][j]);
			}
			
		}
		printf("\n");
	}
	printf("w:\n");
	for(int i=1;i<7;i++){
		for(int j=0;j<6;j++){
			if(w[i][j]>1||w[i][j]<0){
			printf("     ");
			}
			else{
			printf("%1.2f,",w[i][j]);
			}
			
		}
		printf("\n");
	}
	printf("root:\n");
	for(int i=1;i<6;i++){
		for(int j=1;j<6;j++){
			if(root[i][j]>10||root[i][j]<0){
			printf("  ");
			}
			else{
			printf("%d,",root[i][j]);
			}
			
		}
		printf("\n");
	}

}
 

 

  • 大小: 15.5 KB
  • 大小: 27.5 KB
1
2
分享到:
评论

相关推荐

    最优二叉查找树 动态规划法.cpp.rar

    在本课程作业的代码“最优二叉查找树 动态规划法.cpp”中,可能包含了以下关键部分: 1. **数据结构定义**:定义二叉查找树节点的数据结构,包括键值、左子节点和右子节点的引用。 2. **概率分布输入**:程序需要...

    0020算法笔记——【动态规划】最优二叉搜索树问题 - liufeng_king的专栏 - 博客频道 - CSDN1

    【最优二叉搜索树问题】是一种在数据结构和算法领域中的经典问题,主要涉及动态规划的概念。该问题的目标是设计一棵二叉搜索树(BST),使得在给定的元素集合和存取概率分布下,搜索元素时的平均比较次数达到最小。 ...

    最优二叉查找树

    一旦所有子树的成本都被计算出来,算法便可以通过递归地调用`constructOptimalBST`函数,根据动态规划过程中记录的最优根节点选择,构建出整个最优二叉查找树的结构。在构建过程中,函数会打印出树的结构信息,包括...

    最优二叉搜索树

    最优二叉搜索树,也称为最优化二叉查找树或者动态二叉搜索树,是计算机科学中的一个重要概念,尤其在算法设计与分析领域占据一席之地。这种数据结构主要用于提高查询效率,在某些特定操作序列下,它能比普通二叉搜索...

    凸包问题(包含蛮力算法和快速凸包算法)+最优二叉查找树

    凸包问题(包含蛮力算法和快速凸包算法两种解法)+最优二叉查找树,并且都利用javafx生成可视化界面,开箱即用,代码含注释,原理通俗易懂。

    最优二叉搜索树的动态规划算法研究.txt

    本文主要探讨了在解决最优二叉搜索树问题时所采用的一种高效算法——动态规划算法。最优二叉搜索树(Optimal Binary Search Tree, OBST)是在特定概率下查找操作平均时间最短的二叉搜索树。在实际应用中,如数据库索引...

    二叉查找树 减治法——C++代码

    二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树数据结构,它的每个节点都包含一个键(key)、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。在二叉查找树中,对于任意节点,其左子树中的...

    算法与数据结构 算法分析课程 第10章 动态规划 3、最优二叉搜索树 共19页.pptx

    然而,在某些场景下,不同的键(key)被查询的频率各不相同,这就引发了一个问题——如何构建一棵最优的二叉搜索树,使得平均查找成本最低? #### 二、基本概念 - **键(Key)**:二叉搜索树中的数据元素。 - **查询...

    Ruby实现的最优二叉查找树算法

    本篇介绍的Ruby代码提供了一个简洁而完整的最优二叉查找树的构建过程,通过动态规划的方法有效地解决了如何构建最优二叉查找树的问题。这对于理解最优二叉查找树的概念及其实际应用具有重要的意义。在实际开发中,...

    MIT公开课——算法导论教材

    《MIT公开课——算法导论教材》是一份源自美国麻省理工学院(MIT)的珍贵教育资源,专注于教授计算机科学中的核心概念——算法。这份教材涵盖了排序、树和Hash等基础但至关重要的算法,对于学习和理解计算机科学的...

    最优二叉树

    最优二叉查找树,为算法导论上的算法,时间复杂度O(nlgn),思考题15.5-

    用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题.pdf

    用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题.pdf

    算法与数据结构 算法分析课程 动态规则后半部分8 构建最优二叉搜索树 共17页.pptx

    本文将深入探讨如何构建最优二叉搜索树,并通过动态规划的方法解决这一问题。 #### 二、最优二叉搜索树的背景与定义 假设我们有一组键\(K_1, K_2, \ldots, K_n\),每个键\(K_i\)被查询的概率为\(p_i\)。此外,对于...

    数据结构、算法与应用:C++语言描述(原书第2版)第二部分

    第19章 动态规划 19.1 算法思想 19.2 应用 19.2.1 0/1背包问题 19.2.2 矩阵乘法链 19.2.3 所有顶点对之间的最短路径 19.2.4 带有负值的单源最短路径 19.2.5 网组的无交叉子集 19.3 参考及推荐读物 第20章 回溯法 ...

    二叉树源代码(C++)

    本文将对一个用C++编写的二叉树源代码进行详细介绍,并展示其构造、遍历、线索化以及线索遍历等关键部分的实现。 首先,让我们了解二叉树的基本构造。在源代码中,二叉树的构造通常从创建一个根节点开始,然后通过...

    二叉 递归二叉查找算法

    二叉查找算法是一种在二叉树数据结构中高效地寻找目标元素的算法。它基于排序二叉树(也称为搜索二叉树),其中每个节点的值都大于其左子树中的任何节点,小于其右子树中的任何节点。这种特性使得二叉查找算法能以...

    麻省理工——算法导论

    麻省理工--算法导论,非计算机专业的建议不要下载。

    c++线索二叉树源代码

    线索二叉树是一种在二叉树中添加额外线索(thread)的数据结构,目的是为了提高二叉查找树在非递归情况下的遍历效率。在普通的二叉查找树中,我们通常只能通过指针找到左右子节点,但在线索二叉树中,我们可以从前向...

Global site tag (gtag.js) - Google Analytics