数据结构查找表定义
2018-11-12 18:30:57 hq942845204 阅读数 284

前言

今天学习数据结构看到了一个词-静态查找表,还有与之对应的动态查找表,然后我发现。

啊,这是个啥,好像知道又好像不知道,不就是查找吗,干嘛弄这些专业的说法,回头翻了一下数据结构的书,才发现......。

唉,小小的抱怨一下,不过,我从这两个词联想到了一门基础但是要精通又不简单的学问,就是查找,然后还有前天被面试官问到的一个查找题,题目很简单,如何查找单向链表中倒数第K个数?当然你先遍历一遍数组,获取数组的总长度,然后再遍历一遍找倒数第K个数,当然可以,但是既然是面试题,这样的答案基本是凉凉的,我自己都不满意,更别提人家面试官了,当你抛出这个答案之后,面试官会说如果只遍历一遍呢?你就懵逼了,如果你和我一样懵逼的话,那么恭喜你,你现在还来得及,当然正确方法我就不说了,感兴趣的可以去想想,实在想不出来,我相信你会有办法的,xixixi,也不难。

好了,说了这么多,今天既然发现了自己的一个薄弱区-查找,指不准以后哪天还会在查找这里栽倒,于是,何不在这之前好好梳理一下查找这块呢?

目录

1.静态查找表

2.动态查找表

3.哈希表

正文

首先我们需要明白下静态查找表和动态查找表的定义,所谓的静态查找表是指在查找过程中只进行查找操作,动态查找表就是在查找过程中还会进行插入和删除操作,例如,查找某个元素,若查找到了,则删除。

1.静态查找表

静态查找表可以有不同的表示方法,在不同的表示方法中,实现的查找操作方法也不同。

这里列举平时遇到的最为常见的两种情况

a.以顺序表或线性链表表示静态查找表,则查找可用顺序查找来实现

b.以有序表(排好顺序的顺序表) 表示静态查找表,则查找可用折半查找(二分查找)来实现

第一种,就是一个for循环的事,就不赘述了,这里看一下第二种情况,也就是二分查找的代码,思想就是从中间位置起开始查找,如果正好位于正中间,那么就找到了,如果比正中间数据大,那么在后半部分查找,假设整个数据是升序,如果比正中间数据小,那么在前半部分查找,依次类推,递归结束的标志就是左边界大于右边界,也就是已经不能再分了,如果此时还没查找到,那么就返回未查找到即可

public class BinarySearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a=new int[]{2,3,5,8,9};
		int index=search(a,50);
		System.out.println(index);
	}
	public static int search(int[] a,int data){
		return binarlSearch(a, 0, a.length-1,data);
	}
	public static int binarlSearch(int[] a,int left,int right,int data){
		if(left>right)
			return -1;
		int mid=(left+right)/2;
		if(a[mid]==data){
			return mid;
		}else if(a[mid]<data){
			return binarlSearch(a, mid+1, right, data);
		}else{
			return binarlSearch(a, left, mid-1, data);
		}
	}
}

上面的只是查找里的入门知识,学任何东西都像打怪升级一样,先从小怪开始,由简变难,下面我们升级来打一个大点的怪!

2.动态查找表

动态查找表的特点是:表结构本身是在查找过程中动态生成的,即对于给定的key值,若表中存在其关键字等于key的记录,则查找成功返回,否则插入关键字等于key的记录。

动态查找表也可有不同的表示方法,这里主要讨论以各种树结构表示时的实现方法。

a.二叉排序树(又叫  二叉搜索树  二叉查找树)

二叉排序树的特点是:

1.若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值

2.若它的右子树不为空,则右子树上所有节点的值均大于它的根节点的值

3.它的左右子树也分别为二叉排序树

在了解了这个树的性质之后,我们不难联想到二分查找的思想,只不过大同小异,首先和根节点比较,如果比根节点大,则在右子树中查找,如果比根节点小,则在左子树中查找,如果相等,那么正好查找到了,如果左子树也没有,右子树也没有,则查找失败。

好了,我们掌握了上面的思想,不难写出下面的代码

	public boolean contains(Node root, Node node) {
		if (root == null) {
			return false;
		}
		if (node.data == root.data) {
			return true;
		} else if (node.data > root.data) {
			return contains(root.rChild, node);
		} else {
			return contains(root.lChild, node);
		}
	}

代码不难理解,然后我们再考虑这样一种情况,就是一个有序的链表,是不是也符合二叉排序树的性质,也就是说我们查找的这棵二叉排序树是有可能退化为一个链表的,那么我们再对照着上面这个查找的代码去看,会发现查找的效率已经退化成了O(n),这显然不是我们想要看到的结果,我们想要的效果是尽可能的将一组数据分为等长的两部分,以达到类似“二分”的效果,只有这样最终的效率才可以达到O log(n)的最优效果,于是我们就引出了这样一个问题,如何保证二叉排序树查找的效率维持在O log(n)呢?接着往下看

b.平衡二叉树

在上面,我们发现如果不对二叉排序树做任何处理,发现查找的效率会有可能退化为链表的查找效率,所以我们期望有一种解决方案能避免效率的降低,现在再来想想,为什么我们的查找效率会降低,究其原因就是二叉树退化成了链表,那么我们必须以某种手段来防止退化,比如强制要求左右子树的高度差小于某个值等措施,于是我们自然而然想到了平衡二叉树。

 

所以解决方案就是让二叉排序树转换为平衡二叉树,这个就好说了,主要涉及到四个操作,左左旋(LL)、右右旋(RR)、左右旋(LR)、右左旋(RL)。通过在插入一个元素的时候,判断是否符合平衡二叉树的性质,也就是左右子树的高度差是否小于1,如果不符合,那么根据情况做相应的旋转处理即可。

由于几个旋转基本类似,只要掌握了一个,剩下的依葫芦画瓢即可,我们现在来看下左左旋的代码

	// 左左翻转 LL
	// 返回值为翻转后的根结点
	private Node leftLeftRotation(Node node) {
		// 首先获取待翻转节点的左子节点
		Node lNode = node.lChild;

		node.lChild = lNode.rChild;
		lNode.rChild = node;

		node.height = max(getHeight(node.lChild), getHeight(node.rChild)) + 1;
		lNode.height = max(getHeight(lNode.lChild), node.height) + 1;

		if (node == root) {
			root = lNode;// 更新根结点
		}
		return lNode;
	}

