常用查找算法汇总

1.折半查找

 1 //折半查找的非递归实现
 2 int BinSrch(SeqRList L, int K)//L为一个顺序查找表
 3 {
 4     int low = 1, high = L.length, mid;
 5     while (low <= high)
 6     {
 7         mid = (low + high) / 2;
 8         if (k == L.r[mid].key) return mid;
 9         else if (K < L.r[mid].key) high = mid - 1;
10         else low = mid + 1;
11     }
12     return 0;
13 }

View Code

2.基于二叉排序树查找的非递归实现

类似于折半查找

（1）若给定值等于根节点的关键字，则查找成功；

（2）若给定值小于根节点的关键字，则继续在左子树上进行查找；

（3）若给定值大于根节点的关键字，则继续在右子树上进行查找；

 1 BSTree SearchBST(BSTree bst, KeyType K)
 2 {
 3     BSTree q;
 4     q = bst;
 5     while (q)
 6     {
 7         if (q->key == K) return q;
 8         if (k->q - Key) q = qlchild;
 9         else q = q->child;
10     }
11     return NULL;
12 }

View Code

3.二叉排序树的插入

 1 void InsertBST(BST *bst, KeyTYpe K)
 2 {
 3     BinTree s;
 4     if (*bst == null)
 5     {
 6         s = (BSTree)malloc(sizeof(BSTNode));
 7         s->key = k;
 8         s->lchild = NULL;
 9         s->rchild = NULL;
10         *bst = s;
11     }
12     else if (K < (*bst)->key) InsertBST(&((*bst)->lchild), k);
13     else if (K > (*bst)->key) InsertBST(&((*bst)->rchild), k);
14 }

View Code

4.二叉排序树的建立

 1 void CreatBST(BSTree *bst)
 2 {
 3     KeyType key;
 4     *bst = NULL;
 5     scanf("%d", &key);
 6     while (key != ENDKEY)
 7     {
 8         InsertBST(bst, key);
 9         scanf("%d", &key);
10     }
11 }

View Code

5.二叉排序树的删除

 1 BSTNode *DelBST(BSTree bst, KeyType K)
 2 {
 3     BSTNode *p, *f, *s, *q;
 4     p = bst;
 5     f = NUlL;
 6     while (p)
 7     {
 8         if (p->key == K) break;
 9         f = p;
10         if (p->key > K) p = p->lchild;
11         else p = p->rchild;
12     }
13     if (p == NULL) return bst;
14     if (p->lchild == NULL)
15     {
16         if (f == NULL) bst = p->rchild;
17         else if (f->lchild == p) f = lchild=p->rchild
18         else   f = rchild=p->rchild;
19         free(p);
20     }
21     else
22     {
23         q = p;
24         s = p->child;
25         while (s->rchild)
26         {
27             q = ;
28             s = s->rchild;
29         }
30         if (q == p) q->lchild = s->lchild;
31         else q->rchild = s->lchild;
32         p->key = s->key;
33         free(s);
34     }
35     return bst;
36 }

View Code

6.顺序查找及折半查找测试

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include "malloc.h"
 4 #define MAXSIZE 20
 5 
 6 typedef int KeyType;
 7 typedef struct
 8 {
 9     KeyType key;
10 }RecordType;
11 
12 typedef struct
13 {
14     RecordType r[MAXSIZE + 1];
15     int length;  //序列长度，即实际记录个数
16 }SeqList;
17 
18 /*
19 该算法的时间代价主要消耗在while循环处
20 */
21 int SeqSearch1(SeqList L, KeyType k)
22 {
23     int i = L.length;
24     while (i >= 1 && L.r[i].key != k)
25     {
26         i--;
27     }
28     if (i >= 1){
29         return i;
30     }
31     else
32         return 0;
33 }
34 
35 /*
36 算大利用了0号位置作为监视哨，记录待查的关键字，平均查找长度为 （n+1）/2,
37 如果查找失败：  （n+1）/2 <平均查找次数<(n+1)
38 */
39 int SeqSearch2(SeqList L, KeyType k)
40 {
41     L.r[0].key = k;    //监视哨
42     int i = L.length;
43     while (L.r[i].key != k)
44         i--;
45     return i;
46 }
47 
48 //折半查找(二分查找),平均查找长度为 (n+1)/n * (log 2) (n+1)-1
49 int BinSearch(SeqList L, KeyType k)
50 {
51     int low = 1;
52     int high = L.length;
53     int mid;
54     while (low < high)
55     {
56         mid = (low + high) / 2;
57         if (L.r[mid].key == k)
58             return mid;
59         else if (L.r[mid].key >= k)
60             high = mid - 1;
61         else
62             low = mid + 1;
63     }
64     return 0;
65 
66 }
67 int main()
68 {
69     int i = 0;
70     SeqList L;
71     for (int i = 1; i < MAXSIZE; i++){
72         L.r[i].key = i;
73         printf("%3d", L.r[i].key);
74     }
75     printf("
");
76     L.length = MAXSIZE;
77     i = SeqSearch1(L, i);
78     printf("查找的位置为：%d
", i);
79     i = SeqSearch2(L, i);
80     printf("带监视哨查找：%d
", i);
81     printf("折半查找：%d
", i);
82     i = BinSearch(L, i);
83     return 0;
84 }
85 /*
86 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
87 查找的位置为：0
88 带监视哨查找：0
89 折半查找：0
90 请按任意键继续. . .
91 */

View Code

7.hash查找

1.哈希表的创建

 1 void Createht(Hashtable ht, Datatype L[], int n)
 2 {
 3     int i;
 4     for (i = 0; i < HASHSIZE; i++)
 5     {
 6         ht[i].data.key = NULL;
 7         ht[i].times = 0;
 8     }
 9     for (i = 0; i < n; i++)
10         HashInsert(ht, L[i]);
11 }

2.哈希表的查找

1 int HashSearch(Hashtable ht, Datatype x)
2 {
3     int address;
4     address = HashFunc(x,key);  //计算散列地址
5     while (ht[address].data.key!NULL&&ht[address].data.key!x.key)
6         address = Collision(address);//没找到处理冲突
7     if (ht[address].data.key == x.key) return address;
8     else return -1;
9 }

3.哈希表的删除

 1 int HashDel(Hashtable ht, Datatype x)
 2 {
 3     int address;
 4     address = HashFunnc(x, key);
 5     if (address>=0)
 6     {
 7         ht[address].datakey = DEL;
 8         return 1;
 9     }
10     return 0;
11 }

4.哈希表的插入

1 int HashInsert(Hashtable ht, Datatable x)
2 {
3     int address;
4     address = HashFunnc(x, key);
5     if (address >= 0) return 0;
6     ht[-address].data = x;
7     ht[-address].times = 1;
8     return 1;
9 }