搜索
第一章数据结构与算法一、教学目标1、了解算法的基本概念。2、了解数据结构的基本概念。3、了解线性表及其顺序存储结构。4、理解栈和队列的基础知识。5、了解线性链表。6、了解树与二叉树的基本概念，掌握二叉树的性质及遍历。7、了解查找技术。8、了解排序技术。二、教学方法1、重点内容与常考内容重点讲解。2、以实例如真题来讲解程序设计中的重点与难点。三、重点内容1、算法的时间复杂度与空间复杂度。2、判断线性结构与非线性结构。3、栈和队列的基本知识，计算栈和队列中的元素个数。4、二叉树的基本性质和二叉树的遍历。5、查找方法与排序技术中的最坏情况次数。四、教学内容1.1算法1.1.1算法的基本概念算法是指解决问题方案的准确而完整的描述。1、算法的基本特征：（理解+记忆）（1）可行性（2）确定性算法的确定性，是指算法中的每一个步骤都必须有明确定义的，不允许有模棱两可的解释，也不允许有多义性。（3）有穷性算法的有穷性，是指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。（4）有效性所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。2、算法的基本要素：（1）算法中对数据对象的运算和操作。（2）算法的控制结构：顺序、选择、循环（记忆）3、算法设计基本方法：（了解）（1）列举法（2）归纳法（3）递推（4）递归（5）减半递推技术（6）回溯法1.1.2算法的复杂度算法的复杂度主要包括时间复杂度和空间复杂度。1、算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量。算法执行的基本次数与问题的规模有关。分析算法工作量的方法：（了解）（1）平均性态（2）最坏情况复杂性所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。2、算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。算法的时间复杂度与空间复杂度不一定相关。1.2数据结构的基本概念1.2.1什么是数据结构简单地说，数据结构是指相互有关联的数据元素的集合。例如：（1）一年四季的季节名春、夏、秋、冬（2）表示家庭成员的各成员父亲、儿子、女儿在数据处理领域中，通常把数据元素之间的这种固有的关系简单地用前后件关系来描述。前后件关系是数据元素之间的一个基本关系。一般来说数据元素之间的任何关系都可以用前后件关系来描述。1、数据的逻辑结构所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。2、数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。注意：一种数据的逻辑结构根据需要可以表示成多种存储结构，也就是说，数据的逻辑结构与存储结构不是一一对应的。常用的数据存储结构有：顺序、链接、索引等。1.2.2数据结构的图形表示上图为一年四季的数据结构的图形表示上图为家庭成员辈分关系数据结构的图形表示1、结点的基本概念【了解】根结点：在数据结构中，没有前件的结点称为根结点叶子结点（终端结点）：没有后件的结点称为叶子结点。内部结点：除了根结点与终端结点外冬秋夏春儿子女儿父亲的其他结点一般称为内部结点。2、运算【了解】（1）插入运算：在一个数据结构中增加一个新结点。（2）删除运算：删除数据结构中的某个结点。插入与删除运算是数据结构的两种基本运算。1.2.3线性结构与非线性结构如果一个非空的数据结构满足以下两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则该数据结构为线性结构。线性结构又称线性表。一个数据结构不是线性结构，则称之为非线性结构。线性结构与非线性结构都可以是空的数据结构。注意：【记忆】（1）线性结构包括：线性表、栈、队列、循环队列、线性链表（2）非线性结构：树、二叉树1.3线性表及其顺序存储结构（了解）1.3.1线性表的基本概念线性表是最简单、最常用的一种数据结构。（线性结构）1.3.2线性表的顺序存储结构在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中个数据元素在存储空间中是按照逻辑顺序依次存放的。在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。1.3.3顺序表的插入运算（简单了解）1.3.4顺序表的删除运算（简单了解）1.4栈和队列1.4.1栈及其基本运算1、什么是栈栈是限定在一端进行插入与删除运算的线性表。【记忆】数据组织原则：“先进后出”或“后进先出”【记忆】栈具有记忆作用。用指针top来指向栈顶的位置（栈顶元素），用指针bottom指向栈底（栈底元素）2、栈的顺序存储结构及其运算（了解）在程序设计语言中，用一维数组作为栈的顺序存储空间。栈的基本运算：（1）入栈运算（2）退栈运算（3）读栈顶元素附加内容：栈中元素个数的计算，m表示容量，b表示bottom，t表示top大—小+1=栈中元素个数1.4.2队列及其基本运算1、什么是队列队列是指允许在一端进行插入，而在另一端进行删除的线性表。队列的数据组织原则是：“先进先出”或“后进后出”用队头指针front指向队头元素的下一个位置，队尾指针rear指向队尾元素。在程序设计语言中，用一维数组作为队列的顺序存储空间。2、循环队列及其与运算在实际应用中，队列的顺序存储结构一般采用循环队列的形式。（1）入队运算（2）退队运算附加内容：队列中元素个数的计算。m表示容量，f表示队头指针，r表示队尾指针(1)ｆ＜ｒ元素个数＝ｒ－ｆ(2)ｆ＞=ｒ元素个数＝m－ｆ＋ｒ1.5线性链表（了解即可）1.5.1线性链表的基本概念1、线性链表线性表的链式存储结构称为线性链表。2、带链的栈3、带链的队列1.5.2线性链表的基本运算1、在线性链表中查找指定元素2、线性链表的插入3、线性链表的删除1.5.3循环链表及其基本运算1.6树与二叉树（重点）1.6.1树的基本概念树是一种简单的非线性结构。树结构的基本术语：（了解）1、根结点：在树结构中，没有前件的结点只有一个，称为树的根2、子结点：每一个结点的后件称为该结点的子结点3、叶子结点：没有后件的结点4、结点的度：结点拥有后件的个数。5、树的度：所有结点中的最大的度称为树的度。6、树的深度：树分层。树的最大层次称为树的深度。7、子树：以某一个的子结点为根构成的树称为该结点的一棵子树。1.6.2二叉树及其基本性质1、什么是二叉树二叉树有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。结点的度最大是2，树的度最大是2。2、二叉树的基本性质性质1在二叉树的第k层上，最多有2k-1（k=1）个结点性质2深度为m的二叉树最多有2m-1个结点性质3在任意一棵二叉树中，度为0的点（即叶子结点）总是比度为2的结点多一个。n0=n2+1性质4具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。3、满二叉树与完全二叉树（1）满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。DEFGCBA（2）完全二叉树除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。完全二叉树还具有以下两个性质：性质5具有n个结点的完全二叉树的深度为[log2n]+1。性质6设完全二叉树共有……另外：(1)完全二叉树度为1的结点个数为0或1。n1=0,1n0=n2+1n=n0+n1+n2(2)完全二叉树结点总个数为n，n0为叶子结点的个数，则a．n为偶数，n0=n/2b．n为奇数，n0=(n+1)/21.6.3二叉树的存储结构二叉树通常采用链式存储结构。1.6.4二叉树的遍历【掌握】二叉树的遍历是指不重复地访问二叉树中的所有结点。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历有三种遍历的方法。1、前序遍历：根结点→左子树→右子树2、中序遍历：左子树→根结点→右子树3、后序遍历：左子树→右子树→根结点遍历结果：（1）前序遍历：ABDECF（2）中序遍历：DBEAFC（3）后序遍历：DEBFCADEBCAF1.7查找技术对于长度为n的有序线性表1.7.1顺序查找顺序查找最坏情况下需要比较n次。1.7.2二分法查找二分法查找（对分查找）最坏情况下需要比较log2n次。1.8排序技术1.8.1交换类排序法1、冒泡排序法最坏情况下需要比较次数为n(n-1)/22、快速排序法最坏情况下需要比较次数为n(n-1)/21.8.2插入类排序法1、简单插入排序法最坏情况下需要比较次数为n(n-1)/22、希尔排序法最坏情况下需要比较次数为O(n1.5)1.8.3选择类排序法1、简单选择排序法最坏情况下需要比较次数为n(n-1)/22、堆排序法最坏情况下需要比较次数为O(nlog2n)总结：1、最坏情况下，需要比较n(n-1)/2次的排序方法有：冒泡排序法、快速排序法、简单插入排序、简单选择排序。2、希尔排序法，最坏情况下需要比较的次数是O(n1.5)3、堆排序法，最坏情况下需要比较的次数是O(nlog2n)。