等级考基础数据结构.ppt

《等级考基础数据结构.ppt》由会员分享，可在线阅读，更多相关《等级考基础数据结构.ppt（114页珍藏版）》请在三一文库上搜索。

1、等级考基础数据结构与算法,东华大学计算机学院 孙 莉 2012年2月12日,1.1 数据结构的研究对象,数据结构的研究内容： 非数值数据之间的结构关系， 及如何表示，如何存储，如何处理。 归纳为三部分：逻辑结构、存储结构和运算集合。 按某种逻辑关系把一批数据组织起来， 按一定的映象方式把它存放在计算机的存储器中， 并在这些数据上定义一个运算的集合。,逻辑结构是数据结构的抽象，存储结构是数据结构的实现 存储结构的二种类型: 顺序存储结构通过在存储器中的相对位置， 表示数据的逻辑结构。 非顺序存储结构（链式存储结构） -由指针表示数据间的逻辑关系。,1.3 常用的数据结构,(1) 线性结构：结构中

2、的数据元素之间存在着一对一的线性关系。线性表、栈、队、字符串、数组 (2) 树形结构：结构中的数据元素之间存在着一对多的层次关系。-非线性结构 (3) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。- 非线性结构,一 算法的概念 算法是对特定问题求解步骤的一种描述,算法的基本特征： 1）可行性：组成算法的操作必须能够在计算机上实现。 2）确定性：算法的每一步操作必须清晰无二义性。 3）有穷性：算法必须在有限步内结束； 4）有足够的情报：0个或多个输入；1个或多个输出； 算法描述的方法很多，如自然语言、框图、类C等,例: 求两个正整数 m，n 中的最大数MAX的算法 （1）若

3、m n 则 max=m （2）若 m = n 则 max=n,1、正确性： (1) 没有语法错误； (2) 对于几组输入数据能够得出满足要求的结果； (3) 对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。 (4) 对于一切合法的输入数据都能产生满足要求的结果。 2、可读性：便于阅读、理解、调试、修改； 3、健壮性：对不合法的输入能作出正确的反映与处理； 4、高效性：执行时间短（时间复杂度）、 需求存储空间省（空间复杂度）,评价算法标准,1 时间复杂度T（n） 以求解问题的基本操作的执行次数作为算法时间的度量。,14 算法与算法分析,O（n3） 称为矩阵相乘算法时间复杂度； O（

4、n3）表示矩阵相乘算法执行时间与n3成正比, 即O（n3）与n3 同一数量级；,例 n 阶矩 阵相乘的算法,For ( i = 1; i=n; i+ ) For (j = 1; j=n; j+ ) c i j = 0 ; For (k = 1; k= n; k+ ) c i j += a i k * b k j ,矩阵相乘的基本运算：乘法 加法；,数据结构中常用的时间复杂度频率计数有7个： O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型,14 算法与算法分析,例计算 解法1 先计算x 的幂, 存于powe

5、r 中,再分别乘以相应的系数 # define N 100 float evaluate (float coef , float x , int n ) float powerN, f; int i; for (power 0=1, i = 1; i=n; i+ ) poweri=x*poweri-1; for (f = 0, i=0; i=N; i +) f=f+coefi*poweri; return(f); ,问题规模为n, 算法时间复杂度: O(n) 空间复杂度： O(N),线性表,线性表是最简单、最常用的数据结构。 栈、队列、串是特殊的线性表，数组和广义表是线性表的扩展-线性结构,线

6、性表是n 个数据元素的有限序列， 通常记作（a1, a2, a3, , an ）。,2. 1 线性表的概念,例、英文字母表（A, B, C, D, E Z ）。 某单位的电话号码簿。,一 线性表的逻辑结构,2.1 线性表的概念,设 A=（a1, a2, . , ai -1, ai , ai+1, , an ）是一线性表， 1） 同一线性表中的元素必须是同一类型的； 2） 在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai 的前件，ai+1 是ai 的后件； 3） 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个前件，有且仅有一个后件； 4） 线性表中元

7、素的个数n 称为线性表的长度，n=0 时称为空表；,用一组连续的内存单元依次存放线性表的数据元素。,线性表（a1,a2, a3, . an ） 的顺序存储结构,用顺序存储结构存储的线性表称为顺序表,2.2 线性表的顺序存储和实现,一 线性表的顺序存储结构,2.2 线性表的顺序存储和实现,说明： 元素之间的逻辑关系，通过元素的存储顺序表示出来. 设线性表中每个数据元素占 t 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai ) = Loc( a1 )+ ( i 1) t 其中Loc( a1 )基地址，随机存取,2.2 线性表的顺序存储

