資料結構和算法：查找算法

10_查找算法

标簽（空格分隔）： 資料結構和算法

文章目錄

• 10_查找算法
• • 10.1 靜态查找和動态查找
  • 10.2 查找結構
  • 10.3 順序查找
  • 10.4 插值查找
  • 10.5 斐波那契（黃金比例）查找
  • 10.6 線性索引查找
  • • 10.6.1 稠密索引
    • 10.6.2 分塊索引
    • 10.6.3 反向索引
  • 10.7 二叉排序樹
  • • 10.7.1 二叉排序樹的查找操作
    • 10.7.1 二叉排序樹的插入操作
    • 10.7.3 二叉排序樹的删除操作
  • 10.8 平衡二叉排序樹
  • • 10.8.1 平衡二叉排序樹的實作原理
  • 10.9 多路查找樹（Multi-way search tree)
  • • 10.9.1 2-3樹定義
    • 10.9.2 2-3樹的插入原理
    • 10.9.3 2-3樹的删除原理
    • 10.9.4 2-3-4樹
    • 10.9.5 B樹
  • 10.10 散清單（哈希表）查找
  • • 10.10.1 散清單的查找步驟
  • 10.11 散列函數的構造方法
  • • 10.11.1 數字分析法
    • 10.11.2 平方取中法
    • 10.11.3 折疊法
    • 10.11.4 除留餘數法
    • 10.11.5 随機數法
    • 10.11.6 視不同的情況采用不同的散列函數
  • 10.12 處理散列沖突的方法
  • • 10.12.1 開放定址法
    • 10.12.2 再散列函數法
    • 10.12.3 鍊位址法
    • 10.12.4 公共溢出區法
  • 10.13 散清單查找的代碼實作

10.1 靜态查找和動态查找

• 靜态查找
  • 資料集合穩定，不需要添加、删除元素的查找操作。
• 動态查找
  • 資料集合在查找的過程中需要同時添加或删除元素的查找操作。

10.2 查找結構

• 對于靜态查找來說，我們不妨可以用線性表結構組織資料，這樣可以使用順序查找算法，如果我們再對關鍵字進行排序，則可以使用折半查找算法或斐波那契查找算法來提高查找的效率。
• 對于動态查找來說，我們則可以考慮使用二叉排序樹的查找技術，另外我們還可以使用散清單結構來解決一些查找問題。

10.3 順序查找

• 順序查找由叫線性查找，是最基本的查找技術，它的查找過程是：從第一個（或者最後一個）記錄開始，逐個進行記錄的關鍵字和給定值進行比較，若某個記錄的關鍵字和給定值相等，則查找成功。如果查找了所有記錄仍然找不到與給定值相等的關鍵字，則查找不成功。

// 順序查找。a為要查找的數組，n為要查找的數組的長度，key為要查找的關鍵字
int Sq_Search(int *a, int n, int key)
{
	int i;
	for( i=1; i <= n; i++ )
	{
		if( a[i] == key )
		{
			return i;
		}
	}
	return 0;
}

// 順序查找優化方案，a為要查找的數組，n為要查找的數組的長度，key為要查找的關鍵字
int Sq_Search(int *a, int n, int key)
{
	int i = n;
	a[0] = key;
	while( a[i] != key )
	{
		i--;
	}

	return i;
}
           

10.4 插值查找

// 插值查找

#include <stdio.h>

int bin_search(int str[], int n, int key)
{
	int low, high, mid;

	low = 0;
	high = n-1;

	while( low <= high )
	{
		mid = low + (key - a[low]/a[high] - a[low]) * (high-low);  // 插值查找的唯一不同點

		if( str[mid] == key )
		{
			return mid;
		}

		if( str[mid] < key )
		{
			low = mid + 1;
		}

		if( str[mid] > key )
		{
			high = mid -1;
		}
	}

	return -1;
}

int main()
{

}
           

• 時間複雜度：O(log2n)

10.5 斐波那契（黃金比例）查找

10.6 線性索引查找

10.6.1 稠密索引

下标	關鍵碼	指針
5
1	12
2	26
3	36
4	55
5	88

10.6.2 分塊索引

索引表	25	58	88	各塊内的最大關鍵字
各塊内的起始位址字

清單	18	14	12	25	8	28	32	45	36	58	60	88	71
1	2	3	4	5	6	7	8	9	10	11	12

