数据结构 第9章 查找1-静态查找表.ppt

第9章查找数据结构讲义-——若表中存在特定元素,称查找成功,应输出该记录;——否则,称查找不成功(也应输出失败标志或失败位置)查找表查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字——由同一类型的数据元素(或记录)构成的集合。——查询(Searching)特定元素是否在表中。——只查找,不改变集合内的数据元素。——既查找,又改变(增减)集合内的数据元素。——记录中某个数据项的值,可用来识别一个记录(预先确定的记录的某种标志)——可以唯一标识一个记录的关键字例如“学号”例如“女”是一种数据结构——识别若干记录的关键字(2)对查找表常用的操作有哪些?查询某个“特定的”数据元素是否在表中;查询某个“特定的”数据元素的各种属性;在查找表中插入一元素;从查找表中删除一元素。(3)有哪些查找方法?查找方法取决于表中数据的排列方式;讨论:(1)查找的过程是怎样的?给定一个值K,在含有n个记录的文件中进行搜索,寻找一个关键字值等于K的记录,如找到则输出该记录,否则输出查找不成功的信息。例如查字典针对静态查找表和动态查找表的查找方法也有所不同。“特定的”=关键字明确:查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度(ASL:averagesearchlength)。其中:n是文件记录个数;Pi是查找第i个记录的查找概率(通常取等概率,即Pi=1/n);Ci是找到第i个记录时所经历的比较次数。统计意义上的数学期望值物理意义:假设每一元素被查找的概率相同,则查找每一元素所需的比较次数之总和再取平均,即为ASL。显然,ASL值越小,时间效率越高。(4)如何评估查找方法的优劣?针对静态查找表的查找算法主要有:。一、顺序查找(线性查找)二、折半查找(二分或对分查找)三、静态树表的查找四、分块查找(索引顺序查找)一、顺序查找(Linearsearch,又称线性查找)(1)顺序表的机内存储结构:typedefstruct{ElemType*elem;//表基址,0号单元留空。表容量为全部元素intlength;//表长,即表中数据元素个数}SSTable;顺序查找:即用逐一比较的办法顺序查找关键字,这显然是最直接的办法。对顺序结构如何线性查找?见下页之例或教材P216;对单链表结构如何线性查找?函数虽未给出,但也很容易编写;只要知道头指针head就可以“顺藤摸瓜”;对非线性树结构如何顺序查找?可借助各种遍历操作!(2)算法的实现:技巧:把待查关键字key存入表头或表尾(俗称“哨兵”),这样可以加快执行速度。例:若将待查找的特定值key存入顺序表的首部(如0号单元),则顺序查找的实现方案为:从后向前逐个比较!intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中,查找关键字与key相同的元素;若成功,返回其位置信息,[0].key=key;//设立哨兵,可免去查找过程中每一步都要检测是否查找完毕。当n>1000时,查找时间将减少一半。for(i=;[i].key!=key;--i);//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)returni;//若到达0号单元才结束循环,说明不成功,返回0值(i=0)。成功时则返回找到的那个元素的位置i。}//Search_Seq算法演示——返回特殊标志,例如返回空记录或空指针。前例中设立了“哨兵”,[0].key使之结束并返回i=0。讨论②查找效率怎样计算?——用平均查找长度ASL衡量。讨论①查不到怎么办?讨论③如何计算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的范围,直到查找成功或失败为止。对顺序表结构如何编程实现折半查找算法?——见下页之例,或见教材(P219)对单链表结构如何折半查找?——无法实现!因全部元素的定位只能从头指