8、和实现,插入位置 移动元素个数 1 n 2 n-1 i n-i+1 n 1 n+1 0,插入算法时间复杂度分析 算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与插入位置有关。,2.2 线性表的顺序存储和实现,由此可见 在顺序表中插入一个元素 ，平均要移动表的一半元素。 表长为n的顺序表，插入算法的时间复杂度为 O（n）,假设在线性表的任何位置插入元素的概率相同，即 pi= 1/(n+1),设pi为在第i个元素之前插入元素的概率，在长度为n的顺序表中插入一个元素，所需移动元素个数数学期望值为：,删除算法时间复杂度分析,假设在线性表的任何位置删除元素的概率相同，即 pi=

9、1/n 删除所需移动元素个数的数学期望值：,2.2 线性表的顺序存储和实现,顺序表是线性表最简单的一种存储结构,2.3 线性表的链式存储和实现,线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。 为了表示线性表中元素的先后关系，每个元素除需要存储自身的信息外，还要保存直接前趋元素或直接后继元素的存储位置。,一 线性链表的概念 1 线性链表,2. 3. 1 线性链表,用一组任意的存储单元存储线性表中的数据元素，对每个数据元素保存自身信息和直接后继元素的存储位置。,用链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的,结点：数据元素及直接后继的存储位置（

10、地址）组成一个数据元素的存储结构，称为一个结点； 结点的数据域 ：保存数据元素; 结点的指针域 ：保存数据元素直接后继的存储地址;,线性链表有关术语,2. 3. 1 线性链表,存储数据元素,存储后继结点 存储地址,2. 3. 1 线性链表,头指针：存放线性链表中第一个结点的存储地址; 空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针; 头结点：链表的第一个元素结点前的附加结点； 带头结点的线性链表：第一个元素结点前增加一个附加结点的线性链表称为 带头结点的线性链表；,head是头指针,头结点,空指针,head,线性链表的每个结点中只有一个指针域 故也称为单链表,插入结点(存a),

11、q=(LNODE *)malloc(sizeof(LNODE); q-deta=a; q-next=p- next; p- next =q;,head,y,x,p,head,q,插入操作功能：在线性链表的第i个元素结点之前插入一个新元素结点e； 插入操作图示：,2. 3. 1 线性链表,插入前,插入后,head,head,4）删除结点,q=p-next; p- next =q- next; free(q);,head,y,x,q,head,p,p,2. 3. 1 线性链表,删除前,删除后,p,p,q,q,2. 3. 1 线性链表小结,线性链表是线性表的一种链式存储结构,线性链表的特点 1 通过

12、保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系； 2 插入、删除操作通过修改结点的指针实现； 3 不能随机存取元素；,1 循环链表的概念 循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点（首尾相连的单链表） 2 循环链表图示,2. 3 . 2 循环链表,(a)非空表 （b）空表,循环链表,说明 在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面； 对循环链表，有时不给出头指针，而是给出尾指针,a,a1,an,a-next 给出尾指针的循环链表,2.3.4 双向链表 循环单链表，虽然从任一结点出发沿着指针链能找到其前件，但时间耗费是O

13、(n) 。如果希望从表中快速确定某一个结点的前件，另一个解决方法是在链表的每个结点里再增加一个指向其前件的指针域prior。 这样形成的链表中就有两条方向不同的链，称为双向链表。,线性表小结,线性表的顺序存储结构顺序表， 链式存储结构-线性链表,循环链表, 双向链表.不同的存储结构，线性表的同一操作的算法是不同的: 在顺序存储结构下，线性表的插入、删除操作，通过移动元素实现; 在线性链表存储结构下，线性表的插入、删除操作，通过修改指针实现。,3.1 栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,删除,3.

14、1.1 栈的概念 一 什么是栈?,3.1 栈,将表中允许进行插入、删除操作的一端称为栈顶(Top)， 栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。 表的另一端称为栈底(Bottom)。 当栈中没有元素时称为空栈。 栈的插入操作称为进栈或入栈，删除操作称为出栈或退栈。,栈,3.1 栈,栈的示意图,出栈,进栈,栈的特点 后进先出,第一个进栈的元素在栈底， 最后一个进栈的元素在栈顶， 第一个出栈的元素为栈顶元素， 最后一个出栈的元素为栈底元素,小 结 1 栈是限定仅能在表尾一端进行插入、 删除操作的线性表； 2 栈的元素具有后进先出的特点； 3 栈顶元素的位置由一个称为栈顶指针的 变量指示

15、， 进栈、出栈操作要修改栈顶指针；,3.1 栈,32 队列,3.2.1 队列的概念 一 什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,删除,33 队列,a1 a2 a3 an,入队列,队头,队尾,出队列,队 列 的 示 意 图,队列的特点 先进先出,第一个入队的元素在队头， 最后一个入队的元素在队尾， 第一个出队的元素为队头元素， 最后一个出队的元素为队尾元素,rear,front,J1,rear,front,J2,（a)空队列,(b)J1,J2相继入队列,(c)J1出队,(d)J3,J4, J

