数据查找顺序二分索引哈希查找.docx
- 文档编号:18463837
- 上传时间:2023-08-18
- 格式:DOCX
- 页数:28
- 大小:111.20KB
数据查找顺序二分索引哈希查找.docx
《数据查找顺序二分索引哈希查找.docx》由会员分享,可在线阅读,更多相关《数据查找顺序二分索引哈希查找.docx(28页珍藏版)》请在冰点文库上搜索。
数据查找顺序二分索引哈希查找
选题八数据查找
一、基本概念
查找表:
是由同一类型的数据元素(或记录)构成的集合。
查找:
也称检索,即根据给定的某个值,在查找表中确定一个其关键字等于给定值的第一条记录(元素)或全部记录。
若表中存在这样的记录,则查找成功,通常要求返回该记录存储位置;若不存在这样的记录,表明查找失败,返回特定值。
例:
在下表中查找学号为“98182”的学生信息
学号
姓名
性别
籍贯
出生年月
1
98131
刘激扬
男
北京
1979.12
2
98164
衣春生
男
青岛
1979.07
3
98165
卢声凯
男
天津
1981.02
4
98182
袁秋慧
女
广州
1980.10
5
98203
林德康
男
上海
1980.05
平均查找长度:
在查找成功情况下平均比较次数,可用作判定一个查找算法的时间复杂度:
其中:
n:
查找表长;
Pi:
查找第i个元素;
Ci:
查找第i个元素比较次数。
二、顺序查找
1.查找思路
顺序表:
指线性表的顺序存储结构。
本章讨论中,设顺序表采用一维数组A表示,其元素类型为ElemType,它含有关键字域key和其它一些数据域,并设定A的大小为整型常量MaxSize,数组的元素个数为n,n应小于等于MaxSize。
typedefstruct{
KeyTypekey;
…
}ElemType;
顺序查找:
又称线性查找,它是一种最简单最基本查找方法。
查找思路:
从顺序表的一端开始,依次将每个元素关键字同给定值K进行比较,若某个元素关键字等于K,则查找成功,返回该元素所在下标,若直到所有元素都比较完毕,仍找不到关键字为K的元素,则查找失败,反回特定值(常用-1表示)。
基本算法
intSeqsch(ElemTypeA[],intn,KeyTypeK)
{
//从顺序表A的n个元素中顺序查找关键字为K的元素,若成功返回其下标,否则返回-1
for(inti=0;i if(A[i].key==K) break; if(i returni; else return-1; } 如下图: 0 1 2 3 4 5 23 4 56 43 2 78 在顺序表中查找56,比较3次。 改进算法 对该算法作一改进: 在表的尾端A[n]设一岗哨,在查找前先将K赋给A[n],这样每循环一次不需比较下标是否越界,当比较到第n位置时,由于A[n].key==K成立,必退出循环。 intSeqsch(ElemTypeA[],intn,KeyTypeK) { //从顺序表A的n个元素中顺序查找关键字为K的元素,若成功返回其下标,否则返回-1 A[n].key=k;//设置岗哨 for(inti=0;;i++) if(A[i].key==K) break;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 查找 顺序 二分 索引