剩下三个操作就不细说了,接下来我们再在插入和删除的时候,进行适当的判断,插入代码如下

	public void insert(int data) {
		if (root == null) {
			root = new Node(data);

		} else {
			insert(root, new Node(data));
		}
	}

	// node 为插入的树的根结点
	// insertNode 为插入的节点
	private Node insert(Node node, Node insertNode) {
		if (node == null) {
			node = insertNode;
		} else {
			if (insertNode.data < node.data) {// 将data插入到node的左子树
				node.lChild = insert(node.lChild, insertNode);
				// 如果插入后失衡
				if (getHeight(node.lChild) - getHeight(node.rChild) == 2) {
					if (insertNode.data < node.lChild.data) {// 如果插入的是在左子树的左子树上,即要进行LL翻转
						node = leftLeftRotation(node);
					} else {// 否则执行LR翻转
						node = leftRightRotation(node);
					}
				}
			} else if (insertNode.data > node.data) {
				// 将data插入到node的右子树
				node.rChild = insert(node.rChild, insertNode);
				// 如果插入后失衡
				if (getHeight(node.rChild) - getHeight(node.lChild) == 2) {
					if (insertNode.data > node.rChild.data) {
						node = rightRightRotation(node);
					} else {
						node = rightLeftRotation(node);
					}
				}
			} else {
				System.out.println("节点重复啦");
			}
			node.height = max(getHeight(node.lChild), getHeight(node.rChild)) + 1;
		}
		return node;
	}

删除代码如下

	public void remove(int data) {
		Node removeNode = new Node(data);
		if (contains(root, removeNode)) {
			remove(root, removeNode);
		} else {
			System.out.println("节点不存在,无法删除"+data);
		}
	}

	// 删除节点
	private Node remove(Node node, Node removeNode) {
		if (node == null) {
			return null;
		}
		// 待删除节点在node的左子树中
		if (removeNode.data < node.data) {
			node.lChild = remove(node.lChild, removeNode);
			// 删除节点后,若失去平衡
			if (getHeight(node.rChild) - getHeight(node.lChild) == 2) {
				Node rNode = node.rChild;// 获取右节点
				// 如果是左高右低
				if (getHeight(rNode.lChild) > getHeight(rNode.rChild)) {
					node = rightLeftRotation(node);
				} else {
					node = rightRightRotation(node);
				}
			}
		} else if (removeNode.data > node.data) {// 待删除节点在node的右子树中
			node.rChild = remove(node.rChild, removeNode);
			// 删除节点后,若失去平衡
			if (getHeight(node.lChild) - getHeight(node.rChild) == 2) {
				Node lNode = node.lChild;// 获取左节点
				// 如果是右高左低
				if (getHeight(lNode.rChild) > getHeight(lNode.lChild)) {
					node = leftRightRotation(node);
				} else {
					node = leftLeftRotation(node);
				}
			}
		} else {// 待删除节点就是node
				// 如果Node的左右子节点都非空
			if (node.lChild != null && node.rChild != null) {
				// 如果左高右低
				if (getHeight(node.lChild) > getHeight(node.rChild)) {
					// 用左子树中的最大值的节点代替node
					Node maxNode = maxNode(node.lChild);
					node.data = maxNode.data;
					// 在左子树中删除最大的节点
					node.lChild = remove(node.lChild, maxNode);
				} else {// 二者等高或者右高左低
					// 用右子树中的最小值的节点代替node
					Node minNode = minNode(node.rChild);
					node.data = minNode.data;
					// 在右子树中删除最小的节点
					node.rChild = remove(node.rChild, minNode);
				}
				
			} else {
				// 只要左或者右有一个为空或者两个都为空,直接将不为空的指向node
				// 两个都为空的话,想当于最后node也指向了空,逻辑仍然正确
				node = node.lChild == null ? node.rChild : node.lChild;// 赋予新的值
			}
		}
		if(node!=null) {
			node.height = max(getHeight(node.lChild), getHeight(node.rChild)) + 1;
		}
		return node;
	}

 每次在插入和删除时进行这样的操作之后,我们的二叉排序树终于变成一颗平衡二叉树啦,这样我们再执行上面一模一样的查找代码时,查找的效率就可以稳定在O log(n),完美!

 

其实仔细想想,这个问题,也是一个取舍的问题,虽然我们最后让二叉排序树的查找效率稳定为O log(n),但是我们却付出了不小的代价,就是每次插入以及删除的时候,都要进行大量的判断以及节点转换,这肯定会大大降低插入和删除的效率,与之带来的收益就是查找效率高,这样再一想,发现有点类似数组和链表的优缺点了,hhhh,事物总是有两面性,所以我们在实际使用时,也要根据场景来适当的做出取舍。

3.哈希表

在说哈希表之前,先回忆一下两个最简单的容器,一个是数组,一个是链表,这二者的优缺点我就不啰嗦了,之前的博客我也说过这样一个问题,既然数组查询快,链表插入删除快,就不能发明一种容器能兼具这二者的优点吗?这样岂不时省事多了,答案是能,没错,这个神奇的容器就是HashMap,而其核心就是哈希表,这时候,你兴冲冲的去查询哈希表,可能会遇到很多晦涩难懂的概念,什么关键字冲突,线性探测再散列,链地址法,再哈希等等,一下子头就大了,放心,我不会去给你灌输这些概念,我喜欢以实际使用的东西,或者叫“成品”来学习某个新的东西,然后再反过来看这些概念,这样就自然而然懂了,所以我们先简单了解HashMap的实现原理,再来看哈希表,就自然而然懂了。

既然是了解HashMap的实现原理,最最正确的方式就是直接打开jdk的源码去看,重点看核心方法put和remove即可,限于篇幅,我就说下大致思想。

我们首先需要知道的是HashMap存储的数据是键值对的形式,也就是key-value形式,然后就是HashMap里的一些重要成员变量及类,其中最重要的就是Node对象,每个Node对象含有key和value字段,用于保存插入的key和value值,Node数组的默认长度是16,当插入一个元素的时候,首先计算key的hash值,然后直接和数组长度-1做与运算,这样就定位到一个具体的下标,然后判断下标处是否有元素值存在,如果有,则以尾插法在该处形成一个链表,否则,就直接放入这个插入元素即可,所以最终效果就是这样的

