这个作业属于哪个班级	数据结构--网络2011/2012
这个作业的地址	DS博客作业05--查找
这个作业的目标	学习查找的相关结构
姓名	唐宇悦

0.PTA得分截图

查找题目集总得分，请截图，截图中必须有自己名字。题目至少完成总题数的2/3，否则本次作业最高分5分。没有全部做完扣1分。

1.本周学习总结

1.1 查找的性能指标

ASL成功、不成功，比较次数，移动次数、时间复杂度

ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度。
它的定义是这样的：

其中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和不成功ASL。

在顺序查找(Sequence Search)表中，查找方式为从头扫到尾，找到待查找元素即查找成功，若到尾部没有找到，说明查找失败。所以说，Ci（第i个元素的比较次数）在于这个元素在查找表中的位置，如第0号元素就需要比较一次，第一号元素比较2次......第n号元素要比较n+1次。所以Ci=i；所以

可以看出，顺序查找方法查找成功的平均比较次数约为表长的一半。当待查找元素不在查找表中时，也就是扫描整个表都没有找到，即比较了n次，查找失败
折半查找(Binary Search)，也称二分查找，首先待查找表是有序表，这是折半查找的要求。在折半查找中，用二叉树描述查找过程，查找区间中间位置作为根，左子表为左子树，右子表为右子树，，因为这颗树也被成为判定树(decision tree)或比较树(Comparison tree)。查找方式为(找k)，先与树根结点进行比较，若k小于根，则转向左子树继续比较，若k大于根，则转向右子树，递归进行上述过程，直到查找成功或查找失败。在n个元素的折半查找判定树中，由于关键字序列是用树构建的，所以查找路径实际为树中从根节点到被查结点的一条路径，因为比较次数刚好为该元素在树中的层数。
所以Pi为查找k的概率，level(Ki)为k对应内部结点的层次。而在这样的判定树中，会有n+!种查找失败的情况，因为将判定树构建为完全二叉树，又有n+1个外部结点(用Ei(0<=i<=n)表示)，查找失败，即为从根结点到某个外部结点也没有找到，比较次数为该内部结点的结点数个数之和，所以，qi表示查找属于Ei中关键字的概率，level(Ui)表示Ei对应外部结点的层次。所以，在一颗有n个结点判定树中，总数，所以判定树高度为的满二叉树,第i层上结点个数为，查找该层上的结点需要进行i次比较，因此，在等概率情况下ASL为
举例：
给11个数据元素有序表（2,3,10,15,20,25,28,29,30,35,40）采用折半查找。则ASL成功和不成功分别是多少？
首先画出判定树，
查找成功时总会找到途中某个内部结点，所以成功时的平均查找长度为
即25查找一次，成功，10,30要查找2次，成功，2,15,28,35要查找3次，成功，3,20,29,40要查找4次，成功。而不成功的平均查找长度为，为什么这么算呢，因为内部结点都能查找成功，而查找不成功的就是那些空的外部结点，所以到查询到2的左孩子，15的左孩子，28的左孩子，35的左孩子，3的左右孩子，20的左右孩子，29的左右孩子，40的左右孩子时，都是查找不成功的时候。如我要找1，比25小，转向左子树，比较一次，比10小，转左子树，2次，比2 小，转左子树，3次，此时2无左子树，所以失败。所以

1.3 二叉搜索树

二叉搜索树又被称为二叉排序树，那么它本身也是一棵二叉树，那么满足以下性质的二叉树就是二叉搜索树：
1、若左子树不为空，则左子树上左右节点的值都小于根节点的值
2、若它的右子树不为空，则它的右子树上所有的节点的值都大于根节点的值
3、它的左右子树也要分别是二叉搜索树

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

结合一组数据介绍构建过程，及二叉搜索树的ASL成功和不成功的计算方法。
二叉搜索树不同于一般的二叉树，它是一种特殊的二叉树，如果对这棵树进行中序遍历，就会得到一个递增的队列。
第一步给出一组元素 c 38 26 62 94 35 50 28 55
第二步把第一个元素作为根节点