10.6.3 反向索引

10.7 二叉排序樹

• 二叉排序樹（Binary Sort Tree）
  • 又稱為二叉查找樹，它或者是一棵空樹，或者是具有下列性質的二叉樹：
    • 若它的左子樹不為空，則左子樹上所有結點的值均小于它的根結構的值；
    • 若它的右子樹不為空，則右子樹上所有結點的值均大于它的根結構的值；
    • 它的左、右子樹也分别為二叉排序樹（遞歸）。

10.7.1 二叉排序樹的查找操作

// 二叉樹的二叉連結清單結點結構定義
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 遞歸查找二叉排序樹 T 中是否存在 key
// 指針 f 指向 T 的雙親，其初始值調用值為 NULL
// 若查找成功，則指針 p 指向該資料元素結點，并傳回 TRUE
// 否則指針 p 指向查找路徑上通路的最後一個結點，并傳回FALSE
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
	if( !T )  // 查找不成功
	{
		*p = f;
		return FALSE;
	}
	else if( key == T->data )  // 查找成功
	{
		*p = T;
		return TRUE;
	}
	else if( key < T->data )
	{
		return SearchBST( T->lchild, key, T, p );   // 在左子樹繼續查找
	}
	else
	{
		return SearchBST( T->rchild, key, T, p );   // 在右子樹繼續查找
	}
}
           

10.7.1 二叉排序樹的插入操作

// 當二叉排序樹 T 中不存在關鍵字等于 key 的資料元素時，
// 插入 key 并傳回 TRUE, 否則傳回 FALSE
Status InsertBST(BiTree *T, int key)
{
	BiTree p, s;
	if( !SearchBST(*T, key, NULL, &p) )
	{
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = key;
		s->lchild = s->rchild = NULL;

		if( !p )
		{
			*T = s;   // 插入 s 為新的根結點
		}	
		else if( key < p->data )
		{
			p->lchild = s;   // 插入 s 為左孩子
		}
		else
		{
			p->rchild = s;   // 插入 s 為右孩子
		}	      
		return TRUE;                                                                                                                                                                                                                                                                                   
	}
	else
	{
		return FALSE;   // 樹中已有關鍵字相同的結點，不再插入
	}
}
           

10.7.3 二叉排序樹的删除操作

Status DeleteBST(BiTree *T, int key)
{
	if( !*T )
	{
		return FALSE;    // 該元素為空，非空為真，找不到這個元素
	}
	else
	{
		if( key == (*T)->data )
		{
			return Delete(T);
		}
		else if( key < (*T)->data )
		{
			return DeleteBST( &(*T)->lchild, key );
		}
		else 
		{
			return DeleteBST( &(*T)->rchild, key );
		}
	}
}

Status Delete(BiTree *p)
{
	BiTree q, s;

	if( (*p)->rchild == NULL )
	{
		q = *p;
		*p = (*p)->lchild;
		free(q);
	}
	else if( (*p)->lchild == NULL )
	{
		q = *p;
		*p = (*p)->rchild;
		free(q);
	}
	else
	{
		q = *p;
		s = (*p)->lchild;
		while( s->rchild )
		{
			q = s;
			s = s->rchild;
		}

		(*p)->data = s->data;

		if( q != *p )   // q 沒有右子樹
		{
			q->rchild = s->lchild;
		}
		else
		{
			q->lchild = s->lchild;
		}

		free(s);
	}

	return TRUE;
}
           

10.8 平衡二叉排序樹

• 我們将二叉樹上的結點上的左子樹的深度的值減去右子樹的深度的值稱為平衡銀子BF（Balance Factor)，平衡二叉排序樹就是一棵樹上所有結點的平衡因子的絕對值小于等于1的樹。
  • 要麼它是一棵空樹，要麼它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。
  • 左子樹和右子樹的深度之差稱為平衡因子。

10.8.1 平衡二叉排序樹的實作原理

#define LH 1
#define EH 0
#define RH -1

