1. 計算機考研：數據結構常用演算法解析(8)
第九章 查找
查找分成靜態查找和動態查找，靜態查找只是找，返回查找位置。而動態查找則不同，若查找成功，返回位置，若查找不成功，則要返回新記錄的插入位置。也就是說，靜態查找不改變查找表，而動態查找則會有插入操作，會改變查找表的。
不同的查找所採用的存儲結構也不同，靜態查找採用順序表，而動碼遲態查找由於經常變動，所以用二叉排序樹，二叉平衡樹、B-和B+。
靜態查找有，順序查找，折半查找，分塊查找(索引順序查找)
順序查找(Sequential Search)是最簡單的一種查找方法。
演算法思路
設給定值為k，在表(R1 R2……Rn)中，從Rn即最後一個元素開始，查找key=k的記錄。若存在一個記錄Ri(l≤i≤n)的key為k，則查找成功，返回記錄序號i;否則，查找失敗，返回0。
演算法描述
int sqsearch(sqlist r,keytype k) //對表r順序查找的演算法//
{ int i;
r.data[0].key=k; //k存入監視哨//
i=r.len; //取表長//
while(r.data[i].key!=k)
i--; //順序查找//
return(i);
}
演算法用了一點技巧：先將k存入監視哨，若對某個i(≠0)有r.data[i].key=k，則查找成功，返回i;若i從n遞減到1都無記錄的key為k，i再減1為0時，必有r.data[0].key=k，說明查找失敗，返回i=0。
平均查找成功長度ASL= ，而查找失敗時，查找次數等於n+l。
折半查找演算法及分析
當記錄的key按關系≤或≥有序時，不管是遞增的還是遞減的，只要有序且採用順序存儲。
演算法描述
int Binsearch(sqlist r,keytype k) //對有序表r折半查找的演算法//
{ int low,high,mid;
low=1;high=r.len; //上下界初值//
while(low<=high) //表空間存在時//
{ mid=(low+high)/2; //求當前mid//
if (k==r.data[mid].key)
return(mid); //查找成功，返回mid//
if (k
high=mid-1; //調整上界，向左部查找//
else
low=mid+1; //調整下界，向右部查找//
}
return(0); //low>high，查找失敗//
}
判定樹：用來描述二分查找過程的二叉樹。n個結點的判定樹的深度和n個結點的完全二叉樹深度相同= 。但判斷樹不一定是完全二叉樹，但他的葉子結點所在層次之差不超過1。所以，折半查找在查找成功時和給定值進行比笑困較的關鍵字個數至多為
ASL=
分塊查找演算法及分析
分塊查找(Blocking Search)，又稱索引順序查找(Indexed Sequential Search)，是順序查找方法的一種改進，目的也是為了提高查找效率。
1.分塊
設記錄表長為n，將表的n個記錄分成b= 個塊，每塊s個記錄(最後一塊記錄數可以少於s個)，即：
且表分塊有序，即第i(1≤i≤b-1)塊所有記錄的key小於第i+1塊中記錄的key，但塊內記錄可以無序。
2.建立索引
每塊對應一索引項：
KeymaxLink
其中Keymax為該塊內記錄的最大key;link為該塊第一記錄的序號(或指針)。
3.演算法思路 分塊索碰模念引查找分兩步進行：
(1)由索引表確定待查找記錄所在的塊;(可以折半查找也可順序因為索引表有序)
(2)在塊內順序查找。(只能用順序查找，塊內是無序的)
考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/
2. 數據結構 順序查找的平均比較次數不是1+n/2嗎為什麼是n/2
你是對的，這個答案錯了，
順序表查找來說，最好的就是一次就可以找到，時間復雜度是O（1）
最壞是要比較n次,O(n)
如果查找不成功，要進行n+1次比較
由於關鍵字在任何一個位置的概率都是相同的，所以平均查找次數是n+1/2，時間復雜度還是O（n）
3. 順序表長度為n的折半查找演算法的平均查找長度
折半查找演算法在順序表長度為n的情況下，其平均查找長度可以用對數函數來表示。具體而言，該演算法的平均查找長度為log(n)，這里的對數是以2為底。
折半查找，也稱為二分查找，是一種高效的查找演算法。它通過將查找區間逐步縮小一半的方式，快速定位到目標元素。在長度為n的有序列表中，查找過程可以看作是對列表進行對數級的劃分。
假設列表中有n個元素，初始查找區間為整個列表。每次比較後，可以將查找區間縮小一半。因此，查找過程最多需要進行log(n)次比較，這里的log是以2為底。
平均查找長度是指在最壞情況和最好情況之間的查找長度的平均值。對於折半查找，由於每次查找都會使查找區間縮小一半，所以平均查找長度同樣可以用log(n)來表示。
需要注意的是，折半查找要求輸入數據必須是有序的。如果數據是無序的，則需要先進行排序，這將增加額外的時間成本。
折半查找演算法的時間復雜度為O(log(n))，這使得它在處理大規模數據時表現出色。然而，當數據量較小或者數據分布不均勻時，其優勢可能不明顯。
總結來說，順序表長度為n的折半查找演算法的平均查找長度為log(n)，這里的對數是以2為底。這種演算法在有序列表中具有較高的查找效率，是許多實際應用中的重要工具。
4. 檢索和索的區別是什麼
1、順序查找的基本思想
基本思想是：從表的一端開始，順序掃描線性表，依次將掃描到的結點關鍵宇和給定值K相比較。若當前掃描到的結點關鍵字與K相等，則查找成功；若掃描結束後，仍未找到關鍵字等於K的結點，則查找失敗。
2、順序查找的存儲結構要求
順序查找方法既適用於線性表的順序存儲結構，也適用於線性表的鏈式存儲結構（使用單鏈表作存儲結構時，掃描必須從第一個結點開始）。
3、基於順序結構的順序查找演算法
（1）類型說明
typedef struct{
KeyType key；
InfoType otherinfo； //此類型依賴於應用
}NodeType；
typedef NodeType SeqList[n+1]； //0號單元用作哨兵
（2）具體演算法
int SeqSearch(Seqlist R，KeyType K)
{ //在順序表R[1..n]中順序查找關鍵字為K的結點，
//成功時返回找到的結點位置，失敗時返回0
int i；
R[0].key=K； //設置哨兵
for(i=n；R[i].key!=K;i--)； //從表後往前找
return i； //若i為0，表示查找失敗，否則R[i]是要找的結點
} //SeqSearch
④順序查找的優點
演算法簡單，且對表的結構無任何要求，無論是用向量還是用鏈表來存放結點，也無論結點之間是否按關鍵字有序，它都同樣適用。
⑤順序查找的缺點
查找效率低，因此，當n較大時不宜採用順序查找
索引查找分兩步進行：
① 將外存上含有索引區的頁塊送人內存，查找所需記錄的物理地址
② 將含有該記錄的頁塊送人內存
注意：
①索引表不大時，索引表可一次讀入內存，在索引文件中檢索只需兩次訪問外存：一次讀索引，一次讀記錄。
②由於索引表有序，對索引表的查找可用順序查找或二分查找等方法。
5. 寫出順序表上將監視哨設在高端的順序查找演算法子程序
監視哨一般放在a[0]上，將要查找的數據f先賦值給a[0]，然後從後往前找，不設邊界條件，因為即使a[1]-a[n]之間沒有f，也可以在最後a[0]找到f，代表沒查找到。
int find(int a[] , int f) //可以把類型改下
{
a[0]=f;
for(i=n;a[i]!=f;i++); //不用判斷是不是越界。
return i; //如果i是0，代表沒找到，不是0，則返回數組位置。
}
6. 順序表的順序查找和二分查找
順序查找,二分查找和哈希查找演算法,它們各自的特點是：
1.對比順序查找的特點就是從表的第一個元素開始一個一個向下查找，如果有和目標一致的元素，查找成功;如果到最後一個元素仍沒有目標元素，則查找失敗。
2.二分查找的特點就是從表中間開始查找目標元素。如果找到一致元素，則查找成功。如果中間元素比目標元素小，則仍用二分查找方法查找表的後半部分(表是遞增排列的)，反之中間元素比目標元素大，則查找表的前半部分。
3.哈希演算法的特點是是使用給定數據構造哈希表，然後在哈希表上進行查找的一種演算法。先給定一個值，然後根據哈希函數求得哈希地址，再根據哈希地址查找到要找的元素。是通過數據元素的存儲地址進行查找的一種演算法。
7. 編寫無序順序表順序查找、有序順序表順序查找、二分查找演算法。用c語言。高分急求！
int IdxSerch(SeqList A[],IdxType index[],int b,KeyType k,int n) {
//分塊查找關鍵字為k的記錄，索引表為
index[0..b-1]
int low=0,high=b-1,mid,i;
int s=n/b; //每塊記錄個數
while(low<=high)
{
//在索引表中進行二分查找，找到的位置放在low中
mid=(low+high)/2;
if(index[mid].key<k) low=mid+1；
else high=mid-1;
}
if(low<b)
{
//在順序表中順序查找
for(i=index[low].link;i<=index[low].link+s-1 && i<n;i++)
if(A[i].key==k) return i;
return -1;
}
return -1;
}
typedef struct node
{
KeyType key;
//結點中的關鍵字
struct node *lchild,*rchild; //左、右孩子指針
}BsTree;
BsTree *BstSeareh(BsTree *BST,KeyType k ,BsTree **parent)
{
BsTree *p=BST,*q=NULL; //p指向根結點，q指向*p的雙親
while(p!=NULL)
{
if(k==p->key)
{ //查找成功
*parent=q;
return (p);
}
q=p;
if(k<p->key) p=p->lchild；
//在左子樹中查找
else p=p->rchild; //在右子樹中查找
}
*parent=q;
return (p);
//查找失敗，返回空
}