文档介绍：概述
图
查找
排序

本章主要内容
查找

树与二叉树
数组
栈与队
线性表
查找(Searching)
静态查找表(线性查找、对分查找、分块查找)
动态查找表(二叉排序树)
哈希表查找表
本节主要内容:
一、基本概念
查找表:用于查找的数据元素的集合称为查找表。查找表由同一类型的数据元素(或记录)构成。
查找
查找表的操作:
(1)查询某个“特定的”数据元素是否在查找表中;
(2)检索某个“特定的”数据元素的各种属性;
(3)在查找表中插入一个数据元素;
(4)从查找表中删除某个数据元素.
静态查找表:对查找表只作(1)、(2)操作;
动态查找表:可以对查找表作(1)-(4)操作。
关键字: 是数据元素(或记录)中的某个数据项的值,用以标识一个数据元素(或记录) 。
例如:银行帐户中的帐号是。
查找
查找:根据给定的值,在查找表中确定一个关键字等于给定值的记录或数据元素的过程。
查找
平均查找长度(average search length,ASL):
衡量查找算法的优劣标准。对于一个含有n个元素的查找表,查找成功时的平均查找长度可表示为:
Pi为查找第i个元素的概率
一般认为查找每个元素的概率相等,Pi=1/n.
ci为查找第i个元素所经历的比较次数。
查找
1、线性查找
将查找表作为一个线性表,可以是顺序表,也可以是链表,依次用给定的值与查找表中数据元素的关键字值进行比较,若某个记录的关键字值与给定值相等,则查找成功,返回该记录的存储位置,反之,若直到最后一个记录,其关键字值与给定值均不相等,则查找失败,返回查找失败标志。
二、静态查找表
查找
/*线性查找:在表r中查找关键字值为k的元素*/
int seqsearch(node r[n+1],elemtype k)
{
r[0].key=k;
int i=n; /*从表尾开始向前扫描*/
while(r[i].key!=k) i--;
return i;
}
线性查找法最多查找次数为n+1,最少查找次数为1,平均查找次数为(n+1)/2,时间复杂度为O(n)。
查找
如果查找表中各记录是按关键字有序排列的,可以先用表的中间位置上记录的关键字与给定值K比较,若相等,则查找成功;否则,根据比较的结果确定下一步在表的前半部或后半部中继续查找。
2、对分查找
1
2
3
mid=4
key
例: 在顺序表中查找 key = 55 的数组元素。
mid = ┗(low+high)/2┛
13
17
42
46
55
70
94
4
5
6
7
8
high=8
low=5
5
mid=6
low=1
42<55
查找成功
查找
对分法查找只适用于顺序存储的有序表,其最大查找次数为log2n,最小查找次数为1,平均查找次数当n>50时约为:log2(n+1)-1,时间复杂度为O(log2n)。
查找
//对分法查找
Int binsearch(struct node r[n+1] , element k)
{
int low=1, high=n;
while (low<=high)
{
int mid=(low+high)/2; /*取区间中点*/
if( r[mid].key= =k)return mid; /*查找成功*/
else if(r[mid].key>k) high=mid-1;/*在左子区间中查找*/
else low=mid+1; /*在右子区间中查找*/
}
return 0; /*查找失败*/
}