数据结构与算法

第二章 数据结构算法2.1 基本概率考点1数据结构的基本概念1. 数据在计算机系统中，数据不仅包含了通常的数值概念，还有更广泛的含义我们把采用计算机 对客观事物进行识别、存储和加工所做的描述，统称为数据。简言之，数据就是计算机化的 信息数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可 分割的最小单位，又称为关键码，其值能够唯一确定一个数据元素的数据项。2. 数据结构数据结构包括3 个方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式，以及 在这些数据上定义的运算的集合。(1) 数据的逻辑结构。数据的逻辑结构与数据在计算机中的存储方式无关，它用来抽象地反 映数据元素之间的逻辑关系。逻辑结构可分为线性结构和非线性结构。最常见的线性结构是 线性表，最典型的非线性结构是树型结构。(2) 数据的存储结构。数据的存储结构实现了数据的逻辑结构在计算机内的存储问题，存 储结构又称为物理结构。存储结构分为顺序存储结构与链式存储结构。(3) 数据的运算。数据的各种逻辑结构都有相对应的运算，每一种逻辑结构都有一个运算 的集合。数据运算主要包括查找(检索)、排序、插人、更新及删除等。考点2主要的数据存储方式实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。顺序存储结构和链式存储 结构是两种最主要的存储方式。1. 顺序存储结构顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关 系由存储单元的相邻关系来决定，它主要用于存储线性结构的数据。顺序存储结构的主要特 点如下。(1) 由于节点之间的关系由物理上的相邻关系决定，所以节点中没有链接信息域，只有自 身的信息域，存储密度大，空间利用率高。(2) 数据结构中第 i 个节点的存储地址乙可由下述公式计算求得：LiL0+(i l)xKL0 为第一个节点存储地址，左为每个节点所占的存储单元数。(3) 插人、删除运算会引起相应节点的大量移动各节点的物理地址是相邻的，每一次插人 删除运算会引起相应节点物理地址的重新排列。2. 链式存储结构链式存储结构打破了计算机存储单元的连续性，可以将逻辑上相邻的两个数据元素存放在 物理上不相邻的存储单元中链式存储结构的每个节点中至少有一个节点域，来体现数据之间 逻辑上的联系。链式存储结构的主要特点包括以下几个方面。(1) 节点中除自身信自、夕卜，还有表示链接信息的指针域，因此比顺序存储结构的存储密 度小，存储空间利用率低。(2) ：罗辑上相邻的节点物理上不一定相邻，可用于线性表、树、图等多种逻辑结构的存储表示。(3) 插人、删除等操作灵活方便，不需要大量移动节点，只需将节点的指针值修改即可。考点3算法设计与分析在计算机领域，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构 的基础上施加的一种运算，它是解决特定问题的方法。一个算法所占用的计算机资源包括时 间代价和空间代价两个方面时间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法运行时所耗费的时间也以某种单位由f( 1)增至f(n)，则称该算法的时间代价为f(n)。空间代价的含义是：当问题的规模以某种单位由1增至n时，解决该问题的算法实现时所占用的空间也以某种单位由到g(1)增至g(n)，则称该算法的空间代价为g(n)。2.2 线性表线性表的逻辑结构是由n个数据元素组成的一个有限序列。线性表中所包含元素的个数叫 线性表的长度它是可变的可同线性表中增加或删除元素。线性表包括顺序表、链表、散 列表和串等。线性表的基本运算有：置表空、求表长、读表元素、插人、删除及检索等操作。考点 4 顺序表和一维数组线性表的顺序存储是线性表的一种最简单的存储结构。其存储方法是：在内存中为线性表 开辟一块连续的存储空间，该存储空间所包含的存储单元数要大于或等于线性表的长度，让 线性表的第一个元素存储在这个存储空间的第一个单元中，第二个元素存储在第二个单元 中，其他元素依次类推。一般情况下，若长度为n的顺序表，在任何位置土插入或删除的概 率相等，元素移动的平均次数均为n/2。考点 5 链表链表分为线性链表和非线性链表二线性链表是线性表的链式存储表示，非线性链表是非线 性数据结构树和图的链式存储表示。1. 线性链表线性链表也称为单链表，其每个一节点中只包含一个指针域。对链表进行插人、删除运算 时只需改变节点中指针域的值。(1) 在指针一 P 后插人指针 9 的关键运算步骤：q f. link：=Pf. link：p f. link：=q；(2) 删除指针 P 后继节点 q 的关键运算步骤：q：=pf . link；pf. link：=qf. link；(3) 在第一个节点(或称头节点) 前插人一个指针 P 的关键运算步骤：pf. link：=head；head：二 P；(4) 删除表中头节点的关键运算步骤：head：=headf . link：2. 双链表在双链表中，每个节点中设置有两个指针域，分别用以指向其前驱节点和后继节点o rlink 指向节点的后继，Hink指向节点的前驱，这样的结构方便向后和向前查找。若要在双链表中删除指针P所指的节点时，只需修改其前驱的rlink字段和后继的Mink 字段，步骤如下：pf . llinkf. rlink：=pf. rlink；PfT. rlinkf. llink：=Pf. llink；(2)如果要在指针P后面插人指针q所指的新节点，只需修改P指针所指节点的rlink字段 和原来后继均Ilink字段，并重新设置q所指节点的Mink和rlink值，步骤如下：q f. Mink：=P：qf. rlink：=Pf. rlink;Pf. rlink r. Rink：= q；pf. rlink：=q;3. 可利用空间表可利用空间表的作用是管理可用于链表插人和删除的节点，当链表插人需要一个新节点 时，就从可利用空间表中删除第一个节点，用这个节点去做链表插人；当从链表中删除一个 节点时，就把这个节点插人到可利用空间表的第一个节点前面。考点6栈栈又称为堆栈，它是一种运算受限的特殊的线性表，仅允许在表的一端进行插人和删除运 算，可进行运算的一端为栈顶(top)，另一端为栈底(bottom)。表中无任何元素的栈称为空栈。 由于栈的插人和删除运算仅在栈顶进行，后进栈的元素必定先被删除，所以又把栈称为“后 进先出”(LIFO)表。栈的基本操作有：(1) push(S,X)。往栈S中插人(或称推人)一个新的栈顶元素x,即进栈。(2) pop(S)。从栈S中删除(或称弹出)栈顶元素，即出栈。(3) lop(S, X)：把栈S的栈顶元素读到变量x中，栈保持不变。(4) empty(S)。判断栈S是否为空栈，是则返回值为真。(5) makempty。(S)将栈S设置为空。栈既然是一种线性表，所以线性表的存储结构同样也适用于栈。栈通常用顺序存储方式来 存储，分配一块连续的存储区域存放栈中元素，用一个变量来指向当前栈顶。考点 7队列队列简称为队，它也是一种运算受限的线性表，队列的限定是仅允许在表的一端进行插入 而在另一端进行删除。进行删除操作的一端称做队列的头，进行插人操作的一端称为队列的 尾.队列的基本操作有：(1) enq(Q, X)。往队列口中插人一个新的队尾元素x,即人队。(2) deq(口)从队列Q中删除队头元素，即出队。(3 ) front 口,x)将队列口的队头元素值读到变量x中，队列保持不变。empty ( Q ).判断队歹，1 口是否为空，是则返回值为真。makempty(口)将队列口置为空队列。和线性表一样、队列的存储方式也有顺序存储和链式存储两种。顺序队列在进行人队操作 时，会产生假溢出现象解决的办法是让队列首尾相连，构成一个循环队列。考点8串串（或字符串）是由零个或多个字符组成的有限序列。零个字符的串是空串。串中字符的个 数就是串的长度串中的字符可以是字母、数字或其他字符。串的存储同样也有顺序存储和链式存储两种。顺序存储时，既可以采用非紧缩方式，也可 以采用紧缩方式。串的基本运算有连接、赋值、求长度、全等比较、求子串、找子串位置及替换等，其中找 子串位置（或称模式匹配）比较重要。2.3 多维数组、稀疏矩阵和广义表考点 9多维数组的顺序存储多维数组是一维数组的推广。多维数组的所有元素并未排在一个线性序列里，要顺序存储 多维数组就需要按一定次序把所有的元素排在一个线性序列里。常用的排列次序有行优先顺 序和列优先顺序两种。考点 10 稀疏矩阵的存储稀疏矩阵是指矩阵中含有大量的0 元素。对稀疏矩阵可进行压缩存储，即只存储其中的非 0 元素。若非 0 元素分布是有规律的，可用顺序方法存储非0 元素。对于一般的稀疏矩阵， 常见的存储方法还有不元组法和十字链表法，这里就不再介绍了。考点 11 广义表的定义和存储广义表（又称列表）是线性表的另一种推广，是由零个或多个单元素或子表所组成的有限序 列。它与线性表的区别在于：线性表中的元素都是结构上不可分的单元素，而广义表中的元 素既可以是单元素，又可以是有结构的表广义表与线性表相比，具有如下3 个方面的特征。(1) 广义表的元素可以是子表，而子表的元素还可以是子表。(2) 广义表可被其他广义表引用二(3)广义表可以是递归的表，即广义表也可以是自身的一个子表。2.4 树型结构树型结构是节点之间有分支的、层次关系的结构，它类似于自然界中的树，是一类重要的 非线性结构常用的树型结构有树和二叉树。考点12树的定义树是树型结构的一个重要类型。一棵树或者是没有任何节点的空树，或者是由一个或多个 节点组成的有限集合T,其中：(1) 有且仅有一个称为该树根的节点。(2) 除根节点外的其余节点可分为。M(m0)个互不相交的有限集71,兀，T，其中 每一个集合本身又是一棵树,并且称为根的子树。这是一个递归的定义，即在树的定义中又用到了树的概念。这恰好显示了树的固有特性考点 13二叉树定义1. 二叉树的定义二叉树是一种最简单而巨重要的树型结构它或者是一棵空树，或者是一棵由一个根节点和 两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。有两种特殊形态的二 叉树，它们是满二叉树一和完全二叉树。2. 二叉树与树的区别尽管树和二叉树的概念之间有许多关系，但它们是两个概念二叉树不是树的特殊情况，树 和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和了。子树，即使在节点 只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。考点14树与二叉树之间的转换1. 树转换成二叉树将一棵树转换成相应的二叉树应包括以下几个步骤：(1) 在兄弟竹点之间加条连线(2) 对每一个节点，只保留它与第一个子节点的连线，与其他子节点连线全部抹掉(3) 以树根为轴心，顺时针旋转 45 。2. 森林转换成二叉树如果F=T-1- , T-2，Tm是森林，则可按如下规则将其转换乘一棵二叉树B=(root,LB,RB,)：若F为空，即m=0,则B为树。若F非空，即mO,则B的跟root即为森林中的第一棵树的跟ROOT(-T)； B的左子 树LB是从T、中根节点的子树森林F1=T11, T-,，T-m转换而成的二叉树；其右 子树RB是从森林F =T-l,T2,.Tm转换而成的二叉树。3. 二叉树转换成森林如果B 二(root, LB，RB)是、棵二叉树,则可按如下规则转换成森林F=T-l,T2,.Tm：(1)若B为空，则F为空。若B非空，则F中第一棵树T1的根ROOT(Tl)即为二叉树B的根root; T1中根节点的子树森林Fl是由B的左子树LB转换而成的；F中除T1之外其余树组成的森林F= Tl,T2,Tm是由B的右子树RB转换而成的。考点 15二叉树和树的周游周游(或称遍历)是树型结构的一种重要运算，是其他运算的基础。周游一棵树就是按一定 的次序访问树中听有节点，并且每个节点仅被访问一次的过程。1. 周游二叉树二又树的周游主要有以下3 种方式。(1) 前序法(NLR)。访问根，按前序周游左子树，按前序周游右子树。(2) 后序法(LRN)。按后序周游左子树，按后序周游右子树，访问根。(3) 对称序法(LNR)。按对称序周游左子树，访问根，按对称序周游右子树。2. 周游树和树林对树和树林的周游分为按深度优先和按广度优先两种方式进行。按深度优先方式又可分为按先根次序和按后根次序周游两种方式。(1) 先根次序周游访问第一棵树的根，按先根次序周游第一棵树的根子树，按先根次序周 游其他的树。(2) 后根次序周游按后根次序周游第一棵树的子树，访问第一棵树的根，按后根次序周游 其他的树。比较一下树与一又树之间的对应关系，可以看出，按先根次序周游树正好与按前序法周游 树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的二叉树等同。按广度优先方式可以做层次次序周游，首先依次访问层数为0 的节点，然后依次访问下一 层的节点，直至访问完最后一层的节点。考点 16二叉树的存储和线索l 二叉树的 llink 一 rlink 法存储表示二叉树的存储通常采用链接方式，即每个节点除存储节点自身的信息外再设置两个指针域 llink和rlink，分别指向节点的左子女和右子女。当节点的某个子女为空时，则相应的指针 值为空。再加上一个指向树根的指针t,就构成了二叉树的存储表示。这种存储表示法被称为llink - rlink表示法。2.线索二叉树在有n个节点的二叉树的且ink - rlink法存储表示中，必定有n+1个空指针域，将这些指 针位置利用起来，存储节点在指定周游次序F的前驱、后继节点指针，则得到线索二叉树。考点 17哈夫曼树哈夫曼树是树型结构的一种应用二哈夫曼(H uffman)树又称最优树，是一类带权路径长度 最短的树，这种树在信息检索中经常用到。所谓路径长度就是从一个节点到另一个节点所经 过的分支总数。树的路径长度是从树的根到每个节点的路径长度之和。完全二叉树就是这种 路径长度最短的二叉树。节点的带权路径长度为从该节点到树根之间的路径长度与节点上权 的乘积。树的带权路径长度为树中所有叶子节点的带权路径长度之和，WPL最小的不是完 全二叉树，而是权大的叶子离根最近的二叉树。2.5“查找查找是数据结构中一种很常用的基本运算。查找就是在数据结构中找出满足某种条件的节点。所给的条件可以是关键码字段的值，也 可以是非关键码字段的值，本节只考虑基于关键码值的查找考点 18顺序查找顺序查找是线性表的最简单、最基本的查找方法顺序查找的优点是对线性表节点的逻辑次 序无要求，对线性表存储结构也无要求顺序查找的缺点是速度较慢，平均检索长度与表中节点个数和n成正比，查找成功最多需 比较n次，平均查找长度为(n +1 )/2次，约为表长的，半，查找失败需比较n+l次顺序查找 算法的时间复杂度为O(n)。考点 19二分法查找二分法查找是一种效率比较高的查找方法，在进行二分法查找时，线性表节点必须按关键 码值排序，且 线性表是以顺序存储方式存储的。二分法查找的优点是比较次数少，查找速度快，平均检索长度小，经过0&6 n次比较 就可以完成查找过程。缺点是在查找之前要为建立有序表付出代价，同时对有序表的插人和 删除都需要平均比较和移动表中 的一半元素。一般情况下，二分查找适应于数据相对固定 的情况，且二分法查找只适用于线性表的顺序存储。考点 20分块查找分块查找又称索引顺序查找，是介于线性查找和二分法查找之间的一种查找方法。它要求 把线性表分 成若干块，每一块中的节点不必有序，但块与块之间必须排序，不妨设每一块 中各节点的关键码都大于前一块的最大关键码值。另外，还要求将各块中的最大关键码值组 成一个有序的索引表。满足上述条件的线性 表称做分块有序表。它的分块检索的过程分以 下两步进行。先查索引表(可以用线性检索或二分法检索)，确定要找的记录在哪一块。(2)在相应的块中线性检索待查记录。考点 21散列表的存储和查找散列存储中使用的函数称为散列(Hash)函数散列表(又称哈希表)是线性表的一种重要的存 储方式 和检索方法。实现散列技术检索必须解决两个问题：一个是构造一个好的散列函数， 尽可能避免冲突现象的发生；另一个是设计有效的解决冲突的方法。1. 散列函数常用的散列函数有以下几种。(1) 除余法。选择一个适当的正整数川通常选p为不大于散列表存储区域大刁、的最大素数), 用p去除 关键码值，取其余数作为地址，即h(key)二key mod p。(2) 数字分析法。当关键码的位数比存储区域地址码位数多时,可以对关键码的各位进行 分析，去掉分 布不均匀的位，留下分布均匀的位作为地址。(3) 折叠法。将关键码值从某些地方断开，分为几段，折叠相加，作为地址。(4) 中平方法。对关键码值求平方，取中间的几位数作为地址。2. 处理冲突的方法发生冲突是指由关键字求得的散列地址为i(O-i-m 一 1)的位置上已存有记录，处理冲突就 是为该关健字找到另一个“空”的散列地址。常用的处理冲突的方法有开地址法、拉链法等。3. 负载因子(装填因子)和平均检索长度装填因子表示散列表的装满程度，定义为散列表中节点的数目除以基本区域能容纳的节点 数所得的商，用a表示a越小，冲突的可能性越小，a越大，冲突的可能性越大，检索时需 要比较的次数就越多。平均检索长度依赖于散列表的装填因子。2.6 排序排序是数据处理领域经常要使用的一种运算，就是将一组元素按照关键码的递增或递减的 顺序来排列为过程按照排序过程中的存储器不同，可将排序方法分为内部排序和外部排序两类。一厂面将介 绍插人排序、选择排序、交换排序和归并排序等几种常用的内部排序方法。考点 22插入排序插人排序的基本思想：每一步将一个待排序的记录按其关键字值的大小插人到一个有序的 文件中，插人后该文件仍然是有序文件。1. 直接插入排序直接插人排序是一种最简单的排序方法它的基木思想是将一个记录插人到已排好序的有 序表中，从而得到一个新的、记录数增I的有序表整个排序过程为：先将第一个记录看成是 一个有序的子序列，然后从第2 个记录起依次逐个地插人到这个有序的子序列中去。直接插人排序的时间复杂度为0(n )。直接插人排序方法不仅适用于顺序表，而且适用于单链表2. 二分法插入排序在直接插人排序,，若采用二分法查找而不是顺序查找待插入元素的插人位置，则称 为二分法插入排序这种插人排序可减少比较次数，使排序速度有所提高，但提高不会太多， 因为移动记录的总次数不受改变，其时间复杂度仍为0(n2)。直接插人和二分法插入排序方法都是稳定的，因为它们不会改变原序列中具有相同关键字 记录的相对次序。3. 希尔排序希尔排序又称缩小增量排序，它是对直接插人排序的一种改进方法希尔排序的基本思路： 对相隔较大距离的记录进行比较，就能使记录在比较后移动较大的距离这样能使较小的记录 尽快往前移，较大的记录尽快往后移，从而提高排序的速度希尔排序是一种不稳定的排序过程考点 23选择排序选择排序的基木思想是每次从待排序的记录中选出关键码值最小或最大的记录放在已排 好序的记录序列后面，直至排序完毕。1. 直接选择排序直接选择排序也是一种简单的排序方法。选择排序的基本方法是：每次从待排序的区间中 选择出具有最小排序码的元素。把该元素与该区间的第一个元素交换位置。第一次待排序区 间为AlAn,经过选择和交换后，A 1为最小排序码的元素。第二次待排序区间为 A2An,经过选择和交换后，A2为仅次于A 1的具有最小排序码的元素，依次类推， 经过 n-1 次选择和交换后，排序完毕。直接选择排序方法的时间复杂度为O(n2)，此方法是不稳定的。2.堆排序堆的定义如下：n个元素序列k-1,k2,，kn，当且仅当满足下列关系时，称之为堆。人毛人 KiK2i, KiK2i+1，i=1, 2，.，n/2堆排序的基本思想：对一组待排序的关键码，首先把它们按堆的定义排列成一个序列，找 到其中最小的关键码接着将最小的关键码取出，然后将剩下的关键码再建堆排序，依次进 行，直到将全部关键码排好为止。建堆的基本方法是将大的元素下沉，小的元素上浮，即所 谓的筛选法。在最坏的情况下，堆排序时间复杂度为O(nlog2 n )。堆排序仅需一个记录大小的辅助存储 空间。堆排序是不稳定的。考点24交换排序交换排序的基本思想：两两比较待排序记录的关键字值，并交换不满足顺序要求的那些记 录，直到全部记录满足关键字值排序要求为止。1. 起泡排序起泡排序又称为冒泡排序，其基本思想是通过相邻记录之间关键字的比较和交换，使关键 字值较小的记录逐渐从底部移向顶部，即从下标较大的单元移向下标较小的单元，关键字较 大的记录从顶部移向底部。从起泡排序算法可以看出，若初始序列为“正序”序列，则只需进 行一趟排序；反之，若初始序列为逆序”序列，则需进行。一I趟排序。因此，总的时间复 杂度为。 (矿)。起泡排序是一种稳定的排序过程。2. 快速排序快速排序是口前内部排序中速度最快的一种排序算法，其实质是对起泡排序的改进在快速 排序中，记录的比较和交换是从两端向中间进行的，排序码较大的记录一次就能够从前面交 换到后面单元，排序码较小的记录一次就能够从后面交换到前面单元，记录每次移动的距离 较远，总比较和移动次数较少。快速排序是不稳定的排序。排序速度最快时，其时间复杂度为0 ( nlog, n )；排序速度最慢 时，其时间复杂度为。(n)快速排序的平均时间复杂度为0 (nlog2 n )。快速排序除了需要一 个记录的辅助空间来存放每次选取的基准记录外，还需要一个栈空间来实现递归。考点25归并排序归并是将两个或者多个有序表合并成一个有序表归井排序要求待排序文件已经部分排序。归并排序的基本思想是将这些已排过序的文件进行合并，得到完全排序的文件。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1,然 后两两归并，得到n/2个长度为2或I的有序子序列，再两两归并，如此重复，直到得到一 个长度为 n 的有序序列为止。这种排序方法称为二路归并排序。归并排序平均时间复杂度为0(n1092 n )，辅助空间为0(n)。