天天看點

【查找算法】——順序查找、折半查找、分塊查找(索引查找)轉載出處:http://www.cnblogs.com/kunhu/p/3634562.html 查找算法 概述:

轉載出處:http://www.cnblogs.com/kunhu/p/3634562.html

查找算法

概述:

查找算法:就是在是資料元素集合中檢視是否存在于指定的關鍵字相等的元素。

查找分為兩種:靜态查找和動态查找。

1) 靜态查找:是指在資料元素集合中查找與給定的關鍵字相等的元素。

2) 動态查找:就是指在查找過程中,如果資料元素集合中不存在與給定的關鍵字相等的元素,則将該元素插入到資料元素集合中。

靜态查找主要包括順序表、有序順序表和索引順序表的查找。

1) 順序表的查找,就是指從表的第一個元素與給定關鍵字比較,直到表的最後。

2) 有序順序表的查找,在查找的過程中如果給定的關鍵字大于表的元素,就可以停止查找,說明表中不存在該元素(假設表中的元素按照關鍵字從小到大排列,并且查找從第一個元素開始比較)

3) 索引順序表的查找是為主表建立一個索引,根據索引确定元素所在的範圍,這樣可以有效地提高查找的效率。

動态查找主要包括二叉排序樹、平衡二叉樹、B-樹和B+樹。

這些都是利用二叉樹和樹的特點對資料元素集合進行排序,通過将元素插入到二叉樹或樹中建立二叉樹或樹,然後通過對二叉樹或樹的周遊按照從小到大輸出元素的序列。

散清單是利用散列函數的映射關系直接确定要查找元素的位置,大大減少了與元素的關鍵字的比較次數。

建立散清單的方法主要有直接定址法、平方取中法、折疊法和除留餘數法(最常用)等。

但是會存在沖突,解決沖突的最為常用的方法主要有兩個:開放定址法和鍊位址法。

一.靜态查找

1.順序表的查找——順序查找

順序查找(Sequential Search)又稱為線性查找,是一種最簡單的查找方法。  

        從表的一端開始,向另一端逐個按要查找的值key 與關鍵碼key進行比較,若找到,查找成功,并給出資料元素在表中的位置;若整個表檢測完,仍未找到與關鍵碼相同的key值,則查找失敗,給出失敗資訊。

說白了就是,從頭到尾,一個一個地比,找着相同的就成功,找不到就失敗。很明顯的缺點就是查找效率低。

【适用性】:适用于線性表的順序存儲結構和鍊式存儲結構。

 平均查找長度=(n+1)/2.

【順序查找優缺點】:

缺點:是當n 很大時,平均查找長度較大,效率低;

優點:是對表中資料元素的存儲沒有要求。另外,對于線性連結清單,隻能進行順序查找。

#include<iostream>
using namespace std;

#define MAX 11

typedef int key_type;

typedef struct element
{
	key_type key;   //關鍵字 
}elem;

int seq_search(elem e[], key_type key, int n)
{
	int i = 0;
	while(i < n && e[i].key != key)
	{
		i++;
	}
	
	if(i < n)
		return i;
	else 
		return -1;
}
 
 int main(int argc, char** argv)
 {
 	elem linelist[MAX] = {1,5,9,7,12,11,10,8,6,2,3};
 	int n = 11;
 	int i = 0;
 	key_type key = 8;
 	printf("線性表中的元素為: \n");
 	
 	while(i < n)
 	{
		printf("%d\n",linelist[i].key);
		i++; 
	}	
	
	printf("\n關鍵字[%d]線上性表中的位置下标為[%d]\n", key, seq_search(linelist, key, n));
	
	getchar();
	system("pause");
 }
           

2.有序順序表的查找——折半查找

        在有序表中,取中間元素作為比較對象,若給定值與中間元素的關鍵碼key相等,則查找成功;若給定值小于中間元素的關鍵碼,則在中間元素的左半區繼續查找;若給定值大于中間元素的關鍵碼,則在中間元素的右半區繼續查找。不斷重複上述查找過程,直到查找成功,或所查找的區域無資料元素,查找失敗。

【步驟】

① low=0;high=length-1;                                                          // 設定初始區間

② 當low>high 時,傳回查找失敗資訊                                         // 表空,查找失敗

③ 當low<=high,mid=(low+high)/2;                                           //确定該區間的中點位置

      a. 若key < elem[mid].key,high = mid-1;轉②                    // 查找在左半區進行

      b. 若key > elem[mid].key,low  = mid+1; 轉②                  // 查找在右半區進行

      c. 若key = elem[mid].key,傳回資料元素在表中位置        // 查找成功

