1、静态查找表 第九章查找 静态查找表的ADT 静态查找表是一种最简单的查找表 Specification ADT Static Search Table Elements:査找表中的数据元素类型相同,每一数据元素 都存在一个能唯一标识该元素的关键字 Structure:查找表中的n个数据元素具有相同类型,属于一 同一集合。数据元素之间不存在结构关系 Operation: Create(ST,n)生成操作:产生一个含用户给定的n个数据 元素的表ST Search(ST,K)查找函数:若表ST中存在其关键字等于给 定值K的数据元素,则函数值为该元素在表中的位 置;否则函数值为“空”。 Traverse(ST)输出操作:按某种次序输出表ST中所有数 据元素
第九章 查找 第6页 1、静 态 查 找 表 静态查找表的ADT 静态查找表是一种最简单的查找表。 Specification ADT Static_Search_Table Elements：查找表中的数据元素类型相同，每一数据元素 都存在一个能唯一标识该元素的关键字 Structure：查找表中的n个数据元素具有相同类型，属于 同一集合。数据元素之间不存在结构关系 Operation： Create(ST,n) 生成操作：产生一个含用户给定的n个数据 元素的表ST。 Search(ST,K) 查找函数: 若表ST中存在其关键字等于给 定值K的数据元素，则函数值为该元素在表中的位 置；否则函数值为“空”。 Traverse(ST) 输出操作：按某种次序输出表ST中所有数 据元素
+顺序(线性)表的查找一顺序查找 第九章查找 顺序(线性)表的查找是一种最简单的查找方法。它的 算法基本思想是: 从表的一端开始,顺序地扫描线性表,依次将扫描到的 关键字和给定值相比较,若当前扫描到的记录的关键字 与给定值相等,则查找成功,找到所查记录;若直至扫 描结束,仍未找到其关键字与给定值相等的记录,则查 一找不成功。 既适用于线性表的顺序存储结构,也适用于线性表的链 式存储结构。若使用单链表作存储结构时,扫描必须从第 一个结点开始。若以向量作存储结构,则可从前往后或从一 后往前进行扫描
第九章 查找 第7页 顺序(线性)表的查找——顺序查找 顺序（线性）表的查找是一种最简单的查找方法。它的 算法基本思想是： 从表的一端开始，顺序地扫描线性表，依次将扫描到的 关键字和给定值相比较，若当前扫描到的记录的关键字 与给定值相等，则查找成功，找到所查记录；若直至扫 描结束，仍未找到其关键字与给定值相等的记录，则查 找不成功。 既适用于线性表的顺序存储结构，也适用于线性表的链 式存储结构。若使用单链表作存储结构时，扫描必须从第 一个结点开始。若以向量作存储结构，则可从前往后或从 后往前进行扫描
顺序(线性)表的查找 第九章查找 顺序表的查找算法描述 typedef struct i ElemType elem[li int Length }ssTab1e; nt8 research(s9ab1est, keytype k)中的序号,i值为零表明查 /*K为给定值,返回为关键字等于K的记录在表st 找不成功*/ st,e1em[01.key=K;//设置监视赠 for( i=st length; !EQ( st elem[i]. key, key )il-- /从表尾开始向前扫描 七urni //返回找到的位置 }//算法9.1
第九章 查找 第8页 顺序表的查找算法描述 typedef struct { ElemType elem[]; int Length; }SSTable; 顺序（线性）表的查找 int seqsearch( SSTable st, keytype k ) {/*K为给定值，返回i为关键字等于K的记录在表st中的序号，i值为零表明查 找不成功*/ st.elem[0].key = K; //设置监视哨 for( i = st.length; !EQ( st.elem[i].key, key ); i--) //从表尾开始向前扫描 return i; //返回找到的位置 } //算法 9.1
顺序(线性)表的查找 第九章查找 算法性能分析 ASL=∑PC ASLsS=nP+(n-DP+.+2P-+P (9-2 若查找每个记录时是等概率,则有ASLs(n+1)2
第九章 查找 第9页 算法性能分析 ASLSS = nP1 + n − P2 + + 2Pn−1 + Pn ( 1) 若查找每个记录时是等概率，则有 ASLss=(n+1)/2 顺序（线性）表的查找 (9-2)
顺序(线性)表的查找 第九章查找 如果考虑到不成功的查找,则查找算法的平均查找长度应是 查找成功时的平均长度与查找不成功时的平均查找长度之和。若 假设查找成功与不成功的可能性相同,对每个记录的查找概率也 相等,即p=1。由于查找不成 功的比较次数总是n+1,故顺序查找的平均查找长度为 ASD Ss ∑(n-t+1)+n·(n+1) 2n j 72 n+1n+1 4 3 (n+1) 9-4) 4 第10页
第九章 查找 第10页 如果考虑到不成功的查找，则查找算法的平均查找长度应是 查找成功时的平均长度与查找不成功时的平均查找长度之和。若 假设查找成功与不成功的可能性相同，对每个记录的查找概率也 相等，即 。由于查找不成 功的比较次数总是n+1，故顺序查找的平均查找长度为 顺序（线性）表的查找