㈠ 數據結構中有哪些查找演算法
和二分查找性能接近的：既然可以二分查找，那麼關鍵字肯定可以滿足全序關系。那麼可以用二叉查找樹，一般的就是平攤O(logn),最壞O(n)。如果用平衡樹，如AVL,Treap,Splay等等，可以做到保持O(logn)的界。
比二分查找性能更優的：大概只有Hash了吧。如果Hash函數設計的好，基本可以認為是O(1)的。這個你最好系統學習一下，尤其是字元串的Hash函數。
㈡ 要求設計實現一個查找演算法比較，能對順序查找、折半查找、分塊查找的平均查找長度進行比較。急 謝謝啦
給你一個參考程序，你可以看一下，自己仿照著寫一下，只需要修改一下main()函數就可以了：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
const int ARRSIZE= 10015;
// 從小到大排序數組元素
void asort(int *a, int s)
{
int i, j, k, t;
for (i = 0; i < s-1; ++i)
{
k = i;
for (j = i + 1; j < s; ++j)
{
if (a[k] > a[j])
{
k = j;
}
}
if (k != i)
{
t = a[i];
a[i] = a[k];
a[k] = t;
}
}
}
// 順序查找，找到返回該元素數組下標，否則返回-1
int SeqSearch(int *a, int s, int k)
{
int i;
for (i = 0; i < s; ++i)
{
if (k == a[i])
return i;
}
return -1;
}
// 折半查找，找到返回該元素數組下標，否則返回-1
int BinSearch(int *a, int s, int k)
{
int low = 0;
int high = s - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (k == a[mid])
{
return mid;
}
else
{
if (k < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1;
}
// 分塊查找，找到返回該元素數組下標，否則返回-1，bs表示數列分成的塊數
int BlkSearch(int *a, int s, int k, int bs)
{
int i, j, t = s / bs;
for (i = 0; i < bs; ++i)
{
if (k >= a[i*t] && k <= a[i*t+t-1])
{
int e = i*t+t;
for (j = i*t; j < e; ++j)
if (k == a[j])
return j;
}
}
--i;
for (i = i * bs; i < s; ++i)
{
if (k == a[i])
return i;
}
return -1;
}
void main()
{
int i, k, a[ARRSIZE];
srand(time(NULL));
for (i = 0; i < ARRSIZE; ++i)
a[i] = rand() % ARRSIZE;
asort(a, ARRSIZE);
/*
for (i = 0; i < ARRSIZE; ++i)
printf("%d ", a[i]);
*/
putchar('\n');
scanf("%d", &k);
if (SeqSearch(a, ARRSIZE, k) != -1)
printf("%d is found in array\n", k);
if (BinSearch(a, ARRSIZE, k) != -1)
printf("%d is found in array\n", k);
if (BlkSearch(a, ARRSIZE, k, 100) != -1)
printf("%d is found in array\n", k);
}
希望對你有所幫助！
㈢ 常見的數據檢索演算法有哪些資料庫都採用什麼樣的檢索方式如何提高檢索的效率
信息檢索方法包括：普通法、追溯法和分段法。1、普通法是利用書目、文摘、索引等檢索工具進行文獻資料查找的方法。運用這種方法的關鍵在於熟悉各種檢索工具的性質、特點和查找過程，從不同角度查找。普通法又可分為順檢法和倒檢法。2、追溯法是利用已有文獻所附的參考文獻不斷追蹤查找的方法，在沒有檢索工具或檢索工具不全時，此法可獲得針對性很強的資料，查准率較高，查全率較差。3、分段法是追溯法和普通法的綜合，它將兩種方法分期、分段交替使用，直至查到所需資料為止。(3)設計實用的查找演算法擴展閱讀檢索原因信息檢索是獲取知識的捷徑美國普林斯頓大學物理系一個年輕大學生名叫約瀚·菲利普，在圖書館里借閱有關公開資料，僅用四個月時間，就畫出一張製造原子彈的設計圖。他設計的原子彈，體積小(棒球大小)、重量輕(7.5公斤)、威力大(相當廣島原子彈3/4的威力)，造價低(當時僅需兩千美元)，致使一些國家（法國、巴基斯坦等）紛紛致函美國大使館，爭相購買他的設計拷貝。二十世紀七十年代，美國核專家泰勒收到一份題為《製造核彈的方法》的報告，他被報告精湛的技術設計所吸引，驚嘆地說：「至今我看到的報告中，它是最詳細、最全面的一份。」
㈣ 幾種常見的查找演算法之比較
二分法平均查找效率是O(logn)，但是需要數組是排序的。如果沒有排過序，就只好先用O（nlogn)的預處理為它排個序了。而且它的插入比較困難，經常需要移動整個數組，所以動態的情況下比較慢。
哈希查找理想的插入和查找效率是O(1)，但條件是需要找到一個良好的散列函數，使得分配較為平均。另外，哈希表需要較大的空間，至少要比O(n)大幾倍，否則產生沖突的概率很高。
二叉排序樹查找也是O(logn)的，關鍵是插入值時需要做一些處理使得它較為平衡（否則容易出現輕重的不平衡，查找效率最壞會降到O(n)），而且寫起來稍微麻煩一些，具體的演算法你可以隨便找一本介紹數據結構的書看看。當然，如果你用的是c語言，直接利用它的庫類型map、multimap就可以了,它是用紅黑樹實現的，理論上插入、查找時間都是O(logn)，很方便，不過一般會比自己實現的二叉平衡樹稍微慢一些。
㈤ 按值查找該怎樣設計演算法，用數據結構所學內容
（1）查找的方法
按照數據元素的組織方式決定採用的查找方法；為了提高查找方法的效率，又要求數據元素採用某些特殊的組織方式。因此，在研究各種查找方法時，必須弄清各種方法所適用的組織方式。
（2）查找演算法的評價
標准有兩個：時間復雜度和空間復雜度。在查找演算法中，基本運算是給定值與關鍵字值的比較，所以，我們引出一個成為平均查找長度（ASL）的概念，作為評價查找演算法好壞的依據。
㈥ 查找演算法有哪些
查找演算法常用的有，順序查找，二分查找，哈希表查找，等等。
㈦ 最好的查找演算法是什麼
沒有最好只有更好
對不同特徵的數據也有不同的查找演算法，所有的查找演算法都是針對某一特徵的數據進行優化的，比如用散列表查找很快的數據用二分發就不一定快，散列表用不同的哈希演算法查找性能也大不相同。
㈧ 10個常用演算法
原理：
二分法查找，也稱為折半法，是一種在有序數組中查找特定元素的搜索演算法。
一般步驟：
（1）確定該區間的中間位置K；
（2）將查找的值T與array[k]比較。
若相等，查找成功返回此位置；否則確定新的查找區域，繼續二分查找。每一次查找與中間值比較，可以確定是否查找成功，不成功當前查找區間將縮小一半，遞歸查找即可。
原理：
一種通過重復將問題分解為同類的子問題而解決問題的方法
典型例子：
斐波那契數列
描述： 斐波那契數列 指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368.....自然中的斐波那契數列") 自然中的斐波那契數列，這個數列從第3項開始，每一項都等於前兩項之和。
解決方式：
原理：
在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就「回溯」返回，嘗試別的路徑。
回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。
但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
解決問題一般步驟：
1、 針對所給問題，定義問題的解空間，它至少包含問題的一個（最優）解。
2 、確定易於搜索的解空間結構,使得能用回溯法方便地搜索整個解空間 。
3 、以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索。
典型例子：
八皇後問題
描述：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。
解決方式： https://blog.csdn.net/weixin_41865447/article/details/80034433
概念：
將雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程叫做排序。
分類：
非穩定排序演算法：快速排序、希爾排序、堆排序、直接選擇排序
穩定的排序演算法：基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序
十個常用排序演算法
利用計算機的高性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。
分類：
枚舉演算法、深度優先搜索、廣度優先搜索、A*演算法、回溯演算法、蒙特卡洛樹搜索、散列函數等演算法。
將一個數據轉換為一個標志，這個標志和源數據的每一個位元組都有十分緊密的關系。
很難找到逆向規律
只要符合散列思想的演算法都可以被稱為是Hash演算法
對不同的關鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現象稱為 碰撞 。
原理
在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在 某種意義上的局部最優解 。
從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加演算法停止。
一種近似演算法
一般步驟：
1、建立數學模型來描述問題；
2、把求解的問題分成若干個子問題；
3、對每一子問題求解，得到子問題的局部最優解；
4、把子問題的解局部最優解合成原來解問題的一個解。
典型例子：
0/1背包問題
馬踏棋盤
均分紙牌
例題： https://www.cnblogs.com/hust-chen/p/8646009.html
概念：
分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序演算法，簡單問題可用二分法完成。
一般步驟：
（1）分解，將要解決的問題劃分成若干規模較小的同類問題；
（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；
（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。
典型例子：
排序中：歸並排序、堆排序、快速排序；
實例：找偽幣、求最值、棋盤覆蓋
https://ke..com/item/%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95/3263297
概念：
用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。
動態規劃一般可分為線性動規，區域動規，樹形動規，背包動規四類。
舉例：
線性動規：攔截導彈，合唱隊形，挖地雷，建學校，劍客決斗等；
區域動規：石子合並， 加分二叉樹，統計單詞個數，炮兵布陣等；
樹形動規：貪吃的九頭龍，二分查找樹，聚會的歡樂，數字三角形等；
背包問題：01背包問題，完全背包問題，分組背包問題，二維背包，裝箱問題，擠牛奶（同濟）等；
應用實例：
最短路徑問題 ，項目管理，網路流優化等；
https://ke..com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fromtitle=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95&fromid=15742703&fr=aladdin
概念：
在一個給定的字元文本內搜尋出自己想要找的一個字元串，平常所用的各種文本編輯器里的ctrl+F大多就是使用的這些字元匹配演算法。
分類：
KMP、BM、Sunday、Horspool、RK
參考：
https://cloud.tencent.com/developer/news/282694
https://blog.csdn.net/paincupid/article/details/81159320
㈨ 常見的搜索演算法有哪幾種
廣度優先搜索（BFS）
深度優先搜索（DFS）
爬山法（Hill Climbing）
最佳優先演算法（Best-first search strategy）
回溯法 （Backtracking）
分支限界演算法（Branch-and-bound Search Algorithm）
㈩ C語言編寫數據結構查找演算法
實驗五 查找的實現
一、 實驗目的
1．通過實驗掌握查找的基本概念；
2．掌握順序查找演算法與實現；
3．掌握折半查找演算法與實現。
二、 實驗要求
1． 認真閱讀和掌握本實驗的參考程序。
2． 保存程序的運行結果，並結合程序進行分析。
三、 實驗內容
1、建立一個線性表，對表中數據元素存放的先後次序沒有任何要求。輸入待查數據元素的關鍵字進行查找。為了簡化演算法，數據元素只含一個整型關鍵字欄位，數據元素的其餘數據部分忽略不考慮。建議採用前哨的作用，以提高查找效率。
2、查找表的存儲結構為有序表，輸入待查數據元素的關鍵字利用折半查找方法進行查找。此程序中要求對整型量關鍵字數據的輸入按從小到大排序輸入。
一、順序查找
順序查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請輸入您想輸入的%d個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
inti=0;
s->r[s->length].key=k;
while(s->r[i].key!=k)
{
i++;
}
if(i==s->length)
{
printf("該表中沒有您要查找的數據！\n");
return-1;
}
else
returni+1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
順序查找的運行結果：
二、折半查找
折半查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請由大到小輸入%d個您想輸入的個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
intlow,mid,high;
low=0;
high=s->length-1;
while(low<=high)
{
mid=(low+high)/2;
if(s->r[mid].key==k)
returnmid+1;
elseif(s->r[mid].key>k)
high=mid-1;
else
low=mid+1;
}
printf("該表中沒有您要查找的數據!\n");
return-1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
折半查找運行結果：
三、實驗總結：
該實驗使用了兩種查找數據的方法（順序查找和折半查找），這兩種方法的不同之處在於查找方式和過程不同，線性表的創建完全相同，程序較短，結果也一目瞭然。