查找技術

在計算機科學中定義為:在一些(有序的/無序的)數(shù)據(jù)元素中，通過一定的方法找出與給定關鍵字相同的數(shù)據(jù)元素的過程叫做查找。也就是根據(jù)給定的某個值，在查找表中確定一個關鍵字等于給定值的記錄或數(shù)據(jù)元素。
線性表的查找技術
順序查找
順序查找是按照序列原有順序對數(shù)組進行遍歷比較查詢的基本查找算法。
基本原理:
對于任意一個序列以及一個給定的元素，將給定元素與序列中元素依次比較，直到找出與給定關鍵字相同的元素，或者將序列中的元素與其都比較完為止。

#include<stdio.h> int Sequence_search(int *a,int n, int key);int main() {int a[10];int i = 1;int key = 0;int n = 0;int return_number;printf("Please Enter how many you want to input numbers！\n");scanf("%d", &n);printf("Please Enter %d numbers!\n", n);for(; i <= n; i++){scanf("%d", &a[i]);}printf("Please Input the search number!\n");scanf("%d", &key);return_number = Sequence_search(a, n, key);if(return_number != 0){printf("查找成功!\n");printf("查找的數(shù)的位序是%d\n", return_number);}else{printf("查找失敗,未找到該數(shù)!\n");}}int Sequence_search(int *a, int n, int key) {a[0] = key;int i = n;for(; i >= 0; i--){if(a[i] == key){return i;}}return 0;}***折半查找*** 二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好，占用系統(tǒng)內存較少;其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功;否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。``

void binarySearch(int *arr,int length,int key) {

//數(shù)組左端 int left = 0; //數(shù)組右端 int right = length - 1; //中間 int mid;//在左右指針交換之前，查找還沒結束 while (left <= right) {//更新中間的值mid = (left + right) / 2;//查找成功if (arr[mid] == key) {cout << "find it and its index is " << mid;return;}//若還沒有找到，改變左右區(qū)間繼續(xù)尋找if (arr[mid] < key)left = mid + 1;if (arr[mid] > key)right = mid - 1;}cout << "cannot find it" << endl; return;

}

