（四）数据结构基本知识总结

数据结构

1、分类：线性结构（线性表、栈、队列、串、数组）、非线性结构（树、图）。
2、存储结构：顺序存储、链接存储。

线性结构

1、特点：数据元素之间是一种线性关系。单一全驱和后继。

线性表

1、单链表（n个结点通过指针连成链表，且结点只含一个指针域）、头结点、首元结点、双向链表、循环链表、静态链表
2、单链表基本运算：查找Find_List、插入(Insert_List)、删除(Delete_List)。
3、存储方式优缺点：顺序存储（可随机存取数据、查找元素速度快，但插入、删除需移动元素（n/2、(n-1)/2））、链式存储（数据域、指针域，插入、删除无需移动元素，但只能顺序访问元素、无法随机存取）。

栈

1、定义：先进后出的线性表。
2、栈顶、栈底、空栈、顺序栈（上溢现象）、链栈
3、栈基本运算：初始化栈（initStack）、判栈空（isEmpty）、入栈（push）、出栈（pop）、读栈顶元素（top）

队列

1、定义：先进先出的线性表。相关概念：队尾、队头。
2、基本运算：初始化队列（initQueue）、判队空（isEmpty）、入队（enQueue）、出队（deQueue）、读队头元素（frontQueue）
3、队列顺序存储：队尾有上限、循环队列（区别队空与队满：设置标志域、保留一个元素空间）。队列链式存储：链队列。

串

1、定义：一串文字及符号的简称。元素：字符。
2、基本术语：串长、空串、空格串、子串、串相等、串比较。
3、基本操作：赋值（StrAssign）、连接（Concat）、求串长（StrLength）、串比较（StrCompare）、求子串（SubString）。
4、串的存储结构：顺序存储、链式存储

数组

1、一维数组：长度固定、元素类型相同、元素结构一致的线性表。多维数组：定长线性表在维数上的扩张、线性表的元素还是线性表。
2、特点：元素数目固定、元素类型相同、下标有序且受上下界约束
3、基本操作：取值、赋值
4、二维数组顺序存储：以行为主序、以列为主序。
5、矩阵、压缩存储、特殊矩阵（值相同的元素或零元分布有规律）、对阶矩阵、对角矩阵、稀疏矩阵（非零元远少于零元且分布无规律）

树

1、基本概念：空树、根结子树、双亲、孩子、兄弟、结点度、叶子结点、内部结点、结点层次、树高度、有序树、无序树、森林

二叉树

1、与树的区别：明确左右子树、结点最大度为2。
2、3个性质：二叉树第i层（i>=1）上至多有2^{(i-1)个结点；深度为k的二叉树至多有(2}k)-1个结点（k>=1）；对于任意一颗二叉树，若其终端结点数为n0，度为2的结点数为n1，则n0=n1+1
4、满二叉树（深度为k的二叉树有(2^k)-1个结点）、完全二叉树（结点编号与深度相同的满二叉树的结点编号一一对应）
5、二叉树存储结构：顺序存储（一般不采用）、链式存储（二叉链表、三叉链表）
6、二叉树遍历：先序遍历、中序遍历、后序遍历（由根结点所在位置决定，多用递归实现）
7、数和森林与二叉树转换（孩子兄弟表示法）、树的遍历（先根遍历、后根遍历）、森林的遍历（先序遍历、中序遍历、后序遍历）
8、最优二叉树（带权路径长度最短的二叉树）：两结点间路径、结点的路径长度、树的带权路径长度、哈夫曼方法
9、二叉查找树：左子树所有结点小于根结点，右子树所有结点大于根结点。

图

1、基本概念：图是由点集和边集构成的二元组。有向图（弧、出度、入度、强连通图），无向图（度、连通图）、完全图（任意两个顶点相连）、路径、子图、网
2、图的存储结构：邻接矩阵表示法、邻接链表表示法