DS-查找

这个作业属于哪个班级	数据结构--网络2011/2012
这个作业的地址	DS博客作业05--查找
这个作业的目标	学习查找的相关结构
姓名	郑俊佳
0.PTA得分截图

1.本周学习总结（0-5分）
1.1 查找的性能指标
ASL成功
平均需要和给定值k进行比较的关键字次数称为平均查找长度（ASL）
ASL=∑PiCi(i=1~n)
n是查找表中元素个数，
Pi是查找第i个元素的概率（通常假设每个元素的查找概率相等，此时Pi=1/n）
Ci是找到第i个元素所需要的关键字比较次数
一个查找算法的ASL越大，其时间性能越差，反之，若越小其时间性能越好
不成功
没有找到查找表中的元素，平均需要关键字比较次数

比较次数，移动次数
对于一组数据当它以哈希表，链表，二叉搜索树储存时，关键字的搜索就要通过将关键字与其中的元素进行比较才能找到
哈希表因会有冲突导致关键字存储位置不是哈希函数所对应的位置，此时的比较次数就会增加
链表因会有冲突，导致关键字不是某一条链表的第一个元素，此时要找到关键字任然要比较，即比较次数要增加

时间复杂度
顺序查找的时间复杂度：O（n）
折半查找（二分查找）的时间复杂度：O（log2 n),虽然找的高效，但关键字的排序需要是有序的（即适用于顺序表）
二叉排序树的时间复杂度：最好的情况下O（log2 n）与折半查找相似，最坏的情况O（n）
平衡二叉树的时间复杂度：O（log2 n)

1.2 静态查找

一般线性表的顺序查找:
ASL成功=(n+1)/2
ASL不成功=(n+1)

有序顺序表的顺序查找
ASL成功=(n+1)/2
ASL不成功=n/(n+1)+n/2

二分查找
二分查找的ASL成功与ASL不成功通过画出对应查找序列的判定树，进而进行计算。

索引查找
ASL=I块内+I块间
其中块间可以使用二分查找
（1）ASL = (b+1)/2 + (s+1)/2 块内和块间均使用顺序查找，由于n = s*b,可以通过构建方程，得到当s = n^(1/2)。
ASL最小为n^(1/2)+1
（2）ASL = (s+1)/2 + ceil(log2(b+1)) 块内顺序，块间二分

1.3 二叉搜索树
二叉排序树又称二叉搜索树。在一棵二叉排序树中，若根节点的左子树不为空，那么左子树上所有的结点都小于根结点；若根节点的右子树不为空，那么右子树上所有结点都小于根节点。且根结点的左右子树叶都是二叉排序树。二叉排序树中所有的关键字都是唯一的。二叉树还有特殊的性质：按中序遍历可以得到一个递增有序序列。
结构体定义：

typedef struct node
{
   KeyType key;//关键字；
   InfoType data;//其他数据域；
   struct node*lchild,*rchild;//左右孩子指针；
}BSTNode,*BSTree;

1.3.1 如何构建二叉搜索树（操作）
插入

- 在二叉排序树中插入一个关键字为k的结点要保证插入后仍然满足BST性质，其插入过程为：
- 若二叉排序树bt为空，则创建一个key域作为k的结点，将它作为根结点；
- 若不为空，则与根节点的关键字作比较
- 若相等，则说明树中已经存在该关键字，无需插入，直接返回；
- 若比根节点的值小，就进入根节点的左子树中，否则进入右子树；
- 该结点插入后一定为叶子结点
  删除
- 情况1：p节点为叶子结点，直接删去该结点，双亲节点相应指针域修改为NULL；
- 情况2：p结点只有左/右子树，有其左子树或者右子树代替他，双亲节点相应的指针域修改；
- 情况3：p结点既有左子树也有右子树。根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点r（最右结点），用结点r的值代替结点p的值（结点值替换），保存r结点的左孩子，再删去r结点。也可以从右子树中选择关键字最小的结点l（最左结点），用结点l的值代替结点p的值（结点替换），保存l结点的右孩子，再删去结点l。

查找