第三步，把第二个元素拿出来与第一个元素做比较，如果比根节点大就放在右边，如果比根节点小就放在左边

第四步同样道理比较第三个元素62

第五步插入第四个元素94，先与38比较，进入右子树，然后与62比较

第六步按照以上的方式依次把后面的元素插入到树中

如何在二叉搜索树做插入、删除。

插入
由于二叉搜索树的特殊性质确定了二叉搜索树中每个元素只可能出现一次，所以在插入的过程中如果发现这个元素已经存在于二叉搜索树中，就不进行插入。
否则就查找合适的位置进行插入。
第一种情况：_root为空
直接插入，return true；

第二种情况：要插入的元素已经存在
如上面所说，如果在二叉搜索树中已经存在该元素，则不再进行插入，直接return false；
第三种情况：能够找到合适位置
删除
对于二叉搜索树的删除操作，主要是要理解其中的几种情况，写起来还是比较简单的。
当然一开始还是需要判断要删除的节点是否存在于我们的树中，如果要删除的元素都不在树中，就直接返回false；否则，再分为以下四种情况来进行分析：
》要删除的节点无左右孩子
》要删除的节点只有左孩子
》要删除的节点只有右孩子
》要删除的节点有左、右孩子

删除方法解释：
对于第一种情况，我们完全可以把它归为第二或者第三种情况，就不用再单独写一部分代码进行处理；
》如果要删除的节点只有左孩子，那么就让该节点的父亲结点指向该节点的左孩子，然后删除该节点，返回true；

》如果要删除的节点只有右孩子，那么就让该节点的父亲结点指向该节点的右孩子，然后删除该节点，返回true；

对于上面这两种情况我们还应该在之前进行一个判断，就是判断这个节点是否是根节点，如果是根节点的话，就直接让根节点指向这个节点的左孩子或右孩子，然后删除这个节点。
》最后一种也是最麻烦的一种就是要删除的节点的左右孩子都存在。此时我们的删除方法如下：
1、找到该节点的右子树中的最左孩子（也就是右子树中序遍历的第一个节点）
2、把它的值和要删除的节点的值进行交换
3、然后删除这个节点即相当于把我们想删除的节点删除了，返回true；

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

1.如何构建、插入、删除及代码。

/*构建*/
BinTree Create(KeyType A[],int n)
{
      BinTree BST=NULL;
      int i=0;
      while(i<n)
      {
            Insert(BST,a[i])
            i++;
      }
      return BST;
}

/*插入*/
BinTree Insert(BinTree BST, ElementType X)
{
    if (BST == NULL)    //空结点
    {
        BST = new BSTNode;    //生成新结点
        BST->Data = X;
        BST->Left = BST->Right = NULL;    
    }
    else if (X < BST->Data) 
    {
        BST->Left = Insert(BST->Left, X);   //插入左子树
    }
    else if (X > BST->Data)
    {
        BST->Right = Insert(BST->Right, X);   //插入右子树
    }  
    return BST;
}

/*删除*/
BinTree Delete(BinTree BST, ElementType X)
{
    BinTree t;
    if (BST==NULL)
    {
        printf("Not Found\n");
    }
    else
    {
        if (X < BST->Data)
        {
            BST->Left = Delete(BST->Left, X);
        }
        else if (X > BST->Data)
        {
            BST->Right = Delete(BST->Right, X);
        }
        else
        {
            if (BST->Left && BST->Right) //被删除的节点有两个孩子，从左子树中找最大的数代替删除的节点
            {
                t = FindMax(BST->Left);//找最大
                BST->Data = t->Data;//代替删除的节点
                BST->Left = Delete(BST->Left, t->Data);//删除拿来代替的那个节点
            }
            else //只有一个子节点
            {
                t = BST;
                if (!BST->Left) //只有右节点
                {
                    BST = BST->Right;
                }
                else if (!BST->Right) //只有左节点
                {
                    BST = BST->Left;
                }
                free(t);//删除
            }
        }
    }
    return BST;
}

2.分析代码的时间复杂度

