[TOC] # 线性表 ## 概念 * 线性表是由n（n≥0）个具有相同特性数据元素(结点) a1，a2，…，an组成的有限序列。 * 线性表的长度：所含元素的个数,用n表示，n>=０。当n=0时,表示线性表是一个空表，即表中不包含任何元素。 * 线性表的逻辑结构： :-:  * 线性表的特点 1. 有且仅有一个开始结点`$ a_1 $`，没有直接前趋，有且仅有一个直接后继`$ a_2 $`； 2. 有且仅有一个终结结点`$ a_n $`，没有直接后继，有且仅有一个直接前趋`$ a_{n-1} $`； 3. 其余的内部结点`$ a_i $`（2≤i≤n-1）都有且仅有一个直接前趋`$ a_{i-1} $`和一个`$ a_{i+1} $`。 * 线性表实例 英文字母表：(A，B，C，D，…，X，Y，Z) 某校1998-2003年计算机数量：(50，100，250，300，500，1200) * 线性表的顺序存储 顺序存储是线性表的一种最简单的存储结构，存储方式是：在内存中为线性表开辟一块连续的存储空间。 :-:  * 顺序存储的优缺点 * 优点 1. 逻辑相邻，物理相邻，地址连续 2. 可随机存取任一元素 3. 存储空间使用紧凑 * 缺点 1. 插入、删除操作需要移动大量的元素 2. 预先分配空间需按最大空间分配，利用不充分 3. 表容量难以扩充 # 查找算法 * 以查询学生成绩为例 查询学号“18”的学生成绩 查询“周丽”的成绩 :-:  * 按照学号查找相对容易、省时 * 按照姓名查找相对费时 >[danger] 原因：一个有序、一个无序 >[success] 数据存放的方式决定数据查找的方法！ ## 基本概念 * 查找表：由同一类型的数据元素（或记录）构成的集合 * 查找：查询(Searching)特定元素是否在表中 * 静态查找：只查找，不改变集合内的数据元素 * 动态查找：既查找，又改变（增减）集合内的数据元素 * 关键字：元素中某个数据项的值，可用来识别一个元素(预先确定的数据元素的某种标志 ) * 主关键字：可以唯一标识一个元素的关键字 * 次关键字：识别若干元素的关键字 ## 常见操作 * 查询某个“特定的”数据元素是否在查找表中； * 检索某个“特定的”数据元素的各种属性； * 在查找表中插入一个数据元素； * 从查找表中删去某个数据元素。 ## 顺序表的查找运算 线性表有两种基本的查找运算： * 按序号查找:要求查找线性表L中第i个数据元素，其结果是A[i] ; * 按内容查找: 要求查找线性表L中与给定值x相等的数据元素，其结果是：若在表L中找到与x相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。 > 算法分析：查找运算可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与x相比较，若相等，则查找成功，返回该元素在表中的序号；若x与表中的所有元素都不相等，则查找失败，返回“-1”。 ## 折半查找(二分查找) 先给数据排序（例如按升序排好），形成有序表，然后再将key与中间元素相比，若key小，则缩小至前半部内查找；若key大，则缩小至后半部内查找。 :-:  >[success] 二分查找失败时最多比较【`$ log_2N $`】+1次 例题： 1. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。 2. 对22个记录的有序表作折半查找，当查找失败时，至少需要比较 5 次关键字。 ## 哈希表 * 哈希表既是一种**查找方法**，又是一种**存贮方法**。 * 哈希表：即散列存储结构。 * 散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。 * 优点：查找速度极快（O(1)）,查找效率与元素个数n无关！ # 排序算法 * 冒泡排序 * 基本思想： 两两比较待排序数据元素的大小，**发现两个数据元素的次序相反时即进行交换**，直到没有反序的数据元素为止。 * 排序过程：设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，**从下往上扫描数组R**，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。 * 选择排序 * 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后（或最前），直到全部待排序的数据元素排完。 * 排序过程：  * 插入排序 * 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 * 排序过程：  * 桶排序 * 基本思想 若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。 :-:  * 基数排序 * 基本思想 前面介绍的几种排序方法都是按数据元素（或记录关键字）值的大小进行排序的 而多关键字排序是一种按组成数据元素或关键字的各位值进行排序的方法，基数排序借助的就是这种思想，它属于分布式排序，也称口袋排序。 基数排序是把逻辑关键字看成由若干个子关键字复合而成的 假设有n个关键字｛r1，r2，…，rn｝需进行排序 每个关键字由d元组（k1k2k3…kd）子关键字组成，k1是关键字值的最高位，kd是关键字值的最低位，其基数为rd * 希尔排序 * 基本思想 希尔排序实质上还是一种插入排序，其主要特点是：每一趟以不同的增量进行排序。在每趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，所以关键字较小的记录在排序过程中是作跳跃式的移动。 另外，由于开始时增量的取值较大，每组中记录较少，故排序比较快，随着增量值的逐步变小，每组中的记录逐渐变多，但由于此时记录已基本有序了，因次在进行最后一趟增量为1的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。 * 快速排序 * 基本思想 首先对无序的记录序列进行“一次划分”，通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。 * 归并排序 * 基本思想 归并排序又称为表排序，其含义是将两个有序序列合并成为一个有序序列。 设待排序序列有n个记录，开始将其看作是n个长度为1 的有序子文件，然后进行归并，将相邻的有序子文件两两合并，得到n/2个长度为2或1的有序子文件(如果n为奇数，则最后一个有序子文件的长度为1)，再两两归并得到n/4个有序子文件，以此类推，直至得到长为n的有序文件。该有序序列就是原始序列经归并排序后的有序序列。 :-:  ## 排序的选择原则 * 当待排序元素个数n较大，排序码分布随机，而对稳定性不做要求时，则采用快速排序。 * 当待排序元素个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。 * 当待排序元素个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。 * 当待排序元素个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序。 * 当待排序元素个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。 # 栈 * 栈（stack）：一种特殊的线性表，限定只能在表尾进行插入、 删除操作的线性表。 * 特点：后进先出LIFO(Last In First Out) ## 栈的概念 * 栈顶(top)：允许插入和删除数据元素的一端。 * 栈底(bottom)：固定的一端。 * 空栈：不含任何元素。 * 进栈(压栈push)：插入元素。 * 出栈(退栈pop)：删除元素。 :-:  例题： 1. 设栈S的初始状态为空，现有序列1,2,3,4,5，对该序列在栈S上依次进行如下操作（从序列中的1开始）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是：3,4 2. 若进栈的序列是1、2、3、4、5，问能否得到出栈序列4、3、5、1、2 ？不能 3. 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c（如右图所示），另有元素d已经出栈，则可能的入栈顺序是（ AD ）。  A．a, b, c, d B．b, a, c, d C．a, c, b, d D．d, a, b, c # 队列 * 队列也是一种受限的线性表。它的所有插入都在队列的一端进行，所有删除都在另一端进行。 * 特点：先进先出(FIFO，First In First Out) * 实例： 例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。 例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。 ## 队列的概念 * 允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。 * 队列的插入和删除我们称为入队和出队，新元素入队就成为新的队尾元素，删除元素后，其后继元素成为新的队首元素。  例题： 1. 已知队列(13，2，11，34，41，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是（  B    ）。 A） 5      B） 41      C） 77        D） 13       E） 18 2. 设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ B ）。 A）2 B）3 C）4 D）5 # 线性结构总结 >[danger] 栈、队列属于线性结构。在这种结构中，不管其存储方式（顺序和链式）如何，数据元素的逻辑位置之间呈线性关系，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。 # 非线性结构 有很多问题数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个结点（数据元素）有多于一个前驱或后继的数据结构称为非线性结构。具有非线性结构特征的数据结构有两种： **树**  **图**  # 树 ## 树的概念 树是一种常见的非线性的数据结构。树的递归定义如下： 树是n(n>0)个结点的有限集，这个集合满足以下条件： 1. 有且仅有一个结点没有前驱（父亲结点），该结点称为树的根； 2. 除根外，其余的每个结点都有且仅有一个前驱； 3. 除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）； >[danger] 由上述定义可知，树结构没有封闭的回路。 ### 结点的分类  1. 根结点：没有父亲的结点。在树中有且仅有一个根结点。 2. 分支结点：除根结点外，有孩子的结点称为分支结点。b，c，x，t，d，i。分支结点亦是其子树的根； 3. 叶结点：没有孩子的结点称为树叶。w，h，e，f，s，m，o，n，j，u为叶结点。 **根结点到每一个分支结点或叶结点的路径是唯一的。从根r到结点i的唯一路径为rcti。** ### 树的度 1. 结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。 2. 树的度：所有结点中最大的度称为该树的度(宽度）。图中树的度为3。 ### 树的高度（深度） 树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。 树中最大的层次称为树的深度，亦称高度。图中树的深度为5。 ## 树的表示方法和存储结构 ### 树的表示方法 * 自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。 * 广义表方法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））@（表示结束） ### 树的存储结构 静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n 为树的度)的数组，分别存储该结点的每一个儿子的下标 例下图的树，其记录数组如下。由于未规定同层结点的次序，因此每个结点儿子的下标序列（Tree[i].ch）任意。其中Tree[i].ch[j]=0说明结点i的第j个儿子不存在。(编号按层编号)  ## 二叉树 二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个孩子，且其子树有左右之分（有序树，次序不能任意颠倒）。 ### 二叉树的递归定义和基本形态 二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件： 1. 有一个特定的结点称为根； 2. 余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树； > 由上述定义可以看出，二叉树和树是两个不同的概念 > 1. 树的每一个结点可以有任意多个，而二叉树中每个结点的后继不能超过2； > 2. 树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。 ### 二叉树的基本形态  * 满二叉树： 如果一棵深度为K的二叉树，共有`$ 2_{K-1} $`个结点，即第I层有`$ 2_{I-1} $`的结点，称为满二叉树。 * 完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树。  ### 二叉树的基本性质 性质1：在二叉树的第i（≥1）层上，最多有`$ 2^{i-1} $`个结点 性质2：在深度为k(k≥1)的二叉树中最多有`$ 2^k-1 $`个结点 性质3：在任何二叉树中，叶子结点数总比度为2的结点多1,即`$ n_{0} $`=`$ n_{2} $`+1 性质4：具有n个结点的完全二叉树的深度为Trunc（log2n）+1。 ### 二叉树的存储结构 将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括 1. 一个数据域（data）； 2. 三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。  ### 二叉树的遍历 * 二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，或对结点作其它的处理。 * 如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，限定先左后右的次序，三种组合DLR、LDR、 LRD * 这三种遍历规则分别称为 **先（前）序遍历、中序遍历和后序遍历（以根为标准）**  **前（先）序遍历** a b d e h i c f g **中序遍历 ** d b h e i a f c g **后序遍历** d h i e b f g c a **分析：**  **由遍历序列确定二叉树**  已知一棵树的两种序列，如何构造该二叉树 例：已知一棵树的先序和中序序列分别为： A B C D E F G H I B C A E D G H F I 试构造该二叉树 > 答：思路： > 1. 首先看先序序列：先序序列先看根，再看左子树、右子树，那么A就是该二叉树的根；然后，看中序序列，中序序列先看左子树，再看根，再看右子树，B C 在A 前头，而且A又是根，那么B C 就是属于左子树，D E F G H I 就是属于右子树。 > > 2. 其次看左子树：在先序序列中，左子树先访问的是B，然后再是C，那么，B 就是左子树的根；再看中序序列，左子树先访问的也是B，然后再是C，那么C就是B 的右子树 > > 3. 然后再看右子树：在先序序列中，右子树先访问的是D，那么D就是右子树的根，再看中序序列，先访问的是E，然后再是D，那么，E就是右子树下的左子树，F G H I 就是右子树下的右子树。 > > 4. 最后看右子树下的右子树（F G H I）：在先序序列中，先访问的是F，那么F就是该分支树的根，再看中序序列，F前面是G H ,后面是I，则G H是分支树下的左子树，I是分支树下的右子树；又 (F G H ),(G H F)与（A B C),(B C A)一样，所以G 是分支根，H 是其右子树。  ### 表达式树 * 算数表达式是分层的递归结构，一个运算符作用于相应的运算对象，其运算对象又可以是任意复杂的表达式。树的递归结构正好用来表示这种表达式。下面只讨论二元表达式。 * 二元表达式可以很自然的联系到二叉树：以基本运算对象作为叶节点中的数据；以运算符作为非叶节点中的数据，其两棵子树是它的运算对象，子树可以是基本运算对象，也可以是复杂表达式。如图是一个表达式树。  * 前缀、中缀和后缀表达式 * 中缀表达式（中缀记法） 我们平时缩写的表达式，将运算符写在两个操作数中间的表达式，称作中缀表达式。在中缀表达式中，运算符有不同的优先级，圆括号用于改变运算顺序，这使得运算规则比较复杂，求值过程不能直接从左到右顺序进行，不利于计算机处理。 * 后缀表达式 将运算符写在两个操作数之后的表达式称作后缀表达式。后缀表达式中没有括号，并且运算符没有优先级。后缀表达式的求值过程能够严格按照从左到右的顺序进行，有利于计算机处理。 * 前缀表达式 前缀表达式是将运算符写在两个操作数之前的表达式。和后缀表达式一样，前缀表达式没有括号，运算符没有优先级，能严格按照从右到左的顺序计算。 * 另外，算式表达式和表达式树的关系如下： 表达式树的先根遍历：前缀表达式 表达式树的中根遍历：中缀表达式 表达式树的后根遍历：后缀表达式 * 表达式的转换 利用表达式树 * 给定一个表达式的中缀形式：(4+1*(5-2))-6/3 * 首先将每个运算加上括号，区分优先级，得到(4+(1*(5-2)))-(6/3) * 括号外的-优先级最低，作为根节点，(4+(1*(5-2)))作为左子树，(6/3)作为右子树； * 递归的转换4+(1*(5-2))，+最为根节点，4是左子树，(1*(5-2))是右子树。*是右子树的根节点，1是左子树，(5-2)是右子树。最后计算(5-2)，-是根节点，5是左子树，2是右子树。得到的表达式树如文章之初给出的图。 * 构造好表达式树之后，前缀表达式和中缀表达式可根据先根遍历和后根遍历得到。 * 前缀表达式：- + 4 * 1 - 5 2 / 6 3 * 后缀表达式：4 1 5 2 - * + 6 3 / -