有序表按關鍵碼排列如下:

3,  5,  6,  8,  9,  12,  17,  23,  30,  35,  39,  42

在表中查找關鍵碼為9的資料元素:

#include<iostream>
using namespace std;

#define MAX 12

typedef int key_type;

typedef struct element
{
	key_type key;   //關鍵字 
}elem;


int binary_search(elem e[], key_type key, int n)
{
	int low = 0, high = n - 1;
	int mid;
	
	while(low <= high)
	{
		mid = (low + high)/2;
		
		if(e[mid].key == key)
			return mid;
		else if(key < e[mid].key)
			high = mid - 1;
		     else
			low = mid + 1;
	}
	
	return -1; //沒找到 	
}

 
 int main(int argc, char** argv)
 {
 	elem linelist[MAX] = {3,5,6,8,9,12,17,23,30,35,39,42};
 	int n = 12;
 	int i = 0;
 	key_type key = 9;
 	printf("線性表中的元素為: \n");
 	
 	while(i < n)
 	{
		printf("%d\n",linelist[i].key);
		i++; 
	}	
	
	printf("\n關鍵字[%d]線上性表中的位置下标為[%d]\n", key, binary_search(linelist, key, n));
	
	getchar();
	system("pause");
 }
           

折半查找算法的平均查找長度為O(logn),與順序查找方法相比,折半查找算法的效率高。速度比順序查找快。 但折半查找隻能使用于有序表,需要對n個元素預先進行排序(僅限于順序存儲結構,對于線性連結清單無法進行折半查找)。  

3.分塊查找(索引查找)

分塊查找又稱索引順序查找,是對順序查找的一種改進。分塊查找要求将查找表分成 若幹個子表,并對子表建立索引表,查找表的每一個子表由索引表中的索引項确定。索引項包括兩個字段:關鍵碼字段(存放對應子表中的最大關鍵碼值) ;指針字段(存放指向對 應子表的指針) ,并且要求索引項按關鍵碼字段有序。查找時,先用給定值key 在索引表中 檢測索引項,以确定所要進行的查找在查找表中的查找分塊(由于索引項按關鍵碼字段有序,可用順序查找或折半查找) ,然後,再對該分塊進行順序查找。

如關鍵碼集合為:

                           (8, 20, 13, 17, 40, 42, 45, 32, 49, 58, 50, 52, 67, 79, 78, 80)

按關鍵碼值20,45,58, 80分為四塊建立索引表。

分塊查找的函數分為如下兩步: a)首先确定待查找的結點屬于哪一塊,即查找所在的塊; b)然後,在塊内查找要查的結點。

設表共n個結點,分b塊,s=n/b

(分塊查找索引表)平均查找長度=Log2(n/s+1)+s/2

(順序查找索引表)平均查找長度=(S2+2S+n)/(2S)

#include<iostream>
using namespace std;

#define MAX 16

typedef int key_type;

struct elem
{
	key_type key; //關鍵字 
};

//索引結構 
struct index         
{
	key_type key; //索引值 
	long low;     //起始位置 
	long high;    //終止位置 
};

int index_search(elem e[], key_type key, int n, index idx[], int idx_length)
{
	int low = 0;
	int high = idx_length - 1;
	int mid;
	
	//采用折半查找在索引表裡找到關鍵字所在的塊
	while(low <= high)
	{
		mid = (low + high)/2;
		if(key < idx[mid].key)
			high = mid - 1;
		else if(key > idx[mid].key)
			low = mid + 1;
		     else
			break;
	} 
	
	//采用順序查找的方法從塊中查找關鍵值
	int i = idx[mid].low;
	
	while(i <= idx[mid].high && e[i].key != key)
	{
		i++;
	} 
	
	if(i > idx[mid].high)
		return -1;
	else
		return i;
}


int main(int argc, char** argv)
{
	elem linelist[MAX] = {
		8, 20, 13, 17,
		40, 42, 45, 32,
		49, 58, 50, 52,
		67, 79, 78, 80
	};
	
	int n = sizeof(linelist) / sizeof(elem);
	key_type key = 50;
	
	//建立索引表
	index index_table[4] = {{20,0,3}, {45,4,7}, {58,8,11}, {80,12,15}}; 
	int idx_length = sizeof(index_table) / sizeof(index);
	
	printf("線性表中的元素為:\n");

	int i = 0;
	
	while(i < n) 
	{
		printf("%d\n",linelist[i].key);
		i++;
	}
	
	printf("\n關鍵字[%d]線上性表中的位置下标為[%d]", key, index_search(linelist, key, n, index_table, idx_length));
	
	getchar();
	system("pause");
}