数据结构和算法（上）

1. 数据结构基础知识

数据结构是指数据元素的集合及元素间的相互关系和构造方法，结构就是元素之间的关系。

• 逻辑结构：元素之间的相互关系。按照逻辑关系的不同将数据结构分为线性结构和非线性结构，其中，线性结构包括线性表、栈、队列、串，非线性结构主要包括树和图。

• 存储结构：也称物理结构，数据元素及元素之间关系的存储形式，主要有顺序存储和链式存储两种基本方式。

1.1 线性表

线性结构的特点是数据集合中的元素之间是一种线性关系，数据元素“一个接一个地排列”，也就是一个序列。

1）线性表基本概念

• 存在唯一的一个称作“第一个”的元素。
• 存在唯一的一个称为“最后一个”的元素。
• 除第一个元素外，序列中的每个元素均只有一个直接前驱。
• 除最后一个元素外，序列中的每个元素均只有一个直接后继。

2）线性表的存储结构

常用的存储结构有顺序存储和链式存储，主要的基本操作是插入、删除和查找。

顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。在这种存储方式下，元素间的逻辑关系无需占用额外的空间来存储。

• 优点：可以随机存取表中的元素，按序号查找元素的速度很快。
• 缺点：插入和删除操作需要移动元素，插入元素前要移动元素以挪出空的存储单元，然后再插入元素；删除元素时同样需要移动元素，以填充被删除的元素空出来的存储位置。

链式存储是用结点来存储数据元素，元素的结点地址可以连续，也可以不连续，因此，存储数据元素的同时必须存储元素之间的逻辑关系。另外，结点空间只有在需要的时候才申请，无须事先分配。

结点结构通常有数据域和指针域组成。结点中的数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继元素的位置信息，指针域中所存储的信息称为指针(或链)。

根据结点中指针信息的实现方式，有单链表、双向链表、循环链表和静态链表等链表结构。

• 单链表：也称线性链表，n个结点通过指针连成一个链表，结点中只有一个指针域。
• 双向链表：每个结点包含两个指针，分别指明当前元素的直接前驱和直接后继信息，可在两个方向上遍历链表中的元素。
• 循环链表：表尾结点的指针指向表中的第一个结点，可从表中任意结点开始遍历整个链表。
• 静态链表：借助数组来描述线性表的链式存储结构。

线性表采用链表作为存储结构时，只能顺序地访问元素，而不能对元素进行随机存取，所需空间与结点个数成正比。但其优点是插入和删除操作不需要移动元素。 缺点是查找慢。

1.2 队列和栈

栈和队列的逻辑结构和线性表相同，有以下两个特点：

• 栈按后进先出的规则进行修改。
• 队列按先进先出的规则进行修改。

1.2.1 栈

1）栈的定义及基本运算

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈又称为先进后出(FILO)或后进先出(LIFO)的线性表。在栈中进行插入和删除操作的一端称为栈顶(top)，相应地，另一端称为栈底(bottom)。不含数据元素的栈称内空栈。

栈的基本运算如下：

（1）初始化栈initStack(S)：创建一个空栈S。

（2）判栈空isEmpty(S)：当栈S为空栈时返回“真”值，否则返回“假”值。

（3）入栈push(S,x)：将元素x 加入栈顶，并更新栈顶指针。

（4）出栈pop(S)：将栈顶元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将pop(S)定义为 一个函数，它返回栈顶元素的值。

（5）读栈项元素top(S):返回栈顶元素的值，但不修改栈顶指针。

2）栈的存储结构

栈的顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针 top 指示栈顶元素的位置。采用顺序存储结构的栈也称为顺序栈。在顺序存储方式下，需要预先定义或申请栈的存储空间，也就是说栈空间的容量是有限的。因此在顺序栈中，当一个元素入栈时，需要判断是否栈满(栈空间中没有空闲单元)，若栈满，则元素入栈会发生上溢现象。

