數據結構中的查找演算法

⑴ 數據結構有哪些基本演算法

數據結構是一門研究非數值計算的程序設計問題中的操作對象，以及它們之間的關系和操作等相關問題的學科。

可以理解為：程序設計 = 數據結構 + 演算法

數據結構演算法具有五個基本特徵：輸入、輸出、有窮性、確定性和可行性。

1、輸入：一個演算法具有零個或者多個輸出。以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件。後面一句話翻譯過來就是，如果一個演算法本身給出了初始條件，那麼可以沒有輸出。比如，列印一句話：NSLog(@"你最牛逼！");

2、輸出：演算法至少有一個輸出。也就是說，演算法一定要有輸出。輸出的形式可以是列印，也可以使返回一個值或者多個值等。也可以是顯示某些提示。

3、有窮性：演算法的執行步驟是有限的，演算法的執行時間也是有限的。

4、確定性：演算法的每個步驟都有確定的含義，不會出現二義性。

5、可行性：演算法是可用的，也就是能夠解決當前問題。

數據結果的基本演算法有：

1、圖搜索（廣度優先、深度優先）深度優先特別重要

2、排序

3、動態規劃

4、匹配演算法和網路流演算法

5、正則表達式和字元串匹配

6、三路劃分-快速排序

7、合並排序（更具擴展性，復雜度類似快速排序）

8、DF/BF 搜索 （要知道使用場景）

9、Prim / Kruskal （最小生成樹）

10、Dijkstra （最短路徑演算法）

11、選擇演算法

⑵ 數據結構 順序查找演算法和折半查找演算法

//順序查找
int findKey(int array[], int length, int key)
{
for (int i = 0; i < length; i++)
if (array[i] == key)
return i;
return -1;
}
//折半查找
int findKeybyBinary(int array[], int low, int high, int key)
{
if (low > high)
return -1;
int mid = (low + high)/2;
if (array[mid] == key)
return mid;
else if (array[mid] < key)
return findbyBinary(array,mid + 1,high, key);
else
return findbyBinary(array,low,mid - 1, key);
}

查找key=41的演算法： 比較次數：3次
void main ()
{
int array[] = {8，15，19，26，33，41，47，52，64，90};
printf("the pos of 41 is %d \n", findKeybyBinary(array, 0, 9, 41));
}
查找key=35的演算法： 比較次數：6次

void main ()
{
int array[] = {12，76，29，15，62，35，33，89，48，20};
printf("the pos of 41 is %d \n", findKey(array, 10, 35));
}

⑶ 數據結構折半查找演算法的方法

041424344#include <stdio.h> int Dichotomy(int a[],int _value,int n){ // 二分法(也稱折半查找法) int index=0; // 當前數組的首元素下標 int current=n-1; // 數組當前的大小 int k; // 當前數組中間的數的下標 while (index<current) { // 開始二分法查找 k=(index+current)/2; // 除以2代表得到當前數組中間的數的下標 if(a[k]==_value) return k; // 返回要查找的值_value所在的下標 // 否則比較要查找的值_value是在折半後的前半部分還是後半部分 if(a[k]<_value){ // 說明要查找的值在折半後的後半部分 index=k+1; // 令index指向後半部分數組的首元素 } else{ // 說明要查找的值在折半後的前半部分 current=k-1; // 令current等於前半部分數組的長度 } } return -1; // 返回-1代表沒有查找到該值(_value)}void main(){ int arr[5]={2,12,45,87,95};// 前提是一組數組必須是有序數對(即按小到大或大到小) if(Dichotomy(arr,87,5)!=-1) printf("87在數組中對應的下標是:%d\n",Dichotomy(arr,87,5)); else printf("沒有找到指定的值\n");}// 用一句話概括二分法(折半查找法)的思想就是:在一組有序對數組中反復折半後得到中間數組的下標,然後再進行是否與要查找的值相等,若相等則返回當前要查找的值的下標。 那麼，上面的代碼的注釋與下面一一對應，它在執行的結果會產生兩種情況，第一種,不存在。第二種，存在。先來說說第一種情況 不存在： 1.如果給定要查找的值_value大於數組中最大的數,則index不斷增大從而促使while循環終止 2.如果給定要查找的值_value小於數組中最小的數,則current不斷減少從而促使while循環終止(你自己可以動手在紙上畫一個數組,然後思路跟著代碼走就會知道或設單步調試亦可) 第二種情況 存在： 1.要查找的數_value正好是在數組中間.那麼就執行了一次循環,當然這也是最理想的效果. 否則反復執行2和3:2.如果要查找的數_value不存在中間,則判斷它是否大於中間的數還是小於中間的數,如果小於中間的數則說明_value應該在數組中間的前半部分,那麼current=k-1(即令current等於前半部分的長度),然後仍然採取折半的方法,反復此操作直至找到該數的下標為止. 3.如果要查找的數_value不存在中間,則判斷它是否大於中間的數還是小於中間的數,如果大於中間的數則說明_value應該在數組中間的後半部分,那麼index=k+1(即令index指向後半部分的第一個下標),然後仍然採取折半的方法,反復此操作直至找到該數的下標為止.

⑷ 數據結構中有哪些查找演算法

和二分查找性能接近的：既然可以二分查找，那麼關鍵字肯定可以滿足全序關系。那麼可以用二叉查找樹，一般的就是平攤O(logn),最壞O(n)。如果用平衡樹，如AVL,Treap,Splay等等，可以做到保持O(logn)的界。
比二分查找性能更優的：大概只有Hash了吧。如果Hash函數設計的好，基本可以認為是O(1)的。這個你最好系統學習一下，尤其是字元串的Hash函數。

⑸ 數據結構：重要的查找演算法有哪些

折半查找也就是二分查找，它必須滿足排序關系。
查找也可以用二叉查找樹，一般復雜度為O(logn),最壞為O(n)。
也可用平衡樹進行查找，如AVL,Treap,Splay等，可以做到保持O(logn)。

比二分查找性能更優的：大概只有Hash了吧。如果Hash函數設計的好，基本可以認為是O(1)

堆排序比較有意思，值得研究一下，理解了後，很有用～，也很重要。

⑹ 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;
}
折半查找運行結果：
三、實驗總結：
該實驗使用了兩種查找數據的方法（順序查找和折半查找），這兩種方法的不同之處在於查找方式和過程不同，線性表的創建完全相同，程序較短，結果也一目瞭然。

⑺ 【數據結構】幾種重要的查找演算法。

恩你是要問什麼?

順序查找就是按順序查找,復雜度O(n)

二分查找的前提是數據是有序的 一次復雜度O(logn)
例如在數組 A: 1 3 5 7 8 10 12 中
如果要找 10
我們先看中間的數是 7, 10比7大,那麼繼續在右側二分尋找,這是一個遞歸的過程.
偽代碼:
bool find(int L,int R,int What_You_Want) {
if (L > R) return false;
int mid = (L + R) / 2
if (A[mid] == What_You_Want) return true;
else if (A[mid] > What_You_Want) return find(L,mid - 1,What_You_Want);
else return find(mid + 1, R, What_You_Want);
}

二叉搜索樹的原理與二分查找相同

⑻ 數據結構中有哪些基本演算法

數據結構中最基本的演算法有：查找、排序、快速排序，堆排序，歸並排序，，二分搜索演算法
等等。

1、用的最多也是最簡單的數據結構是線性表。

2、有前途的又難數據結構是圖 。

3、常用的80％演算法是排序和查找。

⑼ 數據結構中，查找演算法最優的是哪一種

折半查找法的平均查找長度隨n增大而呈現對數增長趨勢，因此折半查找法為最優查找演算法