湘潭租房网站/关键词优化设计

1，顺序查找（线性查找）

顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。

基本实现：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败。

顺序查找的存储结构要求：

• 顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。
• 另外，顺序查找的表中元素可以是无序的。

private static boolean Search(int[] s, int key) {for (int i = 0; i < s.length; i++) {if (key == s[i]) {return true;} }return false;
}

2，二分查找

二分查找：先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。

private static int Search(int[] s, int key) {int left = 0;int right = s.length - 1;int mid;while (left <= right) {mid = (right + left) / 2;if (key == s[mid]) {return mid;} else if (key < s[mid]) {right = mid - 1;} else if (key > s[mid]) {left = mid + 1;}}return -1;
}

3，基于索引的分块查找

分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。

查询步骤：① 对索引表使用二分查找法（因为索引表是有序表）；② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；

【例子】判断一个字符串是否为Java关键字。

private static String[] keywords={"abstract","assert","boolean","break","byte","case","catch","char","class","continue","default","do","double","else","extends","false","final","finally","float","for","if","implements","import","instanceof","int","interface","long","native","new","null","package","private","protected","public","return","short","static","super","switch","synchronized","this","throw","throws","transient","true","try","void","volatile","while"};private static class IndexItem implements Comparable<IndexItem>{ //索引项，私有内部类char first;                       //关键字的首字符int begin,end;                    //首字符相同的关键字块在主表中的始末下标public IndexItem(char first, int begin, int end){this.first = first;this.begin = begin;this.end = end;}public String toString(){           //返回索引项的描述字符串return "("+this.first+","+begin+","+end+")";}public int compareTo(IndexItem item){    //索引项比较相等和大小，实现Comparable接口return this.first - item.first;                //仅比较首字符}
private static IndexItem[] index;       //索引表
static{                       //创建扩充索引表；静态初始化块，类加载时执行一次index = new IndexItem[23];for (int i=0, j=0; i<index.length && j<keywords.length; i++){char ch=(char)('a'+i);                         //下一个首字符if (keywords[j].charAt(0)>ch)index[i]=new IndexItem(ch, -1, -1);        //创建索引项表示一个不存在的块else{ int begin = j++;while (j<keywords.length && keywords[j].charAt(0)==ch)//寻找下一个首字符不同的关键字j++;index[i]=new IndexItem(ch, begin, j-1);   //创建索引项表示一个首字符相同的块}}System.out.print("index[]:");
}
public static boolean isKeyword(String str){           //判断str是否为Java关键字int i = str.charAt(0)-'a';          //首字符对应的索引项序号return i>=0 && i<index.length && index[i].begin!=-1 &&SortedArray.binarySearch(keywords, index[i].begin, index[i].end, str)>=0;
}//获得主表查找范围的下界//获得主表查找范围的上界   //折半查找主表的指定范围

4，散列（Hash）

散列的思想：根据纪录的关键字直接找到记录的存储位置，即为关键字和记录的存储位置建立一个对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。对应关系f为散列函数，按该思想建立的表为散列表。

哈希（HASH）表的定义：根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为纪录在表中的存储位置，这种表便称为哈希表，这一影像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。

• 散列方法在表项的存储位置与它的关键字之间建立一个确定的对应函数关系Hash( )，使每个关键字与结构中一个唯一存储位置相对应：Address ＝ Hash ( Rec.key )
• 在查找时，首先对表项的关键字进行函数计算，把函数值当做表项的存储位置，在结构中按此位置取表项比较。若关键字相等，则查找成功。在存放表项时，依相同函数计算存储位置，并按此位置存放。

哈希方法：选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。

哈希函数：哈希方法中使用的转换函数称为哈希函数(杂凑函数)

哈希表：按上述思想构造的表称为哈希表(杂凑表)

冲突：通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。

在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。所以，哈希方法必须解决以下两个问题：

（1）构造好的哈希函数

• 所选函数尽可能简单，以便提高转换速度；
• 所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。

（2）制定一个好的解决冲突的方案

• 查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

5，散列（Hash）——构造方法

（1）直接定址法：Hash(key) = a·key + b    (a、b为常数)

优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。

缺点：要占用连续地址空间，空间效率低。

例：关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：

（2）除留余数法：Hash(key)=key  mod  p    (p是一个整数)

特点：以关键码除以p的余数作为哈希地址。

关键：如何选取合适的p？

技巧：若设计的哈希表长为m，则一般取p≤m且为质数（也可以是不包含小于20质因子的合数）。

（3）乘余取整法：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。

例：欲以学号最后两位作为地址，则哈希函数应为：H(k)=100*(0.01*k % 1 )，其实也可以用法2实现： H(k)=k % 100

（4）数字分析法：某关键字的某几位组合成哈希地址。所选的位应当是：各种符号在该位上出现的频率大致相同。

（5）平方取中法：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。

理由：因为中间几位与数据的每一位都相关。

例：2589的平方值为6702921，可以取中间的029为地址。

（6）折叠法：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。

适用于：每一位上各符号出现概率大致相同的情况。

法1：移位法 ── 将各部分的最后一位对齐相加。

法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。

例：元素42751896, 用法1： 427＋518＋96=1041；用法2： 427 518 96—> 724+518+69 =1311

（7）随机数法：Hash(key) = random ( key )  (random为伪随机函数)

适用于：关键字长度不等的情况。造表和查找都很方便。

6，散列（Hash）——冲突处理

（1）开放定址法（开地址法）

设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。

线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素。

线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。

解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。

（2）二次探测法

仍举上例，关键码集为 {47，7，29，11，16，92，22，8，3}，改用二次探测法处理冲突，建表如下：

（3）链地址法（拉链法）

基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

例：设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为：Hash(key)=key mod 11，用拉链法处理冲突，则建表如图所示。注：有冲突的元素可以插在表尾,也可以插在表头

（4）再哈希法（双哈希函数法）

Hi=RHi(key)       i=1, 2,  …，k，RHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。

优点：不易产生聚集。

缺点：增加了计算时间。

（5）建立一个公共溢出区

思路：除设立哈希基本表外，另设立一个溢出向量表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。

7，二叉排序树

具有BST性质的非空二叉树：

• 左子树的所有结点均小于根的值。
• 右子树的所有结点均大于或等于根的值。
• 它的左右子树也分别为二叉排序树。

二叉排序树的特点：

• 元素可比较相等和大小，关键字互不相同。
• 结点，左子树元素均小于该结点，右子树元素均大于该结点。
• 左、右子树也是二叉排序树。
• 中根次序遍历，升序序列 。

二叉树的构造

从空树出发，依次插入R1～ Rn各数据值：

• 如果二叉排序树是空树，则插入结点就是二叉排序树的根结点；
• 如果二叉排序树是非空的，则插入值与跟结点比较，若小于根结点的值，就插入到左子树中去；否则插入到右子树中。

二叉树的查找操作

① 查找过程与顺序结构有序表中的二分查找相似，查找效率高（log2n）。

② 中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）。

③ 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。

（1）二叉排序树的静态查找

• 从根开始。
• 若key==p.data，则查找成功返回；若key<p.data，则查找p的左子树；否则查找p的右子树。
• 重复执行②，直到p为空，查找不成功。

//查找关键字为key元素，若查找成功，返回结点，否则返回null。非递归算法。//若key==null，Java抛出空对象异常
//查找算法经过一条从根到结点的路径，非递归，查找不成功，遍历路径是从根到叶子。
public TriNode<T> searchNode(T key){TriNode<T> p=this.root;while (p!=null && key.compareTo(p.data)!=0){if (key.compareTo(p.data)<0)                   //若key较小p=p.left;                                  //进入左子树elsep=p.right;                                 //进入右子树}return p!=null ? p : null;        //若查找成功，返回结点，否则返回null
}
public T search(T key){               //查找关键字为key元素，若查找成功，返回元素，否则返回nullTriNode<T> find = this.searchNode(key);return find!=null ? find.data : null;
}

（2）二叉排序树的动态查找

查找算法：若二叉排序树为空，则返回插入位置，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤。

插入算法：若二叉排序树为空，则被查结点为新的根节点；否则，作为一个新的叶子结点插入在由查找返回的位置上。

二叉树的插入和删除

将数据元素构造成二叉排序树的优点：

① 查找过程与顺序结构有序表中的二分查找相似，查找效率高；

② 中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）；

③ 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。

//插入元素x结点，不插入关键字重复元素和空对象，返回插入与否状态。//若x==null，Java抛出空对象异常
public boolean add(T x){if (this.root==null)this.root=new TriNode<T>(x);      //创建根结点else{                                 //将x插入到以root为根的二叉排序树中TriNode<T> p=this.root, parent=null;while (p!=null){                  //查找确定插入位置if (x.compareTo(p.data)==0)return false;             //查找成功，不插入关键字重复的元素parent = p;if (x.compareTo(p.data)<0)p=p.left;else  p=p.right;}if (x.compareTo(parent.data)<0)     //插入x叶子结点作为parent的左/右孩子parent.left = new TriNode<T>(x, parent, null, null);else parent.right = new TriNode<T>(x, parent, null, null); }return true;
}

//删除关键字为key结点，返回被删除元素；若没找到则不删除，返回null。
//非递归算法，若key==null，Java抛出空对象异常
public T remove(T key)    {TriNode<T> p = this.searchNode(key);               //查找关键字为key元素，若查找成功，返回结点，否则返回nullif (p!=null && p.left!=null && p.right!=null){     //找到待删除结点p，若p是2度结点TriNode<T> insucc = this.first(p.right);       //寻找p在中根次序下的后继结点insuccT temp = p.data;                               //交换待删除元素，作为返回值p.data = insucc.data;                          //以后继结点值替换p结点值insucc.data = temp;p = insucc;                                    //转化为删除insucc，删除1、0度结点} if (p!=null && p==this.root){           //p是1度或叶子结点，删除根结点，p.parent==nullif (this.root.left!=null)this.root = p.left;                        //以p的左孩子顶替作为新的根结点elsethis.root = p.right;                       //以p的右孩子顶替作为新的根结点if (this.root!=null)this.root.parent = null;return p.data;                                 //返回被删除根结点元素}if (p!=null && p==p.parent.left)                   //p是1度或叶子结点，p是父母的左孩子if (p.left!=null){p.parent.left = p.left;                    //以p的左孩子顶替p.left.parent = p.parent;                  //p的左孩子的parent域指向p的父母}else{p.parent.left = p.right;                    //以p的右孩子顶替if (p.right!=null)p.right.parent = p.parent;}if (p!=null && p==p.parent.right)                  //p是1度或叶子结点，p是父母的右孩子if (p.left!=null){p.parent.right = p.left;                   //以p的左孩子顶替p.left.parent = p.parent;}else{p.parent.right = p.right;                  //以p的右孩子顶替if (p.right!=null)p.right.parent = p.parent;}return p!=null ? p.data : null;
}
public T removeRoot(){                      //删除根结点，返回原根结点元素return this.remove(this.root.data);
}

8，平衡二叉树

平衡二叉树是具有下列性质的二叉排序树：

• 它的左子树和右子树都是平衡二叉树。
• 左子树与右子树的高度之差的绝对值不超过1。结点的平衡因子 = 左子树的高度 – 右子树的高度。

调整不平衡子树

【例子】最小不平衡子树。 {87,66,54,25,40}

4种类型：LL、LR、RL和RR，{1,2,3}  

LL型调整

RR型调整

LR型调整

RL型调整