等级考基础-数据结构.ppt

等级考基础数据结构与算法,东华大学计算机学院 孙 莉 2016年2月,1 数据结构基本概念,1.1数据结构的研究内容： 非数值数据之间的结构关系， 及如何表示，如何存储，如何处理。 归纳为三部分：逻辑结构、存储结构和运算集合。,存储结构的二种类型: 顺序存储结构通过在存储器中的相对位置， 表示数据的逻辑结构。 非顺序存储结构（链式存储结构） -由指针表示数据间的逻辑关系。,1.2常用的数据结构,(1) 线性结构：结构中的数据元素之间存在着一对一的线性关系。线性表、栈、队 (2) 树形结构：结构中的数据元素之间存在着一对多的层次关系。-非线性结构 (3) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。- 非线性结构,算法的概念 算法是对特定问题求解步骤的一种描述,算法的基本特征：1）可行性：组成算法的操作必须能够在计算机上实现。 2）确定性：算法的每一步操作必须清晰无二义性。3）有穷性：算法必须在有限步内结束；4）有足够的情报：0个或多个输入；1个或多个输出； 算法描述的方法很多，如自然语言、框图、类C等,例: 求两个正整数 m，n 中的最大数MAX的算法 （1）若 m n 则 max=m （2）若 m = n 则 max=n,1、正确性： (1) 没有语法错误； (2) 对于几组输入数据能够得出满足要求的结果； (3) 对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。 (4) 对于一切合法的输入数据都能产生满足要求的结果。 2、可读性：便于阅读、理解、调试、修改； 3、健壮性：对不合法的输入能作出正确的反映与处理； 4、高效性：执行时间短（时间复杂度）、 需求存储空间省（空间复杂度）,1.4评价算法标准,时间复杂度T（n） 以求解问题的基本操作的执行次数作为算法时间的度量。,14 算法与算法分析,O（n3） 称为矩阵相乘算法时间复杂度； O（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 ,矩阵相乘的基本运算：乘法 加法；,14 算法与算法分析,例计算 解法1 先计算x 的幂, 存于power 中,再分别乘以相应的系数 # 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),2 线性表,线性表是最简单、最常用的数据结构。 栈、队列是特殊的线性表-线性结构,线性表是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） 线性表中元素的个数n 称为线性表的长度，n=0 时称为空表；,用一组连续的内存单元依次存放线性表的数据元素。,用顺序存储结构存储的线性表称为顺序表,2.2 线性表的顺序存储和实现,线性表（a1,a2, a3, . an ）的顺序存储结构,2.2 线性表的顺序存储和实现,设线性表中每个数据元素占 t 个存储单元，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai ) = Loc( a1 )+ ( i 1) t 其中Loc( a1 )基地址，随机存取 顺序存储结构、随机存取结构,2.2 线性表的顺序存储和实现,插入位置 移动元素个数 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= 1/n 删除所需移动元素个数的数学期望值：,2.3 线性表的链式存储和实现,线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。 为了表示线性表中元素的先后关系，每个元素除需要存储自身的信息外，还要保存直接前趋元素或直接后继元素的存储位置。,线性链表的概念1 线性链表,2. 3. 1 线性链表,用链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的,结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点； 结点的数据域 ：保存数据元素; 结点的指针域 ：保存数据元素直接后继的存储地址;,线性链表有关术语,2. 3. 1 线性链表,存储数据元素,存储后继结点 存储地址,2. 3. 1 线性链表,头指针：存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针;头结点：链表的第一个元素结点前的附加结点；,head是头指针,头结点,空指针,head,线性链表的每个结点中只有一个指针域 故也称为单链表,插入结点(存a),q-deta=a; q-next=p- next; p- next =q;,head,y,x,p,head,q,4）删除结点,q=p-next; p- next =q- next; free(q);,head,y,x,q,head,p,p,随机存储结构、顺序存取结构,1 循环链表 循环链表是将线性链表的最后一个结点的指针指向链表的第一个结点（首尾相连的单链表）,循环链表,(a)非空表 （b）空表,2双向链表,3 栈和队列,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,删除,什么是栈?,3.1 栈,3.1 栈,将表中允许进行插入、删除操作的一端称为栈顶(Top)， 栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。 表的另一端称为栈底(Bottom)。 当栈中没有元素时称为空栈。 栈的插入操作称为进栈或入栈，删除操作称为出栈或退栈。,3.1 栈,栈的示意图,出栈,进栈,栈的特点 后进先出,第一个进栈的元素在栈底，最后一个进栈的元素在栈顶， 第一个出栈的元素为栈顶元素， 最后一个出栈的元素为栈底元素,B,例:如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是? A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2D) 任意顺序,32 队列,什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表,（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, J5和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) 或少用一个空间 Real+1=front 为满 栈、队列的存储结构？,front,（c）,4 树和二叉树,4 1 树的定义,树是n个结点的有限集合T，当n=0时，称为空树；当n0时，T满足如下条件：在任一棵非空树中：（1）有且仅有一个称为根的结点。（2）其余结点可分为M个互不相交的子集合，而且这些子集中的每一个本身又是一棵树，也称为根的子树。,树的实例树可表示具有分枝结构关系的对象,例1家族族谱 设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可用树表示：,计算机中树是常用的数据组织形式 尽管有些应用中数据元素之间并不存在分支结构关系，但为了便于管理和使用数据，将它们用树的形式来组织。 例2 计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件都是用树的形式来组织的。,树的 基本术语 树的结点：包含一个数据元素及若干指 向子树的分支； 孩子结点：结点的子树的根称为该结点 的孩子， B、C是A的孩子； 双亲结点：B 结点是A 结点的孩子，则A 结点是B 结点的双亲； 兄弟结点：同一双亲的孩子结点， H、I、 J互为兄弟；,树的 基本术语 结点的层次：根结点的层次定义为1；根的孩子为第二层，依此类推；树的深度：树中所有结点的层次的最大值结点的度：结点子树的个数树的度： 树中结点度的最大值。叶子结点：度为 0 的结点；分枝结点：度不为0的结点；,4.2 二叉树 二叉树的定义 二叉树： 或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。,二叉树中每个结点最多有两个子树；既：每个结点度小于等于2; 左、右子树不能颠倒有序树;,(a)、(b)是不同的二叉树， (a)的左子树有四个结点， (b)的左子树有两个结点,(a),(b),F,A,二叉树的基本形态,(a)空树,(b)只有根,(c) 右子树空,(e) 左子树空,(d) 左、右子树非空,二叉树的性质,性质1: 在二叉树的第i层上至多有2i-1个结点(i1)。 性质2: 深度为k的二叉树至多有2k-1个结点（k1）。,性质3: 对任意一棵二叉树T，若叶结点数为n0，而其度为2的结点数为n2，则n0=n2+1。,二叉树存储结构-二叉链表 二叉链表中每个结点包含三个域：数据域、左指针域、右指针域,二叉链表图示,二叉树的遍历,遍历：按某种顺序访问二叉树的每个结点，而且每个结点仅被访问一次。 访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。,二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树,令：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）前（先）序遍历右子树：即按 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）后序遍历右子树：即按 L R T 的顺序遍历右子树 （3）访问根结点A,例:已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为? A) GEDHFBCAB) DGEBHFCAC) ABCDEFGHD) ACBFEDHG B,5 查找,5.1 查找的基本概念,查找（列）表：由同一类型的数据元素（或记录）构成的集合， 可利用任意数据结构实现。 关键字：数据元素的某个（几个）数据项的值。如果一个数据项可以唯一标识列表中的一个数据元素， 则称其为关键字。,查找： 根据给定的关键字值，在特定的查找（列）表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。,52 线性表的查找,5.2.1 顺序查找-最简单的查找方法 顺序查找的基本思想,从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。 顺序查找既适用于顺序表，也适用于链表。 用顺序表，查找可从前往后扫描，也可从后往前扫描， 但若采用单链表，则只能从前往后扫描。 顺序查找的表中元素可以是无序的。, 顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n， 则顺序查找算法的平均查找长度为：,顺序查找的特点,顺序查找的优点是算法简单，对查找表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序排，它都同样适用。 顺序查找的缺点是查找效率低，当 n 较大时，不宜采用顺序查找。,5.2.2二分查找（折半查找） 1.二分查找的基本思想,要求表中元素按关键字有序(升序或降序)。假设表中元素为升序排列。 二分查找的基本思想是： 首先将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功； 否则利用中间位置记录将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。,例如，假设给定有序表中关键字为： 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 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,6 排序,61 基本概念,6.1.1 排序定义,排序就是把一组记录（元素）按照某个域的值的递增或递减的次序重新排列的过程。(按学号的递增),表7-1 学生档案表,在没有声明的情形下，所有排序都按排序码的值递增排列。,排序,插入排序（直插排序、希尔排序）,交换排序（冒泡排序、快速排序）,选择排序 （直选排序、堆排序）,归并排序（二路归并排序）,62 插入排序,6.2.1直接插入排序 1直接插入排序（Straight Insertion Sorting）,基本思想：把n个待排序的元素看成一个有序表和一个无序表， 开始时有序表中只包含一个元素，无序表中包含有n-1个元素， 排序过程中每次从无序表中取出第一个元素，把它的排序码 依次与有序表元素的排序码进行比较，将它插入到有序表中 的适当位置，使之成为新的有序表。,例如，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提出来的。 基本思想：先将整个待排元素序列分割成若干个子序列（由 “增量”确定）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。,例如，n=8，数组array 的八个元素分别为：91，67，35，62，29，72，46，57。下面用图7-2给出希尔排序算法的执行过程。,希尔排序的效率分析 与增量有关， 最坏情况，希尔排序的时间复杂性在O（nlog2n）。,63 交换排序,6.3.1 冒泡排序 基本思想:,对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部，就象水底下的气泡一样逐渐向上冒。,例如，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 快速排序,基本思想是：取待排序序列中的某个元素（一般第一个元素）作为基准，通过一趟排序，将待排元素分为左右两个子序列， 左子序列元素的排序码均小于或等于基准元素的排序码， 右子序列的排序码则大于基准元素的排序码， 然后分别对两个子序列继续进行快速排序，直至整个序列有序。 元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面，排序码较小的记录一次就能够交换到前面，记录每次移动的距离较远，因而总的比较和移动次数较少。,例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。,3快速排序的效率分析,若快速排序出现最好的情形（左、右子区间的长度大致相等），快速排序的最好时间复杂度应为O（nlog2n）。 已经证明，快速排序的平均时间复杂度也为O（nlog2n）。 若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，总的比较次数为n(n-1)/2 。因此，快速排序的最坏时间复杂度为O(n2)。 快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。,64 选择排序,6 . 4.1 直接选择排序 基本思想,第一次从array0arrayn-1中选取最小值，与array0交换，第二次从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次比较（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,归并排序的效率分析,归并排序的时间复杂度为O(nlog2n)。,归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为O(n)，比前面介绍的其它排序方法占用的空间大。,对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是A) 冒泡排序为n/2 B) 冒泡排序为n C) 快速排序为n D) 快速排序为n(n-1)/2,D,