- 递归查找，查找思路和普通二叉树不同，因为二叉搜索树的左子树中所有值都比根节点小，右子树中所有值都比根节点大，根据这一特点，我们可以将待查找数据和当前的根节点进行比较，如果待查找数据比较小，就有选择的进入左子树进行查找，不用像之前普通二叉树的查找一样，不仅要进左子树还要进右子树中查找。

1.3.2 如何构建二叉搜索树（代码）
插入

bool InsertBST(BSTNode*& bt, KeyType k)
{
	if (bt == NULL)
	{
		bt = new BSTNode;
		bt->key = k;
		bt->lchid = bt->rchild = NULL;
		return true;
	}
	else if (k == bt->key)
		return false;
	else if (k < bt->key)
		return InsertBST(bt->lchild, k);
	else
		return InsertBST(bt->rchild, k);
}

删除

bool deletek(BSTNode*& bt, KeyType k)
{
	if (bt != NULL)
	{
		if (k == bt->key)
		{
			delete(bt);
			return true;
		}
		else if (k < bt->key)
			delete(bt->lchild, k);
		else
			delete(bt->rchild, k);
	}
}

查找

BSTNode* SearchNode(BSTree bt, KeyType k)
{
	if (bt == NULL || bt->key == k)
		return bt;
	else if (bt->key < k)
		return SearchNode(bt->rchild, k);
	else
		return SearchNode(bt->child, k);
}

1.4 AVL树

- AVL树是二叉搜索树的优化版，又称平衡二叉搜索树，高度平衡树。当一棵二叉搜索树的结点一直单边插入时，这时候它的查找效率趋近于O（n），非常慢。
  而AVL树的特点是：“AVL树中任何结点的两个子树的高度最大差别为1” ，这样就克服了结点单边存储而导致查找效率低下的问题。即平衡因子=某一结点左右子树的高度差，所以平衡因子取值范围：-1 0 1
  一般情况下，一颗平衡二叉树总是二叉排序树，因为脱离二叉排序树来讨论平衡二叉树是没有意义的，所以每个节点是平衡的。
  所有左子树的节点都比根节点的值小，所有右子树节点的值都比根结点值大，这样在查询一个数的时候，可以每次根据根的信息决定左走还是右走
  而这个定义是递归定义的，左子树的左子树所有点比左子树根小，左子树的右子树比左子树的根大，对于每一棵子树都是这样
  如下图为AVL树:

如下图不是AVL树:

结合一组数组，介绍AVL树的4种调整做法。
LR调整

LL调整

RR调整

RL调整

AVL树的高度和树的总节点数n的关系？
高度为 h 的 AVL 树，节点数 N 最多2^h − 1；最少N(h)=N(h− 1) +N(h− 2) + 1
2) 节点最多的时候是满二叉树，如果认为第一层的高度为0，那么节点数最多应该是2^(h+1) -1
介绍基于AVL树结构实现的STL容器map的特点、用法。
Map是STL的一个关联容器，翻译为映射，数组也是一种映射。如：int a[10] 是int 到 int的映射，而a[5]=25,是把5映射到25。数组总是将int类型映射到其他类型。这带来一个问题，有时候希望把string映射成一个int ，数组就不方便了，这时就可以使用map。map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）。
map提供关键字到值的映射，其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个称为该关键字的值，由于这个特性.普通 int 数组是 map<int ,int > a。字符到整型的映射，就是 map<char ,int > a，而字符串到整型的映射，就必须是 map<string , int > a。map的键和值也可以是STL容器，如 map< set ,string> a,而且键和值都是唯一的。

- 使用map:map对象是模板类，需要关键字和存储对象两个模板参数：
  std:map<int,string> personnel;
  这样就定义了一个用int作为索引,并拥有相关联的指向string的指针。为了使用方便，可以对模板类进行一下类型定义，
  typedef map<int,CString> mapc
  mapc enumMap;