二叉树
插入：O(n);查找：O（n);删除：O(n)
二叉平衡树
插入：O(log2 n);查找：O(log2 n)；删除：O(log2 n)

3.为什么要用递归实现插入、删除？递归优势体现在代码哪里？

插入：与顺序表比，不需要大量移动数组；与链表比，不需要更改指针关系，不需要考虑头插法和尾插法
删除：递归查找才能把父子关系保留
递归的利用可以使算法或数据结构大大简化，代码简洁明了，
相同一个具有该特性的课题采用递归或其他算法，所要求的预定义及相应的结果都将不一样，
用了递归可能使用减少部份定义，代码实现部份大大减少

1.4 AVL树

AVL树解决什么问题，其特点是什么？

平衡二叉树（Balanced Binary Tree 或 Height-Balanced Tree）又称为 AVL 树，其实就是一颗平衡的二叉排序树，解决了二叉排序树的不平衡问题，即斜树。AVL树或者是一颗空树，或者是具有下列性质的二叉排序树：

它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1
平衡二叉树上结点的平衡因子 BF(Balanced Factor) 定义为该结点的左子树深度减去它的右子树的深度，平衡二叉树上所有结点的平衡因子只可能是 -1，0，1
AVL树是从二分搜索树升级过来的。所以它满足二分搜索树的基本特征【左子树所有节点都小于其根节点，右子树所有节点都大于其根节点】，AVL树是对于二分搜索树退化成链表的一种解决方案。

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

LL型调整
这是因再A结点的左孩子的左子树上插入结点，使得A结点的平衡因子由1变为2而引起的不平衡。
RR型调整
这是因再A结点的右孩子的右子树上插入结点，使得A结点的平衡因子由-1变为-2而引起的不平衡。
LR型调整
这是因再A结点的左孩子的右子树上插入结点，使得A结点的平衡因子由1变为2而引起的不平衡。
RL型调整
这是因再A结点的右孩子的左子树上插入结点，使得A结点的平衡因子由-1变为-2而引起的不平衡。

AVL树的高度和树的总节点数n的关系？

N(1)=1,N(2)=2,N(h)=N(h-1)+N(h-2)+1

介绍基于AVL树结构实现的STL容器map的特点、用法。

map容器的常用操作

map<Key, value> m

map<Key, value> m;　　构造一个空的map，

empty()　　// 如果map 为空，返回true。否则返回 false

ize()　　　 // 返回map 中元素的大小，即 key-value 的个数

操作符[]　　// m[k] 返回map 中 Key为 k的元素的value的引用。

　　　　　　// 如果 k不存在，那么将会插入一个 key为 k的元素，并返回其默认 value。

　　　　　　// []操作总会将 map的大小 +1

find　　查找

　　　　　　在map中查找key 为 k的元素，返回指向它的迭代器。若k不存在，返回 map::end.

count　计数

　　　　　　统计map中 key为k的元素的个数，对于map，返回值不是1(存在)，就是0(不存在)

1.5 B-树和B+树

B-树和AVL树区别，其要解决什么问题？

AVL树结点仅能存放一个关键字，树的敢赌较高，而B-树的一个结点可以存放多个关键字，降低了树的高度，可以解决大数据下的查找

B-树定义

B-树
也叫B树，即平衡多路查找树，m阶B树表示节点可拥有的最多m个孩子，2-3树是3阶B树，2-3-4树是4阶B树。多叉树可以有效降低树的高度，h=log_m(n)，m为log的底数。
B-树的特点：
1.任意非叶子结点最多只有 M 个儿子， M>2
2.根结点的儿子数为 [2, M]
3.除根结点以外的非叶子结点的儿子数为 [M/2, M]
4.每个结点存放至少 M/2-1 （向上取整）和至多 M-1 个关键字, M> 2
5.非叶子结点的关键字个数 = 指向孩子的指针个数 -1 ；
6.非叶子结点的关键字： K[1], K[2], …, K[M-1] ， K[i] < K[i+1]
7.非叶子结点的指针： P[1], P[2], …, P[M] ；其中 P[1] 指向关键字小于 K[1] 的子树， P[M] 指向关键字大于 K[M-1] 的子树，其它 P[i] 指向关键字属于 (K[i-1], K[i]) 的子树
8.所有叶子结点位于同一层

