《数据结构域算法设计-第九章查找1静态查找表 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第九章查找1静态查找表 课件（33页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第九章 查找,9.1 静态查找表,9.2 动态查找表,9.3 哈希表,花名册,学号,姓 名,性别,年龄,其 他,键码转换表,矩阵式键盘,第九章 查找,由同一类型数据元素（或记录）构成的集合。在查找表中数据元素除了同属一个集合，不考虑元素之间其它关系。,一.查找表,学号,姓 名,性别,年龄,其 他,三.查找操作, 查询某个“特定”元素是否在表中； 检索某个“特定”元素的各种属性； 在查找表中插入一个数据元素； 从查找表中删除某个数据元素。,静态 查找表,动态 查找表,学号,姓 名,性别,年龄,其 他,四.查找表中数据元素(记录)的定义,typedef struct KeyType ke
2、y; ElemType;,学号,姓 名,性别,年龄,其 他,查找算法时间性能通过关键码的比较次数来度量。,算法； 问题规模； 待查关键码在查找集合中的位置； 查找频率。,查找频率与算法无关，取决于具体应用。 通常假设查找频率pi是等概率的，即pi=1/n。,五.查找算法的性能,平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为：,其中：n：问题规模，查找集合中的记录个数；pi：查找第i个记录的概率；ci：查找第i个记录所需的关键码的比较次数。,物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小
3、，时间效率越高。,五.查找算法的性能,一.静态查找表的查找算法,9.1 静态查找表,1、顺序查找（线性查找） 2、折半查找（二分或对分查找） 3、静态树表的查找 4、分块查找（索引顺序查找）,二.顺序查找,9.1 静态查找表,对顺序结构如何线性查找？ 对单链表结构如何线性查找？ 对非线性树结构如何顺序查找?,只要知道头指针head就可以“顺藤摸瓜”!,可借助各种遍历操作！,问题,通常以顺序存储结构的线性表或有序表表示静态查找表； 数据存储空间中，0号单元留空。,9.1 静态查找表,typedef struct ElemType *elem; /数据元素存储空间的基址int length; /表
4、长 SSTable;,二.顺序查找,算法：,二.顺序查找,int Search_Seq(SSTable ST, KeyType key) /Search_Seq,9.1 静态查找表,for(i=1; i0,原则：,9.1 静态查找表,二.顺序查找,从表的最后一个记录（或第一个记录）开始，依次将记录的关键字与给定值比较，若相等：若找到，返回该元素在表中的位置；否则，查找失败。,改进：设置“监视哨”,改进：,二.顺序查找,int Search_Seq(SSTable ST, KeyType key) /Search_Seq,19,61,9.1 静态查找表,ST.elem0.key=key; /监视
5、哨for(i=ST.length; ST. elemi. key!=key; - -i) ;return i;,监视哨,二.顺序查找,性能：,9.1 静态查找表,分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； 查找第n个元素所需的比较次数为n；,总计全部比较次数为：12n = (1+n)n/2,若求某一个元素的平均查找次数，还应当除以n（等概率）， 即： ASL（1n）/2 ，时间效率为 O(n),二.顺序查找,平均查找长度较大，大约为1/2个表长。当表记录数n非常大时，查找效率较低。但其算法简单，适用面广，无论表中记录是否按关键字有序排列均可使用，且对链表同样
6、适用。,特点：,9.1 静态查找表,原则：,三.折半查找对有序表查找,先确定待查记录的范围（区间），然后逐步缩小范围，直到找到或找不到该记录为止。,9.1 静态查找表,三.折半查找对有序表查找,9.1 静态查找表,对顺序结构如何线性查找？ 对单链表结构如何线性查找？ 对非线性树结构如何顺序查找?,无法实现！因全部元素的定位只能从头指针head开始,可借助二叉排序树来查找（属动态查找表形式）。,问题,92,88,80,75,64,56,37,21,19,13,5,11,10,9,8,7,6,5,4,3,2,1,0,ST.elem,ST.length,例,查找key=19,return 3,92,
7、88,80,75,64,56,37,21,19,13,5,11,10,9,8,7,6,5,4,3,2,1,0,ST.elem,ST.length,例,查找key=61,return 0,算法：,int Search_Bin(SSTable ST, KeyType key) low=1; high=ST. length;while(low=high) mid=(low+high)/2;if (key= ST. elemmid.key) return mid; else if (keyID.elemhigh.key) return 0; /给定值比所有关键字都大while(lowID. elemm
8、id. key) low=mid+1; else found=TRUE;low=mid; s=ID.elemlow.stadr; /查找范围在第low块，s为起始位置if(lowID.length-1) t=ID.elemlow+1.stadr-1;/low不是最后一块else t=ST.length; /t为终止位置if(ST.elemt.key)=key return t;else ST.elem0=ST.elemt; ST.elemt.key=key; /设置监视哨for(k=s;ST.elemk.key!=key;k+);ST.elemt=ST.elem0; /恢复暂存值if(k!=t) return k;else return 0; /顺序查找 ,因为索引顺序查找实际上进行了两次查找，因此其平均查找长度为两次查找长度之和。索引顺序查找也适用于线性链表。,特点：,四.索引顺序查找,9.1 静态查找表,