- 函数
  begin() 返回指向map头部的迭代器
  end() 返回指向map末尾的迭代器
  rbegin() 返回一个指向map尾部的逆向迭代器
  rend() 返回一个指向map头部的逆向迭代器
  lower_bound() 返回键值>=给定元素的第一个位置
  upper_bound() 返回键值>给定元素的第一个位置
  empty() 如果map为空则返回true
  max_size() 返回可以容纳的最大元素个数
  size() 返回map中元素的个数
  clear(）删除所有元素
  count() 返回指定元素出现的次数
  equal_range() 返回特殊条目的迭代器对
  erase() 删除一个元素
  swap() 交换两个map
  find() 查找一个元素
  get_allocator() 返回map的配置器
  insert() 插入元素
  key_comp() 返回比较元素key的函数
  value_comp() 返回比较元素value的函数

1.5 B-树和B+树

B-树
B-树一个节点可以放多个关键字，降低树的高度。可放外存，适合大数据量查找，一棵m阶B-树符合以下特性：

- 1.每个结点至多m个孩子结点，至多有m-1个关键字，除根节点外，其他节点至少有m/2个孩子结点，至少有m/2-1个关键字；
- 2.若根节点不是叶子结点，根节点至少两个孩子结点；
- 3.叶子结点一定都在最后一层，叶子结点下面还有一层是虚设的外部结点————就是表示查找失败的结点，不含任何信息，在计算B-树高度时要计入最底层的外部结点；
  结构体定义：

#define MAXM 10
typedef node* BNode;
typedef struct node
{
	int keynum;
	int key[MAXM];
	BNode parent;
	BNode ptr[MAXM];
}BTNode;
int m;
int MAX;
int MIN;

B-树的查找
在一棵B-树上顺序查找关键字，将k于根结点中的key[i]比较：

- 1.若k==key[i],则查找成功；
- 2.若k < key[1]:,则沿指针ptr[0]所指的子树继续查找；
- 3.若key[i]<k<key[i+1],则沿着指针ptr[i]所指的子树进行查找；
- 4.若k>key[i],则沿着指针ptr[i]所指的子树进程查找；
- 5.查找某个结点，若相应指针为空，落入一个外部结点，表示查找失败；类似判断树和二叉排序树的查找。
  B-树的插入
  往B-树中插入一个结点，插入位置必定在叶子结点层，但是因为B-树中对关键字个数有限制，所以，插入情况分为以下两种：
- 1.关键字个数n<m-1,不用调整
- 2.关键字个数n=m-1，进行分裂；如果分裂完之后，中间关键字进入的结点中关键字个数达到n=m-1,就继续进行分裂

B-树的删除
非叶子结点删除

- 1.从Pi子树节点借调最大或者最小关键字key代替删除结点；
- 2.pi子树中删除key；
- 3.若子树节点关键字个数 < m/2-1,重复步骤1；
- 4.若删除关键字为叶子结点层，按叶子结点删除操作。
  叶子结点删除
  情况1：结点b关键字个数 > m/2-1，直接删除；

情况2：结点b关键字个数 = m/2-1, 兄弟结点关键字个数大于 m/2-1，于是我们可以向兄弟结点借一个关键字；

- 步骤1：兄弟结点最小关键字上移至双亲；
- 步骤2：双亲节点大于删除关键字的关键字下移至删除结点。

情况3：结点b关键字个数 = m/2-1，兄弟结点关键字个数 = m/2-1，兄弟结点没有关键字可以借

- 步骤1：删除关键字
- 步骤2：兄弟结点及删除结点，双亲节点中分割二者的关键字合并成一个新的叶子结点
- 步骤3：若双亲节点的关键字个数 < m/2-1 ,则进行步骤2

B+树
一棵m阶b+树满足条件：

- 1.每个分支节点至多有m棵子树；
- 2.根结点或者没有子树，或者至少两棵子树；
- 3.除根结点，其他每个分支结点至少有m/2棵子树；
- 4.有n棵子树的结点有n个关键字；
- 5.所有叶子结点包含全部关键字及指向相应记录的指针；
- 叶子结点按关键字大小顺序链接；
- 叶子结点时直接指向数据文件的记录；
- 6.所有分支结点（可以看成是分块索引的索引表），包含子节点最大关键字及指向子节点的指针；
  B+树的查找
  因为所有的叶子结点链接起来成为一个线性链表，可直接总最小关键字开始进行顺序查找所有叶子节点；
  B-树和B+树的区别
  这都是由于B+树和B-具有这不同的存储结构所造成的区别，以一个m阶树为例。
- 1.关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B-树虽然也有m个子结点，但是其只拥有m-1个关键字。
- 2.存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B-树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。
- 3.分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。
- 4.查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。
  1.6 散列查找。
  定义：哈希表又叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
  给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数

基本概念：
若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。
实际工作中需视不同的情况采用不同的哈希函数，
通常考虑的因素有：

- 1、计算哈希函数所需时间
- 2、关键字的长度
- 3、哈希表的大小
- 4、关键字的分布情况
- 5、记录的查找频率

哈希函数的构造方法：

- 1、直接定地址法：以关键字k本身或关键字加上某个常量c作为哈希地址的方法：h(k)=k+c;
- 2、除留取余法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。p取不大于m的素数时效果最好
- 此方法计算比较简单，适用范围广，是最经常使用的一种哈希函数
- 3、数字分析法：分析一组数据，比如一组员工的出生年月日，发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
- 4、平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
- 5、折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加
- 6、随机数法：选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。

处理冲突
1、开放定址法：
线性探测法：Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

- （1）. di=1,2,3，…，m-1，称线性探测再散列；
- （2）. di=12,-12,22,-22，⑶2，…，±（k)2,(k<=m/2）称二次探测再散列；（平方探测）
- （3）. di=伪随机数序列，称伪随机探测再散列。
  2、拉链法：把所有的同义词用单链表连接起来的方法，所有哈希地址为i的元素对应的节点构成一个单链表，哈希表地址空间为0~m-1,地址为i的单元是一个指向对应单链表的首节点，在者种方法中，哈希表的每个单元中存放的不再是元素本身，而是相应同义词单链表的首结点指针，由于在单链表中可以插入任意多个结点，所以此时填装因子>=1,通常取1
  与开放定址法相比的优点：
- （1）、拉链发处理冲突简单，且无堆积现象，即非同义词绝不会发生冲突，因此平均查找长度较短
- （2）、由于拉链法中各单链表上的结点空间是动态申请的，所以它更适用于造表前无法确定的表的长度
- （3）、开放定址法为为减少冲突要求填装因子a较小，故当数据规模较大时会浪费很多空间，而拉链法中可取a>=1;且元素较大时拉链法中增加的指针域可忽略不计，因此节省空间
- （4）、在用拉链法构造的哈希表中，删除结点的操作更加易于实现。
  缺点：
  指针需要额外的空间，故当数据规模较小时，开放定址法较为节省空间，若将节省的空间指针用来扩大哈希表规模，可使填装因子变小，这又减少了开放定址法中的冲突，从而提高了平均查找速度

结合数据介绍哈希链的构造及ASL成功、不成功的计算

2.PTA题目介绍（0--5分）
介绍3题PTA题目

2.1 是否完全二叉搜索树（2分）
本题务必结合完全二叉搜索树经过层次遍历后在队列的特点去设计实现。结合图形介绍。

2.1.1 伪代码（贴代码，本题0分）

void InserBST(BinTree*& BST,KeyType k)//往二叉树中插入结点k
{
    if(BST==NULL) 建立新结点；
    else if(k<BST->key)  递归进入右子树；
    else    递归进入左子树  
}

/*层次遍历二叉树并判断是否为完全二叉树*/
bool Level_DispBST(BinTree* BST)
{
   定义变量end表示是否已经找到第一个叶子结点或者第一个只有左孩子结点；
   (如果是，则接下来未遍历的结点应该都是叶子结点)
   定义flag保存判断结果；
   
   若根结点BST不为空，入队，并输出；
   while(队不为空)
      出队一个结点p；
      若结点p的左，右孩子不为空，依次输出，并入队；
      若在剩余节点都应该是叶子结点的情况下p为非叶子节点
         不是完全二叉树，flag=flase；
      若结点p只有右孩子，没有左孩子
         不是完全二叉树，flag=flase;
      若结点p为叶子结点或者为第一个只有左孩子的结点
         修改end，表示接下来应该都是叶子结点；
   end while
   return flag;
}

2.1.2 本题知识点

- 完全二叉树的结构
- 二叉树的层次遍历
- 二叉搜索树的插入操作
  2.2 航空公司VIP客户查询（2分）
  本题结合哈希链结构设计实现。请务必自己写代码，学习如何建多条链写法。

2.2.1 伪代码（贴代码，本题0分）

map<string, int>M;
for i=0 to n-1 i++
输入身份证，已行驶里程数据
if 里程小于最小里程k
 then 让里程=k
 end if 
if 该身份证已由会员记录
 then 原来的里程数再加上刚才输入的（M[id1]+=len）
 end if 
else 未被登记为会员
 则现在输入身份证及里程信息(M[id1]=len)
end for
for i=0 to m-1 i++
输入身份证
若信息库（M）里由=有该身份证信息就输出里程信息
若信息库M中未找到该身份证信息
则输出“NO INFO

2.2.2 本题知识点
运用了map库里的函数
map<string,int>M
string为M数组的下标，int为数组里的数据类型
max(a,b)函数为求a b中的较大值
M.count(id)函数为求数组M中下标为id的数据是否存在
M中的数据不会重复存在，下标为某一确定值时，数据元素也只有一个确定的值
本题使用map里的函数会相对简单，因为身份证号码每个人都是唯一的，所以对于数据的记录较为简单，对于代码方面也简洁，更容易让人读懂

2.3 基于词频的文件相似度（1分）
本题设计一个倒排索引表结构实现（参考课件）。单词作为关键字。本题可结合多个stl容器编程实现，如map容器做关键字保存。每个单词对应的文档列表可以结合vector容器、list容器实现。

2.3.1 伪代码（贴代码，本题0分）

int main()
{
   定义一个文件列表list保存所有文件；
   初始化文件列表；
   for i=0 to n
      提取每个文件的内容；
   end for
   for i=0 to m
      比较两个文件的单词数量大小，单词数量小的作为模板，计算两文件的重复率；
      输出结果；
   end for
}

void InserFile(File& F,HashNode* word)//根据单词的首字母插入文件的相对应位置
{
   计算该单词应该插入的位置：ard = word->key[0]-'A';
   遍历单链F.content[ard]上的单词
      若有重复内容 return；
   若遍历完毕没有找到重复内容
      头插法插入，并使该文件的单词数量+1；
}

void GetFile(FileTable& list, int number)//获取每个文件内容，且将每个小写字母都转换为大写
{
    while(1)
       若str为'#' ，说明已经到文件内容末尾，break;
       while(未遍历到字符串str末尾)
           开辟新空间，用于保存新单词word；
           while(为字母)
              if 单词长度小于10，可以继续加入字母
                 若为小写字母：word->key += (str[i++]-'a'+'A');
                 若为大写字母：word->key += str[i++];
              else 
                 直接舍弃，i++;
           end while
           若单词长度小于3，则为不合法单词，舍弃：delete word;
           i++;//跳过非字母字符；
       end while
    end while
}
double File_Similarity(File*file1,File*file2)//计算两文件的重复率
{
   定义count保存模板file1的单词个数
   定义same记录两文件重复的单词数量，all保存两文件总的单词个数；
   
   for i=0 to 26 //遍历模板的哈希表
      p=file1->countent[i].next;//提取其中一个单链表遍历
      while(p不为空)
          count--;//表示模板中的有一个单词已经遍历过
          遍历另一个文件中相对应的位置总寻找是否存在和p相同的单词
              若存在 same++;
          p=p->next;//遍历单链中下一个单词；
      end while
      if  count==0 
         表示模板文件中所有单词都遍历完 ，提前退出对模板的遍历，break;
      end if
   end for
}

2.3.2 本题知识点

- 拉链法构造哈希表
- 头插法插入链表

DS-查找

推荐阅读