数据结构基础ppt课件.ppt

《数据结构基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.3数据结构基础第30讲程序设计与软件开发基础(三)7.3.6查找7.3.7排序掌握顺序查找与二分法查找算法，能利用基本排序算法解决实际问题。教学目标及基本要求第30讲程序设计与软件开发基础(四)教学重点基本排序算法。教学难点基本排序算法。第30讲程序设计与软件开发基础(四)查找排序教学内容第30讲程序设计与软件开发基础(四)1学时教学时间第30讲程序设计与软件开发基础(四)查找是指在一个给定的数据结构中查找某个指定的元素。通常，应根据不同的数据结构采用不同的查找方法。7.3.6查找顺序查找又称顺序搜索。顺序查找一

2、般是指在线性表中查找指定的元素，其基本方法如下：用待查找的关键码值与线性表中各元素的关键码值逐个比较，若找出相等的则查找成功，否则查找失败。7.3.6查找1．顺序查找顺序查找的优点：对线性表的元素逻辑次序无要求（即不必按关键码值排序），对线性表的存储结构无要求（即顺序存储，链式存储皆可）。顺序查找的缺点：平均检索长度大，大约要与线性表中一半的元素进行比较。对于线性表为无序表和有序线性表采用链式存储结构，则只能用顺序查找。顺序查找二分查找是一种效率较高的线性表查找方法，它只适合用于顺序存储的有序表，即线性表中的元素必须

3、按值排好顺序，且以顺序存储方式存储。7.3.6查找2．二分查找二分查找的方法是：首先用要查找的关键码值与线性表中间位置的元素的关键码值比较，比较相等则查找结束，不等则根据比较的结果确定下一步是在线性表的前部，还是后部；按前述方法进行，如此进行下去，直到找到为止，否则在线性表中找不到该关键码值。二分查找【例7.5】设被检索的线性表关键码序列为061、087、154、170、275、426、503、509、512、612、677、703、765、897、908。现在要检索关键码为612的节点，用“［　　］”括住本次检索的

4、子表，用“”指向该子表的中间节点，即本次参加比较的关键码。请画出检索过程，求出比较的次数。例题061[087154170275426503509512612677703765897908]061[087154170275426503509512612677703765897908]061[087154170275426503509512612677703765897908]图7-16二分查找1、检索过程2、比较次数：3二分查找的优点是：平均检索长度小，为log2n。二分查找的缺点是：排序线性表花费时间，顺序方式存储插

5、入、删除不便。二分查找排序是指将一个无序序列整理成按值非递减顺序排列的有序表，排序可以在各种不同的存储结构上实现。7.3.7排序交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。常用的有冒泡排序法和快速排序法。7.3.7排序1．交换排序法冒泡排序的基本方法是：将待排序的元素顺序两两比较，若为逆序，则进行交换。将序列照此方法从头至尾处理一遍称作一趟冒泡，一趟冒泡的效果是将元素关键值最大的元素交换到最后的位置，即该元素的排序最终位置。若某一趟冒泡过程中没有任何交换发生，则排序过程结束。交换排序法（1）冒泡排序

6、法对n个元素进行排序最多需要n1趟冒泡。冒泡排序法【例7.6】设待排序序列的关键码为：38、19、67、15、99、45、94、2、76。画出冒泡排序过程，并求出即本次参加比较的关键码。请画出检索过程，求出冒泡的趟数。例题图7-17冒泡排序1、比较过程2、冒泡趟数：7初始：38196715994594276第1趟：19386715156799994594992997699第2趟：1938153867456794294769499第3趟：第4趟：第5趟：第6趟：第7趟：191519384567267769499769

7、4991915193845456727694996715193823845769499674515192193876949967453821519快速排序又称为分区交换排序，是对冒泡排序的一种改进。其基本方法是：在待排序序列中任取一个元素，以它为基准值，用交换的方法将所有元素分成两部分，比它小的在一个部分，比它大的在另一个部分，再分别对两个部分实施上述过程，一直重复到排序完成。交换排序法（2）快速排序法常用的插入类排序法有：简单插入排序法和希尔排序法。7.3.7排序2．插入类排序法简单插入排序法是最简单直观的排序方法

8、，其基本方法是：每步将一个待排序元素按其关键码值的大小插入到前面已排序文件中的适当位置上，直到全部插入为止。对n个元素进行简单插入排序，需要执行n(n1)次比较。插入类排序法（1）简单插入排序法【例7.7】设待排序序列的关键码为：8、3、2、5、9、1、6，执行简单插入排序的过程例题图7-18简单插入排序1、插入过程8325916初始化：[]