查找是在大量的信息中尋找一個特定的信息元素，在計算機應用中，查找是常用的基本運算，例如編譯程序中符號表的查找。本文簡單概括性的介紹了常見的七種查找算法，說是七種，其實二分查找、插值查找以及斐波那契查找都可以歸為一類——插值查找。插值查找和斐波那契查找是在二分查找的基礎上的優化查找算法。樹表查找和哈希查找會在后續的博文中進行詳細介紹。

查找定義：根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素（或記錄）。

1. 順序查找

說明：順序查找適合于存儲結構為順序存儲或鏈接存儲的線性表。

**基本思想：**順序查找也稱為線形查找，屬于無序查找算法。從數據結構線形表的一端開始，順序掃描，依次將掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等于k的結點，表示查找失敗。

復雜度分析：

查找成功時的平均查找長度為：（假設每個數據元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
　　當查找不成功時，需要n+1次比較，時間復雜度為O(n);

所以， 順序查找的時間復雜度為O(n)。

C++實現源碼：

//順序查找 int SequenceSearch(int a[], int value, int n) {int i;for(i=0; i<n; i++)if(a[i]==value)return i;return -1; }

2. 二分查找

https://www.bilibili.com/video/BV1i4411a78o/?spm_id_from=autoNext

說明：元素必須是有序的，如果是無序的則要先進行排序操作。

**基本思想：**也稱為是折半查找，屬于有序查找算法。**用給定值k先與中間結點的關鍵字比較，中間結點把線形表分成兩個子表，若相等則查找成功；**若不相等，再根據k與該中間結點關鍵字的比較結果確定下一步查找哪個子表，這樣遞歸進行，直到查找到或查找結束發現表中沒有這樣的結點。

復雜度分析：最壞情況下，關鍵詞比較次數為log2(n+1)，且期望時間復雜度為O(log2n)；

注：折半查找的前提條件是需要有序表順序存儲，對于靜態查找表，一次排序后不再變化，折半查找能得到不錯的效率。但對于需要頻繁執行插入或刪除操作的數據集來說，維護有序的排序會帶來不小的工作量，那就不建議使用。——《大話數據結構》

C++實現源碼：

//二分查找（折半查找），版本1 int BinarySearch1(int a[], int value, int n) {int low, high, mid;low = 0;high = n-1;while(low<=high){mid = (low+high)/2;if(a[mid]==value)return mid;if(a[mid]>value)high = mid-1;if(a[mid]<value)low = mid+1;}return -1; } //123456789101112131415161718 //二分查找，遞歸版本 int BinarySearch2(int a[], int value, int low, int high) {int mid = low+(high-low)/2;if(a[mid]==value)return mid;if(a[mid]>value)return BinarySearch2(a, value, low, mid-1);if(a[mid]<value)return BinarySearch2(a, value, mid+1, high); }

總結

通過比較折半查找的平均查找長度，同前面介紹的順序查找相對比，明顯折半查找的效率要高。但是折半查找算法只適用于有序表，同時僅限于查找表用順序存儲結構表示。

3、索引查找

#include <stdio.h> #include <stdlib.h> #include<bits/stdc++.h> using namespace std; struct index { //定義塊的結構int key;int start; } newIndex[3]; //定義結構體數組int cmp(const void *a,const void* b) {return (*(struct index*)a).key>(*(struct index*)b).key?1:-1; } int search(int key, int a[]) {int i, startValue;i = 0;while (i<3 && key>newIndex[i].key) { //確定在哪個塊中，遍歷每個塊，確定key在哪個塊中// 99 99>newIndex[0]=21// 99 99>newIndex[1]=27// 99 99<newIndex[2]=333 i=2i++;}if (i>=3) { //大于分得的塊數，則返回0return -1;}startValue = newIndex[i].start; //startValue等于塊范圍的起始值while (startValue <= startValue+5 && a[startValue]!=key) {startValue++;}if (startValue>startValue+5) { //如果大于塊范圍的結束值，則說明沒有要查找的數return -1;}return startValue; }int main() {int i, j=-1, k, key; // int a[] = {33,42,44,38,24,48, 22,12,13,8,9,20, 60,58,74,49,86,53};int a[]= {1 ,5, 4, 21, 19,22, 25, 23, 24, 27,31, 99, 333, 35, 29};//確認模塊的起始值和最大值for (i=0; i<3; i++) {newIndex[i].start = j+1; //確定每個塊范圍的起始值// newIndex[0]=0~4// newIndex[1]=5~9//new Index[2]=10~14j += 5;for (int k=newIndex[i].start; k<=j; k++) {if (newIndex[i].key<a[k]) {newIndex[i].key=a[k]; // 0 5 4 21 newIndex[0].key=21 // 22 25 23 24 27 newIndex[1].key=27// 31 99 333 newIndex[2].key=333 }}cout<<" newIndex[i].key:==" <<newIndex[i].key<<endl; //查看塊的索引}//對結構體按照 key 值進行排序qsort(newIndex,3, sizeof(newIndex[0]), cmp);// cmp 是一個給定一個排序規則 是從小到大 還是從大到小 //https://www.cnblogs.com/tsingke/p/5347672.html//四、對結構體一級排序 從小到大排序 /*struct In{double data;int other;}s[100]；int cmp( const void *a ,const void *b){return (*(struct In *)a)->data > (*(struct In *)b)->data ? 1 : -1;}qsort(s,100,sizeof(s[0]),cmp);*///輸入要查詢的數，并調用函數進行查找printf("請輸入您想要查找的數：\n");scanf("%d", &key);k = search(key, a);//輸出查找的結果if (k>=0) {printf("查找成功！您要找的數在數組中的位置是：%d\n",k+1);} else {printf("查找失敗！您要找的數不在數組中。\n");}return 0; }

