第一章、数据结构与算法

第一章数据结构与算法,1.1算法1.2数据结构的基本概念1.3线性表及其顺序存储结构1.4栈和队列1.5线性链表1.6树与二叉树1.7查找技术1.8排序技术,注意：在公共基础知识里面，需要记忆的内容比较多，我们的教程中已经将核心记忆的内容提取出来，在学习过程中彩色字体是核心内容，需要同学记忆。,1.1算法,1.1.1算法的基本概念,算法：是指解题方案的准确而完整的描述。,算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。,1.1.2算法设计的基本方法,列举法、归纳法、递推、递归、减半递推技术、回溯法,1.1.3算法复杂度（时间复杂度和空间复杂度）,时间复杂度：执行算法所需要的计算工作量,空间复杂度：执行算法所需要的内存空间,可行性,A=1012,B=1,c=-1012,A+B+C=1012+11012=1,如果计算机程序中，是单精度运算，具有7位有效数字，则：,A+B+C=1012+11012=0,算法的每一个步骤必须能够实现,算法执行的结构要能够达到预期的目的,12/0；1,返回,确定性：算法中每一个步骤都必须要明确定义的，不允许有模棱两可的解释，也不允许有多义性,有穷性：算法必须能在有限时间内做完。,如果算法需要执行1千年？,拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。,例如：做菜,返回,列举法：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。,归纳法：通过列举少量的特殊情况，进过分析，最后找出一般的关系。,递推：从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。,112358132134,递归：将问题逐层分解，最后归结为一些简单的问题。,函数factorial(intn)if(n1)returnfactorial(n-2)+factorial(n-1);else：return1,斐波那契数列：,返回,减半递推技术：将问题的规模减半，而问题的性质不变，并且重复减半的过程,设方程f（x）=0在区间a，b上有实根，且f（a）与f（b）符号相反，即f（a）f（b）0。利用求该方程在区间a，b上的一个实根。用二分法求方程实根的减半递推过程如下：首先计算区间的中点c=（a+b）/2，然后计算函数在中点c的值f（c），并判断f（c）是否为0。若f（c）=0，则说明c就是所求的根，求解过程结束；如果f（c）0，则根据以下原则将原区间减半：若f（a）f（c）0，则取原区间的前半部分，；若f（b）f（c）n时，认为在最后一个元素之后(第n+1个元素之前)插入；当i1，则该结点的父节点编号为INT(k/2)若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子节点。若2k+1n，则编号为k的结点的右子节点编号为2k+1，否则该结点无右子节点。,1.6.3二叉树的存储结构,在计算机中，二叉树通常采用链式存储结构。(二叉链表),二叉树中各元素的存储结点由数据域和两个指针域(左指针和右指针),左指针用于指向该结点的左子结点；右指针用于指向该结点的右子结点。,R(i),二叉树存储结点的结构,注：满二叉树和完全二叉树，根据完全二叉树的性质2，可以按层序进行顺序存储，可以节省存储空间，还能方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储结构对于一般的二叉树不适用,F,E,B,D,C,G,A,P,H,(a)二叉树,F,C,A,D,B,E,H,G,P,0,0,0,0,0,0,0,0,0,0,BT,4,6,9,8,5,2,11,13,1,(b)二叉链表的逻辑状态,存储序号,(c)二叉链表的物理状态,BT,1.6.4二叉树的遍历,二叉树的遍历是指不重复地访问二叉树中的所有结点,三种遍历方法,前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。,F,E,B,D,C,G,A,P,H,(a)二叉树,中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树，并且在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树,后续遍历：首先遍历左子树，然后遍历右子树，最后访问根结点，并且在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。,F、C、A、D、B、E、G、H、P,A、C、B、D、F、E、H、G、P,A、B、D、C、H、P、G、E、F,注：如果知道了某个二叉树的前序序列和中序序列，则可以唯一地恢复该二叉树。同样的，如果知道了某二叉树的后序序列和中序序列，则也可以唯一地恢复该二叉树。但是如果只知道某二叉树的前序序列和后序序列，是不能唯一恢复该二叉树的。,例1：某二叉树的前序序列是DBACFEG,中序序列是ABCDEFG，则恢复该二叉树为,D,F,C,B,G,A,E,例2：某二叉树的中序序列是ABCDEFG，后序序列是ACBEGFD,则恢复该二叉树为,D,F,C,B,G,A,E,1.7查找技术,查找：指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找技术。,1.7.1顺序查找(顺序搜索),在线性表中查找指定的元素。,方法：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到。若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素(查找失败),对于大的线性表，顺序查找的效率很低。,只能采用顺序查找的情况：如果线性表为无序表(表中元素的排列是无序的)，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,HEAD,3,1,7,0,6,1.7.2二分法查找(分查找),只适用于顺序存储的有序表(线性表中的元素从小到大排序)。,设有序线性表的长度为n，被查元素为x，则对分查找的方法为：将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束若x小于中间项的值，则在线性表的前半部分，然后以相同的方法进行查找若x大于中间项的值，则在线性表的后半部分，然后以相同的方法进行查找,二分查找的效率要比顺序查找高很多。对于长度为n的有序表，在最坏的情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。,29,30,31,32,1,4,5,6,8,7,3,2,存储地址,顺序存储结构,33,34,35,1.8排序技术,指将一个无序序列整理成按值非递减顺序(从小到大，允许相邻元素值相等)排列的有序序列。,本课程涉及到的排序方法中，排序对象一般认为是顺序存储的线性表。,29,30,31,32,1,4,5,6,8,7,3,2,存储地址,无序序列,32,34,35,排序方法,交换类排序法,插入类排序法,选择类排序法,简单选择排序法,对排序法,希尔排序法,简单插入排序法,冒泡排序法,快速排序法,29,30,31,32,1,4,5,6,8,7,3,2,存储地址,有序序列,32,34,35,1.8.1交换类排序法,指借助数据元素之间的互相交换进行排序的一种方法。,1、冒泡排序法,通过相邻数据元素的交换逐步将线性表变成有序。,过程：从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换。从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换。以此，对剩下的线性表重复过程，直到剩下的线性表变空为止，此时的线性表已经变为有序表,例1.8.1冒泡排序,如果线性表的长度为n，最坏的情况下需要进行n(n-1)/2次比较。,2.快速排序法,比冒泡排序法速度快，因此称为快速排序法。,方法：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分为了两部分(称为两个子表)，T插入到其分界线的位置处。然后对分割后的各子表再按上述原则进行分割，一直到所有子表为空，则此时的线性表就变成了有序表,T,T,T,分割,分割,分割,无序线性表,如果线性表的长度为n，最坏的情况下需要进行n(n-1)/2次比较。,例1.8.1冒泡排序,返回,6,9,1,4,8,2,3,7,5,1,6,原序列,第一次(从前往后),第一次(从后往前),第二次(从前往后),第二次(从后往前),6,9,1,4,8,2,3,7,5,1,6,6,9,1,4,8,2,3,7,5,1,6,6,9,1,4,8,2,3,7,5,1,6,6,9,1,4,8,2,3,7,5,1,6,1.8.2插入类排序法,1、简单插入排序法,指将无序序列中的各元素依次插入到已经有序的线性表中。,思想：在线性表中，只包含第1个元素的子表显然可以看成是有序表。然后从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序子表中。,插入过程：假设线性表中前j-1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，将第j个元素放到一个变量T中从有序子表的最后一个元素开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T插入到刚移出的空位置上以此循环直到最后一个元素比较结束,例1.8.2简单插入排序,在最坏情况下，简单插入排序需要n(n-1)/2次比较,2、希尔排序法,在简单插入排序基础上做了较大的改进。,思想：将整个无序序列分隔成若干小的子序列分别进行插入排序,子序列的分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成,增量序列一般取,=n/2(=1,2,2),其中n为待排序序列的长度,例1.8.2希尔排序,在最坏情况下，希尔排序需要O(n1.5)次比较,例1.8.2简单插入排序,4,6,1,1,8,7,3,2,6,5,9,原序列,返回,T,插入过程：假设线性表中前j-1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，将第j个元素放到一个变量T中从有序子表的最后一个元素开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T插入到刚移出的空位置上以此循环直到最后一个元素比较结束,j=11,返回,例1.8.2希尔排序,07,19,24,13,31,08,82,18,44,63,05,29,增量序列一般取,=n/2(=1,2,2),其中n为待排序序列的长度,h=6,h=3,07,18,24,13,05,08,82,19,44,63,31,29,h=1,07,05,24,13,18,24,63,19,29,82,31,44,最后结果,05,07,08,13,18,19,24,29,31,44,63,82,子序列的分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成,1.8.3选择类排序法,1.简单选择排序法,思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表空为止。,89,21,56,48,85,16,19,47,原序列,第一遍选择,第二遍选择,第三遍选择,第四遍选择,第七遍选择,第五遍选择,第六遍选择,89,21,56,48,85,16,19,47,89,21,56,48,85,16,19,47,89,21,56,48,85,16,19,47,89,21,56,48,85,16,19,47,89,21,56,48,85,16,19,47,89,21,56,48,85,16,19,47,在最坏情况下需要比较n(n-1)/2次,89,21,56,48,85,16,19,47,2.堆排序法,50,35,40,25,1,4,5,6,8,7,3,2,存储地址,20,45,30,9,10,15,在n个元素的序列里，当且仅当满足,hih2i,hih2i+1,hih2i,hih2i+1,或,时称之为堆,50,20,40,45,25,35,30,10,15,堆的排序方法：将待排序序列构造成一个堆，此时，整个序列的最大值就是堆顶的根节点。将根结点与末尾元素进行交换，此时末尾就为最大值。将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了,如何构造成一个堆？从最后一个非叶子结点开始，将根结点值与左右子树的根结点值进行比较，若不满足堆的条件，则将左右子树根结点中大者与根结点值进行交换。,例：堆排序法,例：堆排序法,4,6,8,5,9,1,2,3,4,5,8,5,步骤一构造初始堆,如何构造成一个堆？从最后一个非叶子结点开始，