16、5和J6相继入队之后,J2出队,rear,front,3. 3 队列,rear,front,J5,J4,J3,front,rear为整数,J2,J6,3. 3 队列,3 . 循环队列,(b)队空,(a)队满,J7,3. 3 队列,判分队空、队满方法： 1、另设一个标志S以区分队空、队满。 S=0 队空： front=rear; S=1 队满： front=rear; 2、少用一个空间，如图C则为队满 元素个数：（尾-头+MAX）MOD MAX,front,（c）,3. 3 队列,入队操作 ：将元素 x 插入队尾,元素 x 入队前,元素 x 入队后,3. 3 队列,出队操作 ：删除队头元素；,小

17、 结 1 队列是限定仅能在表尾一端进行插入，表头一端删除 操作的线性表； 2 队列中的元素具有先进先出的特点； 3 队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示， 4 入队操作要修改队尾指针，出队操作要修改队头指针；,树和二叉树,1树的定义,树是n个结点的有限集合T，当n=0时，称为空树；当n0时，T满足如下条件：在任一棵非空树中： （1）有且仅有一个称为根的结点。 （2）其余结点可分为M个互不相交的子集合，而且这些子集中的每一个本身又是一棵树，也称为根的子树。,2树的实例 树可表示具有分枝结构关系的对象,例1家族族谱 设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、

18、K、L、M，他们之间的关系可用树表示：,计算机中树是常用的数据组织形式 尽管有些应用中数据元素之间并不存在分支结构关系，但为了便于管理和使用数据，将它们用树的形式来组织。 例2 计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件都是用树的形式来组织的。,3、树的 基本术语 树的结点：包含一个数据元素及若干指 向子树的分支； 孩子结点：结点的子树的根称为该结点 的孩子， B、C是A的孩子； 双亲结点：B 结点是A 结点的孩子，则A 结点是B 结点的双亲； 兄弟结点：同一双亲的孩子结点， H、I、 J互为兄弟； 堂兄结点：同一层上结点， E、F、G、H、I、J、互为堂兄弟；

19、,3、树的 基本术语 结点的层次：根结点的层次定义为1；根的孩子为第二层，依此类推； 树的深度：树中所有结点的层次的最大值 结点的度：结点子树的个数 树的度： 树中结点度的最大值。 叶子结点：度为 0 的结点； 分枝结点：度不为0的结点；,一 二叉树的概念 1 二叉树的定义 二叉树： 或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。,一 二叉树的概念,二叉树说明 1）二叉树中每个结点最多有两个子树； 既：二叉树每个结点度小于等于2; 2）左、右子树不能颠倒有序树; 3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;,(a)、(b)是不同的二叉树， (

20、a)的左子树有四个结点， (b)的左子树有两个结点,(a),(b),F,A,2 二叉树的基本形态,(a)空树,(b)只有根,(c) 右子树空,(e) 左子树空,(d) 左、右子树非空,二、 二叉树的性质,性质1: 在二叉树的第i层上至多有2i-1个结点(i1)。 性质2: 深度为k的二叉树至多有2k-1个结点（k1）。,性质3: 对任意一棵二叉树T，若叶结点数为n0，而其度为2的结点数为n2，则n0=n2+1。,两种特殊的二叉树 满二叉树：深度为k的二叉树，如有2k-1个结点则称为满二叉树；,K=3的满二叉树,K=2的满二叉树,满二叉树的顺序表示：,从二叉树的根开始， 从上到下， 从左到右，逐

21、层进行编号（1， 2， ， n）。例如图（a）所示的满二叉树的顺序表示为: (1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11， 12， 13， 14， 15)。 ,完全二叉树： 深度为k，结点数为n的二叉树，如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应，则为完全二叉树， 如上图 (b)所示。 满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。,性质4：具有n个结点的完全二叉树的深度为log2n+1。,性质5: 对于有n个结点的完全二叉树， 按照从上到下、从左到右的顺序对二叉树中的所有结点从1开始顺序编号， 则对于任意的序号为i的结点有： （1）

