NCRE公共基础知识教案(第1章).doc

【教学课题】算法（第1章 数据结构，第1节）【目的要求】掌握算法的概念，算法的特点，理解算法时间复杂度和空间复杂度的含义，掌握时间复杂度的计算方法。【教学重点】算法的概念，算法特点，时间复杂度的概念和计算【教学难点】时间复杂度的概念和计算【方法与手段】讲授+多媒体演示【作业布置】1、什么是算法，算法的特征有哪些？2、算法的基本要素有哪些？3、什么是算法的时间复杂度和空间复杂度？第1章 数据结构和算法1.1 算法一、算法（Algorithm）（P1）1、基本概念解题方案准确而完整的描述（为解决某个问题而采取的方法和步骤）。（不受机器、程序设计语言、编程者等因素的限制，不等于程序，但程序可以看作是算法的一种描述，程序算法+数据，更具体说：程序算法+数据结构+程序设计方法+语言和环境）2、基本特征（1）可行性（算法中每个步骤必须有效可行，如a/b，其中b不能为零）（2）确定性算法中每个步骤都有明确的意义，不允许模棱两可，不允许歧义。（3）有穷性（避免进入无限循环）算法中的操作必须在有限时间内完成。如：循环必须有终止条件。（4）拥有足够的情报（算法中运算对象必须有初值，可以输入，也可直接赋值，必须输出）3、算法基本要素（P2）（1）对数据的运算和操作基本的运算有：算术运算（加、减、乘、除等）、逻辑运算（与、或、非等）、关系运算（大于、小于、等于、不等于等）、数据传输（赋值、输入、输出等）（2）算法的控制结构算法中各操作之间的执行顺序（顺序结构、选择结构、循环结构）4、算法设计基本方法（P3）（1）列举法根据问题，列举所有可能情况。如：从一个地方到达另一个地方的途径。（2）归纳法根据少量情况，分析归纳，得出一般关系。如：找出数列中的通项式。（3）递推法从已知初始条件出发，逐步推出所有中间结构和最后结果。如：案件侦破中根据以有线索进行的推理。本质上是归纳。（4）递归法将复杂的问题一层层进行分解，最后归结为一些简单的问题，然后将简单的问题解决，再沿着分解的逆过程逐步进行综合，将最初的问题解决。如：求n！,可用n！n*（n-1）!递归调用来实现。递归法分为直接递归和间接递归。递归的基础也是归纳。（5）减半递推技术又叫分治法，重复将问题的规模减半。如：设方程f（x）0在区间a，b上的实根，且f（a）与f（b）异号，利用二分法求方程在a，b上的根。减半递推法也是归纳法的一个分支。（6）回溯法也叫试探法，基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。二、算法复杂度（P5）（算法复杂度包括：时间复杂度和空间复杂度）1、时间复杂度（1）概念所谓时间复杂度是指执行算法所需要的计算工作量。（2）计算方法在实际中常用算法中所需基本运算的执行次数来度量算法的计算工作量，即时间复杂度。算法所执行的基本运算次数还与问题的规模有关，是问题规模的函数，记作：算法的工作量f（n）,其中n是问题的规模。通常也记为：T（n）（f（n）(3)举例如下三个程序段：A、+x;s=0;、for(i=1;i=n;i+)+x;s+=x;、for(j=1;j=n;j+) for(k=1;k1，则该结点的父结点编号为INT(k/2)。 若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（当然也没有右子结点） 若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。三、二叉树的存储结构（通常采用链式存储结构）（P36）1、概述：（1）存储形式：常采用链式存储结构（2）构成：数据域：存放结点的数据值。左子针域：存储该结点的左子结点的存储地址指针域：右指针域：存储该结点的右子结点的存储地址第i个结点的存储结构如下：LchildValueRchildiL(i)V(i)R(i)（3）说明：二叉树的链式存储结构也称为二叉树的链表，简称二叉链表。在二叉树在存储中，用一个头指针（BT）指向二叉树的根结点的存储地址。2、举例ABCDEFGHIJKLMNOPQR有如下图所示的二叉树（按层次将所有结点顺序编号）：A1B2C3D4E5F6G7H8I9J10K11L12M13N14O15P16Q17R18BT其二叉链表的逻辑状态如下图所示（BT为二叉链表的头指针，指向二叉树的根结点，字母后的数字为结点的序号）：其二叉链表的物理状态如下图所示：iL(i)V(i)R(i)BT12A324B536C748D9510E11612F13714G15816H17918I0100J0110K0120L0130M0140N0150O0160P0170Q0180R0四、二叉树的遍历（P38）1、概念所谓二叉树的遍历就是指不重复访问二叉树中所有的结点。2、二叉树遍历的种类（3种）（1）前序遍历（DLR，根左右）A、前序遍历规则：先访问根结点，然后遍历左子树，最后遍历右子树。并且，在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。B、具体操作如下：如果：二叉树为空，则结束返回。否则：访问根结点前序遍历左子树前序遍历右子树 C、前序遍历二叉树的过程是一个递归过程，得到的结果称为前序序列。（2）中序遍历（LDR，左根右）A、中序遍历规则：先遍历左子树，然后访问根结点，最后遍历右子树。并且，在遍历左子树和遍历右子树时，依然是先遍历左子树，然后是根结点，再是右子树。B、具体操作如下：如果：二叉树为空，则结束返回。否则：中序遍历左子树访问根结点 中序遍历右子树 C、中序遍历二叉树的过程是一个递归过程，得到的结果称为中序序列。（3）后序遍历（LRD，左右根）A、后序遍历规则：先遍历左子树，然后遍历右子树，最后访问根结点。并且，在遍历左子树和遍历右子树时，依然是先遍历左子树，然后是右子树，再是根结点。B、具体操作如下：如果：二叉树为空，则结束返回。否则：后序遍历左子树后序遍历右子树访问根结点 C、后序遍历二叉树的过程是一个递归过程，得到的结果称为后序序列。（所谓的前、中、后序遍历主要是指访问根结点的顺序，至于左右子树总先左后右）【教学课题】查找技术（第1章 数据结构，第7节）【目的要求】了解两种查找方法的适应范围，掌握其查找的思路，理解两种查找方法不同的查找效率，做到在不同的场合使用不同的查找方法得出结果。【教学重点】查找方法的具体思路，查找效率的对比【教学难点】两种查找方法的具体应用（程序实现）【方法与手段】讲授+多媒体演示【作业布置】1、有15个数按从小到大的顺序存放在数组中，输入一个数，要求用折半查找法找出该数是数组中的第几个元素，如果该数不在数组中，则输出“此数不在数组中。”1.7 查找技术查找：所谓查找是指在一个给定的数据结构中查找某个给定的元素，最终的结果有查找成功和查找失败两种情况。一、顺序查找（又叫顺序搜索）1、适应范围：此方法适应于在线性表中查找指定元素。2、基本思路从线性表的第一个元素开始，与被查元素进行比较，相等则查找成功，否则继续向后查找。如果所有的元素查找完毕后都不相等，则该元素在指定的线性表中不存在（查找失败）。3、具体应用（在C中可用程序实现）例如，现有线性表：7、2、1、5、9、4，要在序列中查找元素6，查找的过程是：（1）整个线性表的长度为6；（2）查找计数器n，n=1时，将元素6与序列的第一个元素7比较，不等，继续查找；（3）n=2，将6与第二个元素2进行比较，不等，继续查找；（4）n=3，将6与第三个元素1进行比较，不等，继续查找；（5）n=4，将6与第四个元素5进行比较，不等，继续查找；（6）n=5，将6与第五个元素9进行比较，不等，继续查找；（7）n=6，将6与第六个元素4进行比较，不等，继续查找；（8）n=7，超出线性表的长度，查找结束，则该表中不存在要查找的元素。4、查找效率最高效率（最好情况）：如果第一个元素就是被查元素，则只需做一次比较就查找成功，这是顺序查找的最好情况，效率最高；最低效率（最坏情况）：如果最后一个元素才是被查元素或被查元素根本不在线性表中，则需要和线性表中的所有元素进行比较，这是顺序查找的最坏情况，效率最低；平均效率：平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中的一半元素进行比较。5、总结对于线性表而言，顺序查找的效率很低。但以下两种情况只能采用顺序查找：（1）线性表为无序表；（2）线性表为有序表，但采用链式存储结构保存数据。二、二分法查找（又叫折半查找，对分查找）1、适应范围：顺序存储的有序表。2、基本思路（以递增序列为例说明）将要查找的元素x与有序序列的中间元素进行比较：如果中间项的值等于x，则查找成功；否则：（1）如果x比中间元素大，则在线性表的后半部分（中间项以后的部分）以相同的方法进行查找；（2）如果x比中间元素小，则在线性表的前半部分（中间项以前的部分）以相同的方法进行查找；一直到查找成功或子表长度为0（说明线性表中没有要查找的元素），查找结束。3、具体应用有15个数按从小到大的顺序存放在数组中