2011年福建专升本数据结构与算法教材教案（425页).ppt

数据结构与算法,北上数据结构考前复习,辅导课需要具备的先导知识辅导课的侧重点、难度辅导课的时间、内容安排,辅导课需要具备的先导知识,C语言的基本概念，至少能够看懂简单的C语言代码。最好有上过数据结构课程，未上过数据结构课程会有些吃力。有一点点高等数学基础更好。,专升本数据结构的特点,课本的组织形式基本上是以代码来讲解理论，这给读书带来一定难度。专升本的考试重点不在代码实现，而在理论知识的掌握。数据结构课程按照理论+题库的讲解模式，应试能力明显增强。,辅导课的侧重点、难度,基本上讲解理论知识+题目，尽量不涉及C语言(必要的C语言结构会进行讲解)。讲解过程采用新课+复习模式，按照新课讲授，例子可能采用后面的章节。希望大家在过程中做好笔记。难度与专升本考试难度持平，相当于学习期间，中游同学可以掌握的难度。,考试大纲见word文档,数据结构的主体内容,线性数据结构集合(散列数据结构)树形(层次)数据结构图(网状)数据结构,时间复杂度排序查找相关数据结构(二叉排序树、堆)递归及其他,开篇：数据结构的定义,数据元素是数据的基本单位，但数据元素是可分的，数据元素由数据项组成。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，基本结构有4类：集合、线性结构、树形结构、图状结构或网状结构存储结构，即数据的物理结构，是数据结构在计算机中的表示。包括数据元素的表示和关系的表示。主要有顺序存储结构、链式存储结构、索引存储方法和散列存储方法等。,习题,要表示高校的校，系，班级的有关数据及其关系，选择_比较合适。【福建2009专升本】A线性结构B树结构C图结构D集合结构_是数据的基本单位，即数据集合中的个体。【福建2009专升本】A数据结构B数据项C数据元素D数据对象,答案:BC,习题,以下哪一个术语与数据的存储结构无关_【福建2007专升本】A队列B静态数组C线索二叉树D双向链表,答案:A,算法定义及复杂度的概念,需要掌握的知识点算法的定义及其五条基本性质时间复杂度的概念、时间复杂度与什么有关最坏、最好、平均情况下的时间复杂度时间复杂度的O表示给定函数式，可以用O表示。能够比较两个函数式代表的复杂度。给出C简单代码，能够计算复杂度（O表示）。熟记常用算法的复杂度(O表示)。,算法(Algorithm),算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。(5)可行性：任意合法输入都对应正确输出,算法复杂性分析,算法复杂性=算法所需要的计算机资源。算法的时间复杂性T(n)。算法的空间复杂性S(n)。数据结构主要讨论时间复杂性。时间复杂性与问题规模和数据初始状态有关，与其它内容无关。,最坏情况、最好情况和平均情况下时间复杂性,三种情况下时间复杂性是针对初始数据进行分类的，与n没有关系。,渐近分析的记号,对所有n，f(n)0，g(n)0。渐近上界记号O的定义O(g(n)=f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n)O符号具有的特点：O符号忽略所有的系数。O符号仅在乎整个表达式的主项（值最大的项）。,习题,下列函数中渐进时间复杂度最小的是_。【2009专升本】,答:A若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为_。【2007专升本】,O(nlogn),习题,算法的计算量的大小称为计算的_【北京邮电大学2000二、3】A效率B复杂性C现实性D难度算法的时间复杂度取决于_【中科院计算所1998二、1】A仅和问题的规模有关B仅和待处理数据的初态有关C和问题的规模及待处理数据的初态有关D和问题的规模、待处理数据的初态、CPU的执行速度有关一个算法的定义是_。【中山大学1998二、1】A程序B问题求解步骤的描述C满足五个基本特性的东西,答:BCB,算法的时间复杂性及看C代码写复杂度见其它课件,常用算法的时间复杂性的大小关系为：常数级对数级n=6)：,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-table6=L-table5,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-table5=L-table4,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-table4=L-table3,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-table3=L-table2,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-table2=70;L-n+;,插入操作移动元素的平均次数,最少情况为表尾插入，移动0次。最多情况为表首插入，移动n次。平均次数=移动的总次数/位置个数,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：L-table2=L-table3,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：L-table3=L-table4,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：L-table4=L-table5,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：L-table5=L-table6,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：L-n-,删除操作移动元素的平均次数,最少情况为表尾删除，移动0次。最多情况为表首删除，移动n-1次。平均次数=移动的总次数/位置个数,单链表（指针实现表）,单链表采用指针的方式将物理上并不相邻的单元串联起来。这种实现方式的优点有：插入删除不需要移动元素表容量可任意变化这种实现方式的缺点有：需要额外的指针空间查找指定位置元素的复杂度高,单链表（指针实现表）,a(1),a(2),a(3),a(n),first,单链表：表的定义,typedefstructnode*link;typedefstructnodeListItemelement;linknext;Node;typedefstructllist*List;typedefstructllistlinkfirst;Llist;,单链表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,单链表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,对应代码：p=L-first,p,单链表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,对应代码：p=p-next,p,单链表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,对应代码：y-next=p-next,p,单链表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,对应代码：p-next=y,p,单链表：删除第3个结点,a(1),a(2),a(3),a(n),first,对应代码：p=L-first,p,单链表：删除第3个结点,a(1),a(2),a(3),a(n),first,对应代码：p=p-next,p,单链表：删除第3个结点,a(1),a(2),a(3),a(n),first,对应代码：p-next=p-next-next,p,其它链表形式,a(1),a(2),a(3),a(n),first,循环链表,双链表,a(1),a(2),a(3),first,头结点,表章节重点,理解表所代表的线性关系的意义。了解表的顺序和链式实现的优缺点。清楚表的插入删除查询过程中移动元素比较元素的次数。能够根据要求填写（至少判断）简单的C实现代码。,表习题,线性表是一个_【福建2009专升本】A有限序列，可以为空B有限序列，不能为空C无限序列，可以为空D无限序列，不能为空某链表中最常见的操作是在已知的一个结点之前插入一个新的结点和删除其之前一个结点，则采用_存储方式最节省运算时间【福建2009专升本】A双向链表B带头指针的单向链表C带尾指针的单向链表D单向循环链表,答案：AA,表习题,下述哪一条是顺序存储方式的优点_【福建2007专升本】A存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构的存储表示对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为_【福建2007专升本】A顺序表B用头指针表示的单循环链表C用尾指针表示的单循环链表D单链表在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为_【福建2007专升本】An-i+1Bn-iCiDi-1,答案：ACA,表习题,链表的结点类型定义如下:typedefstructnode*link;structnodeListItemelement;linkleft;linkright;*p,*q,*r;删除双链表中结点p(由p指向的结点)的操作是_【福建2008专升本】Aq=p-left;r=p-right;q-right=r;r-left=q;Bq=p-right;r=p-left;q-right=r;r-left=q;Cq=p-left;r=p-right;q-left=r;r-right=q;Dq=p-left;r=p-right;q-right=r-left;,答案：A,表习题,已知单链表结点构造为structnodeintdata;structnode*next;*p,*q,*r;删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的是_【福建2006专升本】Aq=p-next;p-next=q-next;Bp-next=p-next-next;Cr=p-next;p-next=q-next;Dq=p-next;r=q-next;p-next=r;单链表中有n个结点,在其中查找值为x的结点,查找成功时,需比较的平均次数是_【福建2006专升本】AnB(n-1)/2Cn/2D(n+1)/2线形表采用链式存储时,结点的存储地址_【福建2006专升本】A必须是不连续的B连续与否均可C必须是连续的D和头结点的存储地址相连续,答案：CDB,第三章：栈（线性数据结构）,栈是一种特殊的表，这种表只在表的一端进行插入和删除操作。因此，这一端对于栈来说具有特殊的意义，称为栈顶。相应地，另外一端称为栈底。不含任何元素的栈称为空栈。栈是限定仅在表一端进行插入或删除操作的线性表，又称后进先出（LIFO）的线性表。栈顶栈底,a(n),.,a(2),a(1),栈的常用运算,StackEmpty(S):测试栈S是否为空StackFull(S):测试栈S是否已满StackTop(S):返回栈S的栈顶元素Push(x,S):在栈S的栈顶插入元素x,简称为将元素x入栈Pop(S):删除并返回S的栈顶元素，简称为抛栈。提示：这些代码基本上是一句话，希望大家能够掌握,栈的实现,栈的实现也有顺序和链式两种方式。数组实现栈中，栈元素存储在数组data中。用top指向当前栈顶位置。栈顶元素存储在datatop中。栈的容量为maxtop+1。两个栈可以共享一个数组data。指针实现栈时用top指针指向栈顶。,数组实现栈的结构,typedefstructastack*Stack;typedefstructastackinttop,maxtop;StackItem*data;Astack;,指针实现栈的结构,typedefstructsnode*slink;typedefstructsnodeStackItemelement;slinknext;StackNode;,栈的应用,表达式求值、括号匹配、进制转换、图的深度优先遍历等。实际上，凡是满足先进后出的应用都可用栈实现。,栈的进出顺序,一个栈的进栈顺序是123n,在进栈的过程中允许出栈，那么出栈的顺序会如何？判断：有n个数顺序进栈，出栈序列有种。输出序列中不可能出现”大、小、中”的情况。要会记录出入栈的情况。,栈的习题,假设进栈的元素序列依次是a、b、c、d,指出不可能的出栈序列_【福建2006专升本】AabcdBadbcCacbdDdcba有6个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列_【福建2007专升本】A5,4,3,6,1,2B4,5,3,1,2,6C3,4,6,5,2,1D2,3,4,1,5,6递归方法实现递归算法时通常需要使用_【福建2008专升本】A循环队列B栈C二叉树D双向队列,答案：BCB,第四章：队列(线性数据结构),队列是一种特殊的表，这种表只在表首进行删除操作，在表尾进行插入操作。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出表，简称FIFO表。假设队列为a(1),a(2),a(n),那么a(1)就是队首元素，a(n)为队尾元素。,队列的常用运算,QueueEmpty(Q):测试队列Q是否为空。QueueFull(Q):测试队列Q是否已满。QueueFirst(Q):返回队列Q的队首元素。QueueLast(Q):返回队列Q的队尾元素。EnterQueue(x,S):在队列Q的队尾插入元素x。DeleteQueue(Q):删除并返回Q的队首元素。,指针实现队列的结构,typedefstructqnode*qlink;typedefstructqnodeQItemelement;qlinknext;Qnode;typedefstructlque*Queue;typedefstructlqueqlinkfront;qlinkrear;Lqueue;,循环数组实现队列的结构,typedefstructaque*Queue;typedefstructaqueintmaxsize;intfront;intrear;QItem*queue;Aqueue;,循环数组实现队列添加元素的过程,A,1,0,B,2,C,3,4,5,6,7,D,E,F,front,rear,队列添加G:,循环数组实现队列添加元素的过程,A,1,0,B,2,C,3,4,5,6,7,D,E,F,front,rear,队列添加G:Q-rear=(Q-rear+1)%Q-maxsize,循环数组实现队列添加元素的过程,A,1,0,B,2,C,3,4,5,6,7,D,E,F,front,rear,队列添加G:Q-queueQ-rear=x,G,循环数组实现队列删除元素的过程,1,0,B,2,C,3,4,5,6,7,D,E,F,front,rear,队列删除:Q-front=(Q-front+1)%Q-maxsize,G,循环数组实现队列删除元素的过程,1,0,2,C,3,4,5,6,7,D,E,F,front,rear,队列删除:Q-front=(Q-front+1)%Q-maxsize,G,循环数组实现队列删除元素的过程,1,0,2,3,4,5,6,7,D,E,F,front,rear,队列删除:Q-front=(Q-front+1)%Q-maxsize,G,循环数组实现队列添加元素的过程,1,0,2,3,4,5,6,7,D,E,F,front,rear,队列添加:Q-rear=(Q-rear+1)%Q-maxsize,G,X,循环数组实现队列添加元素的过程,1,0,2,3,4,5,6,7,D,E,F,front,rear,队列添加:Q-rear=(Q-rear+1)%Q-maxsize,G,X,Y,第四章队列的重点,理解先进先出的数据结构。循环数组实现队列是本章节重点。重点掌握front和rear游标如何判空、判满、计算队列长度、入队、出队等。,队列的习题,设数组queuem作为循环队列Q的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front的值为_【福建2006专升本】Afront=(front+1)%mBfront=(front-1)%mCfront=(front+1)%(m-1)Bfront=front+1以下哪一个术语与数据的存储结构无关_【福建2007专升本】A队列B静态数组线索二叉树D双向链表会引起循环队列队头位置发生变化的操作是_【福建2008专升本】A)取队首元素B)入队列C)取队尾元素D)出队列,答案：,队列的习题,若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为_【浙江大学1999四、1】A)4和2B)1和5C)5和1D)2和4判断：无论如何实现，也无法使队列的入队、出队两个操作的时间复杂度同时将为O(1)。判断：双端队列在逻辑上是队列。,答案：错错,排序算法概述,在一般情况下，排序问题的输入是n个数a0,a1an-1的一个序列，要设计一个有效的排序算法，产生输入序列的一个重排，使序列元素从小到大的顺序排列。掌握排序算法重点是掌握每种排序每趟过程、复杂度（最好最坏平均）、移动元素、交换元素的个数等问题。重点考的排序算法：冒泡、插入、选择、快速。希望掌握的其它排序：合并、希尔、堆排序。,第六章排序,外部排序外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,第六章排序,若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。假定在待排序的记录序列中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ki=kj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。快速排序、希尔排序、堆排序、选择排序不是稳定的排序算法，而基数排序、冒泡排序、插入排序、归并排序是稳定的排序算法,冒泡排序过程演示,原序列：,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：25和10进行交换,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和12进行交换,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和7进行交换,冒泡排序过程演示,第一趟：保持稳定，相等不交换。,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和24交换,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和6交换,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和15交换，第一趟结束，30确定位置,冒泡排序过程演示,第一趟结束，30确定位置,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟结束,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟结束,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟结束,冒泡排序过程演示,第五趟,冒泡排序过程演示,第五趟,冒泡排序过程演示,第五趟,冒泡排序过程演示,第五趟,冒泡排序过程演示,第五趟,冒泡排序过程演示,第五趟结束,冒泡排序过程演示,第六趟,冒泡排序过程演示,第六趟,冒泡排序过程演示,第六趟,冒泡排序过程演示,第六趟,冒泡排序过程演示,第六趟结束,冒泡排序过程演示,第七趟,冒泡排序过程演示,第七趟,冒泡排序过程演示,第七趟结束,冒泡排序过程演示,第八趟,冒泡排序过程演示,第八趟结束，冒泡排序完成,插入排序过程演示,原序列：,插入排序过程演示,第一趟：,插入排序过程演示,第一趟：,插入排序过程演示,第一趟：,插入排序过程演示,第一趟结束,插入排序过程演示,第二趟,插入排序过程演示,第二趟结束,插入排序过程演示,第三趟,插入排序过程演示,第三趟,插入排序过程演示,第三趟,插入排序过程演示,第三趟,插入排序过程演示,第三趟,插入排序过程演示,第三趟结束,插入排序过程演示,第四趟,插入排序过程演示,第四趟,插入排序过程演示,第四趟,插入排序过程演示,第四趟,插入排序过程演示,第四趟,插入排序过程演示,第四趟结束,插入排序过程演示,第五趟,插入排序过程演示,第五趟结束,插入排序过程演示,第六趟,插入排序过程演示,第六趟,插入排序过程演示,第六趟,插入排序过程演示,第六趟,插入排序过程演示,第六趟结束,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟结束,插入排序过程演示,第八趟,插入排序过程演示,第八趟,插入排序过程演示,第八趟,插入排序过程演示,第八趟,插入排序过程演示,第八趟,插入排序过程演示,第八趟结束，插入排序结束,选择排序过程演示,原序列：,目前最小下标：,选择排序过程演示,第一趟：,目前最小下标：0,选择排序过程演示,第一趟：,目前最小下标：1,选择排序过程演示,第一趟：,目前最小下标：1,选择排序过程演示,第一趟：,目前最小下标：1,选择排序过程演示,第一趟：,目前最小下标：4,选择排序过程演示,第一趟：,目前最小下标：4,选择排序过程演示,第一趟：,目前最小下标：4,选择排序过程演示,第一趟：,目前最小下标：7,选择排序过程演示,第一趟：,目前最小下标：7,选择排序过程演示,第一趟：结束,目前最小下标：7,选择排序过程演示,第二趟：,目前最小下标：1,选择排序过程演示,第二趟：,目前最小下标：1,选择排序过程演示,第二趟：,目前最小下标：1,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示,第二趟：结束,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：2,选择排序过程演示,第三趟：,目前最小下标：3,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：结束,目前最小下标：4,选择排序过程演示,第四趟：,目前最小下标：3,选择排序过程演示,第五趟：,目前最小下标：4,选择排序过程演示,第五趟：,目前最小下标：4,选择排序过程演示,第五趟：,目前最小下标：6,选择排序过程演示,第五趟：,目前最小下标：6,选择排序过程演示,第五趟：,目前最小下标：8,选择排序过程演示,第五趟：结束,目前最小下标：8,选择排序过程演示,第六趟：,目前最小下标：5,选择排序过程演示,第六趟：,目前最小下标：6,选择排序过程演示,第六趟：,目前最小下标：6,选择排序过程演示,第六趟：,目前最小下标：6,选择排序过程演示,第六趟：结束,目前最小下标：6,选择排序过程演示,第七趟：,目前最小下标：6,选择排序过程演示,第七趟：,目前最小下标：7,选择排序过程演示,第七趟：,目前最小下标：7,选择排序过程演示,第七趟：结束,目前最小下标：7,选择排序过程演示,第八趟：,目前最小下标：7,选择排序过程演示,第八趟：,目前最小下标：8,选择排序过程演示,第八趟：结束，选择排序结束,目前最小下标：8,快速排序过程演示,原序列：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：0小数下标：7交换,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：0小数下标：7交换,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：2小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：2小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：2小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：2小数下标：4交换,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：4小数下标：无,快速排序过程演示,第一趟：结束,大数下标：4小数下标：无,快速排序过程演示,第二趟：以12为基准,大数下标：小数下标：,快速排序过程演示,第二趟：以12为基准,大数下标：小数下标：,快速排序过程演示,第二趟：以12为基准,大数下标：小数下标：,快速排序过程演示,第二趟：以12为基准,大数下标：3小数下标：无,快速排序过程演示,第二趟：以30为基准,大数下标：5小数下标：7交换,快速排序过程演示,第二趟：以30为基准,大数下标：小数下标：,快速排序过程演示,第二趟：以30为基准,大数下标：7小数下标：无,快速排序过程演示,第二趟：结束,大数下标：7小数下标：无,快速排序过程演示,第三趟：分别以7、24、31为基准,快速排序过程演示,第三趟：结束,快速排序过程演示,第四趟结束，排序宣告结束,合并排序思想,合并排序算法是用分治策略实现对n个元素进行排序的算法。其基本思想是：当n=1时终止排序，否则将待排序元素分成大小大致相同的两个子集，分别对两个子集进行排序，最终将排好序的子集合并成为所要求的排好序的集合。自底向上的合并排序：可以首先将数组中相邻元素两两配对，用合并算法将它们排序，构成n/2组长度为2的排好序的子数组段，然后再将它们排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。,排序章节总结,冒泡、插入、选择是简单排序，平均复杂度。快速、合并是较快的排序算法，平均复杂度。快速排序在最坏情况下的时间复杂度为，合并为快速排序的最坏情况是排好序的情况，与其它排序算法不同。简单排序中，插入排序的复杂度与初态有关，另外两个无关。插入排序可能在最后一趟之前，所有元素都不在最终位置。选择、快速排序不稳定，其它稳定。,第六章排序：习题,若待排序对象序列在排序前已按其关键字递增排列，则采用_比较次数最少【福建2006专升本】A直接插入排序B快速排序C合并排序D简单选择排序在下列排序算法中，时间复杂度为O(nlogn)的是_【福建2006专升本】A冒泡排序B简单选择排序C直接插入排序D堆排序,答案：AD,第六章排序：习题,在待排序记录已基本有序的前提下，下述排序方法中效率最高的是_【福建2007专升本】A直接插入排序B简单选择排序C快速排序D归并排序平均排序效率最好的排序方法是_【福建2009专升本】A直接插入排序B快速排序C简单选择排序D冒泡排序,答案：AB,第七章树(层次数据结构),树章节的重点内容：树的相关概念(度、高度、深度、层)。树和二叉树的三序遍历。已知二叉树前中或中后序画二叉树。树中结点和度之间的关系。树和二叉树的转换。(左儿子右兄弟)线索二叉树（了解即可）。,树的定义,树是一个具有层次结构的集合，它在客观世界中广泛存在。树是由一个集合以及在该集合上定义的一种层次关系构成的。集合中的元素是树的结点，结点间的关系为父子关系。树结点之间的父子关系建立了树的层次结构。在这种层次结构中，有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。,树的定义,树的递归定义单个结点是一棵树，树根就是该结点本身。设T1Tk是树，他们的根结点为n1,nk。用一个新结点n作为n1,nk的父亲，则得到一棵新树。结点n就是新树的根。结点n1,nk成为一组兄弟结点，它们都是结点n的儿子结点。还称T1,Tk为结点n的子树。为方便起见，将空集合也看作是树，成为空树，用表示。空树中没有结点。,树的定义及相关概念,A,左图所示的树，由结点的有限集A,B,C,D,E,F,G,H,I,J构成。其中A是根结点。T中其余结点分成3个互不相交的子集T1=B,E,F,I,JT2=CT3=D,G,HT1,T2,T3是根A的三棵子树，且本身又都是一棵树。,C,B,E,J,I,H,G,D,F,树的定义及相关概念,A,一个结点的儿子结点个数称为该结点的度。一棵树的度是指该树中结点最大度数。树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。在左图中，A,B,E的度分别为3，2，0其中A为根结点，B为内部结点，E为叶结点，树的度为3。,C,B,E,J,I,H,G,D,F,树的定义及相关概念,A,4.如果存在树中的一个结点序列k1,k2,kj,使得结点ki是结点k(i+1)的父结点，则称该结点序列是树中从结点k1到结点kj的一条路径或道路。称这条路经的长度为j-1,它是该路径所经过的边的数目。树中任一结点有一条到其自身的长度为0的路径。左图中，结点A到结点I有一条路经ABFI,它的长度为3,C,B,E,J,I,H,G,D,F,树的定义及相关概念,A,5.如果在树中存在一条从结点k到结点m的路径，则称结点k是结点m的祖先，也称结点m是结点k的子孙或后裔。在左图中，结点F的祖先有A,B和F自己，而它的子孙包括F,I和J。6.将树中一个结点的非自身的祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。,C,B,E,J,I,H,G,D,F,树的定义及相关概念,A,7.树中一个结点的高度是指从该结点到各叶结点的最长路经的长度。树的高度是指根结点的高度。在左图中，B,C,D的高度分别为2,0,1,而树的高度与结点A的高度相同为3。从树根到任意结点n有唯一的一条路经，称这条路经的长度为结点n的深度或层数。根结点的深度为0，其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。在左图中，A的深度为0，结点B,C,D的深度为1，结点E,F,G,H的深度为2，结点I,J的深度为3。在树的第2层结点有E,F,G和H,树的第0层只有一个根结点A.,C,B,E,J,I,H,G,D,F,树的遍历,树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。,树的遍历,三种遍历方式的递归定义：如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。如果T是一棵单结点树，那么对T进行前序遍历、中序遍历、后序遍历都只访问这个单结点。否则对T进行前序遍历是先访问树根n,然后依次前序遍历T1,Tk,即前序遍历T1,前序遍历T2,最后前序遍历Tk。对T进行中序遍历是先中序遍历T1,然后访问树根n,接着依次对T2,Tk进行中序遍历对T进行后序遍历是先依次对T1,T2Tk进行后序遍历，最后访问树根n。,前序遍历演示,A,C,B,E,J,I,H,G,D,F,A,B,E,F,I,J,C,D,G,H,中序遍历演示,A,C,B,E,J,I,H,G,D,F,A,B,E,F,I,J,C,D,G,H,后序遍历演示,A,C,B,E,J,I,H,G,D,F,A,B,E,F,I,J,C,D,G,H,树的遍历,A,前序列表：ABEFIJCDGH中序列表:EBIFJACGDH后序列表:EIJFBCGHDA,C,B,E,J,I,H,G,D,F,二叉树,二叉树是一类非常重要的特殊的树形结构，它递归定义下：二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的2棵互不相交的二叉树u(1)和u(2)组成。子树u(1)和u(2)有时分别称为T的第一和第二子树。,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,二叉树性质,高度为h=0的二叉树至少有h+1个结点。高度不超过h的二叉树至多有2的h+1次方-1个结点。含有h=1个结点的二叉树的高度至多为n-1。含有h=1个结点的二叉树的高度至少为logn。含有n个结点的不同二叉树的数目有个。一棵高度为h且有2的h+1次方-1个结点的二叉树称为满二叉树。若一棵二叉树至多只有最下面的2层上结点的度数可以小于2，并且最下面一层上的结点都集中在该层的最左边，则称这种二叉树为近似满二叉树（有时也称为完全二叉树）。,二叉树的遍历,二叉树的遍历与树遍历的递归过程一致。二叉树的前、后序结果与树的前后序过程完全一样。由于二叉树严格区分左右，中序遍历的结果与树中序有些区别。二叉树前序遍历可简单记成:根左右。二叉树中序遍历可简单记成:左根右。二叉树后序遍历可简单记成:左右根。,二叉树中序遍历演示,A,C,B,E,J,I,H,G,D,F,K,E,B,I,F,J,A,G,C,D,K,H,已知后中序如何确定二叉树,已知一棵二叉树的中序序列BDCEAFHG，后序序列DECBHGFA，请画出该二叉树。再求出前序。,A,B,C,D,E,F,G,H,已知后中序如何确定二叉树,已知一棵二叉树的中序序列BDCEAFHG，后序序列DECBHGFA，请画出该二叉树。再求出前序。,A,B,C,D,E,F,G,H,已知后中序如何确定二叉树,已知一棵二叉树的中序序列BDCEAFHG，后序序列DECBHGFA，请画出该二叉树。再求出前序。,A,B,C,D,E,F,G,H,已知后中序如何确定二叉树,已知一棵二叉树的中序序列BDCEAFHG，后序序列DECBHGFA，请画出该二叉树。再求出前序。,A,B,C,D,E,F,G,H,树和二叉树的转换,任意一棵树（森林）都可以通过左儿子右兄弟的对应法则对应唯一一棵二叉树。任意一棵二叉树也可以通过左儿子右兄弟的对应法则对应一棵森林。,树和二叉树转换演示,A,C,B,E,J,I,H,G,D,F,A,C,B,E,J,I,H,G,D,F,树和二叉树三序遍历的关系,A,C,B,E,J,I,H,G,D,F,A,C,B,E,J,I,H,G,D,F,二叉树的前序等于树的前序。二叉树的中序等于树的后序。,树中结点和度之间的关系,假设树A的度为K，且度为0的结点(叶子)有个。,度为1的结点(叶子)有个。,度为2的结点(叶子)有个。,。,总结点有n个。,度为k的结点(叶子)有个。,两个重要公式：,二叉树中公式变形,线索二叉树,用指针实现二叉树时，每个结点只有指向其左、右儿子结点的指针，所以从任意结点出发只能直接找到该结点的左、右儿子。在一般情况下无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储效率。用指针实现二叉树时,在n个结点二叉树中含有n+1个空指针。可以利用这些空指针存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为“线索”。加上了线索的二叉树称为线索二叉树。,第7章树：习题,由3个结点可以构造出多少种不同的二叉树_【福建2007专升本】A2B3C4D5一棵非空二叉树中，(设根结点在第0层)，在第i层上最多有_个结点【福建2006专升本】A2的i+1次方B2iC2的i-1次方D2的i次方一个有n个结点的k叉树,树中所有结点的度数之和为_【福建2006专升本】Ak+nBn-1Ck*nDn*n树是结点的集合,它_根结点【福建2009专升本】A有0个或者1个B有0个或多个C有且只有1个D有1个或1个以上,答案：DDBA,第八九章集合散列表,集合章节的重点是散列表。散列表散列函数（哈希函数）的选取。解决冲突的方法。线性重新散列函数。,集合,要清楚散列表的概念，首先要了解集合概念。集合是由元素组成的一个类，元素间关系是“松散”的。一般集合的成员是互不相同的。集合中的元素没有其它关系存在，存在线性序的集合被称为字典。,集合的基本运算,SetUnion(A,B),并集运算SetIntersection(A,B),交集运算SetDifference(A,B),差集运算SetAssign(A,B),集合间赋值运算SetEqual(A,B),判等运算SetMember(x,S),成员运算,数组实现集合,数组的大小至少等于集合的值域。如果x在集合中，则Ax=1,否则Ax=0。上述数组表示集合3，4，6，7，8。这种实现方式优点：添加元素、删除元素、查询元素均可以在O(1)完成。缺点：浪费空间。,散列表,在算法中用到的集合，往往不经常作交并补运算，而经常要判断一个元素是否属于集合，这种数据类型被称为符号表用数组实现符号表，复杂度较高用位向量实现符号表，只适用于较小规模。实现符号表的重要技巧是散列技术。开散列将符号表元素存放在一个潜在的无穷的空间里。闭散列将符号表元素直接存放在桶数组单元中。,散列表的概念,散列表设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K（|K|比|U|小得多）。散列方法是使用函数h将U映射到表T0.B-1的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。桶T0.B-1的每一个称为桶，共有B个桶散列值h(x)的值称为散列值，h(x)称为散列函数。冲突：两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。,散列表的增删查,当根据散列函数把元素放入桶中，发现桶