22、如i=1，则序号为i的结点是根结点， 无双亲结点； 如i1， 则序号为i的结点的双亲结点序号为i/2 （下取整） （2） 如2in，则序号为i的结点无左孩子；如2in，则序号为i的结点的左孩子结点的序号为2i。 （3） 如2i1n，则序号为i的结点无右孩子；如2i1n， 则序号为i的结点的右孩子结点的序号为2i1。,二叉树存储结构-二叉链表 二叉链表中每个结点包含三个域：数据域、左指针域、右指针域,二叉链表图示,若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域， 其中必有n+1个空的指针域。 ,二、二叉树的遍历,遍历：按某种顺序访问二叉树的每个结点，而且每个结点仅被访问一次。 访问

23、：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。,二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树,令：L：遍历左子树 T：访问根结点 R：遍历右子树,约定先左后右, 有三种遍历方法： T L R前序遍历、 L T R中序遍历、 L R T后序遍历。,先序遍历（T L R） 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；,先序遍历序列：A,B,D,E,G,C,F,例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按 T L R 的顺序遍历左子树 （3）先序遍

24、历右子树：即按 T L R 的顺序遍历右子树,中序遍历（L T R） 若二叉树非空 （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树,中序遍历序列： D,B,G,E,A,C,F,例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按 L T R 的顺序遍历左子树 （2）访问根结点A （3）中序遍历右子树：即按 L T R 的顺序遍历右子树,后序遍历（L R T） 若二叉树非空 （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点,后序遍历序列： D,G,E,B,F,C,A,例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按 L R T 的顺序遍历左子树 （2）后序遍

25、历右子树：即按 L R T 的顺序遍历右子树 （3）访问根结点A,后序遍历序列：a,b,c,d,-,*,+,e,f,/,-,中序遍历序列：a,+,b,*,c,-,d,-,e,/,f,例：中序遍历、后序遍历下图所示的二叉树,例:已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为? A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG B,二叉树,查找,5.1 查找的基本概念,查找（列）表：由同一类型的数据元素（或记录）构成的集合， 可利用任意数据结构实现。 关键字：数据元素的某个（几个）数据项的值。如果一个数

26、据项可以唯一标识列表中的一个数据元素， 则称其为关键字。,查找： 根据给定的关键字值，在特定的查找（列）表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。 若找到相应的数据元素， 称查找成功，否则称查找失败,52 线性表的查找,5.2.1 顺序查找-最简单的查找方法 顺序查找的基本思想,从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。 顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序

27、查找的表中元素可以是无序的。, 顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n， 则顺序查找算法的平均查找长度为：,顺序查找的特点,顺序查找的优点是算法简单，对查找表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序排，它都同样适用。 顺序查找的缺点是查找效率低，当 n 较大时，不宜采用顺序查找。,5.2.2二分查找（折半查找） 1.二分查找的基本思想,高效率的查找方法。要求表中元素按关键字有序(升序或降序)。假设表中元素为升序排列。 二分查找的基本思

28、想是： 首先将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功； 否则利用中间位置记录将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。,例如，假设给定有序表中关键字为： 05,13,19,21,37,56,64,74,80,88,92，查找K=21的情况：,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8

29、 9 10,3.二分查找的性能分析,二分查找的过程可以用二叉树来描述。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。 例如，给定的关键字序列05,13,19,21,37,56,64,74,80,88,92，的判定树。 0 1 2 3 4 5 6 7 8 9 10,在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为 log2n,排序,61 基本概念,6.1.1 排序定义,排序就是把一组记录（元素）按照某个域的值的递增或递减的次序重新排列的过程。(按学号的递增),表7-1 学生

30、档案表,为讨论方便，我们直接将排序码写成一个一维数组的形式， 并且在没有声明的情形下，所有排序都按排序码的值递增排列。,排序,插入排序（直插排序、希尔排序）,交换排序（冒泡排序、快速排序）,选择排序 （直选排序、堆排序）,归并排序（二路归并排序）,62 插入排序,6.2.1直接插入排序 1直接插入排序（Straight Insertion Sorting）,基本思想：把n个待排序的元素看成一个有序表和一个无序表， 开始时有序表中只包含一个元素，无序表中包含有n-1个元素， 排序过程中每次从无序表中取出第一个元素，把它的排序码 依次与有序表元素的排序码进行比较，将它插入到有序表中 的适当位置，使