4、動態查找

觀看視頻：

https://www.bilibili.com/video/BV1Ca4y1i7Mj 1

https://www.bilibili.com/video/av17499415/ 2

https://www.cnblogs.com/sench/p/7783331.html 3 博客（二叉樹的建立和操作）[c++類操作]

https://blog.csdn.net/yixianfeng41/article/details/52802855 4 博客（二叉樹的建立和操作）[普通c++操作]

注：動態查找表中做查找操作時，若查找成功可以對其進行刪除；如果查找失敗，即表中無該關鍵字，可以將該關鍵字插入到表中。

4.1、什么是二叉排序樹？

二叉排序樹要么是空

二叉樹

，要么具有如下特點：

• 二叉排序樹中，如果其根結點有左子樹，那么左子樹上所有結點的值都小于根結點的值；
• 二叉排序樹中，如果其根結點有右子樹，那么右子樹上所有結點的值都大于根結點的值；
• 二叉排序樹的左右子樹也要求都是二叉排序樹；

例如，

圖 1 就是一個二叉排序樹：

圖 1 二叉排序樹

4.2、使用二叉排序樹查找關鍵字 二叉排序樹是中序遍歷

二叉排序樹中查找某關鍵字時，查找過程類似于次優二叉樹，在二叉排序樹不為空樹的前提下，首先將被查找值同樹的根結點進行比較，會有 3 種不同的結果：

• 如果相等，查找成功；
• 如果比較結果為根結點的關鍵字值較大，則說明該關鍵字可能存在其左子樹中；
• 如果比較結果為根結點的關鍵字值較小，則說明該關鍵字可能存在其右子樹中；

實現函數為：（運用遞歸的方法）