在普通平衡二叉树中，插入删除后若不满足平衡条件则进行旋转操作，而在B树中，插入删除后不满足条件则进行分裂及合并操作。所以，B树并不需要把节点一次性加载到内存，而B树的查找过程是一个顺指针查找节点和节点中查找关键字的交叉过程。

B树查找虽然很方便，但是存在一个缺陷，如果我们要完成对数据的遍历，那么需要不断在内外存做数据交互，这显然是影响性能的。为了解决这个问题，提出了B+树。

B+树定义，其要解决问题

B-树的变体，也是一种多路搜索树，与B-树的区别是：

1.非叶子结点的子树指针与关键字个数相同，即n 个 key 值的节点指针域为 n 而不是 n+1
2.非叶子结点的子树指针 P[i] ，指向关键字值属于 [K[i], K[i+1]) 的子树（左闭右开，B树是全开区间）
3.为所有叶子结点增加一个链指针
4.B+树的key 的副本存储在内部节点，真正的 key 和 data 存储在叶子节点上。
B+树结构如下图：

B+树的两个明显特点：

数据只出现在叶子节点
所有叶子节点增加了一个链指针
B树和B+树的不同：
因为内节点并不存储 data，所以一般B+树的叶节点和内节点大小不同，而B-树的每个节点大小一般是相同的。在磁盘存储中，为了满足局部性原理，一般会给每个结点分配一页的存储容量，这使得B+树的非叶节点可以保存更多的key，减少了查找时的磁盘IO次数。
B+ 树只有达到叶子结点才命中（ B树可以在非叶子结点命中），其查询时间复杂度固定为 log n，查询效率很稳定，而B-树查询时间复杂度不固定，与 key 在树中的位置有关。
B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询，而B树每个节点 key 和 data 在一起，无法区间查找。

1.6 散列查找。

哈希表的设计主要涉及哪几个内容？

哈希函数的构造方法
其实要设计一个哈希表首先要做的就是散列函数的计算，通过散列函数就可以将键转换为数组的索引

直接定址法
直接定址法是以关键字k本身加上某个常数c作为哈希地址的方法。
哈希函数为h(k)=k+c
该方法的特点是哈希函数计算简单，若关键字分布不连续将造成内存单元大量浪费。
除留余数法
除留余数法是用关键字k除以某个不大于哈希表长度m的整数p所得的余数作为哈希地址。
哈希函数为h(k)=k mod p
该方法选取的p最好为不大于m的素数，从而尽量减少发生哈希冲突的可能性。
数学分析法
该方法是提取关键字中取值较均匀的数字位作为哈希地址。
适用于所有关键字值都已知的情况，并需要对关键字中每一位的取值分布情况进行分析。
哈希表中的ASL 查找成功的平均查找长度是指查找到哈希表中已有关键字的平均探测次数。而查找不成功的平均查找长度是指在哈希表中找不到待查的元素，最后找到空位置元素的探测次数平均值。

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

哈希表即散列表
例：散列表长度为13，地址空间为0~12，散列函数H(k) =K mod 13,关键字序列{19,14,23,01,68,20,84,27,55,11,10,79} 所以线性探测结果为：

当然成功的很好理解，12个元素，每个元素的探测次数之和除以12就行。而不成功的计算是这样的。散列表长度为13，根据定义，假设待查关键字不在散列表中，要一直找到空元素才算查找失败。
如H[0]为空，与待查找元素不等，不成功，比较一次，H[1]，此时H[1]的元素与原本放在H[1]的元素不等(假设不在散列表在之中，但也不是空的)，继续向后比，与H[2]比也不等，继续向后，一直到H[12]，也不等，继续向后时，回到H[0]，为空，也不等，查找失败，总计比较13次，然后计算第二号元素，一样的比较，一直把每个位置都统计一遍，从而得出ASL不成功的.
哈希表建立：

