专升本（计算机专业课件)数据结构第章课件顺序查找key.pdf

《专升本（计算机专业课件)数据结构第章课件顺序查找key.pdf》由会员分享，可在线阅读，更多相关《专升本（计算机专业课件)数据结构第章课件顺序查找key.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、顺序查找的算法思想顺序查找，又叫“线性查找”，通常用于线性表。算法思想：从头到ji。挨 个 找（或者反过来也0K）查找目标:43顺序查找的算法思想顺序查找，又叫“线性查找”，通常用于线性表。算法思想：从头到ji。挨 个 找（或者反过来也0K）33 I 10 I 13 I 29 I 16 I 19 I 32 I 7 I 43 I 41 I 37查找目标:43第1页 共9页顺序查找的实现typedef structElemType*elem;in t TableLen;SSTable;/查找表的数据结构（顺序表）/动态数组基址/表的长度/顺序查找in t Search_Seq(SSTable ST

2、,ElemType key)in t i;for(i=0;iST.TableLen&ST.elemi!=key;+i);/查找成功，则返回元素下标；查找失败，则返回-2return i=ST.TableLen?-1:i;查找目标:43TableLen=110 1 2 3 4 5 6 7 8 9 10 11 12 13第2页 共9页顺序查找的实现typedef structElemType*elem;int TableLen;SSTable;查找表的数据结构（顺序表）/动态数组基址/表的长度/顺序查找int Search_Seq(SSTable ST,ElemType key)int i;for

3、(i=0;iST.TableLen&ST.elemii!=key;+i);/查找成功，则返回元素下标；查找失败，则返回return i=ST.TableLen?-1:i;查找目标:ITableLen=110 1 2 3 4 5 6 7 8 9 10 11 12 13查找成功顺序查找的实现typedef structElemType*elem;int TableLen;SSTable;/查找表的数据结构（顺序表）/动态数组基址/表的长度/顺序查找int Search_Seq(SSTable ST,ElemType key)int i;for(i=0;iST.TableLen&ST.elemi!=

4、key;+i);/查找成功，则返回元素下标；查找失败，则返回-2return i=ST.TableLen?-1:i;查找目标:TableLen=110 1 2 3 4 5 6 7 8 9 10 11 12 13第 3 页 共 9 页顺序查找的实现typedef structElemType*elem;in t TableLen;SSTable;查找表的数据结构（顺序表）/动态数组基址/表的长度/顺序查找in t Search_Seq(SSTable ST,ElemType key)in t i;fo r(i=0;iST.TableLen&ST.elem ii!=k e y;+i);/查找成功，

5、则返回元素下标；查找失败，则返回return i=ST.TableLen?-1:i;TableLen=11顺序查找的实现（哨兵）typedef structElemType*elem;in t TableLen;SSTable;/查找表的数据结构（顺序表）/动态数组基址/表的长度/顺序查找int Search_Seq(SSTable ST,ElemType key)ST.elem0=key;int i;0号位置存“哨兵”fo r（i=ST.TableLen;ST.elemi!=key;-i）;从后往前找return i;查找成功，则返回元素下标；查找失败，则返回0数据从下标1开始存TableL

6、en=1116 33 10 13 29 I 16 19 3243 41370 1 2 3 4 5 6 7 8 9 10 11 12 13第 4 页 共 9 页顺序查找的实现（哨兵）typedef structElemType*elem;in t TableLen;SSTable;查找表的数据结构（顺序表）/动态数组基址/表的长度/顺序查找int Search_Seq(SSTable ST,ElemType key)ST.elem0=key;int i;/哨兵 V0号位置存“哨兵”for(i=ST.TableLen;ST.elemi!=key;i);从后往前找顺序查找的实现（哨兵）typedef

7、 structElemType*elem;in t TableLen;SSTable;/查找表的数据结构（顺序表）/动态数组基址/表的长度/顺序查找int Search_Seq(SSTable ST,ElemType key)ST.elem0=key;int i;0号位置存“哨兵”fo r(i=ST.TableLen;ST.elemi!=key;-i);从后往前找查找成功第 5 页 共 9 页顺序查找的实现（哨兵）typedef structElemType*elem;int TableLen;SSTable;查 找 表 的 数 据 结 构（顺 序 表）/动 态数组基址/表的长度/顺序查找in

8、t Search_Seq(SSTable ST,ElemType key)ST.elem0=key;int i;0号位置存“哨兵”for(i=ST.TableLen;ST.elemi!=key;i);从后往前找顺序查找的实现（哨兵）typedef structElemType*elem;int TableLen;SSTable;顺序查找int Search_Seq(SSTableST.elem0=key;int i;ST,ElemType key)/哨兵/查 找 表 的 数 据 结 构（顺 序 表）/动态数组基址/表的长度fo r（i=ST.TableLen;ST.elemi!=key;-i）

9、;从后往前找return i;查 找 成 功，则返回元素下标；查找失败，则返回00 1 2 3 4 5 6 7 8 9 10 11 12 13卜查找失败第6页 共9页查找效率分析0 12 35 6 7 8 9 10 11 12 13查找成功1+2 +3 +.+1 ASL成 -=ASL=Y P CZ=1 1TableLen=11ASL失败;n+1顺序查找的优化（对有序表）查找表中元素有序存放（递增/递减）查找目标:2113 I 19 I 29 I 37 I 43第 7页 共 9页顺序查找的优化（对有序表）查找表中元素有序存放（递增/递减）用查找判定树分析ASL一个成功结点的查找长度=自身所在层数

10、一个失败结点的查找长度=其父节点所在层数默认情况下，各种失败情况或成功情况都等概率发生第8页 共9页顺序查找的优化（被查概率不相等）被查概率7:15%13:5%19:10%29:40%37:28%43:2%13 I 19 I 29 I 37 I 43ASL成 功=1*0.15+2*0.05+3*0.1+4*0.4+5*0.28+6*0.02=3.67nASL=Y Pi Ci=1被查概率大的放在靠前位置 H 29 I 37 I 7 I 19 I 13 I 43ASL成 功=1*0.4+2*0.28+3*0.15+4*0.1+5*0.05+6*0.02=2.18知识回顾与重要考点*顺序查找第9页 共9页