BiTree SearchBST(BiTree T,KeyType key){//如果遞歸過程中 T 為空，則查找結果，返回NULL；或者查找成功，返回指向該關鍵字的指針if (!T || key==T->data) {return T;}else if(key<T->data){//遞歸遍歷其左孩子return SearchBST(T->lchild, key);}else{//遞歸遍歷其右孩子return SearchBST(T->rchild, key);} }

4.3、二叉排序樹中插入關鍵字

二叉排序樹本身是動態查找表的一種表示形式，有時會在查找過程中插入或者刪除表中元素，當因為查找失敗而需要插入數據元素時，該數據元素的插入位置一定位于二叉排序樹的葉子結點，并且一定是查找失敗時訪問的最后一個結點的左孩子或者右孩子。

例如，在圖 1 的二叉排序樹中做查找關鍵字 1 的操作，當查找到關鍵字 3 所在的葉子結點時，判斷出表中沒有該關鍵字，此時關鍵字 1 的插入位置為關鍵字 3 的左孩子。

所以，二叉排序樹表示動態查找表做插入操作，只需要稍微更改一下上面的代碼就可以實現，具體實現代碼為：

BOOL SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){//如果 T 指針為空，說明查找失敗，令 p 指針指向查找過程中最后一個葉子結點，并返回查找失敗的信息if (!T){*p=f;return false;}//如果相等，令 p 指針指向該關鍵字，并返回查找成功信息else if(key==T->data){*p=T;return true;}//如果 key 值比 T 根結點的值小，則查找其左子樹；反之，查找其右子樹else if(key<T->data){return SearchBST(T->lchild,key,T,p);}else{return SearchBST(T->rchild,key,T,p);} } //插入函數 BOOL InsertBST(BiTree T,ElemType e){BiTree p=NULL;//如果查找不成功，需做插入操作if (!SearchBST(T, e,NULL,&p)) {//初始化插入結點BiTree s=(BiTree)malloc(sizeof(BiTree));s->data=e;s->lchild=s->rchild=NULL;//如果 p 為NULL，說明該二叉排序樹為空樹，此時插入的結點為整棵樹的根結點if (!p) {T=s;}//如果 p 不為 NULL，則 p 指向的為查找失敗的最后一個葉子結點，只需要通過比較 p 和 e 的值確定 s 到底是 p 的左孩子還是右孩子else if(e<p->data){p->lchild=s;}else{p->rchild=s;}return true;}//如果查找成功，不需要做插入操作，插入失敗return false; }

通過使用二叉排序樹對動態查找表做查找和插入的操作，同時在中序遍歷二叉排序樹時，可以得到有關所有關鍵字的一個有序的序列。

例如，假設原二叉排序樹為空樹，在對動態查找表 {3，5，7，2，1} 做查找以及插入操作時，可以構建出一個含有表中所有關鍵字的二叉排序樹，過程如圖 2 所示:

圖 2 二叉排序樹插入過程

通過不斷的查找和插入操作，最終構建的二叉排序樹如圖 2（5） 所示。當使用中序遍歷算法遍歷二叉排序樹時，得到的序列為：1 2 3 5 7 ，為有序序列。

一個無序序列可以通過構建一棵二叉排序樹，從而變成一個有序序列。

4.4、二叉排序樹中刪除關鍵字

在查找過程中，如果在使用二叉排序樹表示的動態查找表中刪除某個數據元素時，需要在成功刪除該結點的同時，依舊使這棵樹為二叉排序樹。

假設要刪除的為結點 p，則對于二叉排序樹來說，需要根據結點 p 所在不同的位置作不同的操作，有以下 3 種可能：

1、結點 p 為葉子結點，此時只需要刪除該結點，并修改其雙親結點的指針即可；
2、結點 p 只有左子樹或者只有右子樹，此時只需要將其左子樹或者右子樹直接變為結點 p 雙親結點的左子樹即可；
3、結點 p 左右子樹都有，此時有兩種處理方式：

1）令結點 p 的左子樹為其雙親結點的左子樹；結點 p 的右子樹為其自身直接前驅結點的右子樹，如圖 3 所示；

圖 3 二叉排序樹中刪除結點（1）

2）用結點 p 的直接前驅（或直接后繼）來代替結點 p，同時在二叉排序樹中對其直接前驅（或直接后繼）做刪除操作。如圖 4 為使用直接前驅代替結點 p：

圖 4 二叉排序樹中刪除結點（2）

圖 4 中，在對左圖進行中序遍歷時，得到的結點 p 的直接前驅結點為結點 s，所以直接用結點 s 覆蓋結點 p，由于結點 s 還有左孩子，根據第 2 條規則，直接將其變為雙親結點的右孩子。

4.5、二叉排序樹的實現：

一、

#include<bits/stdc++.h> using namespace std;class BSTNode {public:int key; //結點的值BSTNode* left; //結點的左孩子BSTNode* right; //結點的右孩子BSTNode* parent; //結點的雙親/*構造函數*/BSTNode():parent(NULL) {}BSTNode(int key, BSTNode* left, BSTNode* right, BSTNode* parent) :key(key), left(left), right(right), parent(parent) {} }; class BSTree {private:BSTNode* root; //根節點public:/*構造函數*/BSTree() :root(NULL) {};/*獲取根節點*/BSTNode* getRoot() {return root;}/*將鍵值key插入到二叉樹中*/void insert(int key);/*將結點插入到二叉樹中*/void insert(BSTNode*& root, BSTNode* node);/*先序遍歷*/void preOrder(BSTNode* root);/*中序遍歷*/void inOrder(BSTNode* root);/*后序遍歷*/void postOrder(BSTNode* root);/*查找二叉樹中鍵值為key的結點并返回*/BSTNode* search(BSTNode* node, int key);/*找出二叉樹中鍵值最小的結點并返回*/BSTNode* minimum(BSTNode* node);/*找出二叉樹中鍵值最大的結點并返回*/BSTNode* maximum(BSTNode* node);/*找到二叉樹結點node的后繼結點*/BSTNode* successor(BSTNode* node);/*找到二叉樹結點node的前驅結點*/BSTNode* predecessor(BSTNode* node);/*移除鍵值為key的結點*/BSTNode* remove(BSTNode*& root, int key);/*銷毀二叉排序樹*/void destroy(BSTNode* root); }; /* * 將結點插入到二叉樹中 * * 參數說明： * root 二叉樹的根結點 * node 要插入的結點 */ void BSTree::insert(BSTNode*& root, BSTNode* node) {BSTNode* y = NULL;BSTNode* x = root;/*找到要插入的位置*/while (x != NULL){y = x;if (node->key > x->key)x = x->right;else x = x->left;}/*插入結點*/node->parent = y;if (y == NULL)root = node;else if(y->key > node->key)y->left = node;else y->right = node; }void BSTree::insert(int key) {BSTNode* node = new BSTNode(key, NULL, NULL, NULL);insert(root, node); } /*先序遍歷*/ void BSTree::preOrder(BSTNode* root) {if (root != NULL) {cout << root->key;preOrder(root->left);preOrder(root->right);} } /*中序遍歷*/ void BSTree::inOrder(BSTNode* root) {if (root != NULL) {inOrder(root->left);cout << root->key;inOrder(root->right);} } /*后序遍歷*/ void BSTree::postOrder(BSTNode* root) {if (root != NULL) {postOrder(root->left);postOrder(root->right);cout << root->key;} } BSTNode* BSTree::search(BSTNode* node, int key) {if (node == NULL || node->key == key)return node;if (node->key < key)search(node->right, key);else search(node->left, key); } BSTNode* BSTree::minimum(BSTNode* node) {if (node->left == NULL)return node;minimum(node->left); } BSTNode* BSTree::maximum(BSTNode* node) {if (node->right == NULL)return node;maximum(node->right); } /*查找結點node的前驅節點*/ BSTNode* BSTree::predecessor(BSTNode* node) {/*（1）左子樹非空，返回左子樹最大值結點*/if (node->left != NULL)return maximum(node->left);/*（2）*/BSTNode* pnode = node->parent;while (pnode != NULL&&node == pnode->left) {node = pnode;pnode = pnode->parent;}return pnode; } /*查找node的后繼結點*/ BSTNode* BSTree::successor(BSTNode* node) {/*（1）右子樹非空，返回右子樹最小值結點*/if (node->right != NULL)return minimum(node->right);/*（2）*/BSTNode* pnode = node->parent;while (pnode != NULL&&node == pnode->right) {node = pnode;pnode = pnode->parent;}return pnode; } /*獲取要刪除的結點并返回*/ BSTNode* BSTree::remove(BSTNode*& root, int key) {BSTNode* node = search(root, key);printf("%d\n", node->key);if (node != NULL) {if (node->left == NULL && node->right == NULL) { //node為葉子結點if (node->parent == NULL) //要刪除的結點為根結點return node;else if (node->parent->left == node)//判斷要刪除點在雙親結點的左邊還是右邊node->parent->left = NULL;elsenode->parent->right = NULL;} else if (node->left == NULL) { //node左子樹為空if (node->parent == NULL) { //要刪除的結點為根結點this->root = node->right;node->right->parent = NULL;} else if (node->parent->left == node) //判斷要刪除點在雙親結點的左邊還是右邊node->parent->left = node->right;elsenode->parent->right = node->right;} else if (node->right == NULL) { //node右子樹為空if (node->parent == NULL) { //要刪除的結點為根結點this->root = node->left;node->left->parent = NULL;} else if (node->parent->left == node) //判斷要刪除點在雙親結點的左邊還是右邊node->parent->left = node->left;elsenode->parent->right = node->left;} else { //node左右子樹均不為空BSTNode* lnode = node->left; //lnode初始為node左子樹的根節點while (lnode->right) //找到node左子樹的最右結點賦值為lnodelnode = lnode->right;lnode->right = node->right; //將node的右子樹變成lnode的右子樹node->right->parent = lnode;if (node->parent == NULL) { //要刪除的結點為根結點this->root = node->right;if (node->right->left != NULL) {BSTNode* leftDownNode = minimum(node->right);leftDownNode->left = node->left;node->left->parent = leftDownNode;} else {node->right->left = node->left;node->left->parent = node->right;}} else if (node->parent->left == node) { //將node的左子樹替換node的位置node->parent->left = node->left;node->left->parent = node->parent;} else if (node->parent->right == node) {node->parent->right = node->left;node->left->parent = node->parent;}}}return node; } /*銷毀二叉樹*/ void BSTree::destroy(BSTNode* root) {if (root == NULL)return;destroy(root->left);destroy(root->right);delete root; } int main() {int a[] = { 1, 5, 4, 3, 2, 6 };BSTree* tree = new BSTree();for (int i = 0; i < 6; i++)tree->insert(a[i]);cout << "先序遍歷：";tree->preOrder(tree->getRoot());cout << endl;cout << "中序遍歷：";tree->inOrder(tree->getRoot());cout << endl;cout << "后序遍歷：";tree->postOrder(tree->getRoot());cout << endl;cout << "最小值：";BSTNode* minNode = tree->minimum(tree->getRoot());if(minNode != NULL)cout << minNode->key << endl;cout << "最大值：";BSTNode* maxNode = tree->maximum(tree->getRoot());if (maxNode != NULL)cout << maxNode->key << endl;BSTNode* node = tree->search(tree->getRoot(), 6);BSTNode* snode = tree->successor(node);if (snode != NULL)cout << snode->key << endl;BSTNode* pnode = tree->predecessor(node);if (pnode != NULL)cout << pnode->key << endl;BSTNode* root = tree->getRoot();BSTNode* dnode = tree->remove(root, 5);cout << "刪除" << dnode->key << "后先序遍歷：" << endl;if (dnode) delete dnode;tree->preOrder(tree->getRoot());cout << endl;cout << "銷毀二叉樹" << endl;tree->destroy(root);return 0; }

二、

#include<bits/stdc++.h> using namespace std;// 定義一個二叉排序樹結構： typedef int DataType; typedef struct BST_Node {DataType data;struct BST_Node *lchild, *rchild; }BST_T, *BST_P;//遞歸版查找 BST_P Search_BST(BST_P root, DataType key) {if (root == NULL)return NULL;if (key > root->data) //查找右子樹 return Search_BST(root->rchild, key);else if (key < root->data) //查找左子樹 return Search_BST(root->lchild, key);elsereturn root; } //插入代碼如下： void Insert_BST(BST_P *root, DataType data) {//初始化插入節點BST_P p = (BST_P)malloc(sizeof(struct BST_Node));if (!p) return;p->data = data;p->lchild = p->rchild = NULL;//空樹時，直接作為根節點if (*root == NULL){*root = p;return;}//是否存在，已存在則返回，不插入if (Search_BST(*root, data) != NULL) return; //進行插入，首先找到要插入的位置的父節點BST_P tnode = NULL, troot = *root;while (troot){ tnode = troot;troot = (data < troot->data) ? troot->lchild : troot->rchild;}if (data < tnode->data)tnode->lchild = p;elsetnode->rchild = p; } //建立二叉排序樹，用到Insert_BST方法 void CreateBST(BST_P *T, int a[], int n) {int i;for (i = 0; i < n; i++){Insert_BST(T, a[i]);} }// 查找最小關鍵字 BST_P SearchMin(BST_P root) {if (root == NULL)return NULL;if (root->lchild == NULL)return root;else //一直往左孩子找，直到沒有左孩子的結點 return SearchMin(root->lchild); } // 查找最大關鍵字 BST_P SearchMax(BST_P root) {if (root == NULL)return NULL;if (root->rchild == NULL)return root;else //一直往右孩子找，直到沒有右孩子的結點 return SearchMax(root->rchild); }//刪除節點代碼： void DeleteBSTNode(BST_P *root, DataType data) {BST_P p = *root, parent = NULL, s = NULL;if (!p) return;if (p->data == data) //找到要刪除的節點了{/* It's a leaf node */if (!p->rchild && !p->lchild) *root = NULL;// 只有一個左節點else if (!p->rchild&&p->lchild) *root = p->lchild;// 只有一個右節點else if (!p->lchild&&p->rchild) *root = p->rchild;//左右節點都不空else {s = p->rchild;/* the s without left child */if (!s->lchild)s->lchild = p->lchild;/* the s have left child */else {/* find the smallest node in the left subtree of s */while (s->lchild) {/* record the parent node of s */parent = s;s = s->lchild;}parent->lchild = s->rchild;s->lchild = p->lchild;s->rchild = p->rchild;}*root = s;}free(p);}else if (data > p->data) //向右找DeleteBSTNode(&(p->rchild), data);else if (data < p->data) //向左找DeleteBSTNode(&(p->lchild), data); }//先序遍歷 void PreOrderTraverse(BST_P T) {if (T){cout << T->data << " ";PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);} }//中序遍歷void MidOrderTraverse(BST_P T) {if (T){MidOrderTraverse(T->lchild);cout << T->data << " ";MidOrderTraverse(T->rchild);} } //后序遍歷void PostOrderTraverse(BST_P T) {if (T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout << T->data << " ";} } int main() {int arr[] = { 17,12,19,10,15,18,25,8,11,13,16,22}; BST_P root = NULL;//創建二叉排序樹CreateBST(&root, arr, 12);printf("\nCreate BST: ");printf("\npre order traverse: ");PreOrderTraverse(root);printf("\npost order traverse: ");PostOrderTraverse(root);cout << endl;//在二叉排序樹中查找節點12.BST_P result = Search_BST(root, 12);printf("\nSearch Data: ");cout << "查找結果：\n" << "指針：" << result << endl << "指針的值：" << result->data << endl;//在二叉排序樹中插入9Insert_BST(&root, 9);printf("\nInsert Data: ");printf("\npre order traverse: ");PreOrderTraverse(root);printf("\npost order traverse: ");PostOrderTraverse(root);cout << endl;//刪除二叉排序樹中的節點12DeleteBSTNode(&root, 12);printf("\nDelete Data: ");printf("\npre order traverse: ");PreOrderTraverse(root);printf("\npost order traverse: ");PostOrderTraverse(root);printf("\n");return 0; }

三、

#include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define ElemType int #define KeyType int /* 二叉排序樹的節點結構定義 */ typedef struct BiTNode {int data;struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;//二叉排序樹查找算法 int SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){//如果 T 指針為空，說明查找失敗，令 p 指針指向查找過程中最后一個葉子結點，并返回查找失敗的信息if (!T){*p=f;return FALSE;}//如果相等，令 p 指針指向該關鍵字，并返回查找成功信息else if(key==T->data){*p=T;return TRUE;}//如果 key 值比 T 根結點的值小，則查找其左子樹；反之，查找其右子樹else if(key<T->data){return SearchBST(T->lchild,key,T,p);}else{return SearchBST(T->rchild,key,T,p);} } int InsertBST(BiTree *T,ElemType e){BiTree p=NULL;//如果查找不成功，需做插入操作if (!SearchBST((*T), e,NULL,&p)) {//初始化插入結點BiTree s=(BiTree)malloc(sizeof(BiTree));s->data=e;s->lchild=s->rchild=NULL;//如果 p 為NULL，說明該二叉排序樹為空樹，此時插入的結點為整棵樹的根結點if (!p) {*T=s;}//如果 p 不為 NULL，則 p 指向的為查找失敗的最后一個葉子結點，只需要通過比較 p 和 e 的值確定 s 到底是 p 的左孩子還是右孩子else if(e < p->data){p->lchild=s;}else{p->rchild=s;}return TRUE;}//如果查找成功，不需要做插入操作，插入失敗return FALSE; } //刪除函數 int Delete(BiTree *p) {BiTree q, s;//情況 1，結點 p 本身為葉子結點，直接刪除即可if(!(*p)->lchild && !(*p)->rchild){*p = NULL;}else if(!(*p)->lchild){ //左子樹為空，只需用結點 p 的右子樹根結點代替結點 p 即可；q = *p;*p = (*p)->rchild;free(q);}else if(!(*p)->rchild){//右子樹為空，只需用結點 p 的左子樹根結點代替結點 p 即可；q = *p;*p = (*p)->lchild;//這里不是指針 *p 指向左子樹，而是將左子樹存儲的結點的地址賦值給指針變量 pfree(q);}else{//左右子樹均不為空，采用第 2 種方式q = *p;s = (*p)->lchild;//遍歷，找到結點 p 的直接前驅while(s->rchild){q = s;s = s->rchild;}//直接改變結點 p 的值(*p)->data = s->data;//判斷結點 p 的左子樹 s 是否有右子樹，分為兩種情況討論if( q != *p ){q->rchild = s->lchild;//若有，則在刪除直接前驅結點的同時，令前驅的左孩子結點改為 q 指向結點的孩子結點}else{q->lchild = s->lchild;//否則，直接將左子樹上移即可}free(s);}return TRUE; } int DeleteBST(BiTree *T, int key) {if( !(*T)){//不存在關鍵字等于key的數據元素return FALSE;}else{if( key == (*T)->data ){Delete(T);return TRUE;}else if( key < (*T)->data){//使用遞歸的方式return DeleteBST(&(*T)->lchild, key);}else{return DeleteBST(&(*T)->rchild, key);}} } void order(BiTree t)//中序輸出 {if(t == NULL){return ;}order(t->lchild);printf("%d ", t->data);order(t->rchild); } int main() {int i;int a[5] = {3,4,2,5,9};BiTree T = NULL;for( i = 0; i < 5; i++ ){InsertBST(&T, a[i]);}printf("中序遍歷二叉排序樹：\n");order(T);printf("\n");printf("刪除3后，中序遍歷二叉排序樹：\n");DeleteBST(&T,3);order(T); }

5、哈希表的概念

在面前討論的各種結構（線性表、樹）中，記錄在結構中的相對位置是隨機的，和記錄的關鍵字之間不存在確定的關系，因此，在結構中查找記錄時需進行一系列和關鍵字的比較。這一類查找方法建立在“比較”額基礎上。在順序查找時，比較的結果為“=”與“≠”兩種可能；在折半查找、二叉排序樹查找，比較的結果為“<”、“=”和“>”三種可能。查找的效率依賴于查找過程中所進行的比較次數。

理想的情況是希望不經過任何比較，一次存取便能得到所查記錄，那就必須在記錄的儲存位置和它的關鍵字之間建立一個確定的對應關系f，使每個關鍵字和結構中一個唯一的儲存位置相對應。因而在查找時，只要根據這個對應關系f找到給定值k得像f（k）。若結構中存在關鍵字和k相等的記錄，則必定在f（k）的儲存位置上，由此，不需要進行比較便可直接取得所查記錄。在此，我們稱這個對應關系f為哈希（Hash）函數，按這個思想思想建立的表為哈希表。

我們可以舉一個哈希表的最簡單的例子。假設要建立一張全國30個地區的各民族人口統計表，每個地區為一個記錄，記錄的各數據項為：

編號地區名總人口漢族回族···

顯然，可以用一個一維數組c（1:30）來存放這張表其中C[i]是編號i的地區的人口情況。編號i便于記錄的關鍵字，由他唯一確定記錄的儲存位置C[i]。列如：假設北京市的各民族人口，只要取出C[1]的記錄即可。假如把這個數組看成是哈希表f（key）=key。然而，很多情況下的哈希函數并不如此簡單。可仍以此為例，為了查看方便應以地區名作為關鍵字。假設地區名以漢語拼音的方式表示，則不能簡單地取哈希函數f(key)=key，而是首先要將它們轉化為數字，有時還要作些簡單的處理。列如我們可以有這樣的哈希函數：（1）取關鍵字中第一個字母在字母表中的序號作為哈希函數。列如：BEIJNG的哈希函數：

（1） 取關鍵字中第一個字母在字母表中的序號作為哈希函數。列如:BEIJING的哈希函數值為字母“B”在字母表中的序號，等于02:；

（2）先求關鍵字的第一個和最后一個字母在字母表中的序號之和，然后判別這個和值，若比30（表長）大，則減去30.列如:TIANJIN的首尾兩個字母“T”和“N”的序號之和為34，故取04為他它的哈希函數值；或

（3）先求每個漢字的第一個字母的ASCII碼（和英文字母相同）之和的八進制形式，然后將這個八進制數看成是十進制再除以30取余數，若余數為零再加上30而為哈希函數值。

例如：HENAN的兩個拼音字母為“H”和“N”，他們的ASCII碼之和為（266），以（266）除以（30）的余數為16，則16為HENAN的哈希函數值。上述人口統計部分關鍵字在這三種不同的哈希函數情況下的哈希函數值如表下圖所列：

從這個例子可見：

（1） 哈希函數一個映像，因此哈希函數的設定很靈活，只要是的任何關鍵字由此所得的哈希函數值都落在表長允許范圍之類即可；

對不同的關鍵字可能得到同一哈希地址，即key≠key2面f（key1）=f（key2）這種現象稱沖突（collision）。具有相同函數值的關鍵詞對該哈希函數來說乘坐同義詞（synonym）。例如：關鍵詞HEBEI和HENAN不等，但f1（HEBEI）=f1（HENAN）,又如：f2（SHANGHAI）:f3（HENAN）==f3（SICHUAN）.這種現象給建造成困難，如在第一種哈希函數的情況下，因為山西，上海，山東和四川這四個記錄的哈希地址均為19而C[19]只能存放一個記錄，那么其他三個記錄存放在表中的什么位置呢？并且，從上表三個不同的哈希函數的情況下就可以看出，哈希函數選的合適可以減少這種突發情況。特別是在這個例子中。只可能有30個記錄，可以仔細分析這30個關鍵詞的特性，選擇一個恰當的哈希函數來避免沖突的發生。

一、 哈希函數的構造方法

構造哈希函數的方法撒很多。在介紹各種方法之前，首先需要明確什么是“好”的哈希函數。

若對于關鍵字集合中的任何一個關鍵字，經哈希函數映像到地址集合中任何一個地址的概率是相等的。則稱此類哈希函數為均勻的（Uniform）哈希函數。換句話說，就是是關鍵字經過哈希函數得到一個“隨機的地址”，以便使一組關鍵字的哈希地址均勻分布在整個地址區間中，從而減少沖突。

常用的構造哈希函數的方法有：

1. 直接定址法

取關鍵字或關鍵字的某個線性函數值為哈希地址。即：

? H(Key)=key或（key）=a*key+b

其中a和b為常數（這種哈希函數叫做自身函數）。

例如：有一個從1歲到100歲的人口數字統計表，其中，年齡作為關鍵字，哈希函數取關鍵字自身。如表9.2所示

地址010203.。。。252627。。。100

年齡	1	2	3	。。。	25	26	27	。。。	.。。。
人數	3000	2000	5000	。。。	1050	。。。	.。。。	。。。	。。。
。。。

? 表1直接定址哈希函數例之一

這樣，若要詢問25歲的人有多少，則只要查詢的第25項即可。又如：有一個解放后出生的人口調查表，關鍵字是年份，哈希函數取關鍵字加一常數：

H（key）=key+（-1948），如表9.3所示。

地址01 02 03 …. 22 …

年份	1949 1950 1951 …. 1970 ……
人數	…. …… …… …. 15000 ….
….

表2直接定址哈希函數例之二

這樣，若要查1970年出生的人數，則只要查第）（1970-1948）=22項即可。由于直接定址所得地址集合關鍵詞集合的大小相同。因此，對于不同的關鍵詞不會發生沖突。但實際中能用這種哈希函數的情況很少。

2. 數字分析法

假設關鍵字是以r為基的數（如：以10為基的十進制數）。，并且哈希表中可能出現的關鍵字都是事先知道的，則可取關鍵字的若干數位組成哈希地址。例如有80個記錄，其關鍵字為8位十進制數。假設 哈希的表長為10010，則可無取兩位十進制數組成哈希地址。取哪兩位?原則是使得到的哈希地址盡量避免產生沖突，則需從分析這80個關鍵字著手。假設這80個關鍵字中的一部分如下所列：

對關鍵字全體的分析中我們發現第1,2 位都是“8，,1”，第三位3或4， 第8位只可能取2，5,7，因此這四位數都不可取。由于中間的四位數可看成是近乎隨機的，因此可取其中任意兩位，獲取其中兩位與另外兩位的疊加求和后舍去進位作為哈希地址。

1. 平方取中法：

取關鍵字平方后的中間幾位為哈希地址。這是一種較常見的構造哈希函數的方法。

通常在選定哈希函數時不一定能知道關鍵最的全部情況，去其中哪幾位也不一定合適，而一個數平方后的中間幾位數的每一位都想關，由此使隨機分布的關鍵字得到的哈希地址也是隨機的。取的位數由表長決定。

例如：為BASIC源程序中的標識符建立一個哈希表。假設BASIC語言中允許的標識符為一個字母，或一個子母和一個數字，在計算機內可用兩位八位進制 數表示字母和數字。取標識符在計算機中的八進制數為它的關鍵字。假設表長為512=29.則可取關鍵字平方后的中間9二進制數為哈希地址。例如下圖列出了一些標識符及它們的哈希地址。

? A B C … Z 0 1 2 … 9

? 01 02 03 32 60 61 62 71

1. 除留余數法

取關鍵字被某個不大于哈希表表長m的數p除后所得余數為哈希地址。即

? H（key）=key MOD p p< m（一般取小于m的最大質數

這是一種最簡單，也最常用的構造哈希函數的方法。他不僅可以對關鍵字直接取摸（MOD），也可以在折迭、平方取中等運算之后取摸。值得注意的是，在使用除留余數法時，對p的選擇很重要。若p選的不好，容易產生同義詞。

二、 處理沖突的方法

在“第一小節什么是哈希表”中曾提及均勻的哈希函數可以減少沖突，但不能避免，因此，如何處理沖突是哈希表不可缺少的另一方面。

假設哈希表的地址集為0~（n-1），沖突是指由關鍵字得到的哈希地址為j（0≤j≤n-1）的位置上已存有記錄，則“處理沖突”就是為該關鍵字的記錄找到另一個“空”的哈希地址。

在處理沖突的過程中可能得到一個地址序列Hi i=1，2，…，k，（Hi∈[0，n-1]。

即在處理哈希地地址的沖突時，

若得到的另一個哈希地址Hi仍然發生沖突，則再求下一個地址H2 若H2仍然沖突，再求得H3. 以此類推， 直至Ha不發生沖突為止，則Ha為記錄在表中的地址。

通常用的處理沖突的方法有下列幾種：

1. 開放定址法

Hi=（H（key）+di）MODm i=1,2，…， k（k≤M-1）其中：h（key）為哈希函數；m為哈希表表長；di為增量序列，可有下列三種取法:

di=1,2,3，…，m-1，呈線性探測在散列；

例如， 在長度為11的哈希表中一填中有關鍵字分別為17,60,29的記錄（哈希函數H（key）=key MOD11），現有第四個記錄，其關鍵字為38 由哈希函數得到哈希地址為5，產生沖突。若用線性探測在散列的方法處理時

，得到下一個地址6，扔沖突：再求下一個地址7仍沖突

；直到哈希地址為8的位置為“空”時止處理沖突的過程結束，

記錄填入哈希表中序列為8的位置。若用二次探測在散列，則應該填入序號為4的位置類似地可得到偽散列，則應該填入序號為4的位置。類似地可得到偽序列再散列的位置。

2. 再哈希法

? i=1,2,…,k

RHi均是不同的哈希函數，即在同義詞產生地址沖突時計算另一個哈希函數的地址，直到沖突不再發生。這種方法不易產生“聚集”，但增加了計算的時間。

注：會產生空隙

三、 哈希表的查找及分析

在哈希表上進行查找的過程跟哈希造表過程基本一致，給定K值，根據造表時設計的哈希函數計算出哈希地址，若此位置上沒有記錄，則查找不成功；否則比較關鍵字若與給定的關鍵字相同，則查找成功。否則根據造表時處理沖突的方法找“下一地址”，直至哈希表中某個位置為空，或者表中所填記錄的關鍵字與給定的關鍵字相等為止。

已知如圖所示一組關鍵字按哈希函數H（key）=key MOD 13和線性探測處理沖突，構造所得的哈希表。

例如查找關鍵字84，H(84)=6,去6查看發現該單元格不空，但是不等于84，采用線性探測處理沖突則去下一位位置7查找，發現不空也不等于84，則再線性探測去8單元格找，不空恰好等于84，則查找成功，查找次數為3。

其他元素依次類推，可得到平均的查找長度（ASL）：

綜上所述，一般情況，查找的平均長度與三個因素相關：

1、哈希函數

2、處理沖突的方法

3、裝填因子

哈希表的裝填因子定義為：

?

的值越小，發生沖突的概率越小，反正 越大，表中填入的記錄越多，在填入的時候發生沖突的可能性就越大，在進行查找時候，查找的次數也就越多。

四、代碼哈希表的實現

#include <stdio.h> #include <memory.h> #include <string.h> #include <stdlib.h>#define HARSH_TABLE_MAX_SIZE (1000) // 哈希數組的最大元素個數typedef struct HarshNode_struct HarshNode;// 定義一個哈希表的節點 struct HarshNode_struct {char * sKey; // [sKey,nvalue]是一對鍵值對int nValue;HarshNode *pNext; };HarshNode * harshTable[HARSH_TABLE_MAX_SIZE]; // 哈希表數組 unsigned int g_harsh_table_size = 0x0;//初始化哈希表 void harsh_table_init(void) {int i = 0x0;memset(harshTable,0,sizeof(HarshNode *)*HARSH_TABLE_MAX_SIZE);g_harsh_table_size = 0x0;}// 將字符給變成hashcode unsigned int harsh_table_harsh_string(const char * sKey) {const unsigned char* p = (const unsigned char*) sKey;unsigned int value = *p;if(value) {for( p += 1; *p != '\0'; p++) {value = (value << 5) - value + *p;}}return value;}//根據鍵值對向哈希表中添加節點，如果skey已經存在則直接更新鍵值nValue //添加成功返回0，添加失敗返回-1 int harsh_table_insert_node(const char * sKey, int nValue) {HarshNode * pHarshNodeHead = NULL;HarshNode * pNewNode = NULL;unsigned int pos = 0x0;if((g_harsh_table_size >= HARSH_TABLE_MAX_SIZE )||(NULL == sKey))return -1;pos = harsh_table_harsh_string(sKey) % HARSH_TABLE_MAX_SIZE; //用這種方法計算sKey在哈希數組中對應的位置printf("skey在哈希表中的位置 : pos = %d\n",pos);pHarshNodeHead = harshTable[pos];if(NULL == pHarshNodeHead)printf("最后空指向頭指針:NULL == pHarshNodeHead\n");while(NULL != pHarshNodeHead ) { // 如果這個位置對應的不是這一串中最后一個節點的話，那就要向后移動了if(strcmp(pHarshNodeHead->sKey,sKey) == 0) { //如果這個鍵值對已經存在，只更新鍵值即可pHarshNodeHead ->nValue = nValue;return 0;}pHarshNodeHead = pHarshNodeHead->pNext; //向后移動,肯定會有NULL的時候}pNewNode = (HarshNode *)malloc(sizeof(HarshNode)); //申請一塊HarshNode 大小的內存if(NULL == pNewNode) {return -1;}memset(pNewNode,0,sizeof(HarshNode));pNewNode ->sKey = (char *)malloc(strlen(sKey) + 1); //申請一塊sKey大小的內存if(NULL == pNewNode ->sKey ) {return -1;}memset(pNewNode ->sKey,0,strlen(sKey) + 1);strcpy(pNewNode ->sKey,sKey); //將sKey的內容賦給 pNewNode -> sKeypNewNode ->nValue = nValue; //鍵值也復制過來pNewNode ->pNext = NULL; //由于是新節點，也是尾節點，所以pNext指向NULLpHarshNodeHead = pNewNode;harshTable[pos] = pHarshNodeHead; //最后一定要讓數組中的這個位置指向這個頭指針g_harsh_table_size ++;return 0;}//打印數組中對應的某個位置的那一串哈希值 void print_harsh_node(int pos) {HarshNode * pHarshNodeHead = NULL;if(pos >= HARSH_TABLE_MAX_SIZE)return;pHarshNodeHead = harshTable[pos];if(NULL == pHarshNodeHead)printf("NULL == pHarshNodeHead\n");while(NULL != pHarshNodeHead) {printf("位置:%d, sKey:%s, nValue:%d \n",pos,pHarshNodeHead->sKey,pHarshNodeHead->nValue);pHarshNodeHead = pHarshNodeHead->pNext;}}// 根據鍵值sKey來查找對應的哈希節點 HarshNode * harsh_table_lookup(const char *sKey) {unsigned int pos = 0x0;HarshNode * pHarshHead = NULL;if(NULL == sKey) {return NULL;}pos = harsh_table_harsh_string(sKey) % HARSH_TABLE_MAX_SIZE; //計算出在哈希數組中的位置pHarshHead = harshTable[pos];while(NULL != pHarshHead) {if(strcmp(sKey,pHarshHead->sKey) == 0)//找到了return pHarshHead;pHarshHead = pHarshHead->pNext; // 沒有找到的話來到下一個節點}return NULL;}int main() {char * pSkey = "abcd";int nValue = 1234;int ret = -1;int pos = 0xffffffff;HarshNode * pHarshNode = NULL;harsh_table_init();ret = harsh_table_insert_node(pSkey,nValue);printf("ret = %d\n",ret);if(!ret) {pos = harsh_table_harsh_string(pSkey) % HARSH_TABLE_MAX_SIZE;printf("main: pos = %d\n",pos);print_harsh_node(pos);}pHarshNode = harsh_table_lookup(pSkey);if(NULL != pHarshNode) {printf("最終值: sKey:%s, nValue: %d\n",pHarshNode->sKey,pHarshNode->nValue);} }

總結

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

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