第5章 数据结构与算法-理科.ppt

计算机等级考试公共基础知识,第2页,计算机二级考试公共基础知识大纲,数据结构与算法程序设计基础软件工程基础数据库设计基础,这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。,第3页,计算机二级考试公共基础知识试卷分析,第4页,算法算法的基本概念2.算法复杂度的概念和意义,一、基本数据结构与算法,数据结构数据结构的概念线性表栈和队列树与二叉树查找技术排序技术,对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。,第5章数据结构与算法,5.1算法基础5.2数据结构5.3栈5.4队列,5.5链表5.6树与二叉树5.7查找5.8排序,本章要求,算法的基本概念；算法复杂度的概念和意义(时间复杂度与空间复杂度)数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念线性表的定义；线性表的顺序存储结构及其插入与删除运算栈和队列的定义；栈和队列的顺序存储结构及其基本运算,本章要求,线性单链表、双向链表与循环链表的结构及其基本运算树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历顺序查找与二分法查找算法；基本排序算法(交换类排序,选择类排序,插入类排序),5.1算法基础(P191),5.1.1算法的基本概念5.1.2算法复杂性分析,5.1.1算法的基本概念(P191),所谓算法是指解决问题的方法和步骤。算法的基本特征：可行性：算法中有待执行的运算和操作必须是相当基本的，都是能够精确地进行的。例：在算法中不允许出现分母为0的情况。算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。有穷性：一个算法在执行有穷步之后必须结束。拥有足够的情报：一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。,算法的基本要素,1.算法中对数据的运算和操作算术运算：主要包括加、减、乘、除等运算。逻辑运算：主要包括“与”、“或”、“非”等运算。关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。数据传输：主要包括赋值、输入、输出等操作2.算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。,三种控制结构,算法设计基本方法,（1）列举法（2）归纳法（3）递推（4）递归（5）减半递推技术（6）回溯法,列举法的基本思是根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。列举法的特点是算法比较简单。但当列举的可能情况较多时，列举算法的计算量将会很大。因此，尽量使得列举法能在一个局部范围内进行。列举算法虽然是一种比较原始的方法，其运算量比较大，但在有些实际问题中（如寻找路径、査找、搜索等问题）、局部使用列举法却是很有效的，因此，列举算法是计算机算法中的一个基础算法。,(1)列举法,归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。归纳是一种抽象，即从特殊现象中找出一般关系。但由于在归纳的过程中不可能对所有的情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。,(2)归纳法,（3）递推,递推，是指初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。递推算法在数值计算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。,（4）递归,人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。递归分为直接递归与问接递归两种。如果一个算法显式地调用自己则称为直接递归。如果算法F调用另一个算法P，而算法P又调用算法F，则称为间接递归调用。,递归调用实例:求n的阶乘,#includeintfact(intn)intf;if(nnext,a2,p,p,s,s,p-next=s,插入前：,插入后：,s-next=p-next;p-next=s;,删除指针p所指的结点后的结点,a1,a3,a2,p,删除前：,删除后：,a1,a3,a2,p,p-next=p-next-next,s,s=p-next,释放结点后：,a1,a3,p,free(s),单链表的删除,p-next=p-next-next;,链式栈栈也是线性表，也可以采用链式存储结构，栈的链式结构和单链表存储结构基本相同，单链表的头指针含义为栈的栈顶指针。插入和删除结点只能通过栈顶指针在栈顶端进行。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。链式队列队列的链式结构也和单链表的存储结构基本相同，不过链式队列有两个指针，一个队首指针，一个队尾指针。,5.6树和二叉树(P205),5.6.1树的基本概念定义：树(tree)是n(n=0)个结点的有限集T当n0时，空树当n0时有且仅有一个特定的结点，称为树的根(root)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点根树中各子树是互不相交的集合,A,只有根结点的树n=1,有子树的树n1,根,子树,现实中的例子,定义：度为2的有序树递归定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态,左孩子,右孩子,5.6.2二叉树概念及其基本性质(P206),二叉树基本性质,满二叉树与完全二叉树,满二叉树是指这样的一种二叉树：(1)除最后一层外，每一层上的所有结点都有两个子结点。(2)在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，(3)在深度为m的满二叉树共有2m-1个结点。完全二叉树是指这样的二叉树：(1)除最后一层外，每一层上的结点数均达到最大值；(2)在最后一层上只缺少右边的若干结点。,理想平衡二叉树,性质1：具有n个结点的完全二叉树的深度为log2n+1。性质2：设完全二叉树共有n个结点。如果从根结点开始，按层次（每一层从左到右）用自然数1，2，n给结点进行编号，则对于编号为k（k=1，2，n）的结点有以下结论：若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点,编号为k/2；若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）；若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。,完全二叉树的性质,遍历的定义按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列.常用方法前序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点,5.6.3二叉树的遍历(P208),前序遍历:,DLR,前序遍历序列：ABDC,LDR,中序遍历序列：BDAC,中序遍历:,LRD,后序遍历序列：DBCA,后序遍历:,前序遍历：,中序遍历：,后序遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,作业,1.,2.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,画出其二叉树结构并计算后序遍历顺序。,5.7查找(P208),查找(search):也称检索，即根据给定的某个值，在查找表中确定一个其关键字等于给定值的第一条记录(元素)或全部记录。若表中存在这样的记录，则查找成功，通常要求返回该记录存储位置；若不存在这样的记录，表明查找失败，返回特定值。,顺序查找(SequentialSearch)：又称线性查找，它是一种最简单最基本查找方法。思路：(1)从顺序表的一端开始，依次将每个元素关键字同给定值K进行比较，(2)若某个元素关键字等于K，则查找成功，返回该元素所在下标，(3)若直到所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败，返回特定值(常用-1表示)。,5.7.1顺序查找(P208),顺序查找时间复杂度为O(n),缺点：速度较慢，查找成功最多需比较n次，平均查找长度约为表长一半。优点：算法简单，适应面广，对表结构无任何要求。,顺序查找性能分析：,在下列两种情况下也只能采用顺序查找：如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找；即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,二分查找(BinarySearch)：又称折半查找。作为二分查找对象的表必须是顺序存储的有序表。查找过程：首先取整个有序表A0An-1的中点元素Amid(mid=(n-1)/2)的关键字与K比较,Amid.key=K成功，返回mid,Amid.keyK在A0Amid-1中继续找,Amid.keyK在Amid+1An-1中继续找,5.7.2二分法查找(P210),查找96过程如下：,排序定义将一组杂乱无章的记录按一定的规律顺次排列起来。排序目的便于查找。排序域通常数据记录有多个属性域,即多个数据项,其中有一个属性域可用来区分记录,作为排序依据。该域即为排序域或排序项。每个数据表用哪个属性域作为排序域，要视具体的应用需要而定。排序码排序域中的每一个值。,存放在数据表中,按某个域的值排序,5.8排序(P212),排序算法的好坏如何衡量时间效率空间效率占内存辅助空间的大小稳定性排序算法的稳定性如果在记录序列中有两个记录ri和rj,它们的排序码ki=kj,且在排序之前,记录ri排在rj前面。如果在排序之后,对象ri仍在对象rj的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。,排序算法的时间开销排序算法的时间开销是衡量算法好坏的最重要的标志。排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。,基本思想两两比较待排序记录的排序码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。,5.8.1交换类排序法(P212),排序过程（升序）将最后一条记录（第n条记录）的排序码与倒数第二条记录（第n-1条记录）的排序码进行比较，若为逆序，即rn-1rn-2，则交换；然后比较第n-1记录与第n-2条记录；依次类推，直至第2条记录和第1条记录比较为止第一趟冒泡排序，结果排序码最小的记录被安置在第条记录上。对后n-1个记录进行第二趟冒泡排序，结果使关键字次小的记录被安置在第条记录位置。重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止，即没有记录交换。,(1)冒泡排序法(P212),例,4938659776132730,初始排序码,1349386597762730,第一趟,1327493865977630,第二趟,1327304938659776,第三趟,第四趟,第五趟,76,13,27,97,13,76,76,27,30,13,27,65,13,49,30,27,27,38,38,13,97,65,38,49,97,49,30,30,30,97,65,38,49,76,1327303849657697,1327303849657697,在最坏的情况下，N个数冒泡排序需要比较次数为n(n-1)/2。时间复杂度为O(n2)。,（2）快速排序法（划分排序）,基本思想对冒泡排序的改进，从待排序列中任取一个元素(例如取第一个)作为基准元素，通过从区间两端向中间顺序进行比较和交换，使所有比基准元素的排序码小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表，然后把基准元素交换到左右两个子表的交界处，这样，左子表中所有元素的排序码均小于等于基准元素的排序码，右子表中所有元素的排序码均大于等于基准元素的排序码；然后再对各子表重新选择基准元素并依此规则调整，直到每个子表的元素只剩一个或为空。此时便为有序序列了。,排序过程对rst中记录进行一趟快速排序，附设两个指针i和j，设基准元素为rp=rs，x=rp.stn初始时令i=s+1,j=t首先从j所指位置向前搜索第一个排序码小于x的记录。再从i所指位置起向后搜索，找到第一个排序码大于x的记录。交换Ai和Aj。重复上述两步，直至i=j或i=j+1为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录或为空为止。,45531836723048931536第一次划分：30361836154548937253第二次划分：18153036364548937253第三次划分：15183036364548537293第四次划分：15183036364548537293,5.8.2插入类排序法,（1）直接插入排序基本思想：每步将一个待排序的记录,按其排序码大小,插入到前面已经排好序的一组记录的适当位置上,直到记录全部插入为止。直接插入排序排序过程：先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序，整个排序过程为n-1趟插入。,例,49386597761327,i=238(3849)6597761327,i=365(384965)97761327,i=497(38496597)761327,i=576(3849657697)1327,i=613(133849657697)27,i=1(),i=7(133849657697)27,27,97,76,65,49,38,27,（2）希尔排序法,基本思想是：将待排序列分为若干组，在每组内进行直接插入排序，以使整个序列基本有序，然后对整个序列进行直接插入排序。关键在于如何分组，常用办法是第一轮取步长为初始长度n的一半，即间隔为n/2的元素为一组；以后每轮的步长为上次的一半（缩小增量法）；此方法称为折半插入排序。,折半插入排序排序过程：在已形成的有序表中用折半查找方法确定插入位置的排序。,例:数据（51，45，80，36，14，75，58，96）P21551，45，80，36，14，75，58，96,基本策略第i趟在后面n-i个待排记录中选取排序码最小的（或最大的）记录作为有序序列中的第i个记录。,5.8.3选择类排序法,排序过程（升序）首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换。重复上述操作，共进行n-1趟排序后，排序结束。,（1）直接选择排序,例,初始：49386597761327,i=1,13,49,一趟：13386597764927,i=2,27,38,六趟：13273849657697,排序结束：13273849657697,堆的定义：n个元素的序列(k0,k1,kn-1)，当且仅当满足下列关系时，称之为堆。,或,(i=0,1,.,n/2-1),kik2ikik2i+1,kik2ikik2i+1,例（96，83，27，38，11，9）,例(13，38，27，50，76，65，49，97）,可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值。,（2）堆排序,堆排序：将无序序列建成一个堆，得