int InsertHT(HashTable ha,int p,int k,int &n){
    int adr,i;
   adr=k % p;
   if(adr==NULLKEY || adr==DELKEY)    //地址为空，可插入数据
         { ha[adr].key=k;ha[adr].count=1;} 
  else
       { i=1;
        while(ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY)
          {    
             adr=(adr+1) % m; 
              i++;}//查找插入位置
         ha[adr].key=k;ha[adr].count=i;   //找到插入位置 
        }
   n++;
}

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

假设散列表的长度是13，三列函数为H(K) = k % 13，给定的关键字序列为{32， 14， 23， 01， 42， 20， 45， 27， 55， 24， 10， 53}。分别画出用线性探测法和拉链法解决冲突时构造的哈希表，并求出在等概率情况下，这两种方法的查找成功和查找不成功的平均查找长度。
先利用散列函数（一般是取余数的方法）定位数组具体哪个点，比如1就是余数为1的点的链表中，然后再遍历链表查找具体数值的位置，如,果是53，那就在链表的第四位置，需要查找四次；同理，27就需要查找3次！

查找成功时的平均查找长度：

ASL = (16+24+31+41)/12 = 7/4

查找不成功时的平均查找长度：

ASL = (4+2+2+1+2+1)/13

注意：查找成功时，分母为哈希表元素个数，查找不成功时，分母为哈希表长度

2.PTA题目介绍

2.1 是否完全二叉搜索树

2.1.1 伪代码

定义队列q;
输入n;
for i=0 to n do
{
      输入整数X;
      将X插入BST;
}
/*对BST层次遍历*/
if(!BST) return true;
根结点入队；
while(队列不空) do
{
      出队结点T;
      if(T不是空结点)
            输出T的值，将T的左右孩子入队;
      else if(队列不空&&队头不是空结点）
            BST不是完全二叉树搜索树;
}
BST是完全二叉搜索树;

2.1.2 提交列表

2.1.3 本题知识点

1.树的层次遍历
2.队列的方法

2.2 航空公司VIP客户查询

本题结合哈希链结构设计实现。请务必自己写代码，学习如何建多条链写法。

2.2.1 伪代码

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 提交列表

2.2.3 本题知识点

1.用了count函数
2.运用了map函数

2.3 基于词频的文件相似度

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

2.3.1 伪代码

定义set文档集合set<string> doc[MaxN];
输入文档数N；
getchar()吸收回车符；
for（i=1 to N）
  while（循环输入数据）
    getline（cin，line）输入一行数据；
    if（输入的数据line==“#”）  文档数据输入完毕，break；
    for（j=0 to 当前行数据的长度line.size();）//j为单词首字母位置
      k=j；//k用来记录单词尾字母位置
      while（k小于当前行数据长度line.size()&&line[k]为字母）  k++； end while
      if（单词长度大于等于3即k-j≥3）
        if（单词长度小于10） 
          调用word = line.substr(j, k - j)提取主串中的单词；
          for（l=0 to 单词长度word.size()-1） 将word[l]转换为大写字母word[l] -= 'a' - 'A';
        else  
          调用word = line.substr(j, 10)提取主串中的单词；
          for（l=0 to 单词长度word.size()-1） 将word[l]转换为大写字母word[l] -= 'a' - 'A';
        将单词word插入到文档i中doc[i].insert(word);
      while（k小于当前行数据长度&&line[k]不为字母）  滤去非字母字符k++； end while
      修改下一个单词首字母位置 j=k；
    end for
  end while
end for
输入待查询次数m；
while（m--）
  输入待查询文档p、q；
  定义公共词汇量s=0；
  for（遍历文档p中的所有单词it）
    if（文档q中存在单词it） 公共词汇量s++；
  end for
  两个文档的总词汇量t=doc[p].size()+doc[q].size();
  两个文档的相似度=s/(t-s);
end while

2.3.2 提交列表

2.3.3 本题知识点

1.使用了string函数
2.使用了getchar()
3.使用了map函数

DS博客作业05--查找