有序表的静态折半查找(判定树)-----数据结构与算法笔记
一、折半(二分)查找
参考书：《数据结构（C语言）》–严蔚敏等编著，清华大学出版社。
1、三种静态查找
在有序表的顺序查找中，它的平均ASL为 n + 1 2 \frac{n+1}{2} 2n+1，是三种静态查找方法(顺序查找-折半查找-分块查找)中最大，他们之间的比较如下：
| \ | 顺序查找 | 折半查找 | 分块查找 |
|---|---|---|---|
| ASL | 最大 | 最小 | 中间 |
| 表结构 | 有序、无序表 | 有序表 | 分块有序 |
| 存储结构 | 顺序、链表 | 顺序表 | 顺序、链表 |
优缺点也很明显，其中折半查找的优缺点为：
优点：效率比顺序查找高；
缺点：只适用于有序表，且仅限于顺序存储结构，对线性链表使用时无法有效的查找；
折半查找的最大特点是：每次将待查找记录区间缩小一半区域，减少比较的次数；
2、判定树
这个查找过程可以利用二叉树来描述。其中每个节点表示一个记录，把这样的树称为判定树；其中判定树需满足一下特点：
存储：大的在右，小的在左；
查找：大的向右找，小的向左找；
特别：0号元素空出，从1号开始存储，便于返回值
可以看出：
查找记录在第几层，就会比较几次，但是如果查找不成功(无此记录)的情况下，只会出现在第3、4层，因为只有这两层会有NULL空出现表示不存在的节点；
查找成功的平均ASL长度计算如下：节点个数x层数/n
ASL= 1 ∗ 1 + 2 ∗ 2 + 4 ∗ 3 + 4 ∗ 4 11 \frac{1*1+2*2+4*3+4*4}{11} 111∗1+2∗2+4∗3+4∗4 = 3
查找不成功的平均ASL长度计算如下：空节点个数x层数/n
ASL= 4 ∗ 3 + 8 ∗ 4 12 \frac{4*3+8*4}{12} 124∗3+8∗4 = 3.67
相关代码：
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define MAXSIZE 100typedef int Status;
typedef int KeyType;
typedef struct {KeyType key;
} ElemType;typedef struct {ElemType *elem;int length;
} SSTable;int order[MAXSIZE]; //全局变量，记录比较的数值Status InitTable(SSTable &ST,int n);
Status InitTable(SSTable &ST,int n) {ST.elem = (ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(!ST.elem) exit(OVERFLOW);ST.length = 0;for(int i=1; i<=n; i++) {int num;scanf("%d",&num);ST.elem[i].key = num;ST.length++;}return OK;
}Status Search_Bin(SSTable &ST,KeyType key);
//折半查找
Status Search_Bin(SSTable &ST,KeyType key) {int low=1,high=ST.length,i=0;while(low <= high) {int mid = (low + high)/2;if(key == ST.elem[mid].key) {order[i] = ST.elem[mid].key; //存比较的数(路径) return mid;} else if(key > ST.elem[mid].key) {order[i] = ST.elem[mid].key;low = mid + 1;} else {order[i] = ST.elem[mid].key;high = mid - 1;}i++;}
}int main(void) {SSTable ST;int i,n;int key;printf("请输入列表项个数: ");scanf("%d",&n);printf("请输入列表项: ");InitTable(ST,n);printf("请输入查找关键字: ");scanf("%d",&key);i = Search_Bin(ST,key);printf("比较的数依次为:");for(int j=0; order[j] != 0; j++)printf("%d->",order[j]);putchar('\n');if(i != 0)printf("该关键字的位置为: %d\n",i);elseprintf("查无此项\n");return 0;
}/*
测试输入：
5
8 10 12 15 33
20
预期输出：
12-15-33- //比较数
查无此项预期输出：
9
12 15 33 42 45 77 78 80 89
12
预期输出：
45-15-12- //比较数
1
*/
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！