栈的链式存储。为了克服顺序存储的栈可能存在上溢的不足，可以用链表存储栈中的元素。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必设置头结点，链表的头指针就是栈顶指针。

栈的典型应用包括表达式求值、括号匹配等，在计算机语言的实现以及将递归过程转变为非递归过程的处理中，栈有重要的作用。

1.2.2 队列

1）队列的定义及基本运算

队列是一种先进先出(FIFO)的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾(rear)，允许删除元素的一端称为队头(front)。

队列的基本运算如下：

（1）初始化队列initQueue(Q)：创建一个空的队列Q。

（2）判队空isEmpty(Q)：当队列为空时返回“真”值，否则返回“假”值。

（3）入队enQueue(Q,x)：将元素x加入到队列Q的队尾，并更新队尾指针。

（4）出队deQueue(Q)：将队头元素从队列Q中删除，并更新队头指针。

（5）读队头元素frontQueue(Q):返回队头元素的值，但不更新队头指针。

2）队列的存储结构

队列的顺序存储。队列的顺序存储结构又称为顺序队列，它也是利用一组地址连续的存储单元存放队列中的元素。由于队中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指示出当前的队首元素和队尾元素。

在顺序队列中，为了简化运算，元素入队时，只修改队尾指针；元素出队时，只修改队头指针。当队尾指针达到其上限时，就不能只通过修改队尾指针来实现新元素的入队操作了，这时可以称之为循环队列。

队列的链式存储。队列的链式存储也称为链队列。为了便于操作，可给链队列添加一个头结点，并令头指针指向头结点列为空的判定条件是头指针和尾指针的值相同，且均指向头结点。

队列常用于处理需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。

示例.元素按照a、b、c的次序进入栈，请尝试写出其所有可能的出栈序列。

答：先进后出原则有abc、acb、bac、bca、cba

1.3 串

注：其中LS是表名，a i a_ia

i

是表元素，它可以是表（称做子表），也可以是数据元素（称为原子）。其中n是广义表的长度（也就是最外层包含的元素个数），n=0的广义表为空表；而递归定义的重数就是广义表的深度，直观地说，就是定义中所含括号的重数（原子的深度为0，空表的深度为1）。

示例.有广义表 LS1 = (a,(b,c),(d,e))，则其长度为多少，深度为多少。

答：长度为3，也就是去掉最外层括号逗号加1；深度为2，每个元素所拥有括号的最大个数。

1）串的定义及运算

字符串是一串文字及符号的简称，是一种特的线性表。字符串的基本数据元素是字符，计算机中非数值问题处理的对象经常是字符串数据，如在汇编和高级语言的编译程序中，源程序和目标程序都是字符串数据；在事务处理程序中，姓名、地址等一般也是作为字符串处理的。另外，串还具有自身的特性，常常把一个串作为一个整体来处理。

• 串长：串的长度，指字符串中的字符个数。
• 空串：长度为0的串，空串不包含任何字符。
• 空格串：由一个或多个空格组成的串。虽然空格是一个空白符，但它也是一个字符， 计算串长度时要将其计算在内。
• 子串：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串 。子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串的位置。空串是任意串的子串。
• 串相等：指两个串长度相等且对应位置上的字符也相同。
• 串比较：两个串比较大小时以字符的ASCII码值作为依据。比较操作从两个串的第一个字符开始进行，字符的ASCII码值大者所在的串为大；若其中 一个串先结束，则以串长较大者为大。

大多数的程序语言在其开发资源包中都提供了字符串的赋值(拷贝)、连接、比较、求串长、求子串等基本运算，利用它们就可以实现关于串的其他运算。

2）串的存储结构

顺序存储。该方式是用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符，所以可通过程序语言提供的字符数组定义串的存储空间(即存储空间的容量固定)，也可以根据串长的需要动态申请字符串的空间 (即存储空间的容量可扩充或缩减)。

链式存储。字符串也可以采用链表作为存储结构，当用链表存储串中的字符时，每个结点中可以存储 一个字符，也可以存储多个字符，需要考虑存储密度问题。

