数据结构第九章

一、静态查找表

（1）顺序表的查找

? ? ? ? ?1）顺序表查找的结构

typedef struct{
ElemType * elem; //存储空间基址
int length;      //表长
}SSTable;

顺序查找的过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较。（也就是说，在查找到时候从最后一个元素开始查找，在这个表中位置为0的位置空着，留给你要查找的元素）

在顺序表的查找中，需要有一个“哨兵”负责担任监视哨的任务。

ST.elem[0].key = key;
//判断查找的元素（也就是位置0放的位置）是不是和值相等

2）查找的性能分析

查找的操作其实很简单，就是将你要找的值与表中元素一一比较，若不符合，则向前查找，直到找到或者表空为止。

因此顺序查找表的长度为：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【其中i = 1】

可以看做是：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

（2）有序表的查找

有序表的查找，可以从小到大，或者从大到小。我们一般默认是从小到大查找。

1）折半查找

折半查找，查找方式有三个指针：low,high和mid。其中mid指示区间的中间位置，即mid=[(high+low)/2]

1.若key与中间元素相等，则查找成功，返回该元素的存储位置，即mid；
2.若key与中间元素不相等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。（至? ? ?于是前半部分还是后半部分要看key与mid所指向元素的大小关系）
? ?a.在查找表升序排列的情况下，若给定值key大于中间元素则所查找的元素只可能在后半部分。? ? ? ?此时让low=mid+1；
? ?b.若给定值key小于中间元素则所查找的元素只可能在前半部分。此时让high=mid-1；

//折半查找
int Search Bin(SSTable L,ElemType key){
	low = 1,high = ST.length;
	while(low <= high){
		mid=(low+high)/2;		//取中间位置
		if(L.elem[mid]==key)	
			return mid;			//查找成功返回所在的位置
		else if(L.elem[mid]>key){	//从前部分查找
			high=mid-1;
		}
		else
			low=mid+1;		//从后部分查找
	}
	return 0;				//失败返回0
}

二、索引顺序表的查找

索引顺序表也就是分块查找，许多情况下可能遇到这样的表：整个表中未必有序，但若划分成若干块后，每一块中的所有元素均大于或小于其后面的所有元素，称这种特性为分块有序，因此可以为该顺序表建立一个索引表，索引表中为每一块设置设置一索引项，每一索引项包括两部分：该块的起始地址和该块中最大(或最小)关键字的值（或是所限定的最大（小）关键字）。将这些索引项按顺序排列成一有序表，即为索引表。

三、二叉排序树和平衡二叉树

二叉树定义：

二叉排序树（又名二叉查找树）或者是一棵空树；或者是具有以下性质的二叉树：
1）若它的左子树不为空，则左子树上所有结点的值均小于它根节点的值
2）若它的右子树不为空，则右子树上所有结点的值均大于它根节点的值
3）它的左右子树也分别为二叉排序树

简单来说就是：左比根小，右比根大

1）二叉排序树的构造过程

首先我们使用画图的方式来描绘一下二叉排序树的插入过程，如图，我们要在一棵空的二叉排序树中插入一个数组6,2,7,4,0,3,1,5，如图所示：

??首先我们插入第一个元素6，此时二叉排序树中还没有任何一个节点，因此我们应该新建一个节点，并将6存储进去，并将6认定为根节点，如图所示：

??之后我们插入第二个元素2，此时二叉排序树已经不是一个空树了，因此我们需要首先找到适合它的位置，我们将2和6进行对比，判断谁大谁小，我们发现2更小，因此2应该被插入在6的左子树中，之后我们将2和根节点6的左子树进行对比，发现6的左子树是空的，因此这时我们将2存放在6的左子树根节点位置，如图所示：

??之后是元素7,7显然大于6，因此我们要将7放在6的右子树中，经过探寻我们发现6的右子树根节点也是空的，因此我们需要将7放在右子树的根节点上，如图所示：

??之后是元素4，我们首先将4和6对比，发现4是小于6的，因此4应该位于6的左子树上，之后我们将4和6的左子树根节点进行对比，发现4是大于2的，因此4应该被放在2的右子树上，而2的右子树为空，因此4直接被放置在2的右子树根节点上，如图所示：

??之后是元素0，首先我们将0和元素6进行对比，发现0是小于元素6的，因此应该被放置在6的左子树上，之后我们将0和6的左子树根节点进行对比，发现其小于2，因此0应该被放置在2的左子树上，这时我们发现0是小于2的，因此0应该被放置在2的左子树上，同时我们发现2的左子树为空，因此我们将0放置在2的左子树根节点上，如图所示：

??之后是元素3，我们发现元素3是小于6的，因此3应该被放置在6的左子树上，而这时我们就开始研究6的左子树，3大于2，因此3应该被放置在2的右子树上，这时我们开始研究2的右子树，而3是小于2的右子树根节点4的，因此3应该放置在4的左子树上，我们发现4的左子树为空，因此我们将3放置在4的左子树根节点上，如图所示：

??之后是元素1，首先我们将1和6进行对比，发现1是小于6的，因此1应该被放置在6的左子树上，而1又小于2，因此应该被放置在2的左子树上，而1又大于0，因此应该被放置在0的右子树上，0的右子树为空，因此1应该被放置在0的右子树根节点上，如图所示：

??之后我们研究最后一个元素5,5小于根节点6，因此我们应该将5放置在6的左子树上，而5大于2，因此我们应该将5放置在2的右子树上，5大于4，因此5应该被放置在4的右子树上，4的右子树为空，因此我们将5放置在4的右子树根节点上，如图所示：

整个的过程都是从中序这个节点前驱替代

2）平衡二叉树

定义：

左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1

方法：

从一组数中选三个，由小到大排序，取中间为新根，小的放左边，大的放右边

调之前：有左边，将左调到右

? ? ? ? ? ? ? 有右边，将右调到左

比如：

将它调整一下：

四、哈希表

不想比较，直接用函数。

根据关键码值（Key Value）直接进行访问的数据结构。

哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。

哈希表的关键思想是使用哈希函数，将键 key 映射到对应表的某个区块中。我们可以将算法思想分为两个部分：

1.向哈希表中插入一个关键码值：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中。

2.在哈希表中搜索一个关键码值：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值。

构造方法

直接定址法

除留余数法

数字分析法

平方取中法

折叠法

处理冲突方法

开放定址法：

先开n个房间，利用线性放入，如果找x在下面写上比较次数

比如：依次插入9? ?11? ?23? ?19? ?54

用数字除以表长取余数即可