计算机软件技术基础86424.pptVIP

计算机软件技术基础 数据结构与算法（5） * 数据结构研究的内容 2.5 查找 基本概念 ——若表中存在特定元素，称查找成功（应输出该记录） ——否则，称查找不成功（也应输出失败信息） 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询(Searching)特定元素是否在表中。 ——只查找，不改变集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 （预先确定的记录的某种标志 ） 例如“学号” 是一种数据结构 讨论2：对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中； 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。 讨论3：有哪些查找方法？查找方法取决于表中数据的排列方式; 讨论1：查找的过程是怎样的？给定一个值K，在含有n个记录的文件中进行有哪些信誉好的足球投注网站，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。 例如查字典 针对静态查找表和动态查找表的查找方法也有所不同。 “特定的”=关键字 讨论4：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度ASL。 其中： n是文件记录个数； pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; ci是找到第i个记录时所经历的比较次数。 统计意义上的数学期望值 物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。 显然，ASL值越小，时间效率越高。 Average Search Length 一、顺序查找（ Linear search，又称线性查找 ）顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直接的办法。假定记录按逻辑次序顺序存储在一个连续存储区中，n个记录用数组R[1..N] 表示，用C语言说明如下：#define N 100 //数组长度常量 typedef int keytype; //关键字类型定义 typedef struct{keytypekey; //关键字数据项othertype otherdata; //其他数据项 } Element; //数据元素类型定义 typedef Element Sqlist[N+1]; //数组定义 int Seq_Search (Sqlist R , KeyType k ){ int i; R[0].key =k; for( i=n; ST.elem[i].key!=k; i - - );return i; } // Search_Seq 算法的实现： 技巧：把待查关键字key存入表头或表尾（俗称“监视哨”），这样可以加快执行速度。 例： 若将待查找的特定值key存入顺序表的首部（如0号单元），并从后向前逐个比较，就不必担心“查不到”。 //在顺序表R中，查找关键字与k相同的元素；若成功，返回其位置信息，否则返回0 //设立监视哨，可免去查找过程中每一步都要检测是否查找完毕。当n1000时，查找时间将减少一半。 //找不到=不成功，返回值必为i=0； //找得到=成功，返回值i正好代表所找元素的位置。 监视哨在顺序表的首部，所以扫描的方向必须是从后向前。返回特殊标志，例如返回空记录或空指针。前例中设立了“监视哨”，就是将关键字送入ST.elem[0].key使之结束，并返回 i=0。 讨论2：查找效率怎样计算？用平均查找长度ASL衡量。 讨论1：查找失败怎么办？ 讨论3：如何计算ASL？分析：查找第1个元素所需的比较次数为1；查找第2个元素所需的比较次数为2；……查找第n个元素所需的比较次数为n；总计全部比较次数为：1＋2＋…＋n = (1+n)n/2 未考虑查找不成功的情况：查找监视哨所需的比较次数为n+1 这是查找成功的情况 若求某一个元素的平均查找次数，还应当除以n（等概率）， 即：ASL＝(1＋n) / 2 ，时间效率为 O(n) 二、折半查找（又称二分查找或对分查找） 优点：算法简单，且对顺序结构或链表结构均适用。 缺点： ASL 太大，时间效率太低。这是一种容易想到的查找方法。先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。 对顺序表结构如何编程实现折半查找算法？——见下页之例，或见教材（P113） 对单链表结构如何折半查找？——无法实现！因全部元素的定位只能从头指针head开始 对非线性(树)结构