看了这个结构图后,我们再回到我们的主题--查找,我们再来看看HashMap是如何查找的,首先拿到key值,计算key的hash值,然后同样的方法,和长度减1做与运算,得到下标,如果该下标处为空,则返回找不到,如果不为空,则从链表头开始,逐个遍历该链表,直到找到对应的value值与给定value值相等,若链表遍历完了仍然没有找到,则返回找不到。

我们现在再来看看这个设计有什么巧妙的地方,当我们在查询一个元素时,发现,对于哈希表来说,首先会根据key值来定位一个下标,这个巧妙利用了数组的优势,这样就不用去逐个遍历所有元素,然后如果发现该下标处已经存在了元素,则形成一个链表,而在形成一个链表之后,对同一个下标处的元素来说,插入删除的效率也变高了。或者换种通俗的话就是,使用数组将一个链表分割成了多个小段。总的来说这种设计就是结合了数组和链表,利用了二者的优势所在,完美结合!

好了,到这里,其实就已经学习了哈希表的一种,如上图,就是链地址法解决冲突的哈希表,相信到这里你也明白了,所谓的链地址法的具体含义,就是形成一个链表来解决冲突问题。

链地址法也是最常见的一种设计哈希表的方法,我们现在再来看看另外的两种。

线性探测再散列法,这种设计方式设计的哈希表的原理就是,当插入一个元素的时候,同样的先定位到一个下标,然后如果该下标处已经存在了元素,则判断下标+1的地方是否有元素存在,同样的如果仍然有元素存在,则下标继续+1,直到对应下标处没有元素存在时,则将元素插在这个地方。

再哈希法,这个设计方式就比较简单粗暴了,直接在计算key的hash值的方法时,也就是在定位具体的下标时,用两次hash函数来计算,这样原本一次hash计算到相同地方的元素,因为有第二次hash计算,所以会在二次hash函数处理之后,再次判断是否定位到了同一下标,若还是定位在统一下标,则继续hash函数处理,直到冲突不再发生。

我们仍然回到我们的主旨--查找上来,对这两种方法设计的哈希表,我们在查找时就是先定位,然后如果不存在元素,则“查找返回空”,否则比对对应的value值,如果不相等,则根据设计方法(线性探测再散列或再哈希)得到“下一个地址”,然后判断“下一个地址”是否为要查找的元素。

好了,到这里,基本说完了三种设计哈希表的方式以及对应的查找方法,个人觉得每一种方式都有自己的特点和适用场景,没有孰好孰坏,只有当我们都掌握了之后,我们才可以去选择用哪种方式来实现哈希表,完成业务要求。

结语

这次说的主要是查找,内容相对简单,但是查找这个东西,一但结合实际场景之后,还是有很多需要注意和深究的地方,比如海量数据排序和查找,所以只有会了基础,才能有选择的余地,以后实际场景中若是遇到了相关的问题,再总结归纳一篇“实际场景版”的,今天就到这里了。

2018-10-06 00:29:00 weixin_34168700 阅读数 84

1. 二叉排序树

  • 如果它的左子树不为空,那么左子树上的所有结点的值均小于它的根结点的值
  • 如果它的右子树不为空,那么右子树上的左右结点的值均大于它的根结点的值
  • 根结点的左子树和右子树又是二叉排序树。
    二叉排序树通常采用二叉链表作为存储结构。
    中序遍历二叉排序树便可得到一个递增有序序列
    一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即是对无序序列进行排序的过程。

二叉排序树的二叉链表存储表示

typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct BSTNode
{
    ElemType data;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

(1) 二叉排序树的递归查找

  1. 若二叉排序树为空,则查找失败,返回空指针。
  2. 若二叉排序树非空。将给定值key与根结点的关键字T->data.key进行比较。
  • 若key等于T->data.key,则查找 成功,返回根结点地址。
  • 若key小于T->data.key,则递归查找左子树。
  • 若key大于T->data.key,则递归查找右子树。
BSTree SearchBST(BSTree T, KeyType key)//递归算法  
{           
    If((!T)|| key == T->data.key)     return T;                   
    else if(key <  T->data.key)      return SearchBST(T->lchild, key);           
    else    return SearchBST(T->rchild, key);  
} 
 

(2) 二叉排序树的插入

  1. 若二叉树为空,则将待插入结点*S作为根结点插入到空树。
    2.若二叉排序树非空,则将key与根结点的关键字 T->data.key进行比较:
  • 若key小于 T->data.key,则将*S插入左子树。
  • 若key大于 T->data.key,则将*S插入右子树。

时间复杂度:插入一个节点算法的O(㏒2n),插入n个的总复杂度为O(n㏒2n)。
二叉排序树插入的基本过程是查找,所以时间复杂度同查找一样。

void InsertBST(BSTree &T,ElemType e)
{
    if(!T)
    {
        S=new BSTNode;
        S->data =e;
        S->lchild = S->rchild =NULL;
    }
    else if(e.key <  T->data.key)  InsertBST(T->lchild,e);
    else if(e.key >  T->data.key)  InsertBST(T->rchild,e);
}

(3) 二叉排序树的创建

  1. 将二叉排序树初始化为空树。
    2.读入一个关键字为key的结点。
  2. 如果读入的关键字key不是输入结束的标志,则循环执行以下操作:
  • 将此结点插入二叉排序树T中:
  • 读入一个关键字为key的结点。
void CreateBST(BSTree &T)
{
    T=NULL;
    cin >> e;
    while(e.key != ENDFLAG)
    {
      InsertBST(T,e)    ;
      cin>>e;
    }
}

(4)二叉排序树的删除

11116807-6c99ba384ace0c39.png

11116807-7f5b9c9fd3b3755d.png

void DeleteBST(BSTree &T,KeyType key)


11116807-a4cbe620a21c6e3f.png

11116807-caa3f309e980d046.png

2.平衡二叉树

(1) 左子树和右子树的深度之差的绝对值不超过1.
(2)左子树和右子树也是平衡二叉树。
若将二叉树上结点的平衡因子定义为该结点左子树和右子树的深度之差,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。

2010-06-18 09:52:00 liutailiang2 阅读数 173

查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。

对查找表经常进行的操作有:

1. 查询某个特定的数据元素是否在查找表中

2. 检索某个特定的数据元素的各种属性

3. 在查找表中插入一个数据元素

4. 从查找表中删除某个元素。

 

查找分为:静态查找,动态查找

 

二叉排序树(Binary Sort Tree)或是一颗空树,或是具有以下性质的二叉树:①。若它的左子树不空,则左子树上的所有节点的值均小于它的根节点的值;②。若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;③。它的左右子树也分别为二叉排序树。

 

平衡二叉树(Balance Binary Tree 或 Height-Balance Tree)又称AVL树。它或则是一颗空树,或则是具有下列性质的二叉树:它的左右子树都是平衡二叉树,且左右子树的深度之差的绝对值不超过1.

 

 

 

2016-09-17 21:42:31 WKX18330698534 阅读数 476

     我们知道,将数据采用顺序存储或者链式存储等多种方式存储不是最终目的,我们要使用存储的数据,发挥它的作用。但是,在使用数据时,要先对数据进行查找,在日常生活和各种软件系统中,查找是一种十分常见的操作,下面我为大家讲解一下我对查找表的理解。

导图:

                 


    由图可以看出,查找表可分为动态查找表和静态查找表。之所以这么区分他们,是根据我们的需求而来。如果我们仅需要查找表中的某一元素或某一元素的属性,则使用静态查找,如果需要对查找表结构进行修改,则选择动态查找。

静态查找表:

   静态查找表中,最简单的实现方式是以顺序表为存储结构,顺序表的存储更像我们的数组,通过键值进行存储。查找时,从表的最后一个元素开始向前查找,设置第一个元素为岗哨,将要被查找的值赋给岗哨。每次拿岗哨的值与表中的值从后向前做对比。查到后终止,返回位置。也可以倒过来,将岗哨放在最后,从后往前查。
   静态查找表是已经完全储存好数据的表,为了提高查找速率,我们将数据进行处理,使其有序。方法有两种:按块有序,建立有序表。按块有序,将数据分块,标明每块的最大键值和块起始位置(索引派上用场)。在查找时,分两个阶段:第一阶段,将key与最大键值比较确定在哪个块(这个过程可以使用二分查找,也可使用顺序查找)。而建立完全的有序表后,就可以使用我们最熟悉的二分查找(向下取整)。

动态查找表:

   静态查找表一旦建立后,所含的数据元素是固定不变的,动态查找表是根据排序规则实现边查边生成。有两种方式:二叉排序树(二分法)和散列表(函数关系)。

二叉排序树:

性质:

若左子树不空,则左子树上所有的结点的键值均小于根结点键值
若右子树不空,则右子树上所有的结点的键值均大于根结点键值
根的左右子树也分别为二叉排序树。
中序遍历得到升序序列(有序序列)  
  查找二叉排序树中的数据和向其中插入数据都需要查找,因为二叉树的性质,查找的过程就使用了二分法规则。二叉排序树是一种树形存储,和顺序表一样,都是将值存储到某种结构中,根据该结构的位置找到存储位置。我们在使用该值时,要先用键值进行比较,才能找到在该结构中的位置,比如,数组 ele【i】=key。

散列表:

   散列表使用函数将键值和存储地址建立函数关系,直接根据key找到存储位置,不需要找i。关于散列表,主要是解决同义词之间的冲突,相信大家看我的导图就能理解了,我就不多做解释了。

最后:

   这是我对概念的简单理解,还没有联系到具体的生活中,如果大家有更通俗的理解,希望咱们能一起探讨。

2018-01-09 22:00:37 angela2016 阅读数 233

2018年6月5日思考

【静态查找】
顺序查找:线性查找(顺序表的结构)可以通过设置哨兵使判断最后一定成立,然后退出循环,避免了多余的边界(与n的比较)比较。
折半查找:有序表,时间复杂度为O(logn), mid = low + 1/2(high-low)
插值查找:有序表, 时间复杂度为O(logn), mid = low+((key -low)/(high-low))*(high-low)
在查找表较大,关键字分布比较均匀的情况下,性能较好。
斐波那契查找:有序表,时间复杂度为O(logn),mid = low + F[k-1]-1
索引,加快查找的一种数据结构。分为线性索引,树形索引,多级索引。其中线性索引,分为三种,分别是稠密索引,分块索引和倒排索引。其中稠密索引中的索引项多是按照关键码有序的排列,可以采用有序表的查找技术;分块索引,块内无序,快间有序,需要维护的表项有块最大的关键码,块起始的地址,块元素的个数;倒排索引,记录号表存储具有相同的次关键字的所有记录的记录号,这样的索引方法为倒排索引,就是索引到底有那些记录次关键字相同。

【动态查找】
二叉排序树的目的不是为了排序,而是为了查找和插入删除关键字的速度提高而产生的。在有序数据集上查找,速度快于无序的数据集,而二叉树的非线性结构也有利于插入和删除的实现。
二叉排序树中序遍历就是一个从小到大排好序的结构!!!
查找:有序表查找
插入:查找,若存在则不进行插入,否则,在查找的最后一个元素的地方继续插入。
删除:如果删除的是叶子结点, 则不会影响到整个二叉排序树的结构,可直接删除;
如果删除的是只有左子树或右子树的分支结点,则子承父业即可。
如果删除的是既有左子树,又有右子树的分支结点,则需要考虑的是利用前驱结
点或后继结点来代替。利用前驱结点来代替的话,我们只需要考虑前驱结点的左子
树的情况即可,也就是把前驱结点的左子树的根节点替换到前驱结点原来的位置,
前驱结点替换到需要删除的结点位置。如果考虑利用后继结点来代替的话,我们只
需要考虑后继结点的右子树即可,将后继结点的右子树的根节点代替后继结点,将
后继结点代替到需要删除的地方即可。
二叉树删除时的代码思路:
判断删除的地方属于删除的哪种情况,属于左右子树均有的情况,也需要分,如果左子树没有右分支的情况,和有右分支的情况,不同的处理手段。
二叉树的性能,我们希望看到的二叉树排序树是平衡的,此时时间复杂度为O(logn), 类似于折半查找的情况,当二叉排序树是斜树时,此时时间复杂度为O(n),类似于顺序查找。

平衡二叉排序树(self-Balancing Binary Search Tree/Height-Balanced Binary Search Tree),AVL树,每一个结点的左子树和右子树的高度最多相差1。查找和插入,删除的时间复杂度均为o(logn)。
平衡二叉树的构建代码思路:
平衡二叉树的结点的结构需要存储自身的值,需要左右结点的指针域,也需要有一个存储其平衡因子的变量(BF/balance factor),在插入AVL树中,我们首先要判断一下能不能插入,如果已经存在的,当然不能插入了,否则,可以插入,插入时,如果插到了左子树上,则原本是LH,则不平衡了,需要做左平衡处理,然后跳出;原本是EH,则仍然平衡,需要退回上一层继续平衡的判断;原本是RH,则整个树肯定是平衡的,跳出判断;如果插到了右子树上,与左子树的判断对称相反即可。
左平衡处理,需要判断,最小不平衡子树的左结点的平衡因子,如果是LH的情况,则直接进行左旋即可,不可能是EH的情况,哈哈,如果是RH的时候,比较复杂,需要把RH转变为LH然后进行处理。
平衡二叉树的构建中,需要用到左旋和右旋的操作,RH>1的情况下发。操作的对象都是最小不平衡子树,只要他平衡了,整体也就平衡了。而用到左旋右旋是在左平衡,右平衡中用到旋转操作。在左平衡中,如果最小不平衡子树的根节点和其左子节点的平衡因子均为LH,说明可以直接旋转,并且其最小不平衡子树根节点和左子结点的平衡因子均为EH;若最小不平衡子树的根节点和左子树结点的平衡因子符号不同,也就是左子节点为RH时,判断左子节点的右子结点的情况,若右子结点为LH,说明插入在了右子结点的左边,需要左旋,然后右旋操作,若右子结点为RH,说明插入在了右子结点的右边,说明也是需要左旋,然后右旋。

在AVL树中,最主要的是将不平衡消灭在摇篮里,然后再消灭的时候,需要考虑他们之间的符号,也就是同号之间,旋转一次即可,不同号之间需要旋转二次。

多路查找树(B树):每一个结点的孩子数可以是多于二个,且每一个结点处可以存储多个元素,由于是查找树,所有元素之间存在某种特定的排序关系。
2-3树,2结点或3结点来组成,2结点存储一个元素,无孩子结点或有二个孩子结点;3结点存储二个元素,无孩子结点或有三个孩子结点。并且所有的叶子都在同一层上。
2-3树的插入:插入操作发生在叶子结点上,如果是空树,2结点的情况比较简单,如果是3结点的情况,如上一层为2结点,则可以在上一层2结点作文章,将其变为3结点的情况,若上一层也是3结点,则返回到上上层来进行判断;若一直到根节点都不存在2节点的情况,说明目前的高度已经无法满足需求,需要分裂来加高深度了。(中间大小做根节点是不变的真理)
2-3树的删除:【叶子结点】若删除的的节点在3结点,可以将其变为2结点;若删除的是2结点,若双亲也是2结点,且有一个3结点的兄弟,则分裂3结点,若双亲是2结点,我们需要将上一级的结点放下来,形成一个3结点的兄弟,然后分裂3结点;若删除的2 结点,双亲是3结点,则分裂3结点为2结点;若全部结点全部都是2结点,说明需要减少高度来满足条件。【分支结点】需要通过中序遍历,利用前驱结点或后继结点来代替。

2-3-4树,增加了4结点的扩展的问题。
2-3树,2-3-4树均为B树的扩展,是一种平衡的多路寻找树,最大的孩子结点的数目为阶数。B树的应用,最主要的是结点存储的数值灵活,并且把根结点常驻内存,需要什么就从硬盘中调用,大大提高了效率。可以说B树就是为了内外存数据交互而存在的。
B+树,是对于B树的改造,此时,分支结点中的元素在叶子结点中也会被列出来,避免了从不同的页面进行切换的困扰。也就是根结点只提供索引的作用,不提供实际的访问,实际的访问需要在叶子结点中进行,这样就避免了不停的切换的时间花费。

hash(散列表),散列技术既是一种存储技术,也是一种查找技术。一般可以利用hash来继续存储查找的关键词,一般都具有代表性,并且不适合范围查找,或者模糊查找,只适合精确查找,并且有一个很重要的点在于解决冲突的问题。
散列函数的选择:
直接定址法f(key) = a*key +b(知道分布的情况,小且连续)
数字分析法:抽取关键的数字,然后对数字进行运算。(位数大,知道分布,并且中间几位分布均匀)
平安取中法:取平方后取中间几位(不知道分布,位数不大的情况)
折叠法:二头取数字,然后对其叠加求和(不知道分布,位数比较大)
除留余数法:f(key) = key mod p (p的选取小于等于表长最好接近的最小质数或不包含小于20质因子的合数)
随机数法:f(key) = random(key)
处理冲突的办法:
开放定址法
(线性探测法):一旦发生冲突,则寻找下一个空的散列地址(存储)
fi(key)= (f(key)+di) mod m(di = 1,2,3,4..m-1)
(二次探测法)
fi(key) = (f(key)+di) mod m(di = 1^2,-1^2,2^2,-2^2,….q^2, q<=m/2)
(随机探测法)
fi(key) = (f(key)+di) mod m(di采用随机函数来计算)
再散列函数法
多种散列函数,一个冲突换另一个
fi(key) = RHi(key) (i = 1,2,3..k)
链地址法
对于堆积的情况,采用单链表来扩展。
公共溢出区法
对于冲突的情况,存储在公共的溢出区。

散列表的好坏:
散列函数是否均匀
处理冲入的方法
散列表的装填因子(空间换时间,保证装填因子不变)

查找表(Search Table):由同一类型的数据元素(或记录)构成的集合。
关键字(Key): 是数据元素中的某个数据项的值,又称为键值、用它可以表示一个数据元素。他也可以用来标识一个记录的某个数据项(字段),称为关键码。
主关键字(唯一标识一个数据元素也就是记录),主关键字所在的数据项称为主关键码。
次关键字(可以识别多个数据元素),次关键字所在的数据项称为次关键码。
查找表的操作方式分为二种:静态查找表和动态查找表。
静态查找表:只做查找操作的查找表。查询某个“特定的”数据元素是否在查找表中,检索某个“特定的”数据元素和各种属性。
动态查找表:在查找过程中,同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素。
我们为了面向查找设置的数据结构,称为查找结构。从逻辑上说,查找所基于的数据结构是集合,一般来说集合中的元素是没有什么本质的关系,但我们可以不改变数据元素之间的关系,在存储时将其组织为表,树等结构。

顺序表查找
顺序查找又叫做线性查找,是从表中的第一个元素开始进行比对,然后进行元素的关键字与给定值的比较过程。
【技巧】可以添加一个哨兵,在查找方向的尽头,或者头部,或者尾部,这样可以避免越界的一些比较,在数据量比较大的时候,还是比较有优势,但顺序查找自身的缺点也是很明显的,因为在N极大的情况下,查找的效率极其低下,不过优点也是有的,就是很简单啊·~~

有序表查找
对数据元素来进行排序,采用线性存储的方式实现,然后采用比较有技巧的手段来进行查找操作。
折半查找(二分查找)
在二分查找中,时间复杂度为O(logn),而之前的时间复杂度为O(n),所以,很大程度上提高了查找的效率,但有序表查找的一个显著的缺点在于需要维护一个有序表,对于需要大量进行插入或者删除的数据集而言,维护数据的有序性需要不小的工作量。
插值查找
在插值查找中,我们要根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心在于插值的公式。一般而言,插值查找适用于分布比较均匀的查找表。
斐波拉契查找
在斐波那契查找中,我们利用了黄金分割的原理来实现。对于平均性能而言,斐波那契查找要优于二分查找,尽管其时间复杂度也为O(logn),但如果是最坏的情况下,查找的效率要低于二分查找。
三种有序的查找中,二分查找利用的是加法和除法的运算,插值查找利用的是复杂的四则运算,斐波那契查找利用的是加法和减法运算,在海量的数据时,可能在计算时间上有细微的差别,三种有序表的查找分割点选择不同,在不同情况下,选择不同的方法。
【注意的要点】在这个地方,我一直不明白为什么要用斐波那契数列来做呢,查找资料之后才知道,这个著名的数列确实有很多迷人的地方,可以利用递归或者循环来实现数列,并且后一个数是前二个数的和,这是可以从数列的定义角度可以得知的,但还有一个很重要的性质是前一个数除以后一个数无比接近于黄金分割。
觉得斐波那契数列真的是一个很神奇的数列,怎么那么神奇,此时的斐波那契数列是从下标为1的1来进行处理的,也就是仅处理{1,1,2,3,5,8,13,21,34…},依次来看斐波那契数列,前一个数除以后一个数无限接近于0.618,多完美的一个数啊。对于数组的下标是我们拆分的目标,我们寻找最大的数组下标,将这个下标放置在斐波那契数列中,然后在数列中寻找数值与数组下标+1最相近的稍大或者相等的数,为什么这个时候涉及到加一或者减一操作,是因为描述的是数组的个数。
将F[k]-1个数拆分为F[k-1]与F[k-2]个数。
这里写图片描述

索引是为了加快数据查找速度而设计的一种数据结构,索引是把一个关键字与它对应的记录相关联的过程。一个索引包括若干个索引项,每个索引项至少要包括关键字以及其对应的记录在存储器中的位置等信息。
索引在大型数据库以及磁盘文件中是一种重要的技术。
索引按照结构可以分为线性索引,树形索引和多级索引。我们主要关注线性索引的知识。线性索引也就是把索引项集合组织为线性结构,也称为索引表。

线性索引之稠密索引
稠密索引是指在线性索引中,将数据集中的每个记录对应一个索引项,此时索引项按照关键码有序的排列。O(logn)
有序的关键码排列,使得查找时可以采用有序表的查找技术来优化,但是数据量非常大的情况下,索引项的规模同样很大,对于内存有限的计算机而言,需要反复的访问磁盘,查找性能反而下降。

线性索引之分块索引
稠密索引的空间消耗巨大,为了克服稠密索引的缺点,我们将数据分块,块内无序,块间有序,然后对每一块建立索引,这种方法称为分块索引。
在块索引中,需要记录块中最大关键码,需要存储块中记录的个数,需要指向块首的元素,以便对块来进行遍历。
在对分块索引进行查找时:
块间有序,所以可以利用有序表的查找技术,找到所在块;块内无序,所以需要顺序查找块内的无序表。
O(n1/2),最佳的情况是分的块数与块中的数据元素的个数相同。

线性索引之倒排索引
在倒排索引中,我们的索引项分为二个部分,第一个部分是次关键码,第二个部分是记录号表,记录号表存储具有相同次关键字的所有记录的记录号。倒排索引是根据属性值来确定记录的位置。
倒排索引的优点是查找记录非常快,在生成索引表之后,不需要读取记录,即可得到结果,但缺点在于记录号不定长,而且对于每个属性值都建立索引项维护比较困难。

在学习数据结构,一个很大的感受在于,一定要因地制宜,也就是在什么情况下,要选用合适的数据结构,这样会带来极大的便利。

二叉排序树又称为二叉查找树,或者为空树,或者对于根的左子树都比他小,对于根的右子树的值都比根结点的数值大(递归的定义法则
二叉排序树的查找操作
最主要的还是利用了递归来做,递归主要是来找到退出的条件
什么样的情况属于正常退出,什么样的情况属于异常退出。
二叉排序树链表结点的定义

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

二叉排序树的查找

Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
    if(!T)
    {
       *p = f;
       return FALSE;
    }
    else if(key == T->data)
    {
       *p = T;
       return TRUE;
    }
    else if(key < T->data)
       return SearchBST(T->lchild, key, T, p);
    else
       return SearchBST(T->rchild, key, T, p);
}

二叉树的插入操作

Status InsertBST(BiTree *T, int key)
{
    BiTree p,s;
    if(!SeaechBST(*T, key, NULL, &p))
    {
       s = (BiTree)malloc(sizeof(BiTNode));
       s->data = key;
       s->lchild = s->rchild = NULL;
       if(!p)
           *T = s;
       else if(key < p->data)
           p->lchild = s;
       else
           p->rchild = s;
       return TRUE;
    }
    else
       return FALSE;
}

对于二叉排序树而言,删除操作则稍显困难,我们对删除结点来进行分类分析,叶子结点的情况,比较简单,仅有左或者右子树的情况,也比较简单,可以直接子承父业,对于左右子树都存在的情况,则需要找一个中间的傀儡,也就是继承人。。哈哈~~

Status Delete(BiTree *p)
{
   BiTree q, s;
   if((*p)->rchild == NULL)
   {
      q = *p;
      *p = (*p)->lchild;
      free(q);
   }
   else if((*p)->lchild == NULL)
   {
      q = *p;
      *p = (*p)->rchild;
      free(q);
   }
   else
   {
      q = *p;
      s = (*p)->lchild;
      while(s->rchild)
      {
         q = s;
         s = s->rchild;
      }
      (*p)->data = s->data;
      if(q!=*p)
         q->rchild = s->lchild;
      else
         q->lchild = s->lchild;
      free(s);
   }
   return TRUE;
}
Status DeleteBST(BiTree *T, int key)
{
   if(!*T)
   {
      return FALSE;
   }
   else
   {
      if(key == (*T)->data)
         return Delete(T);
      else if(key < (*T)->data)
         return DeleteBST(&(*T)->lchild, key);
      else
         return DeleteBST(&(*T)->rchild, key);
   }

}

二叉排序树是以链接的方式来进行存储的,插入删除操作的时间性能比较好,而对于二叉树的查找而言,与二叉树的形状有很大的关系,我们希望二叉排序树能够尽可能的平衡,这样近似于折半查找(完全二叉树是极致的平衡状态),对于不平衡的极致状态是顺序查找,此时时间复杂度为O(n)。

平衡二叉树(AVL树)
平衡二叉树(Self-Balancing Binary Search Tree或者Height-Balancing Binary Search Tree),是一种二叉排序树,其中每一个结点的左子树和右子树的高度差至多等于1。(考虑用统用的递归的定义来理解。。)
平衡因子BF(Balance Factor):二叉树上的结点左子树深度减去右子树深度的值称为平衡因子。平衡二叉树的平衡因子只能为-1,0,1中的一个值。
最小不平衡子树:距离插入结点最近的,且平衡因子的绝对值大于1的结点为根结点的子树,我们称为最小不平衡子树。
构建平衡二叉树的过程:每插入一个结点,先检查是否因为插入而破坏了树的平衡性,若破坏了,就找到最小不平衡子树,在保证二叉排序树的前提下,调整最小不平衡子树中各个结点的关系,然后使之成为新的平衡子树。

typedef struct BiTNode
{
    int data;
    int bf;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

右旋操作

void R_Rotate(BiTree *p)
{
   BiTree L;
   L = (*p)->lchild;
   (*p)->lchild = L->rchild;
   L->rchild = (*P);
   *P = L;
}

左旋操作

void L_Rotate(BiTree *P)
{
   BiTree R;
   R = (*P)->rchild;
   (*P)->rchild = R->lchild;
   R->lchild = (*P);
   *P = R;
}

左平衡旋转处理的函数

#define LH +1
#define EH 0
#define RH 1
void LeftBalance(BiTree *T)
{
   BiTree L,Lr;
   L = (*T)->lchild;
   switch(L->bf)
   {
       case LH:
          (*T)->bf = L->bf = EH;
          R_Rotate(T);
          break;
       case RH:
          Lr = L->rchild;
          switch(Lr->bf)
          {
             case LH: (*T)->bf = RH;
                 L->bf = EH;
                 break;
             case EH: (*T)->bf = L->bf = EH;
                 break;
             case RH: (*T)->bf = EH;
                 L->bf = LH;
                 break;
          }
          Lr->bf = EH;
          L_Rotate(&(*T)->lchild);
          R_Rotate(T);
   }
}

最本质的问题,是应该找到那个地方不平衡了,哪个地方最应该修正。

这里写图片描述
这里写图片描述
这里写图片描述

Status InsertAVL(BiTree *T, int e, Status *taller)
{
   if(!*T)
   {
      *T = (BiTree)malloc(sizeof(BiTNode));
      (*T)->data = e;
      (*T)->lchild = (*T)->rchild = NULL;
      (*T)->bf = EH;
      *taller = TRUE;
   }
   else
   {
      if(e == (*T)->data)
      {
         *taller = FALSE;
         return FALSE;
      }
      if(e < (*T)->data)
      {
         if(!InsertAVL(&(*T)->lchild, e, taller))
             return FALSE;
         if(*taller)
         {
             switch((*T)->bf)
             {
                case LH:
                   LeftBalance(T);
                   *taller = FALSE;
                   break;
                case EH:
                   (*T)->bf = LH;
                   *taller = TRUE;
                   break;
                case RH:
                   (*T)->bf = EH;
                   *taller = FALSE;
                   break;
             }
         }
      }
      else
      {
         if(!InsertAVL(&(*T)->rchild, e, taller))
             return FALSE;
         if(*taller)
         {
            switch((*T)->bf)
            {
               case LH:
                  (*T)->bf = EH;
                  *taller = FALSE;
                  break;
               case EH:
                  (*T)->bf = RH;
                  *taller = TRUE;
                  break;
               case RH:
                  RightBalance(T);
                  *taller = FALSE;
                  break;
            }
         }
      }
   }
   return TURE;
}

主函数

int i;
int a[10] = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
BiTree T = NULL;
Status taller;
for(i = 0; i < 10; i++)
{
   InsertAVL(&T, a[i], &taller);
}

多路查找树
我们处理的数据在内存中,因此,考虑的是内存中的运算时间复杂度。如果处理的数据非常大,大到内存没有办法来处理,需要不断的从硬盘等存储设备中饭调入调出内存页面。涉及到了外部存储设备,则时间复杂度的计算也就会发生变化,访问该集合元素的时间已不仅仅是寻找该元素所需要的比较次数的函数,还必须考虑到对硬盘等外部存储设备的访问时间以及会对该设备做出多少次单独访问。
为了减低对外存设备的访问次数,我们需要新的数据结构来处理这样的问题。我们传统的树结构中,每个结点存储一个元素,但这在数据量大的情况下会造成高度高,结点度数大等问题,造成了时间效率上的瓶颈,为了解决这个问题,我们将一个结点不一定存储一个数据,不一定仅仅有二个子结点来对问题进行扩展,得到了多路查找树的结构。
2-3树
2-3-4树
B树,上述二种树都是B树的一种扩展。。呜呜,今天中午写了一中午的文章,因为网络故障,然后没有保存了,哭,,算了,记到脑子里就算了,不管了·~
B树中有几个概念还是要重复一下:首先,是M阶结点,也就是有M个孩子结点,然后本身有M-1个元素,然后将M个孩子结点的取值分布范围分散开来;其次,每个叶子结点都在同一层上。
在B+树中,我们B树的中序遍历过程中,可能存在重复遍历数据,所以,我们对B树来进行改进,最终得到适合遍历的组织形式。
一棵B+树和B树的差异在于:
①有n棵子树的结点中包含有n个关键字;
②所有的叶子结点包含全部关键字的信息,及指向含这些关键字记录的指针,叶子结点本身也是按照关键字的大小自大而小顺序链接;
③所有分支结点可以看成是索引,结点中仅含有其子树中的最大的关键字。

散列表查找(哈希表)
散列技术是一种不需要比较就可以获得需要的记录的存储位置的技术。散列技术是一种对应关键,key—>f(key)的对应关系。此时的f称为散列函数,也称为哈希函数(Hash)。采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或者哈希表。关键字对应的记录存储位置,称为散列地址。
散列表查找步骤:
1,在存储时,根据散列函数计算记录的散列地址,并按照此散列地址存储该记录。
2,在查找记录时,通过同样的散列函数来计算记录的散列地址,按此散列地址访问该记录。
所以,,通过以上的说法,我们可以知道,散列技术既是一种存储方法,也是一种查找方法。散列表是主要面对查找的一种存储结构。
对于散列表而言:适合于查找给定值相等的记录,简化了比较结果,效率大大的提高,但散列表也存在很多的问题,首先,散列表只适合关键词唯一的情况下建模,才能具有代表性,其次,散列表对于范围查找而言,真的没有办法的,最后,最主要的问题是冲突的问题。所以,我们的目的是建立一个简单,均匀,存储利用率高的散列函数是我们主要的研究的最关键的问题。而且,为了减少冲突的产生,也是我们研究的关键的问题。

散列函数的构造方法
1, 计算简单
2, 散列地址分布均匀
常见的构造方法:
1,直接定址法
关键词的线性函数来作为散列函数,我们需要提前知道关键字的分布情况,适合查找表较小且连续的情况。
2,数字分析法
抽取有代表性的部分来进行计算散列存储位置,能够通过这种代表性的数字来进行数学操作来将关键字分配到散列表的各个位置。适合于关键字的位数比较大,并且事先知道关键字的分布,并且关键字的分布比较均匀。
3,平方取中法
对数字来取平方,然后取平方之后的数的中间几位,来作为散列地址。平方取中法比较适合不知道关键字的分布,而且位数又不是很大的情况。
4,折叠法
将关键字从左到右分割为位数相等的几部分,然后对几部分来叠加求和,并按散列表表长,取后几位来作为散列地址。
适合于事先不知道关键字的分布,适合关键字位数比较多的情况。
5,除留余数法
f(key) = key mod p (p<=m),此时最重要的部分就是寻找合适的p。根据经验,若散列表表长为m,通常p为小于或者等于表长m的最小质数或不包含小于20质因子的合数。
6,随机数法
选择一个随机数,取关键字的随机函数值来为它的散列地址,也就是f(key)=random(key),这里random是随机函数。当关键字的长度不等时,采用这个方法来构造散列函数是比较合适的。
总之,就是根据实际的情况来选择合适的散列函数。在选择的过程中,我们需要考虑,记录散列地址的时间,需要考虑关键字的长度,需要考虑散列表的大小,需要考虑关键字的分布情况,需要考虑记录被查找的频率等问题。
处理散列表的冲突的方法:
1,开放定址法
一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到。
fi(key) = (f(key)+di) mod m (di = 1,2,3…m-1)
我们把这种解决冲突的开放定址法称为线性探测法。
在这种方法中,本来不是同义词却需要争夺一个地址的情况,我们称这种现象为堆积。堆积的出现,使得我们需要不断的处理冲突,无论是存入还是查找效率都会大大降低。
fi(key) = (f(key)+di) mod m (di = 1^2, -1^2, 2^2, -2^2…q^2, -q^2,q

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct 
{
    int *elem;  动态数组
    int count;
}HashTable;
int m = 0;

对散列表进行初始化

Status InitHashTable(HashTable *H)
{
   int i;
   m = HASHSIZE;
   H->count = m;
   H->elem = (int *)malloc(m*sizeof(int));
   for(i = 0; i < m; i++)
      H->elem[i] = NULLKEY;
   return OK;
}

定义了散列函数

int Hash(int key)
{
   return key % m;
}

对散列表进行插入操作

void InsertHash(HashTable *H, int key)
{
   int addr = Hash(key);
   while (H->elem[addr] != NULLKEY)
      addr = (addr+1) % m;
   H->elem[addr] = key;
}

对散列表进行查找操作

Status SearchHash(HashTable H, int key, int *addr)
{
    *addr = Hash(key);
    while(H.elem[addr]!=key)
    {
       *addr = (*addr+1) % m;
       if(H.elem[*addr] == NULLKEY|| *addr == Hash(key))
       {
           return UNSUCCESS;
       } 
    }
    return SUCCESS;
}

散列表的查找性能分析:
1,散列函数是否均匀
2,处理冲突的方法
3,散列表的装填因子
装填因子 = 填入表中的记录的个数/散列表的长度
散列表的平均查找长度取决于装填因子,而不是取决于查找集合中的记录的个数。所以,我们需要选择一个合适的装填因子,以便将平均查找长度限定在一个范围之内,虽然是浪费了一定的空间,但换来的是查找效率的大大提升,是值得的

数据结构 查找 静态查找表

阅读数 28

下面用到的结构定义#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)&lt;(b))#defineLQ(a,b)((a)&lt;=(b))typedefintKeyType;typedefstruct...{KeyTypekey;}ElemType;typedefstruct...{ElemType*elem;intlength;}SSTable;...

博文 来自: iteye_12827

数据结构 查找 静态查找表

阅读数 986

下面用到的结构定义#define EQ(a, b) ((a) == (b))#define LT(a, b) ((a) #define LQ(a, b) ((a) typedef int KeyType;typedef struct ...{    KeyType key;}ElemType;typedef struct ...{    ElemType *elem;    int len

博文 来自: nomad2

数据结构--查找(静态查找表)

阅读数 461

构造了次优先查找树//NearlyOptimalSearchTree.cpp:Definestheentrypointfortheconsoleapplication./*-----CODEFORFUN----------------------CREATEDBYDream_Whui-------------2015-3-4----------------

博文 来自: Dream_WHui

数据结构 查找 动态查找表二

阅读数 15

(3)B-树from:http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.3.2.1.htm 当查找的文件较大,且存放在磁盘等直接存取设备中时,为了减少查找过程中对磁盘的读写次数,提高查找效率,基于直接存取设备的读写操作以"页"为单位的特征。1972年R.Bayer和E.M.McCreight提出了...

博文 来自: iteye_12827

数据结构_查找_动态查找表_二叉排序树

阅读数 476

定义:二叉排序树(BinarySortTree)又称二叉查找树。它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)左、右子树也分别为二叉排序树;下面代码中主要实现了二叉树的插入,删除,查找三个功能;具体的实现有注释,如果有错误或者您不理解

博文 来自: lzj5451896
没有更多推荐了,返回首页