2024新粤教版（2019）《高中信息技术》选择性必修第一册第五章 数据结构的应用 ppt课件(共36张PPT).pptx

1、数据结构的应用查找和排序，与我们的学习、生活息息相关。如从字典 中查找汉字，从电话号码本中查找电话，在图书馆中查找图 书，高考查询成绩等；教师按身高来安排学生的座位，大学 按照高考成绩高低顺序录取新生，网上商城按照销量高低排 序来推荐商品等。在信息时代，数据的增长速度越来越快，导致信息量呈几何级的增长。在庞大的数据里进行人工查找和排序是非常困难的，甚至是无法办到的，所以必须依靠计 算机才能快速、准确地对数据进行查找和排序。5.1迭代与递归在利用计算机解决实际问题中，迭代和递归都是非常实用的算法，很多难的问题都是通过迭代或递归算法解出来的。1迭代法迭代法是用计算机解决问题的一种基本方法。它利用计

2、算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令（或一定步骤），在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。int n,sum=0;/sum初始化为0 for(int i=1;i=3)算法分析：设f(n)表示第n个月的兔子对数，先看前几个月的情况：第一个月有一对 刚出生的兔子，即f(1)=1；第二个月，这对兔子长成成年兔，兔子对数还是只有1对，即f(2)=1；第三个月，这对成年兔生出一对小兔，共有两对兔子，即f(3)=2；第四个月，成年兔又生出一对小兔，第三个月出生的兔子长成成年兔，共有三对兔子，即f(4)=3；第五个月，原成年兔又生出一对小兔，新成年兔

3、也生出一对小兔，共有五对兔子，即 f(5)=5以此类推，每个月兔子数为1，1，2，3，5，8，13，21，转化为数学模型，设f(n)为第n个月的兔子对数，则有：下面是实现求一年后繁殖的兔子总数的核心代码，其中f1、f2、fn这三个迭代变量分别代表前两个月、前一个月、当前月的兔子数，用迭代关系式“fn=f1+f2;”计算当月的兔子数，再用“f1=f2;f2=fn;”为下一个月的迭代计算做好准备。int f1=1,f2=1,fn=0;/迭代变量 for(int i=3;i=12;i+)/用i的值来控制迭代的次数 fn=f1+f2;/计算当月数量 f1=f2;/f1、f2迭代计算，为下个月迭代赋初值

4、 f2=fn;每个月的兔子对数组成数列：1，1，2，3，5，8，13，21，34，55，89，144，此数列也称为斐波那契数列。5.1.2递归1递归的基本概念若一个对象用自己来定义自己或部分地包含自己，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归过程。在程序设计中，函数直接调用函数本身，称为直接递归调用直接递归调用；在函数中调用其他函数，其他函数又调用原函数，构成了函数自身的间接调用，则称为间接递归调用间接递归调用。2递归在数学中的应用:在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列，即通过初值及与

5、前面临近几项之间的关系来描述。要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，二是数列间各项一是最前面几项的数值，二是数列间各项的关系。的关系。这是递归函数的最简单形式，从中可以明显看出递归函数一般的写法特点：先处理一 些特殊情况（递归终结条件），再处理递归关系。递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作 为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。3递归算法的思想与应用（1）递归算法的思想。为求解一个不能或不好直接求解的“大问题”，设法将它分解成规模较小但解法相同的“小问题”，并且这些“小问题”也能

6、采用同样的分解方法再分解成规模更小的“小问题”，当规模最小的一个或几个值能直接得出解时，再利用这些“小问题”的解构造出“大问题”的解。（2）递归算法解决问题的特点。递归算法有四个特性：必须有明确的递归终结条件，否则程序将陷入无穷循环而造成栈溢出。子问题在规模上比原问题小，或更接近终止条件。子问题可通过再次递归调用求解或因满足终止条件而直接求解。子问题的解应能组合为整个问题的解。（3）递归算法一般用于解决的三类问题。数据的定义是按递归定义的。如数学上常用的阶乘数列、斐波那契数列、幂函数等，它们的定义都是递归的。问题方便用递归算法实现。有些问题用递归方法实现更方便，如求阶乘函数的值。数据的结构形式