31、之成为新的有序表。,例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如图7-1所示。,3直接插入排序的效率分析,直接插入排序算法十分简单。 空间:只需要一个元素的辅助空间，用于元素的位置交换。 时间:外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1，2，n-1）。 直接插入排序的时间复杂度为O（n2）。 最坏情况比较n(n-1)/2,6.2.2希尔排序,希尔排序(缩小增量排序):1959年由D.L.Shell提出来的。 基本思想：先将整个待排元素序列分割成若干个子序列（由 “增量”确定

32、）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。,例如，n=8，数组array 的八个元素分别为：91，67，35，62，29，72，46，57。下面用图7-2给出希尔排序算法的执行过程。,希尔排序的效率分析 与增量有关， 最坏情况，希尔排序的时间复杂性在O（nlog2n）。,63 交换排序,6.3.1 冒泡排序 基本思想:,对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部，就象水底下的气泡一样

33、逐渐向上冒。,例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。下面用图7-3给出冒泡排序算法的执行过程。,冒泡排序的效率分析 若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0； 若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n )/2， 最坏情况比较n(n-1)/2 因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。,6.3.2 快速排序,基本思想是：取待排序序列中的某个元素（一般第一个元素）作为基准，通过一趟排序，将待排元素分为左右两个子序列

34、， 左子序列元素的排序码均小于或等于基准元素的排序码， 右子序列的排序码则大于基准元素的排序码， 然后分别对两个子序列继续进行快速排序，直至整个序列有序。 元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面，排序码较小的记录一次就能够交换到前面，记录每次移动的距离较远，因而总的比较和移动次数较少。,例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。,3快速排序的效率分析,若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2nhlog2n+1 ，所以总的比较次数不会超过(n+1) lo

35、g2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。 已经证明，快速排序的平均时间复杂度也为O（nlog2n）。 若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，总的比较次数为n(n-1)/2 。因此，快速排序的最坏时间复杂度为O(n2)。 快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。,快速排序是一种不稳定的排序方法。,64 选择排序,6 . 4.1 直接选择排序 基本思想,直接选择排序是一种简单的排序方法。基本思想是：第一次从array0arrayn-1中选取最小值，与a

36、rray0交换，第二次从array1arrayn-1中选取最小值，与array1交换，第三次从array2arrayn-1中选取最小值，与array2交换，第i次从arrayi-1arrayn-1中选取最小值，与arrayi-1交换，, 第n-1次从arrayn-2arrayn-1中选取最小值，与arrayn-2交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。,例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图7-5所示。,直接选择排序的效率分析,在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行n-i次比较

37、（1in-1），而每次交换最 多需3次移动，因此，总的比较次数C= =(n2-n)/2， 总的移动次数M= =3(n-1)。 直接选择排序的时间复杂度为O(n2)数量级，所以当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些。 最坏情况比较n(n-1)/2,75 归并排序,1、基本思想：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从1增加到n（元素个数）时，整个区间变为一个，即为有序序列.,例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序过程如图7-10所示。算法P284,归并

38、排序的效率分析,归并排序的时间复杂度为O(nlog2n)。,归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为O(n)，比前面介绍的其它排序方法占用的空间大。,对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 A) 冒泡排序为n/2 B) 冒泡排序为n C) 快速排序为n D) 快速排序为n(n-1)/2,D,B,例:线性表的顺序存储结构和线性表的链式存储结构分别是? A) 顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意

39、存取的存储结构,在单链表中，增加头结点的目的是 A) 方便运算的实现 B) 使单链表至少有一个结点 C) 标识表结点中首结点的位置 D) 说明单链表是线性表的链式存储实现 A,例:对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为? A) log2n B) n/2 C) n D) n+1,C,例:链表不具有的特点是 A) 不必事先估计存储空间 B) 可随机访问任一元素 C) 插入删除不需要移动元素 D) 所需空间与线性表长度成正比 B,B,例:如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是? A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2 D) 任意顺序,例:栈和队列的共同特点是 A) 都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点 C,例:下列关于栈的描述中错误的是 A)栈是先进后出的线性表 B) 栈只能顺序存储 C) 栈具有记忆作用 D) 对栈的插入与删除操作中，不需要改变栈底指针,B,例:数据结构分为逻辑结构和存储结构，循环队列属于【5】结构。,存储结构,例:已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 A) acbed B) decab C) deabc D) cedba D,