查找

0.PTA得分截圖

1.本周學習總結（0-5分）

1.1 查找的性能指標

ASL成功、不成功，比較次數，移動次數、時間復雜度

ASL（Average Search Length），即平均查找長度，在查找運算中，由于所費時間在關鍵字的比較上，所以把平均需要和待查找值比較的關鍵字次數稱為平均查找長度。
ASL分為查找成功情況下的ASL成功和查找不成功情況下的ASL不成功

ASL成功表示成功查找到查找表中的元素，平均需要關鍵字比較次數
ASL不成功表示沒有找到查找表中的元素，平均需要關鍵字比較次數

1.2 靜態查找

分析靜態查找幾種算法包括：順序查找、二分查找的成功ASL和不成功ASL。

順序查找
順序查找是一種最簡單的查找方法，它的基本思路是從表的一端向另一端逐個將元素的關鍵字和給定值k比較，若相等，則查找成功，給出該元素在查找表中的位置；若整個查找表掃描結束后仍未找到關鍵字等于k的元素，則查找失敗。
所以說，Ci（第i個元素的比較次數）在于這個元素在查找表中的位置，如第0號元素就需要比較一次，第一號元素比較2次......第n號元素要比較n+1次。

當待查找元素不在查找表中時，也就是掃描整個表都沒有找到，即比較了n次，查找失敗

查找代碼：

in SeqSearch(RecType R[], int n, KeyType k)
{
	int i = 0;
	while (i < n && R[i].key != k)//從表頭往后找
		i++;
	if (i >= n)//沒找到，返回0
		return 0;
	else//找到返回邏輯序號i+1
		return i + 1;
}

二分查找
在有序表中，取中間元素作為比較對象，若給定值與中間元素的關鍵字相等，則查找成功；
若給定值小于中間元素的關鍵字，則在中間元素的左半區繼續查找；
若給定值大于中間元素的關鍵字，則在中間元素的右半區繼續查找。不斷重復上述查找過程，直到查找成功，或所查找的區域無數據元素，查找失敗。
折半查找，折半查找又稱二分查找，它是一種效率較高的查找方法。但是，折半查找要求線性表是有序表，即表中的元素按關鍵字有序（遞增或遞減）有序排列。
代碼實現：

int BinarySearch(SeqList list, KeyType kx)
{ 

//若找到返回該元素在表中的位置，否則返回0 
  int mid,low=1, high=list.n;   //設置初始區間 
  while(low<=high)
  {   /*當查找區間非空*/
      mid=(low+high)/2;  //取區間中點 
      if(kx==list.data[mid].key) 
          return mid;  //查找成功，返回mid 
      else if (kx<list.data[mid].key) 
          high=mid-1;   // 調整到左半區 
      else low=mid+1;     // 調整到右半區    
  }
  return  0;     //查找失敗，返回0
}

時間復雜度：O(log2n)

1.3 二叉搜索樹

二叉搜索樹具有下列性質：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左、右子樹也分別為二叉排序樹。

1.3.1 如何構建二叉搜索樹（操作）

結合一組數據介紹構建過程，及二叉搜索樹的ASL成功和不成功的計算方法。
如何在二叉搜索樹做插入、刪除。

二叉搜索樹的概念
二叉搜索樹又稱為二叉排序樹，它或者是一棵空樹，或者具有如下性質的二叉樹：
（1）若它的左子樹不為空，則左子樹上的所有節點值都小于根節點的值。
（2）若它的右子樹不為空，則右子樹上的所有節點值都大于根節點的值。
（3）它的左右子樹也為二叉搜索樹。
創建二叉搜索樹
給出一組元素 38 26 62 94 35 50 28 55

把第一個元素作為根節點
把第二個元素拿出來與第一個元素做比較，如果比根節點大就放在右邊，如果比根節點小就放在左邊
同理比較第三個元素62
插入第四個元素94，先與38比較，進入右子樹，然后與62比較
按照以上的方式依次把后面的元素插入到樹中

1.3.2 如何構建二叉搜索樹（代碼）

類型定義和函數聲明

#include<stdio.h>
#include<stdlib.h>

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