7、是按递归定义的。如链表、树的遍历、图的搜索等。5.2查找在日常生活和学习中，我们经常要进行查找工作，例如从字典中查找汉字、单词，从电话号码本中查找电话，在图书馆中查找图书，高考查询成绩等。其实，“电话号码本”“字典”等都可以看作一张表，查找则是在一个含有众多数据元素（或记录）的表中找出某个特定的数据元素（或记录）。在信息时代，由于信息量巨大，人工查找是非常困难的，甚至是无法办到的，所以必须依靠计算机才能快速、准确地查找信息。5.2.1 顺序查找顺序表是指采用顺序存储的方式存储的集合或线性表。在本章，我们主要探讨一维数 组这种顺序表的顺序查找和二分查找方法。顺序查找也称为线性查找，它的基本思想是

8、：从顺序表的一端开始，将每个元素的关 键字与给定值k进行比较，如果相同，则表明查找成功，返回该元素的下标；如果在所有 元素都进行了比较后，仍找不到关键字为k的元素，则表明查找失败，返回特定值-1。在超市中，要实现查询某商品在哪个货架，我们可以用数组存储商品的编号、存放的 货架等信息。程序运行时，输入需查询商品的编号，然后在数组中依次查找编号，就可查找出该商品的信息，方便顾客查找商品。下面是顺序查找算法的核心代码：5.2.2 二分查找顺序查找虽然能帮助顾客查找到所需信息，但由于超市销售的商品种类繁多，数据量比较大，而顺序查找每次都要从头到尾去查找，需要花费不少时间，很多顾客没有耐心长时间等待查询

9、结果。所以查找的速度必须要快，可以考虑用查找速度更快的二分查找来实现。二分查找又称折半查找，是针对顺序存储的有序表（有序表是指各元素按关键字的值以升序或降序存放的表）进行的查找，它是一种较常用的查找方法。在按升序存储的顺序表a中查找k，其二分查找算法流程如下：（1）选取查找范围a0an-1。（2）选定查找范围的中点元素amid，与k值比较。（3）若相等，则查找成功，返回该元素的下标。（4）若k amid，则将范围缩小到右子表amid+1an-1。（6）迭代以上过程，直到找到k或当前查找区间为空（即查找失败）。对比解决同一个问题，我们可以用不同的算法编写程序，不同的算法对数据结构的要求可 能是不

10、同的。对比顺序查找与二分查找算法，当数据量较大时，二分查找会比顺序查找快 很多，这是它的主要优点，但它要求查找表是有序的，所以在进行二分查找之前，必须先 对查找表进行排序。另外，二分查找要求表是顺序存储顺序存储的，为保持表的有序性，在进行插 入、删除操作时，都必须移动大量记录。因此，二分查找的高查找效率是以排序为代价 的，所以它特别适合一经建立就很少移动而且经常需要查找的线性表。了解不同算法的特点，可以帮助我们在解决实际问题时，从不同的算法中选择出较为 合适的一种，或对现有算法进行改进或创新，从而设计出更好的算法5.3排序排序与我们的日常生活息息相关。例如，教师按身高来安排学生的座位，试卷和答

11、题 卡按从小号到大号的顺序来整理，各类比赛按成绩的高低来排名，查询火车票时会按照出 发的先后来显示，到网上购物会参考销量高低来排序购买等。排序是数据处理和分析中最 常用的运算之一，它往往可以提高数据处理的效率；排序也是最基本的算法之一，其他很 多算法都是以排序算法为基础，所以研究和掌握排序算法是非常重要的。在信息时代，面 对庞大的信息量，想要靠人工进行排序，会耗费大量时间和精力，甚至无法完成。所以，依靠计算机快速、准确地对数据进行排序，是很有必要的。5.3.1 认识排序1排序排序是指把一个任意序列的数据元素重新排列成按照某关键字递增或递减序列的过程。作为排序依据的数据项称为排序关键字，简称关键

12、字（Key）。排序时选取哪一个数据项作为关键字，应根据具体情况而定。2排序的分类假定在待排序的序列中，存在多个具有相同键值的数据元素，若经过排序，这些数据元素的相对次序仍然保持不变，则称这种排序是稳定的排序；否则，称这种排序是不稳定的排序。例如以表5-3中的“销售数量”来排列名次：待排序的序列：2510171310376/给其中一个“10”加底色以区分稳定的排序：6101013172537/因为10还是在 10 的前面不稳定的排序：6101013172537/因为10已在 10 的后面在排序过程中，可以使用内存储器，也可以使用外存储器。如果参加排序的数据元素的数量不多，能够全部调入内存中进行排

