順序查找垛吗、二分查找残腌、二叉搜索樹、Hash表
1. 順序查找
設(shè)想有一個1M的數(shù)據(jù)鸠删，我們?nèi)绾卧诶锩嬲业轿覀兿胍哪莻€數(shù)據(jù)抱完。此時數(shù)據(jù)本身沒有特征，所以我們需要的那個數(shù)據(jù)可能出現(xiàn)在數(shù)組的各個位置刃泡，可能在數(shù)據(jù)的開頭位置巧娱，也可能在數(shù)據(jù)的結(jié)束位置。這種性質(zhì)要求我們必須對數(shù)據(jù)進(jìn)行遍歷之后才能獲取到對應(yīng)的數(shù)據(jù)烘贴。
int find(int array[], int len, int val)
{
if(array == NULL && length == 0) return -1;
for(int i=0;i<len;i++){
if(val == array[i])
return i;
}
return -1;
}
分析：由于我們不清楚這個數(shù)據(jù)判斷究竟需要多少次禁添。但是，我們知道桨踪，這樣一個數(shù)據(jù)查找最少需要1次老翘，那么最多需要n次，平均下來可以看成是（1+n）/2锻离，差不多是n的一半铺峭。我們把這種比較次數(shù)和n成正比的算法復(fù)雜度記為o（n）。
2. 二分查找
如果數(shù)據(jù)排列地非常整齊汽纠，那結(jié)果會是什么樣的呢卫键？就像在生活中，如果平時不注意收拾整齊疏虫，那么找東西的時候非常麻煩永罚，效率很低啤呼；但是一旦東西放的位置固定下來卧秘，所有東西都?xì)w類放好，那么結(jié)果就不一樣了官扣，我們就會形成思維定勢翅敌，這樣查找東西的效率就會非常高。那么惕蹄，對一個有序的數(shù)組蚯涮，我們應(yīng)該怎么查找呢？二分法就是最好的方法卖陵。
int BinaryFind(int array[], int len, int val)
{
if(array == NULL && length == 0) return -1;
int start = 0, end = len-1, middle=0;
while(start<=end){
middle = (start + end)/2;
if(val == array[middle]) return middle;
else if(val > array[middle]) start = middle+1;
else end = middle-1;
}
return -1;
}
分析：上面我們說到普通的數(shù)據(jù)查找算法復(fù)雜度是o（n）遭顶。那么我們可以用上面一樣的方法判斷一下算法復(fù)雜度。這種方法最少是1次泪蔫，那么最多需要多少次呢棒旗？我們發(fā)現(xiàn)最多需要log（n+1）/log（2）即可。
3. 二叉搜索樹
二叉搜索樹是二分查找的二叉樹實現(xiàn)撩荣，二叉搜索樹每個結(jié)點都有作為搜索依據(jù)的關(guān)鍵碼铣揉，饶深，所有結(jié)點的管家嗎互不相同；左子樹（若存在）上的所有結(jié)點的關(guān)鍵碼都小于根結(jié)點的關(guān)鍵碼逛拱；右子樹（若存在）上的所有結(jié)點的關(guān)鍵碼都大于根結(jié)點的關(guān)鍵碼敌厘；左子樹和右子樹也是二叉搜索樹。
typedef struct _NODE
{
int data;
struct _NODE* left;
struct _NODE* right;
}NODE;
const NODE* find_data(const NODE* pNode, int data){
if(NULL == pNode)
return NULL;
if(data == pNode->data)
return pNode;
else if(data < pNode->data)
return find_data(pNode->left, data);
else
return find_data(pNode->right, data);
}
4. Hash表
typedef struct _LINK_NODE
{
int data;
struct _LINK_NODE* next;
}LINK_NODE;
LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data)
{
int index = data % mod;
if(NULL == array[index])
return NULL;
LINK_NODE* pLinkNode = array[index];
while(pLinkNode){
if(data == pLinkNode->data)
return pLinkNode;
pLinkNode = pLinkNode->next;
}
return pLinkNode;
}
分析：hash表因為不需要排序朽合，只進(jìn)行簡單的歸類俱两，在數(shù)據(jù)查找的時候特別方便。查找時間的大小取決于mod的大小曹步。mod越小锋华，那么hash查找就越接近于普通查找；那么hash越大呢箭窜，那么hash一次查找成功的概率就大大增加毯焕。