void CreateBiTree(BiTree *T);
void ProOrderTraversal(BiTree T);
Position Find(int tar, BiTree T);
Position Find2(int tar, BiTree T);
Position FindMax(BiTree T);
Position FindMin(BiTree T);
BiTree Insert(int data, BiTree T);
BiTree Delete(int data, BiTree T);

在二叉搜索樹中查找指定元素
查找的效率取決于樹的高度（每遞歸一次，程序進入樹的下一層進行查找）。查找操作的思想也可應用到接下來的插入操作和刪除操作。查找程序是用尾遞歸的方法實現的，而尾遞歸的程序都可以轉換成循環的形式。

//從二叉搜索樹T中查找元素，返回其所在結點的地址(尾遞歸實現)
Position Find(int tar, BiTree T)
{
	if (!T)/*沒有找到該元素*/
		return NULL;
	if (tar > T->data)/*該元素在該節點的右子樹中*/
		return Find(tar, T->rchild);
	else if (tar < T->data)/*該元素在該節點的左子樹中*/
		return Find(tar, T->lchild);
	else/*找到該元素*/
		return T;
}

//從二叉搜索樹T中查找元素，返回其所在結點的地址(循環實現)
Position Find2(int tar, BiTree T)
{
    while (T && T->data != tar)
    {
        if (T->data > tar)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

在搜索二叉樹中插入元素
插入操作的關鍵是找到元素應該插入的位置，其思想與Find函數類似。

//插入元素(遞歸)
//最終返回元素為根節點指針
BiTree Insert(int data, BiTree T)
{
	if (!T)//找到插入位置,進行插入
	{
		T = (BiTree)malloc(sizeof(BiTNode));
		T->data = data;
		T->lchild = T->rchild = NULL;
	}
	else if (data > T->data)//進行右子樹遞歸插入
		T->rchild = Insert(data, T->rchild);
	else if (data < T->data)//進行左子樹遞歸插入
		T->lchild = Insert(data, T->lchild);
        else//插入失敗
                printf("元素已經存在，插入失敗");
	return T;
}

在搜索二叉樹中刪除元素
刪除函數是這里面最困難的函數。被刪除元素有三種具體情況：葉子結點、度為1的結點和度為2的結點。關鍵在于將度為2的結點通過其左子樹的最大元素或右子樹的最小元素替換成度為1的結點而完成刪除操作。

//刪除元素(遞歸)
//最終返回元素為根節點指針
BiTree Delete(int data, BiTree T)
{
	Position Tmp;

	if (!T)
		printf("沒有找到待刪除元素");
	else if (data > T->data)//進行右子樹遞歸刪除
		T->rchild = Delete(data, T->rchild);
	else if(data < T->data)//進行左子樹遞歸刪除
		T->lchild = Delete(data, T->lchild);
	//找到對應節點
	else if (T->lchild && T->rchild)//被刪除節點有左右兩個子節點(需要轉換成有一個子節點或沒有子節點的情況)
		{
			Tmp = FindMax(T->lchild);
			T->data = Tmp->data;
			T->lchild = Delete(T->data, T->lchild);
		}
	else//被刪除節點有一個子節點或沒有子節點
		{
			Tmp = T;
			if (!T->rchild)//有左節點或沒有子節點
				T = T->lchild;
			else if (!T->lchild)//有右節點或沒有子節點
				T = T->rchild;
			free(Tmp);
		}
	return T;
}

分析代碼的時間復雜度
最好：O(log2n)
最壞: O(n)
為什么要用遞歸實現插入、刪除？遞歸優勢體現在代碼哪里？
1.遞歸的實現明顯要比循環簡單得多
2.保留父子關系，便于刪除和插入順利找到父親和孩子

1.4 AVL樹

AVL樹解決什么問題，其特點是什么？

平衡二叉搜索樹，它的特點是在二叉搜索樹（BST）的基礎上，要求每個節點的左子樹和右子樹的高度差至多為1。
這個要求使AVL的高度h = logn，底數為2，避免了BST可能存在的單鏈極端情況（h = n）。
AVL樹中任何節點的兩個子樹的高度最大差別為1

結合一組數組，介紹AVL樹的4種調整做法。

*LL的旋轉。LL失去平衡的情況下，可以通過一次旋轉讓AVL樹恢復平衡。步驟如下：
1、將根節點的左孩子作為新根節點。
2、將新根節點的右孩子作為原根節點的左孩子。
3、將原根節點作為新根節點的右孩子。
LL旋轉示意圖如下：

RR的旋轉：RR失去平衡的情況下，旋轉方法與LL旋轉對稱，步驟如下：
1、將根節點的右孩子作為新根節點。
2、將新根節點的左孩子作為原根節點的右孩子。
3、將原根節點作為新根節點的左孩子。
RR旋轉示意圖如下：
LR的旋轉：LR失去平衡的情況下，需要進行兩次旋轉，步驟如下：
1、圍繞根節點的左孩子進行RR旋轉。
2、圍繞根節點進行LL旋轉。
LR的旋轉示意圖如下：
RL的旋轉：RL失去平衡的情況下也需要進行兩次旋轉，旋轉方法與LR旋轉對稱，步驟如下：
1、圍繞根節點的右孩子進行LL旋轉。
2、圍繞根節點進行RR旋轉。
RL的旋轉示意圖如下：

AVL樹的高度和樹的總節點數n的關系？

設N(h)為高度為h的AVL樹的最小節點數目，則N(h)=N(h-1) + N(h-2) +1; N(0)=0, N(1)=1; 類似斐波那契數列；
插入、查找和刪除的性能均為log(n)。

介紹基于AVL樹結構實現的STL容器map的特點、用法。

1、什么是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內部所有的數據都是有序的，后邊我們會見識到有序的好處。
map的特點是增加和刪除節點對迭代器的影響很小，除了那個操作節點，對其他的節點都沒有什么影響。對于迭代器來說，可以修改實值，而不能修改key。
2. map的基本操作函數：

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-樹和AVL樹區別，其要解決什么問題？

B-樹
也叫B樹，即平衡多路查找樹，m階B樹表示節點可擁有的最多m個孩子，2-3樹是3階B樹，2-3-4樹是4階B樹。多叉樹可以有效降低樹的高度，h=log_m(n)，m為log的底數。
B-樹的特點：

任意非葉子結點最多只有 M 個兒子， M>2
根結點的兒子數為 [2, M]
除根結點以外的非葉子結點的兒子數為 [M/2, M]
每個結點存放至少 M/2-1 （向上取整）和至多 M-1 個關鍵字, M> 2
非葉子結點的關鍵字個數 = 指向孩子的指針個數 -1 ；
非葉子結點的關鍵字： K[1], K[2], …, K[M-1] ， K[i] < K[i+1]
非葉子結點的指針： P[1], P[2], …, P[M] ；其中 P[1] 指向關鍵字小于 K[1] 的子樹， P[M] 指向關鍵字大于 K[M-1] 的子樹，其它 P[i] 指向關鍵字屬于 (K[i-1], K[i]) 的子樹
所有葉子結點位于同一層
如：（M=3）

B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果
命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為
空，或已經是葉子結點；

B-樹的特性：
* 關鍵字集合分布在整顆樹中；
* 任何一個關鍵字出現且只出現在一個結點中；
* 搜索有可能在非葉子結點結束；
* 其搜索性能等價于在關鍵字全集內做一次二分查找；
* 自動層次控制；
由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少
利用率，其最底搜索性能為：

其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數；
所以B-樹的性能總是等價于二分查找（與M值無關），也就沒有B樹平衡的問題；
由于M/2的限制，在插入結點時，如果結點已滿，需要將結點分裂為兩個各占
M/2的結點；刪除結點時，需將兩個不足M/2的兄弟結點合并；
B-樹的結構體定義

 #define MAXN 10
typedef int KeyTypw;
typedef struct node{   
     int keynum;//節點當前擁有關鍵字的個數  
 KeyType key[MAXM];//存放關鍵字   
  struct node *parent;//雙親節點指針   
   struct node *ptr[MAXM];//孩子節點指針數組
}BTNode;

B+樹定義，其要解決問題

B+樹是B-樹的變體，也是一種多路搜索樹：
* 其定義基本與B-樹同，除了：
* 非葉子結點的子樹指針與關鍵字個數相同；
* 非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹
（B-樹是開區間）；
* 為所有葉子結點增加一個鏈指針；
* 所有關鍵字都在葉子結點出現；
如：（M=3）
B+的特性：
*所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好
是有序的；
- 不可能在非葉子結點命中；
- 非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲
  （關鍵字）數據的數據層；
- 更適合文件索引系統；比如對已經建立索引的數據庫記錄，查找10<=id<=20，那么只要通過根節點搜索到id=10的葉節點，之后只要根據葉節點的鏈表找到第一個大于20的就行了，比B-樹在查找10到20內的每一個時每次都從根節點出發查找提高了不少效率。

1.6 散列查找。

1. 哈希表的設計主要涉及哪幾個內容？

散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

2. 構造方法

直接取地址法
根據關鍵字直接加上某個常量作為地址，確定所坐在位置
優點：計算簡單，并且不可能有沖突
缺點：關鍵字分布不是連續的將造成內存單元浪費
除留余數法
用關鍵字k除以某個不大于哈希表長度的m的數p所得的余數作為哈希表地址，即需要一個哈希函數h(k)= k mod p(p最好為素數)
優點：得到的哈希表是大致連續的，且不會超過原來哈希表的長度，可以節省空間
缺點：余數有可能相同，會產生沖突
數字分析法
數字分析法是取數據元素關鍵字中某些取值較均勻的數字位作為哈希地址的方法。即當關鍵字的位數很多時，可以通過對關鍵字的各位進行分析，丟掉分布不均勻的位，作為哈希值。它只適合于所有關鍵字值已知的情況。通過分析分布情況把關鍵字取值區間轉化為一個較小的關鍵字取值區間。

哈希表的設計

與三個因素有關：

哈希表長度
采用的哈希函數

結合數據介紹哈希表的構造及ASL成功、不成功的計算

關鍵字序列：（7、8、30、11、18、9、14）
散列函數：
H(Key) = (key x 3) MOD 7

所以查找成功的計算：
如果查找7，則需要查找1次。
如果查找8，則需要查找1次。
如果查找30，則需要查找1次。
如果查找11，則需要查找1次。
如果查找18，則需要查找3次：第一次查找地址5，第二次查找地址6，第三次查找地址7，查找成功。
如果查找9，則需要查找3次：第一次查找地址6，第二次查找地址7，第三次查找地址8，查找成功。
如果查找地址14，則需要查找2次：第一次查找地址0，第二次查找地址1，查找成功。
所以，ASL成功=（1+2+1+1+1+3+3）/ 7=12/ 7
查找不成功計算
查找地址為0的值所需要的次數為3，
查找地址為1的值所需要的次數為2，
查找地址為2的值所需要的次數為1，
查找地址為3的值所需要的次數為2，
查找地址為4的值所需要的次數為1，
查找地址為5的值所需要的次數為5，
查找地址為6的值所需要的次數為4。
ASL不成功=（3+2+1+2+1+5+4）/ 7=18/ 7

2.PTA題目介紹（0--5分）

介紹3題PTA題目
2.1 是否完全二叉搜索樹（2分）

BinTree Insert(BinTree T, int x)//建樹函數

    if T為空
        開辟結點
        T->Data = x;
        T->Left = T->Right 為 空
    else 
        if x >根結點值 
            插入到左子樹
        else if x < 根結點值 
            插入到右子樹

void Output(BinTree T)//輸出函數

    while (!q.empty())
        p = q.front();
        q.pop();
        if (flag == 0)//控制空格
        {
            cout << p->Data;
            flag = 1;
        }
        else cout << ' ' << p->Data;
        if 左子樹不空 輸出左子樹
        if 右子樹不空 輸出右子樹

bool judge(BinTree T)//判斷函數
  if（根節點不空）  入隊根節點；
  初始化狀態status = true；//如果status==false，則后續所有結點都只能是葉子結點
  while（隊列不為空）
  出隊隊頭結點t；
  if（t的左孩子不為空）
  if（status == false）     
        else  標記status = false；
            if（t的右孩子不為空）
            if（status == false）  
            t的右孩子入隊；
        else  標記status = false；
            end while
            return true；

2.1.2 提交列表

2.1.3 本題知識點
二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。是數據結構中的一類。在一般情況下，查詢效率比鏈表結構要高。
一棵空樹，或者是具有下列性質的二叉樹：
（1). 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
（2). 若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
（3). 左、右子樹也分別為二叉排序樹；
（4). 沒有鍵值相等的結點.
2.2 航空公司VIP客戶查詢（2分）