typedef struct BiTNode 
{
	int data;
	int bf;   // balance factor
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void R_Rotate(BiTree *p)
{
	BiTree L;
	L = (*p)->lchild;
	(*p)->lchild = L->rchild;
	L->rchild = (*p);
	*p = L;
}

void LeftBalance(BiTree *T)
{
	BiTree L, Lr;
	L = (*T)->lchild;

	switch( L->bf )
	{
		case LH:
			(*T)->bf = L->bf = EH;
			R_Rotate(T);
			break;
		case RH:
			Lr = L->rchild;
			switch( Lr->bf )
			{
				case LH:
					(*T)->bf = RH;
					L->bf = EH;
					break;
				case EH:
					(*T)->bf = L->bf = EH;
					break;
				case RH:
					(*T)->bf = EH;
					L->bf = LH;
					break;
			}
			Lr->bf = EH;
			L_Rotate( &(*T)->lchild );
			R_Rotate(T);
	}
}

int InsertAVL(BiTree *T, int e, int *taller)
{
	if( !*T )
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = e;
		(*T)->lchild = (*T)->rchild = NULL;
		(*T)->bf = EH;
		*taller = TRUE;
	}
	else
	{
		if( e == (*T)->data )
		{
			*taller = FALSE;
			return FALSE;
		}
		if( e < (*T)->data )
		{
			if( !InsertAVL(&(*T)->lchild, e, taller) )
			{
				return FALSE;
			}
			if( *taller )
			{
				switch( (*T)->bf )
				{
					case LH:
						LeftBalance(T);
						*taller = FALSE;
						break;
					case EH:
						(*T)->bf = LH;
						*taller = TRUE;
						break;
					case RH:
						(*T)->bf = EH;
						*taller = FALSE;
						break;
				}
			}
		}
		else
		{
			if( !InsertAVL(&(*T)->rchild, e, taller) )
			{
				return FALSE;
			}
			if( *taller )
			{
				switch( (*T)->bf )
				{
					case LH:
						(*T)->bf = EH;
						*taller = FALSE;
						break;
					case EH:
						(*T)->bf = RH;
						*taller = TRUE;
						break;
					case RH:
						RightBalance(T);
						*taller = FALSE;
						break;
				}				
			}
		}
	}
}
           

10.9 多路查找樹（Multi-way search tree)

10.9.1 2-3樹定義

• 多路查找樹中的每一個結點都具有兩個孩子或者三個孩子，我們稱之為2-3樹。
• 一個結點擁有兩個孩子和一個元素我們稱之為2結點，它跟二叉排序樹類似，左子樹包含的元素小于結點的元素，右子樹包含的元素大于結點的元素。不過與二叉排序樹不同的是，這個2結點要麼沒有孩子，要有就應該有兩個孩子，不能隻有一個孩子。
• 2-3樹所有葉子都在同一層次。

10.9.2 2-3樹的插入原理

10.9.3 2-3樹的删除原理

10.9.4 2-3-4樹

10.9.5 B樹

• B樹是一種平衡的多路查找樹，2-3樹和2-3-4樹都是B樹的特例。
• 我們把結點最大的孩子樹數目稱為B樹的階（order），是以，2-3樹是3階B樹，2-3-4樹是4階B樹。
• 一個m階的B樹具有如下屬性：
  • 如果根結點不是葉結點，則其至少有兩棵子樹
  • 每一個非根的分支結點都有k-1個元素（關鍵字）和k個孩子，其中k滿足：[m/2] <= k <= m
  • 所有葉子結點都位于同一層次
  • 每一個分支結點包含下列資訊資料：
    • n, A0, K1, A1, K2, A2, K3, A3…
    • 其中k為關鍵字，且Ki < ki+1
    • Ai為指向子樹根結點的指針

10.10 散清單（哈希表）查找

• 我們要在a[]中查找key關鍵字的記錄：
  • 順序表查找：挨個查找
  • 有序表查找：二分法查找
  • 散清單查找：？
• 散列技術是在記錄的存儲位置和它的關鍵字之間建立一個确定的對應關系 f，使得每個關鍵字 key 對應一個存儲位置 f(key)。
• 我們把這種對應關系 f 稱為散列函數，又稱為哈希(hash)函數。采用散列技術将記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間稱為散清單或哈希表（Hash Table)。

10.10.1 散清單的查找步驟

• 當存儲記錄時，通過散列函數計算出記錄的散列位址
• 當查找記錄時，我們通過同樣的是散列函數計算記錄的散列位址，并按此散列位址通路該記錄。
• 我們可以取關鍵字的某個線性函數值為散列位址，即：f(key) = a * key + b