在链式存储结构中，结点大小的选择和顺序存储方法中数组空间大小的选择一样重要，它直接影响对串处理的效率。

1.4 数组和矩阵

1）数组

数组可看作是线性表的推广，其特点是多维数组的数据元素仍然是一个表。

一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n 维数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。

数组结构的特点如下：

• 数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。
• 数据元素具有相同的类型。
• 数据元素的下标关系具有上下界的约束且下标有序。

数组通常做两种操作：

• 取值操作。给定一组下标，读其对应的数据元素。
• 赋值操作。给定一组下标，存储或修改与其相对应的数据元素。

几乎所有的程序设计语言都提供了数组类型。在语言中把数组看成是具有共同名字的同一类型多个变量的集合。但要注意不能对数组进行整体的运算，只能对单个数组元素进行运算。

数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。一旦确定了它的维数和各维的长度，便可为它分配存储空间。从0开始，数组的存储地址计算如下：

稀疏矩阵的三元组表构成一个线性表，其顺序存储结构称为三元组顺序表，其链式存储结构称为十字链表。

1.4 树和图

1.4.1 树

1）树

树结构是一种非常重要的非线性结构，该结构中一个数据元素可以有两个或两个以上的直接后继元素，可以用来描述客观世界中广泛存在的层次关系。

树的定义是递归的，它表明了树本身的固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。从数据结构的逻辑关系角度来看，树中元素之间有明显的层次关系。

常见的层级关系如下：

• 双亲、孩子和兄弟：结点的子树的根称为该结点的孩子，相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。如A是树根，B、C、D是A的孩子结点，B、C、D互为兄弟；B是E、F的双亲，E、F是兄弟。
• 结点的度：一个结点的子树的个数记为该结点的度。如A的度为3，B的度为2，C的度为0，D的度为1。
• 叶子结点：也称终端结点，指度为0的结点。如E、F、C、G都是叶子结点。
• 内部结点：度不为零的结点称为分支结点或非终端结点。除根结点之外，分支结点也称为内部结点。如B、D都是内部结点。
• 结点的层次：根为第一层，根的孩子为第二层，以此类推。如A在第1层，B、C、D在第2层，E、F、G在第3层。
• 树的高度：一棵树的最大层次数记为树的高度（或深度）。如上图树的高度为3。
• 有序（无序）树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换， 则称该树为有序树，否则称为无序树。

• 森林：m(m≥0)棵互不相交的树的集合。

2）二叉树

二叉树是n(n ≥0)个结点的有限集合，它或者是空树(n =0)，或者是由一个根结点及两棵不相交的、分别称为左子树和右子树的树所组成。

树和二叉树的主要区别是：

二叉树中结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树，树中则不区分。

二叉树中结点的最大度为 2，而树中不限制结点的度数。

二叉树的遍历，遍历是按某种策略访问树中的每个结点，且仅访问一次。

由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根结点、左子树和右子树三部分构成，因此若能依次遍历这三个部分的信息，也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定，依据访问根结点位置的不同，可得到二叉树的前序、中序和后序三种遍历方法，另外自上而下、自左至右逐层访问树中各层结点的过程就是层次遍历。

前序遍历：根结点->左子树->右子树。

中序遍历：左子树->根结点->右子树。

后序遍历：左子树->右子树->根结点。

层次遍历：自上而下、自左至右逐层访问树中各层结点。

最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树。从树中一个结点到另一个结点之间的通路称为结点间的路径，该通路上分支数目称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积。

二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树。

若它的左子树非空，则左子树上所有结点的关键码值均小于根结点的关键码值。

若它的右子树非空，则右子树上所有结点的关键码值均大于根结点的关键码值；

左、右子树本身就是两棵二叉查找树。

对二叉查找树进行中序遍历，可得到一个关键码递增有序的结点序列。

数据结构和算法（下）：https://developer.aliyun.com/article/1529463