2.2.1 偽代碼（貼代碼，本題0分）
偽代碼為思路總結，不是簡單翻譯代碼。

2.2.2 提交列表
2.2.3 本題知識點
2.3 基于詞頻的文件相似度（1分）
本題設計一個倒排索引表結構實現（參考課件）。單詞作為關鍵字。本題可結合多個stl容器編程實現，如map容器做關鍵字保存。每個單詞對應的文檔列表可以結合vector容器、list容器實現。

2.3.1 偽代碼（貼代碼，本題0分）

for (int i = 0; i < 個數; i++)do
	輸入身份證  里程數
	if (里程數 < 最小里程數）
		更改里程數
		end if
		調用Insert向H插入結點數；
		end for
		for（int i = 0; i < 查找次數; i++) do
		調用查找函數造H中查找數據
		找到數據賦值給ptr
		若 ptr == NULL do
		else
		查找成功
		end if
		end for

2.3.2 提交列表

2.3.3 本題知識點

建立一個哈希表，哈希表中存放的是結點所在的下標（相當于存放鏈表頭指針，只不過這里的指針用下標表示）。
i. 哈希沖突解決方法：拉鏈法，即在沖突的位置存放一個鏈表。
建立一個存放數據的表（表長同哈希表），該表用作鏈表。