10.11 散列函數的構造方法

10.11.1 數字分析法

• 數字分析法通常适合處理關鍵字位數比較大的情況，例如我們現在要存儲某家公司員工登記表，如果用手機号作為關鍵字，那麼我們發現抽取後四位數字作為散列位址是不錯的選擇。

10.11.2 平方取中法

• 平方取中法是将關鍵字平方之後取中間若幹位數字作為散列位址。
• eg: 1234^2 = 15|227|56

10.11.3 折疊法

• 折疊法是将關鍵字從左到右分割成位數相等的幾部分，然後将這幾部分疊加求和，并按散清單表長取後幾位作為散列位址。

10.11.4 除留餘數法

• 此方法為最常用的構造散列函數方法，計算公式為：
• f(key) = key mod p(p<=m)
• 事實上，這個方法不僅可以對關鍵字直接取模，也可通過折疊，平方取中後再取模。
• 例如下表，我們對有12個記錄的關鍵字構造散清單時，就可以用 f(key) = key mod 12 的方法。

下标	1	2	3	4	5	6	7	8	9	10	11
關鍵字	12	25	38	15	16	29	78	67	56	21	22	47

10.11.5 随機數法

• 選擇一個随機數，取關鍵字的随機函數值為它的散列位址。
• 即: f(key) = random(key)。
• 這裡的random是随機函數，當關鍵字的長度不等時，采用這個方法構造散列函數是比較合适的。

10.11.6 視不同的情況采用不同的散列函數

• 現實中，我們應該視不同的情況采用不同的散列函數
• 參考方向：
  • 計算散列位址所需的時間
  • 關鍵字的長度
  • 散清單的大小
  • 關鍵字的分布情況
  • 記錄查找的頻率

10.12 處理散列沖突的方法

10.12.1 開放定址法

• 所謂的開放定址法就是一旦發生了沖突，就去尋找下一個空的散列位址，隻要散清單足夠大， 空的散列位址總能找到，并将記錄存入。
• 它的公式是：fi(key) = (f(key)+di) MOD m (di=1,2,…,m-1)
• 例：假設關鍵字集合為{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，使用除留餘數法（m=12)求散清單。

下标	1	2	3	4	5	6	7	8	9	10	11
關鍵字	12	25	37	15	16	29	48	67	56	34	22	47

• 可以修改 di 的取值方式，例如使用平方運算來盡量解決堆積問題：
• fi(key) = (f(key)+di0 MOD m(di=12,-12,22,-22,…,q,-q2,q<=m/2)
• 還有一種方法是，在沖突時，對于位移量 di 采用随機函數計算得到，我們稱之為随機探測法：
• fi(key) = (f(key)+di) MOD m (di 是由一個随機函數獲得的數列）

10.12.2 再散列函數法

• fi(key) = RHi(key)(i=1,2,3,…,k)

10.12.3 鍊位址法

10.12.4 公共溢出區法

10.13 散清單查找的代碼實作

#define HASHSIZE 12
#define NULLKEY -32768

typedef struct 
{
	int *elem;  // 資料元素的基址，動态配置設定數組
	int count;  // 目前資料元素的個數
} HashTable;

void InitHashTable(HashTable *H)
{
	H->count = HASHSIZE;
	H->elem = (int *)malloc(HASHSIZE * sizeof(int));
	if( !H->elem )
	{
		return -1;
	}
	for( i=0; i < HASHSIZE; i++ )
	{
		H->elem[i] = NULLKEY;
	}
	return 0;
}

// 使用除留餘數法
int Hash(int key)
{
	return key % HASHSIZE;
}

// 插入關鍵字到散清單
void InsertHash(HashTable *H, int key)
{
	int addr;

	addr = Hash(key);
	while( H->elem[addr] != NULLKEY )  //如果不為空，則沖突出現
	{
		addr = (addr + 1) % HASHSIZE;
	}

	H->elem[addr] = key;
}

// 散清單查找關鍵字
int SearchHash(HashTable H, int key, int *addr)
{
	*addr = Hash(key);

	while( H.elem[*addr] != key )
	{
		*addr = (*addr + 1) % HASHSIZE;
		if( H.elem[*addr] == NULLKEY || *addr == Hash(key) )
		{
			return -1;
		}
	}

	return 0;
}