***樹表的查找技術 二叉排序樹*** 二叉排序樹（Binary Sort Tree）或者是一棵空樹；或者是具有下列性質的二叉樹： （1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； （2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； （3）左、右子樹也分別為二叉排序樹； 若根結點的關鍵字值等于查找的關鍵字，成功。否則，若小于根結點的關鍵字值，遞歸查左子樹。若大于根結點的關鍵字值，遞歸查右子樹。若子樹為空，查找不成功。插入算法：首先執(zhí)行查找算法，找出被插結點的父親結點。判斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。若二叉樹為空。則首先單獨生成根結點。注意：新插入的結點總是葉子結點。void InsertBST(t，key)//在二叉排序樹中插入查找關鍵字key{if(t==NULL){t=new BiTree;t->lchild=t->rchild=NULL;t->data=key;return; }if(keydata ) InsertBST(t->lchild,key);else InsertBST (t->rchild, key );}void CreateBiTree(tree,d【 】,n）//n個數(shù)據(jù)在數(shù)組d中，tree為二叉排序樹根{tree=NULL;for(i=0;i InsertBST(tree,d);} ***平衡二叉樹*** 平衡二叉搜索樹(Self-balancing binary search tree)又被稱為AVL樹(有別于AVL算法)，且具有以下性質:它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹的常用實現(xiàn)方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。 最小二叉平衡樹的節(jié)點總數(shù)的公式如下 F(n)=F(n-1)+F(n-2)+1 這個類似于一個遞歸的數(shù)列，可以參考Fibonacci(斐波那契)數(shù)列，1是根節(jié)點，F(n-1)是左子樹的節(jié)點數(shù)量，F(n-2)是右子樹的節(jié)點數(shù)量。 ***紅黑樹*** 紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數(shù)據(jù)結構，典型的用途是實現(xiàn)關聯(lián)數(shù)組。它是在1972年由Rudolf Bayer發(fā)明的，他稱之為"對稱二叉B樹"，它現(xiàn)代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。它是復雜的，但它的操作有著良好的最壞情況運行時間，并且在實踐中是高效的: 它可以在O(log n)時間內做查找，插入和刪除，這里的n是樹中元素的數(shù)目。***AVL*** AVL是最先發(fā)明的自平衡二叉查找樹算法。在AVL中任何節(jié)點的兩個兒子子樹的高度最大差別為一，所以它也被稱為高度平衡樹，n個結點的AVL樹最大深度約1.44log2n。查找、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。***Treap*** Treap是一棵二叉排序樹，它的左子樹和右子樹分別是一個Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的數(shù)據(jù)，就是優(yōu)先級。Treap在以關鍵碼構成二叉排序樹的同時，還滿足堆的性質(在這里我們假設節(jié)點的優(yōu)先級大于該節(jié)點的孩子的優(yōu)先級)。但是這里要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap并不一定是。***伸展樹*** 伸展樹(Splay Tree)是一種二叉排序樹，它能在O(log n)內完成插入、查找和刪除操作。它由Daniel Sleator和Robert Tarjan創(chuàng)造。它的優(yōu)勢在于不需要記錄用于平衡樹的冗余信息。在伸展樹上的一般操作都基于伸展操作。***SBT*** Size Balanced Tree(簡稱SBT)是一自平衡二叉查找樹，是在計算機科學中用到的一種數(shù)據(jù)結構。它是由中國廣東中山紀念中學的陳啟峰發(fā)明的。陳啟峰于2006年底完成論文《Size Balanced Tree》，并在2007年的全國青少年信息學奧林匹克競賽冬令營中發(fā)表。由于SBT的拼寫很容易找到中文諧音，它常被中國的信息學競賽選手和ACM/ICPC選手們戲稱為"傻B樹"、"Super BT"等。相比紅黑樹、AVL樹等自平衡二叉查找樹，SBT更易于實現(xiàn)。據(jù)陳啟峰在論文中稱，SBT是"目前為止速度最快的高級二叉搜索樹"。SBT能在O(log n)的時間內完成所有二叉搜索樹(BST)的相關操作，而與普通二叉搜索樹相比，SBT僅僅加入了簡潔的核心操作Maintain。由于SBT賴以保持平衡的是size域而不是其他"無用"的域，它可以很方便地實現(xiàn)動態(tài)順序統(tǒng)計中的select和rank操作。 ***散列表*** 散列表(Hash table，也叫哈希表)，是根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。給定表M，存在函數(shù)f(key)，對任意給定的關鍵字值key，代入函數(shù)后若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash)表，函數(shù)f(key)為哈希(Hash) 函數(shù)。 ***?基本概念*** 若關鍵字為k，則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數(shù)，按這個思想建立的表為散列表。 對不同的關鍵字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，這種現(xiàn)象稱為碰撞(英語:Collision)。具有相同函數(shù)值的關鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)f(k)和處理碰撞的方法將一組關鍵字映射到一個有限的連續(xù)的地址集(區(qū)間)上，并以關鍵字在地址集中的"像"作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。 若對于關鍵字集合中的任一個關鍵字，經散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)(Uniform Hash function)，這就是使關鍵字經過散列函數(shù)得到一個"隨機的地址"，從而減少碰撞。1. 直接尋址法:取關鍵字或關鍵字的某個線性函數(shù)值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數(shù)(這種散列函數(shù)叫做自身函數(shù))。若其中H(key)中已經有值了，就往下一個找，直到H(key)中沒有值了，就放進去。2. 數(shù)字分析法:分析一組數(shù)據(jù)，比如一組員工的出生年月日，這時我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同，這樣的話，出現(xiàn)沖突的幾率就會很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大，如果用后面的數(shù)字來構成散列地址，則沖突的幾率會明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構造沖突幾率較低的散列地址。3. 平方取中法:當無法確定關鍵字中哪幾位分布較均勻時，可以先求出關鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因為:平方后中間幾位和關鍵字中每一位都相關，故不同關鍵字會以較高的概率產生不同的哈希地址。4. 折疊法:將關鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和(去除進位)作為散列地址。數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對齊，然后相加;間界疊加是從一端向另一端沿分割界來回折疊，然后對齊相加。4. 隨機數(shù)法:選擇一隨機函數(shù)，取關鍵字的隨機值作為散列地址，通常用于關鍵字長度不同的場合。5. 除留余數(shù)法:取關鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之后取模。對p的選擇很重要，一般取素數(shù)或m，若p選的不好，容易產生同義詞。 查找性能 散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數(shù)轉換的地址直接找到，另一些關鍵碼在散列函數(shù)得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突后的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。查找過程中，關鍵碼的比較次數(shù)，取決于產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。影響產生沖突多少有以下三個因素:1. 散列函數(shù)是否均勻;2. 處理沖突的方法;3. 散列表的裝填因子。散列表的裝填因子定義為:α= 填入表中的元素個數(shù) / 散列表的長度α是散列表裝滿程度的標志因子。由于表長是定值，α與"填入表中的元素個數(shù)"成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大;α越小，填入表中的元素較少，產生沖突的可能性就越小。實際上，散列表的平均查找長度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。了解了hash基本定義，就不能不提到一些著名的hash算法，MD5 和 SHA-1 可以說是目前應用最廣泛的Hash算法，而它們都是以 MD4 為基礎設計的。那么他們都是什么意思呢?這里簡單說一下:⑴ MD4MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設計的，MD 是 Message Digest 的縮寫。它適用在32位字長的處理器上用高速軟件實現(xiàn)--它是基于 32 位操作數(shù)的位操作來實現(xiàn)的。⑵ MD5MD5(RFC 1321)是 Rivest 于1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯(lián)，與 MD4 相同。MD5比MD4來得復雜，并且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現(xiàn)更好⑶ SHA-1 及其他SHA1是由NIST NSA設計為同DSA一起使用的，它對長度小于264的輸入，產生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設計時基于和MD4相同原理，并且模仿了該算法。那么這些Hash算法到底有什么用呢?Hash算法在信息安全方面的應用主要體現(xiàn)在以下的3個方面:⑴ 文件校驗我們比較熟悉的校驗算法有奇偶校驗和CRC校驗，這2種校驗并沒有抗數(shù)據(jù)篡改的能力，它們一定程度上能檢測出數(shù)據(jù)傳輸中的信道誤碼，但卻不能防止對數(shù)據(jù)的惡意破壞。MD5 Hash算法的"數(shù)字指紋"特性，使它成為目前應用最廣泛的一種文件完整性校驗和(Checksum)算法，不少Unix系統(tǒng)有提供計算md5 checksum的命令。⑵ 數(shù)字簽名Hash 算法也是現(xiàn)代密碼體系中的一個重要組成部分。由于非對稱算法的運算速度較慢，所以在數(shù)字簽名協(xié)議中，單向散列函數(shù)扮演了一個重要的角色。對 Hash 值，又稱"數(shù)字摘要"進行數(shù)字簽名，在統(tǒng)計上可以認為與對文件本身進行數(shù)字簽名是等效的。而且這樣的協(xié)議還有其他的優(yōu)點。⑶ 鑒權協(xié)議如下的鑒權協(xié)議又被稱作挑戰(zhàn)--認證模式:在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。MD5、SHA1的破解2004年8月17日，在美國加州圣芭芭拉召開的國際密碼大會上，山東大學王小云教授在國際會議上首次宣布了她及她的研究小組的研究成果--對MD5、HAVAL-128、MD4和RIPEMD等四個著名密碼算法的破譯結果。2005年2月宣布破解SHA-1密碼。

總結

以上是生活随笔為你收集整理的数据结构笔记 第六章 查找技术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。