posted on 2021-06-14 22:45 長安& 閱讀(52) 評論(0) 收藏舉報

刷新頁面返回頂部

楊佳琴

查找

0.PTA得分截圖

1.本周學習總結（0-5分）

1.1 查找的性能指標

1.2 靜態查找

1.3 二叉搜索樹

1.3.1 如何構建二叉搜索樹（操作）

1.3.2 如何構建二叉搜索樹（代碼）

1.4 AVL樹

AVL樹解決什么問題，其特點是什么？

結合一組數組，介紹AVL樹的4種調整做法。

AVL樹的高度和樹的總節點數n的關系？

介紹基于AVL樹結構實現的STL容器map的特點、用法。

1.5 B-樹和B+樹

1.6 散列查找。

1. 哈希表的設計主要涉及哪幾個內容？

2. 構造方法

哈希表的設計

結合數據介紹哈希表的構造及ASL成功、不成功的計算

2.PTA題目介紹（0--5分）

導航

公告

楊佳琴

查找

0.PTA得分截圖

1.本周學習總結（0-5分）

1.1 查找的性能指標

1.2 靜態查找

1.3 二叉搜索樹

1.3.1 如何構建二叉搜索樹（操作）

1.3.2 如何構建二叉搜索樹（代碼）

1.4 AVL樹

AVL樹解決什么問題，其特點是什么？

結合一組數組，介紹AVL樹的4種調整做法。

AVL樹的高度和樹的總節點數n的關系？

介紹基于AVL樹結構實現的STL容器map的特點、用法。

1.5 B-樹和B+樹

1.6 散列查找。

1. 哈希表的設計主要涉及哪幾個內容？

2. 構造方法

哈希表的設計

結合數據介紹哈希表的構造及ASL成功、不成功的計算

2.PTA題目介紹（0--5分）

導航

公告

AVL樹解決什么問題，其特點是什么？

結合一組數組，介紹AVL樹的4種調整做法。

AVL樹的高度和樹的總節點數n的關系？

介紹基于AVL樹結構實現的STL容器map的特點、用法。

1.6 散列查找。

結合數據介紹哈希表的構造及ASL成功、不成功的計算