`

数据结构和算法-查找

阅读更多

根据某个关键字查找某个数据元素

1.线性查找

遍历所有元素,优化策略是减少比较次数,复杂度O(n)

2.有序表查找

1).二分查找O(logn)

public static int binarySearch(int k, int[] arr) {
		int high = arr.length - 1;
		int low = 0;
		int mid;
		while (low <= high) {
			mid = (low + high) / 2;
			if (k == arr[mid]) {
				return mid;
			} else if (k > arr[mid]) {
				low = mid + 1;
			} else {
				high = mid - 1;
			} 
		}
		return -1;
	}

3.线性索引查找

稠密索引:将数据集中的每一个记录对应一个索引项,索引按关键码有序排列

分块索引:快内无序、块间有序,块中最大关键字,块中的记录数,块的首地址

倒排索引:次关键码、记录号

 

4.二叉排序树

left-child < parent < right-child

二叉树的删除,删除叶子或只有右子树或只有左子树的情况补上就行,但是既有左子树又有右子树的情况,找到被删除节点的直接前驱或直接后继替还被删除节点。

中序遍历,复杂度O(logn),考虑树变成了链表的情况O(n)

 

5.平衡二叉树:二叉排序树但是左子树和右子树高度差1

找出最小不平衡子树,计算每个节点的平衡因子BL,> 1进行右旋, < -1进行左旋

 

6.多路查找树(B树)

每一个节点的孩子可以多于2个,每个节点可以存储多个元素

2-3:每个节点2个孩子或3个孩子

2节点:一个元素2个(或没有)孩子

3节点:一大一小2个元素3个(或没有)孩子

2-3-4:对2-3树的扩展,多了4节点3元素  

BTree:平衡多路查找树,节点最大的孩子为BTree的阶

B的阶数与硬盘大小相匹配,与磁盘页面进行多次访问

B+Tree:分支出现该元素则作为该分支下的叶子节点,每一个叶子节点保存的后一个叶子节点指针

 

7.散列表O(1)

适合查找和给定值相等问题

要求:简单、均匀、存储利用率高

直接定址、数字分析、平方取中、折叠法、取模、随机数

处理冲突的方法:

开放定址:寻找下一个 fi(k) = (f(k) + di) % m,线性探测,二次探测:di^2,随机探测:random(di)

再次散列:还一种散列方式

链地址方:构建链表,存储头指针

公共溢出区:为冲突关键字建立的顺序表

 

分享到:
评论

相关推荐

    数据结构和算法-思维导图.pdf

    在数据结构和算法领域中,存在大量不同的概念和术语,这些都构成了计算机科学的基础。思维导图是一种有效的方式来组织和回顾这些概念,通过可视化方式帮助记忆和理解。从提供的文件【标题】:"数据结构和算法-思维...

    数据结构与算法-PPT课件

    数据结构与算法是计算机科学中的核心课程,它探讨如何有效地组织和处理数据,以及如何设计和分析解决问题的算法。这份“数据结构与算法-PPT课件”提供了丰富的学习材料,涵盖了多个关键主题。 首先,我们要了解数据...

    Java数据结构和算法-带书签目录扫描版

    《Java数据结构和算法-带书签目录扫描版》是一本深入探讨Java编程语言中数据结构和算法的书籍。此扫描版特别包含了完整的书签目录,使得读者在电子版阅读时能够快速定位到所需章节,提高了学习和查阅的效率。 在...

    数据结构与算法 -电子教案

    数据结构与算法是计算机科学的基础,对于理解和解决复杂问题至关重要。这份"数据结构与算法 -电子教案"无疑是学生们深入学习这一领域的宝贵资源。以下是对其中可能包含的知识点的详细阐述: 1. **数据结构**: 数据...

    数据结构和算法-Flash动画演示

    数据结构和算法是计算机科学的基础,对于理解和设计高效的软件至关重要。本资源——“数据结构和算法-Flash动画演示”提供了一种生动形象的方式来学习这些核心概念。通过Flash动画,你可以直观地看到各种算法的动态...

    数据结构与算法--面向对象的C++设计

    本书标题为《数据结构与算法——面向对象的C++设计》,其内容主要围绕数据结构和算法在C++中的面向对象设计模式展开。本书不仅介绍了数据结构与算法的基本概念,还着重强调了面向对象编程范式(Object-Oriented ...

    数据结构与算法--Java语言描述

    数据结构与算法是计算机科学的基础,对于任何编程语言来说,理解和掌握它们都是至关重要的,特别是对于Java语言。在这个“数据结构与算法--Java语言描述”的资料中,我们有望深入理解这些核心概念,并通过Java语言来...

    hello-algo-数据结构与算法-zh-csharp.pdf

    本书《Hello 算法》是为了帮助读者学习数据结构与算法而编写的,作者靳宇栋(Krahets)认为刷题虽然是学习算法的一种方法,但对于基础不足的同学来说,可能会感到困扰和挫折。因此,本书旨在引导读者探索数据结构与...

    数据结构与算法-C语言版本

    数据结构与算法是计算机科学的基础,对于理解和设计高效的软件至关重要。C语言因其高效、底层特性,常被用于实现数据结构和算法。本资料包“数据结构与算法-C语言版本”聚焦于通过源码实例和答案解析,帮助学习者...

    西安电子科技大学-数据结构与算法-期末知识点总结.pdf

    "西安电子科技大学-数据结构与算法-期末知识点...本资源涵盖了数据结构与算法的基本概念、线性表、栈与队列、树与二叉树、图、查找算法和排序算法等方面的知识点,对于学习数据结构与算法的学生具有重要的参考价值。

    数据结构与算法---C++版(Adam Drozdek)书中的源代码

    在压缩包文件中,我们可能找到书中提到的各种数据结构和算法的源代码实现,如链表、栈、队列、树、图、排序算法和查找算法等。 1. **链表**:链表是数据结构的基础,包括单链表、双链表和循环链表。在C++中,链表...

    Java数据结构和算法-第二版-高清扫描版-带目录书签

    《Java数据结构和算法》第二版是一本深入探讨Java编程中数据结构与算法的权威书籍。这本书涵盖了在软件开发中至关重要的基础知识,旨在帮助程序员提升解决问题的能力和代码效率。高清扫描版提供了清晰的文本和图表,...

    数据结构与算法分析--C语言描述_数据结构与算法_

    数据结构与算法是计算机科学的基础,对于理解和设计高效的软件至关重要。C语言因其高效、底层特性,常被用于实现数据结构和算法,使得程序更接近硬件,性能更优。本资源"数据结构与算法分析--C语言描述"是针对数据...

    数据结构与算法-----PPT版本

    数据结构与算法是计算机科学的基础,对于任何编程学习者来说,理解和掌握它们至关重要。这个“数据结构与算法-----PPT版本”很可能包含了徐旭松教授或专家精心制作的一系列教学材料,旨在帮助学习者深入理解这些核心...

    数据结构与算法-----C语言描述

    数据结构与算法》以基本数据结构和算法设计策略为知识单元,系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法,主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。《数据结构与...

    数据结构经典算法-多种排序和查找

    在这个"数据结构经典算法-多种排序和查找"的项目中,我们重点关注了查找和排序这两种核心操作,它们在编程中有着广泛的应用。以下是这些算法的详细介绍: 1. **查找算法**: - **折半查找(二分查找)**:基于有序...

    C++数据结构与算法-高清

    《C++数据结构与算法-高清》是一本深入讲解C++编程中数据结构与算法的教材,适合初学者和进阶者深入理解这两个关键领域的知识。数据结构是计算机科学的基础,它涉及到如何有效地存储和组织数据,以便进行高效地访问...

    数据结构与算法----面向对象的C++模式

    国外经典教材 数据结构与算法----面向对象的C++模式 ...8 散列,哈希表与分散表 9树 10查找树, 11堆和优先队列 12集合,多重集和分区 13动态存储分配 14 算法模式和问题求解 15 排序算法和排序器 16 图和图算法

    数据结构与算法-python

    数据结构与算法是计算机科学的基础,对于理解和解决复杂问题至关重要。在Python编程语言中,学习数据结构和算法能让你编写出更高效、可维护的代码。以下是对这些主题的详细阐述: 1. **数据结构**: 数据结构是组织...

    Python版数据结构与算法-查找算法源代码,含顺序搜索、二分查找、哈希表搜索、树(图)数据查找源代码

    在IT领域,数据结构与算法是核心组成部分,它们直接影响到程序的效率和性能。本资源包含的是Python实现的各种查找算法的源代码,这些查找算法在实际编程中有着广泛的应用。以下将详细介绍标题和描述中提到的几个关键...

Global site tag (gtag.js) - Google Analytics