13、序，则称这种排序为内部排序；若参加排序的数据元素的数量较大，需要分批调入内存中进行排序，排序后再分批存回外存储器，则称这种排序为外部排序。2排序的分类内部排序的方法很多，按照排序过程中所用策略的不同，通常分为五大类：插入排序、选择排序、交换排序、归并排序和基数排序。其中，交换排序又包含冒泡排序和快速排序，都是常用的排序算法。冒泡排序是一种简单、常见的排序算法，适合初学者学习；快速排序是对冒泡排序的改进，它是目前内部排序中平均速度最快的排序算法，也是20世纪十大算法之一。3排序的存储结构排序的方法很多，通常都要进行两种基本操作：（1）比较两个元素关键字的大小。（2）根据比较结果，将元素从一个位置

14、移到另一个位置。其中，第（1）种操作对大多数排序方法来说都是必要的，第（2）种操作可通过改变元素的存储方式，比如采用链表存储结构存储的数据元素。从操作角度看，排序是线性结构的一种操作，待排序元素可以用顺序存储结构和链式存储结构来存储。在顺序存储结构中，待排序元素按自然顺序存放在连续的一块内存空间中，元素之间的次序关系由其存储位置决定，所以排序过程中一定要移动元素；在链式存储结构中，待排序元素按原始次序链接起来，排序时只需要修改链表指针，不用移动元素。5.3.2 冒泡排序冒泡排序（Bubble Sort）是一种简单的交换排序算法，它是通过交换相邻的两个数据元素，逐步将待排序列变成有序序列。它的基

15、本思想如下：（1）假设待排序元素有n个，从第一个元素开始，依次交换相邻的两个逆序元素，直到最后一个元素为止，当第一趟排序结束，就会将最大（小）的元素移动到序列的末尾。（2）然后按照以上方法进行第二趟排序，次大（小）的元素将会被移动到序列的倒数第二个位置。（3）依次类推，经过n-1趟排序后，整个元素序列就成了一个有序（升序或降序）的序列。每趟排序过程中，值小（大）的元素向前移动，值大（小）的元素向后移动，就像气泡一样向上升，因此将这种排序方法称为冒泡排序。最少比较n-1次，最多比较n（n-1）/2次次数？例5：假设有五个元素的待排序列为25、10、17、37、13，将此序列按升序排序的冒泡排序过

16、程如图5-7所示。例5：假设有五个元素的待排序列为25、10、17、37、13，将此序列按升序排序的冒泡排序过程如图5-7所示。5.3.3 快速排序1快速排序的基本思想快速排序采用分治法的策略：将原问题划分成规模更小但与原问题相似的小问题，然后用递归法解决这些小问题，最后将它们组合形成原问题的解。以关键字升序排列为例，设待排序列存放在数组a1.n中，n为元素个数，i、j分别是待排序列首尾关键字的下标，初值分别为1和n，令a1作为基准元素赋给pivotkey：（1）j从右往左扫描，若i=pivotkey，j=j-1，否则将aj与ai交换。（2）i从左往右扫描，若ij且ai.key pivotke

17、y，i=i+1，否则将ai 与aj 交换。（3）重复执行（1）和（2），直到出现ij，则将基准元素pivotkey移动到ai中。此时整个元素序列在位置i被划分成两个部分，前一部分的元素关键字都小于或等于ai.key，后一部分元素的关键字都等于或大于ai.key，即完成了一趟快速排序。（4）继续对分割后的子表进行上述划分，直至所有子表的表长不超过1为止，此时的元素序列就成了一个有序序列。5.3.3 快速排序例6：假设待排序列为39，26，54，83，91，47，18，32，用快速排序算法对该序列进行升序排序，第一趟快速排序的过程如图5-8所示，快速排序的全部过程如图5-9所示。选择法选择排序就是从a0开始依次和后面的元素进行比较，第一遍把a0及其以后中最小的筛选出来并将值赋给a0，第二遍把a1及其以后中最小的筛选出来并赋值，依次类推，内层循环的j=i+1是为了不让ai和本身比较而浪费时间,选择排序法是每个元素都要和比自己大的元素进行一次比较。总之：内循环每循环完一次就会就把最小的值给相应的ai