查找算法的总结
聲明：以下內容來源于網絡資料的學習和整理
一、查找技術分類
1、靜態查找表技術（順序查找、二分查找、分塊查找）
2、動態查找表技術（二叉查找樹）
3、哈希表技術（哈希表技術）
?
二、查找技術說明
????衡量查找算法優劣的標準——平均搜索長度（ASL）=，其中Ci為查找第i個數需要進行比較的次數（比如開始對比一個數組中的第i個數，則前面已經對比了i-1個數字），Pi表示查找第i個數的概率（一般會平均，即1/n）。
?
A、靜態查找表技術
1、順序查找
（1）平均查找長度為：(n+1)/2，即時間復雜度為O(n)。
2、二分查找
（1）必須是有序表，而且只適用于順序存儲結構；性能只有在均勻分布的時候才是最優的。
（2）查找長度：每經過一次比較，查找范圍都要縮小一半，因此最大查找長度為MSL=[log2 n]+1。當n足夠大時，可近似的表示為log2(n)，即時間復雜度為O(log2(n))。
（3）二分查找要求查找表按關鍵字有序，而排序是一種很費時的運算；而且二分查找法要求表是順序存儲的，為保持表的有序性，在進行插入和刪除操作時，都必須移動大量記錄。因此，二分查找的高查找效率是以犧牲排序為代價的，它特別適合于一經建立就很少移動、而又經常需要查找的線性表。
（4）代碼示例
//k為待查找的數字，R為數據集合，函數返回k在R[]中的位置 int binsearch(int R[], int k) {int low = 0, high = n-1;//R長度為nint mid;int find = 0;while ((low <= high) && (!find)){mid = (low + high) / 2; /*求區間中間位置*/if (k == R[mid])find = 1; /*查找到*/elseif (k>R[mid])low = mid + 1; /*在后半區查找，修改low*/elsehigh = mid - 1; /*在前半區查找，修改high*/}if (find)return (mid); /*查找成功，返回找到的元素位置*/elsereturn (-1); /*查找失敗，返回-1*/ }
3、分塊查找（索引順序查找）
（1）分塊查找要求把線性表分成若干塊，塊與塊之間必須有序（即假如升序排列，那么第一塊的最大值，必須小于第二塊的最小值），但是在每一塊中記錄的關鍵字不一定有序。假設這種排序是按關鍵字值遞增排序的，抽取各塊中的最大關鍵字及該塊的起始位置構成一個索引表，按塊的順序存放在一個數組中，顯然這個數組是有序的。
（2）分塊查找過程分兩步進行：
a、首先查找索引表，確定待查記錄所在塊（可用二分查找法或順序查找法）；
b、在相應塊（子表）中用順序查找法查找記錄。 ??
（3）分塊查找的效率介于順序查找和折半查找之間，對于數據量巨大的線性表，它是一種較好的方法。在表中插入或刪除一個記錄時，只要找到該記錄所屬的塊，就可以在該塊內進行插入和刪除運算，插入和刪除無需移動大量記錄。分塊查找的主要代價是：需要增加一個輔助數組的存儲空間和將初始表分塊排序的運算。
（4）代碼示例：
struct idtable {int key;//這里指的是該塊的最大值int addr;//該快的最大值在數組中的位置 }; struct idtable ID[b]; /*b為塊數*/int blksearch(int R[], struct idtable ID[], int k) {int i;int low1=0, high1=b-1;//low1、high1為索引表的區間下、上界int low2, high2;int mid; while (low1 <= high1){mid = (low1 + high1) / 2;if (k <= ID[mid].key)high1 = mid - 1;elselow1 = mid + 1;}/*查找完畢，low1存放找到的塊號*/if (low1 < b){low2 = ID[low1].addr; /*low2為待查值所在的那個表的起始地址*/if (low1 == b - 1)high2 = N - 1; /*N為查找表的長度，high2為塊在表中的末地址*/elsehigh2 = ID[low1 + 1].addr - 1;for (i = low2; i <= high2; i++) /*在塊內順序查找*/if (R[i].key == k)return i;}else /*若low1>=b，則k大于查找表R中的所有關鍵字*/return -1;B、動態查找表技術
C、哈希表技術
1、哈希表的定義
???哈希表是通過關鍵字進行某種計算（映射）來確定該記錄的存儲位置的一種查找表。
2、沖突解決方法
???不同的關鍵字，根據哈希函數被映射到同一個存儲地址，這種現象被稱為沖突。沖突是不可避免的，因為關鍵字的取值集合遠遠大于表空間的地址集合，我們只能盡量減少沖突的發生。在構造哈希函數時，主要面臨兩個問題：一是構造較好的哈希函數，把關鍵字集合中元素盡可能均勻地分布到地址空間中去，減少沖突的發生，另一個就是找到解決沖突的方法。 解決沖突的方法中比較常用的是鏈地址法，即為每一個哈希地址建立一個鏈表，當沖突發生時，將具有相同哈希地址的記錄鏈接到同一鏈表中。
3、哈希算法的過程：首先得建立哈希表（一般都有從文件中讀取吧？），其次才是查找。
4、完整代碼示例：
#include<stdio.h> #include<stdlib.h>struct keyNum {int key;//關鍵字struct keyNum *next; };struct keyNum* hash[100]; struct keyNum* insertHash(struct keyNum*, int m);//關鍵字插入鏈表 int searchHash(struct keyNum*, int m);//查找鏈表中是否存在值為m的整數 void print(struct keyNum*);//打印鏈表void main() {printf("關鍵字列表請保存在data.txt文件中，其中第一個值為關鍵字的個數\n其他值為具體的關鍵字，各個關鍵字之間用空格隔開\n");int i, k, m, n, num, flag, l, j;FILE *p=NULL;struct keyNum *head = NULL;p = fopen("C:\\Users\\Horrobo\\Desktop\\data.txt", "r");if (p == NULL){printf("cannot open file 2.txt");exit(0);}fscanf(p, "%d", &num);//data.txt第一個值為關鍵字的個數，因此num讀入的是關鍵字的個數，這里默認num小于100的for (i = 0; i<num; i++)//由于hash[]只有100個指針，因此關鍵字映射后最多只能有100個不相同的。hash[i] = NULL;for (i = 0; i<num; i++){ //fscanf()遇到空格停止讀取？fscanf(p, "%d", &k);//獲取關鍵字m = k % (num + 1);//計算得到關鍵字的哈希值hash[m] = insertHash(hash[m], k);//將關鍵字k插入到哈希值為m的鏈表中}printf("-----------------------------------------------\n請選擇要進行的操作：\n1、打印采用鏈地址法得到的哈希表\n");printf("2、進行關鍵字查找\n3、退出\n------------------------------------------------\n");scanf("%d", &flag);while ((flag == 1) || (flag == 2)){if (flag == 1)//打印哈希表{printf("采用鏈地址法得到的哈希表為：\n");for (i = 0; i<num + 1; i++){printf("第%d行：", i);print(hash[i]);printf("\n");}}else //查找{printf("請輸入要查找的整數值：\n");scanf("%d", &n);for (i = 0; i<num + 1; i++)//只是返回一個標志值，后面再根據標志來執行操作，這個流程值得參考哦{l = searchHash(hash[i], n);if (l == 1){j = i;break;}}if (l == 1)printf("整數值%d在哈希表中，位置為鏈表%d\n", n, j);//只是找出位于第幾鏈表而已。else printf("整數值%d不在哈希表中！\n");}printf("-----------------------------------------------\n請選擇要進行的操作：\n1、打印采用鏈地址法得到的哈希表\n");printf("2、進行關鍵字查找\n3、退出\n------------------------------------------------\n");scanf("%d", &flag);} }struct keyNum * insertHash(struct keyNum*head, int m) {struct keyNum *p0, *p1, *p2=NULL, *temp;//這些都僅僅是結構體指針，而不是結構體，它所指向的內容才是結構體內容。就把它理解為類型 int*指針就好temp = (struct keyNum*)malloc(sizeof(struct keyNum));temp->key = m;p1 = head;p0 = temp;//要插入的節點（值為m);if (head == NULL)//1，原來的鏈表為空，插入到head后{head = p0;p0->next = NULL;}else//原來的鏈表不為空{while ((p0->key>p1->key) && (p1->next != NULL))//移動到適當位置 起碼有兩個節點了，否則p1->next != NULL這個就不滿足了。因為P1=head，是第一個節點的指針{//判斷語句從head開始，查詢鏈表（p1->next != NULL，p1=p1->next）,看是否滿足條件（p0->key>p1->key） p2 = p1;p1 = p1->next;}if (p0->key <= p1->key){if (head == p1)head = p0;//2，插入到第一個節點之前else p2->next = p0;//3,插入到p2指向的節點之后p0->next = p1;}else//4,插入到結尾處{p1->next = p0;p0->next = NULL;}}return(head); }int searchHash(struct keyNum*head, int m)//查找鏈表head中是否存在m {int k = 0;struct keyNum*p;p = head;if (head != NULL)do{if (p->key == m) //存在m{k = 1;break;}p = p->next;} while (p != NULL);return(k);//存在m值則返回1，否則返回0； }void print(struct keyNum*head)//打印鏈表head {struct keyNum*p;p = head;if (head != NULL){do{printf(" -> %d ", p->key);p = p->next;} while (p != NULL);}elseprintf("null"); }/* struct keyNum * insertHash(struct keyNum*head, int k)// {struct keyNum *p = (struct keyNum *)malloc(sizeof(struct keyNum));//1.首先開創一個結構體區間，給里面的相應內容賦值p->key = k;struct keyNum * temp = NULL;if (head == NULL)//2、判斷是否是空指針，如果是，則將剛才創建的結構體區間作為頭//具體的實現方法，就是將傳過來的空指針指向剛才創建的結構體空間（yes）{head = p;p->next = NULL;}else//如果不是，則在原來的鏈條的尾巴上添加新的節點（上面已經創建好的節點）//具體的實現方法，就是將head指針指向剛才所創建的結構體空間？（NO）：head并不是指向尾巴節點的指針，而是整個鏈條的首指針！！！！{head->next = p;p->next = NULL;}return head; } */總結：
（1）順序查找的查找效率很低；但是對于待查記錄的存儲結構沒有任何要求，既適用于順序存儲，又適用于鏈式存儲；當待查表中的記錄個數較少時，采用順序查找法較好。
（2）折半查找的平均查找長度較小，查找速度快；但它只能用于順序存儲，不能用于鏈式存儲；且要求表中的記錄是有序的。對于不常變動的有序表，采用折半查找法是較為理想的。
（3）分塊查找的平均查找長度介于順序查找和折半查找之間；跟順序查找一樣，對記錄的存儲結構沒什么要求，既可以用于順序存儲，也可用于鏈式存儲；要求表中元素是逐段有序的，即塊與塊之間的記錄按關鍵字有序。當待查表的數據量較大時，分塊查找的優越性更為突出。
（4）哈希法是一種直接計算地址的方法，通過對關鍵字值進行某種運算來確定待查記錄的存儲地址。在查找過程中不需要進行比較，因此，其查找時間與表中記錄的個數無關。當所選擇的哈希函數能得到均勻的地址分布時，其查找效率比前面的三種方法都要快。哈希法的查找效率取決于以下三個因素：哈希函數、處理沖突的方法及裝填因子。
?
P.s.線性表包括順序存儲表（比如數組）、鏈式存儲表（鏈表）。
另外在編程的過程中，也體會到了以下內容：指向結構體的指針P或者head，無論是通過賦值還是開創的空間的強制轉換，head->next,p->next都是p結構體內next。
總結
- 上一篇： 文件（夹）权限操作
- 下一篇： 2022年最佳的9种逆向工程工具[持续更