软件设计师（三） 数据结构

数据结构是指数据元素的集合及元素间的相互关系和构造方法。
元素之间的相互关系是数据的逻辑结构，数据元素及元素之间关系的存储称为存储结构(或物理结构)。
数据结构按照逻辑关系的不同分为线性结构和非线性结构两大类，其中，非线性结构又可分为树结构和图结构。（图可以包含树，树可以包含线性结构）

各种数据结构的特点和作用是什么样的

数据结构	特点
栈	后进先出，先进后出。
队列	先进先出，后进后出。
数组	内存连续区域，查询快，增删慢。
链表	元素是游离的，查询慢，首尾操作极快。

一、线性结构

线性结构是一种基本的数据结构，主要用于对客观世界中具有单一前驱和后继的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系，即元素“一个接一个排列”。

1、线性表

线性表是最简单、最基本、最常用的一种线性结构。主要的基本操作是插入、删除和查找等。

（1）定义

定义：线性表是n个元素的有限序列，通常表示为（a1，a2，a3，…，an）
特点：

• 存在惟一的表头和表尾。
• 除了表头外，表中的每个元素均只有一个直接前驱。
• 除了表尾外，表中的每个元素均只有一个直接后继。

（2）存储结构

存储结构分为顺序存储和链式存储

① 顺序存储

定义：用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
优缺点：

类型	说明
优点	可以随机存储表中的元素
缺点	插入和删除操作需要移动数据

• 计算公式：$LOC(a_i)=LOC(a_1)+(i-1)\ast L$。 其中，$LOC(a_1)$表示线性表中第一个元素的存储位置，L是表中每个数据元素所占空间的字节数
• 插入一个新元素需要移动的元素个期望值 为 n/2
• 删除一个元素需要移动的元素个数期望值为（n-1）/ 2

② 链式存储

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

链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址。
链表查询慢，无论查询哪个数据都要从头开始找。

优缺点：

类型	说明
优点	插入和删除操作不需要移动元素，操作方便
缺点	增加了存储空间开销，不能随机访问任一结点

类型：

• 单向链表：结点之间通过指针域构成一个链表，若结点中只有一个指针域，则称为线性链表(或单向链表)
• 双向链表：每个结点包含两个指针，分别指出当前元素的直接前驱和直接后继。其特点是可以从表中任意的结点出发，从两个方向上遍历链表。
• 循环链表：在单向链表(或双向链表)的基础上令表尾结点的指针指向表的第一个结点，构成循环链表。其特点是可以从表中任意结点开始遍历整个链表。
• 静态链表：借助数组来描述线性表的链式存储结构，用数组元素的下标表示元素所在结点的指针。

③ 比较

2、栈和队列

栈和队列是程序中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算有所限制：栈按“后进先出”规则进行操作，队列按“先进先出”的规则进行操作，故称为运算受限的线性表。

（1）栈

① 定义

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。因此，栈又称为后进先出(Last In First Out，LIFO)的线性表。
在栈中进行插入和删除操作的一端称为栈顶(Top)，相应地，另一端称为栈底(Bottom)。不含数据元素的栈称为空栈。
数据进入栈模型的过程称为压/进栈；
数据离开栈模型的过程称为弹/出栈。

② 基本运算

运算	说明
初始化栈 InitStack(S)	创建一个空栈S
判栈空栈 isEmpty(S)	当S空时返“真”，否则返“假”
入栈 Push(S,x)	将元素x 加入栈顶，并更新栈顶指针
出栈 Pop(S)	将栈顶元素从栈中删除，并更新栈顶指针。
读栈顶元素 Top(S)	返回栈顶元素的值，但不修改栈顶指针

③ 栈的存储结构

1. 顺序存储
   栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针 top 指示顶元素的位置。采用顺序存储结构的栈也称为顺序栈。在这种存储方式下，需要预先定义栈的存储空间，也就是说，栈空间的容量是有限的。
2. 链式存储
   用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。

（2）队列

① 定义

队列是一种先进先出 (First In First Out，FIFO)的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾(Rear)，允许删除元素的一端称为队头 (Front）。
数据从队尾进入队列模型的过程称为入队列；数据从队头离开队列模型的过程称为出队列

② 基本运算

运算	说明
初始化队列 InitQueue(Q)	创建一个空的队列 Q
判段队列空 isEmpty(Q)	当队列为空时返回“真”，否则返回“假”
入队 EnQueue(Q,x)	将元素x 加入到队列Q 的队尾，并更新队尾指针
出队 DelQueue(Q)	将队头元素从队列 Q 中删除，并更新队头指针
读队头元素 FrontQue(Q)	返回队头素的值，但不更新队头指针

③ 队列的存储结构

1. 顺序存储
   又称为顺序队列，它也是利用一组地址连续的存储单元存放队列中的元素。
2. 链式存储
   也称为链队列。这里为了便于操作，给链队列添加一个头结点，并令头指针指向头结点。因此，