软件设计（十一）数据结构(上)

• 线性结构

1. 线性表

线性表是n个元素的有限序列，通常记为(a1，a2....an)，特点如下。

1. 存在唯一的一个称作“第一个”的元素。
2. 存在位移的一个称作“最后一个”的元素。
3. 除了表头外，表中的每一个元素均只有唯一的直接前趋
4. 除了表尾外，表中的每一个元素均只有唯一的直接后继

1）线性表的 顺序存储：优点随机存取表中元素，缺点每次插入需要移动大量元素。

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

链表作为存储结构时，不能进行数据元素随机访问，但优点是插入和删除操作时候不需要移动大量数据。

常用的链表结构：

1. 双向链表：每个节点包含两个指针，指明直接前趋和后继，可在两个方向遍历链表。
2. 循环链表：表尾的指针指向第一个节点。
3. 静态链表：借助数组来描述线性表的链式存储结构。

1. 栈和队列

栈

只能通过访问它一端来实现数据存储和检索的一种线性数据结构。它是先进后出的原则FILO。

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

队列

队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，表的另一端删除元素。

• 数组、矩阵和广义表

1. 数组

n维数组是一种“同构”的数据结构，其每一个元素类型相同，结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。

数组结构特点：数据元素数目固定、数据元素具有相同的类型、数据元素的下标关系具有上下界的约束且下标有序。

一旦定义了数组，结构中元素个数和元素之间的关系就不再发生改变，因此数组适用于采用顺序存储结构。

因为计算机内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理。

1. 矩阵

特殊矩阵：若矩阵中元素（或非0元素）的分部有一定规律，则为特殊矩阵。（如 三角矩阵、对称矩阵、对角矩阵）

稀疏矩阵：若非零的元素远远小于零元素的个数，且非零元素的分部没有规律，则为稀疏矩阵。

1. 广义表

广义表是线性表的推广，由0个或者多个单元素或子表所组成的有限序列。

广义表长度是元素的个数，深度指广义表展开后所含括号的最大层数。

• 树

树是n(n>=0)个节点的有限集合，n=0时称为空树，在任意非空树中：

1. 有且仅有一个称为根的节点。
2. 其余的节点可分为m（m>=0）个互不相交的子集T1，T2...Tm，其中每个子集本身又是一棵树，并称为根节点的子树。

树由若干子树构成，子树又由子树构成。

1. 双亲和孩子：节点的子树的跟称为该节点的孩子，该节点称为其子节点的双亲。
2. 兄弟：具有相同双亲的节点互为兄弟。
3. 节点的度：一个节点的子树的个数记为该节点的度。
4. 叶子结点：也称为终端节点，指度为0的节点。

等...

1. 二叉树

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

二叉树节点最大度为2，而普通树不限制节点的度数。

二叉树基本运算时是遍历，他有如下性质：

1. 二叉树第i层上的节点数目最多为 2 的 (i-1)次方。(i>=1)
2. 深度为k的二叉树至多 （2的k次方）-1 个节点。(i>=1)
3. 在任意一颗二叉树中，若终端节点数为n0，度为2的节点数为n2，则n0 = n2+1。

等...

二叉树的遍历

二叉树分为根节点、左子树和右子树，按照左子树必须遍历在右子树之前，所以分为前序、中序、后续。

也可以层序遍历，从树的根节点出发，依次访问第一层节点，从左往右依次访问第二层的节点，以此类推，自上而下，自左往右。

• 图

图G是由两个集合V和E构成的二元组，记作G=(V,E)，其中V是图中顶点的非空有限集合，E是图中边的有限集合。从数据结构逻辑关系看，图中任意顶点都与其他顶点有关，而图中所有顶点都有可能与某一顶点有关。在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系则用边表示。

1. 有向图：若图中每条边都是有方向的，则称G为有向图。
2. 无向图：若图中每一条边都是无方向的。
3. 无向完全图：若一个图像图具有n个顶点，若每一个顶点与其他n-1个顶点之间都有边，则称为无向完全图。显然含n个顶点的无向完全图共有n(n-1)/2条边。
4. 有向完全图：有n个顶点的有向完全图中孤的数目为n(n-1)，即任何两个不同顶点之间都有方向相反的两条弧存在。

等...

图的遍历分为：

1. 深度优化遍历 DFS：从图G任意一个顶点v出发。设计搜索指针，指向旁边未访问的顶点。
2. 广度优化遍历：BFS：从顶点v出发，访问v旁边都未访问过的顶点。