順序查找

針對無序序列的一種最簡單的查找方式。

算法思想：

從表中第一個記錄開始，逐個與給定值進行比較，若某個記錄的關鍵字和給定值相等，則查找成功；反之，若直到最后一個記錄，其關鍵字和給定值都不相等，則表明表中沒有所查記錄，查找失敗。

由于我們不清楚這個數據判斷究竟需要多少次。但是我們知道，這種數據查找最少需要1次，最多需要n次，平均查找長度為(1+n)/2。順序查找算法的時間復雜度為O(n)。

---

二分/折半查找（有序表）

算法思想：

先確定待查記錄所在的范圍，然后逐步縮小范圍，直到找到或者找不到記錄為止。

普通的數據查找算法復雜度是O(n)。下面我們來分析一下二分查找的復雜度。這種方法最小是1次，最多需要log(n+1)/log2即可。很明顯，這種數據查找的效率要比前面的查找方法高很多。

---

java實現代碼如下（二分查找 && 順序查找）：

public class Search {public static void main(String[] args) {int[] array = {3,5,7,9,1,2,0};System.out.println(find(array, 7, 9));}//順序查找public static int find(int[] array,int length,int value){if (null == array || 0 == length) {return -1;}for (int index = 0; index < array.length; index++) {if (array[index] == value) {return index;}}return -1;}//二分查找public static int binarySort(int[] array,int length,int value){if (null == array || 0 == length) {return -1;}int start = 0;int end = length - 1;while(start <= end){int middle = (end + start) / 2;//這個地方還有問題if (array[middle] == value) {return middle;}else if (array[middle] < value) {start = middle + 1;}else{end = middle - 1;} }return -1;}}

---

排序二叉樹（B樹）

順序查找和二分查找都是建立在連續內存基礎之上的，如果是指針類型的數據就要引入排序二叉樹了。

排序二叉樹定義：

1、非葉子結點至少一邊的分支非空；
2、葉子節點左右分支都為空；
3、每一個節點記錄一個數據，同時左分支的數據都小于右分支的數據。
4、排序二叉樹中序遍歷得到的必定是一個有序序列。

排序二叉樹查找過程：

1、若查找樹為空，查找失敗；
2、若查找樹非空，將給定值和查找樹的根節點比較：
若相等，查找成功，結束查找過程；
若給定值小于根節點，查找將在根節點的左子樹上繼續進行，轉至1；
若給定值大于根節點，查找將在根節點的右子樹繼續進行，轉至1；

時間復雜度：平均O(logn)，最壞O(n)

排序二叉樹的插入：

新插入的節點一定是一個新添加的葉子節點，并且是查找不成功時查找路徑上訪問的最后一個節點的左孩子或右孩子節點。

排序二叉樹的節點刪除：

假設在排序二叉樹上需要被刪除的節點為p，且p為f的左孩子，下面分三種情況討論：

1、若p節點為葉子節點，即pl和pr均為空樹，由于刪去葉子節點不破壞整棵樹的結構，則只需修改其雙親結點的指針即可；
2、若p節點只有左子樹pl或者只有右子樹pr，此時只要令pl和pr直接成為其雙親結點f的左子樹即可；
3、若p節點的左子樹和右子樹均不空。

---

C實現排序二叉樹：

/*************************************************************************排序二叉樹，實現了以下操作：插入結點、構造二叉樹、刪除結點、查找、查找最大值、查找最小值、查找指定結點的前驅和后繼。上述所有操作時間復雜度均為o(h),其中h是樹的高度 *************************************************************************/#include<stdio.h> #include<stdlib.h>//二叉查找樹結點描述 typedef int KeyType; typedef struct Node {KeyType key; //關鍵字struct Node * left; //左孩子指針struct Node * right; //右孩子指針struct Node * parent; //指向父節點指針 }Node,*PNode;//往二叉查找樹中插入結點 //插入的話，可能要改變根結點的地址，所以傳的是二級指針 void inseart(PNode * root,KeyType key) {//初始化插入結點PNode p=(PNode)malloc(sizeof(Node));p->key=key;p->left=p->right=p->parent=NULL;//空樹時，直接作為根結點if((*root)==NULL){*root=p;return;}//插入到當前結點（*root）的左孩子if((*root)->left == NULL && (*root)->key > key){p->parent=(*root);(*root)->left=p;return;}//插入到當前結點（*root）的右孩子if((*root)->right == NULL && (*root)->key < key){p->parent=(*root);(*root)->right=p;return;}if((*root)->key > key)inseart(&(*root)->left,key);else if((*root)->key < key)inseart(&(*root)->right,key);elsereturn; }//查找元素,找到返回關鍵字的結點指針，沒找到返回NULL PNode search(PNode root,KeyType key) {if(root == NULL)return NULL;if(key > root->key) //查找右子樹return search(root->right,key);else if(key < root->key) //查找左子樹return search(root->left,key);elsereturn root; }//查找最小關鍵字,空樹時返回NULL PNode searchMin(PNode root) {if(root == NULL)return NULL;if(root->left == NULL)return root;else //一直往左孩子找，直到沒有左孩子的結點return searchMin(root->left); }//查找最大關鍵字,空樹時返回NULL PNode searchMax(PNode root) {if(root == NULL)return NULL;if(root->right == NULL)return root;else //一直往右孩子找，直到沒有右孩子的結點return searchMax(root->right); }//查找某個結點的前驅 PNode searchPredecessor(PNode p) {//空樹if(p==NULL)return p;//有左子樹、左子樹中最大的那個if(p->left)return searchMax(p->left);//無左子樹,查找某個結點的右子樹遍歷完了else{if(p->parent == NULL)return NULL;//向上尋找前驅while(p){if(p->parent->right == p)break;p=p->parent;}return p->parent;} }//查找某個結點的后繼 PNode searchSuccessor(PNode p) {//空樹if(p==NULL)return p;//有右子樹、右子樹中最小的那個if(p->right)return searchMin(p->right);//無右子樹,查找某個結點的左子樹遍歷完了else{if(p->parent == NULL)return NULL;//向上尋找后繼while(p){if(p->parent->left == p)break;p=p->parent;}return p->parent;} }//根據關鍵字刪除某個結點,刪除成功返回1,否則返回0 //如果把根結點刪掉，那么要改變根結點的地址，所以傳二級指針 int deleteNode(PNode* root,KeyType key) {PNode q;//查找到要刪除的結點PNode p=search(*root,key);KeyType temp; //暫存后繼結點的值//沒查到此關鍵字if(!p)return 0;//1.被刪結點是葉子結點，直接刪除if(p->left == NULL && p->right == NULL){//只有一個元素，刪完之后變成一顆空樹if(p->parent == NULL){free(p);(*root)=NULL;}else{//刪除的結點是父節點的左孩子if(p->parent->left == p)p->parent->left=NULL;else //刪除的結點是父節點的右孩子p->parent->right=NULL;free(p);}}//2.被刪結點只有左子樹else if(p->left && !(p->right)){p->left->parent=p->parent;//如果刪除是父結點，要改變父節點指針if(p->parent == NULL)*root=p->left;//刪除的結點是父節點的左孩子else if(p->parent->left == p)p->parent->left=p->left;else //刪除的結點是父節點的右孩子p->parent->right=p->left;free(p);}//3.被刪結點只有右孩子else if(p->right && !(p->left)){p->right->parent=p->parent;//如果刪除是父結點，要改變父節點指針if(p->parent == NULL)*root=p->right;//刪除的結點是父節點的左孩子else if(p->parent->left == p)p->parent->left=p->right;else //刪除的結點是父節點的右孩子p->parent->right=p->right;free(p);}//4.被刪除的結點既有左孩子，又有右孩子//該結點的后繼結點肯定無左子樹(參考上面查找后繼結點函數)//刪掉后繼結點,后繼結點的值代替該結點else{//找到要刪除結點的后繼q=searchSuccessor(p);temp=q->key;//刪除后繼結點deleteNode(root,q->key);p->key=temp;}return 1; }//創建一棵二叉查找樹 void create(PNode* root,KeyType *keyArray,int length) {int i;//逐個結點插入二叉樹中for(i=0;i<length;i++)inseart(root,keyArray[i]); }int main(void) {int i;PNode root=NULL;KeyType nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9};create(&root,nodeArray,11);for(i=0;i<2;i++)deleteNode(&root,nodeArray[i]);printf("%d\n",searchPredecessor(root)->key);printf("%d\n",searchSuccessor(root)->key);printf("%d\n",searchMin(root)->key);printf("%d\n",searchMax(root)->key);printf("%d\n",search(root,13)->key);return 0; }

總結

以上是生活随笔為你收集整理的【大话数据结构算法】查找算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。