数据结构学习笔记（一）

逻辑图：

其中：集合结构、树结构、图结构为非线性结构

1.线性表

定义：一个线性表是n个具有相同特性的数据元素的有限序列，线性表的元素仅限于原子项，原子是结构上不可分割的成分

1.1顺序存储结构：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构，通常用数组来描述顺序存储结构,下同

分类：数组 

1.2链式存储结构：结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻（链表）

分类：单(向)链表、双(向)链表、单向循环链表、双向循环链表

2. 栈和队列

2.1：栈

定义：先进后出，后进先出，只要满足此条件就可以称为栈，所以我们把数组和链表加上限制条件后便成了栈

主要方法：初始化、压栈、出栈、判空、遍历、清空等

分类：静态栈（顺序存储）、动态栈（链式存储）

2.2：队列

应用：数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值，递归实现

定义：先进先出，后进后出，只要满足此条件就可以称为队列

分类：单向对列(按存储结构又可分为顺序队列和链式队列)、双向(端)队列、循环队列

应用：银行排队办理业务

2.3：总结

栈和队列是两种特殊的线性表

3.串

定义：由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表

分类：定长顺序存储串、堆分配存储串(动态分配长度)、块链存储串（即链式存储）

空串和空白串的区别：

空串(Null String)是指长度为零的串

空白串(Blank  String)是指包含一个或多个空白字符‘  ’(空格键)的字符串

4.数组和广义表

4.1：数组

定义：用一组连续的内存空间来存储一组具有相同类型的数据

分类：一维数组、二维数组、多维数组

应用：对称矩阵的压缩存储、稀疏矩阵(矩阵中包含大量0元素)的压缩存储

4.2：广义表

定义：n个元素的序列，广义表的元素或者是原子项，或者是一个广义表

5.树和二叉树

5.1：树

定义：它是由n（n>=1）个有限节点组成一个具有层次关系的集合

存储方式：双亲表示法、孩子表示法、孩子兄弟表示法

操作：树转二叉树、遍历(先根遍历、后根遍历)

5.2：二叉树

操作：创建节点、插入节点、查找节点、删除节点、遍历二叉树(先序、中序、后序)、销毁二叉树、求节点或叶子节点个数、求树高、求路径、交换节点的左右孩子

分类：完全二叉树、满二叉树、哈夫曼树（带权路径长度最小的二叉树又叫最优二叉树）、平衡二叉树（任意节点的子树的高度差都小于等于1）、线索二叉树（加上结点前趋后继信息的二叉树）、二叉排序树(又叫二叉查找树)、红黑树(解决二叉排序树插入新节点导致的不平衡)、B-树(B树)、B+树（对B-树的简化）、

存储结构：顺序存储结构(仅仅适用于满或完全二叉树)、二叉链表法(每个节点存储左子树和右子树)/三叉链表法(左子树、右子树、父节点)、

5.3：森林

操作：森林转二叉树、遍历(先序遍历、后序遍历)

6.图

定义：由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为:G(V,E),G表示一个图，V是图G中顶点的集合，E是图G中边的集合，带权的图称为网，入度/出度/度(有向图的弧 e = 所有顶点入度的和 = 所有顶点出度的和)、邻接点、

分类：有向图、无向图

存储结构：邻接矩阵(数组)表示法、邻接表(链式)表示法 

操作：遍历(深度优先遍历、广度优先遍历)、构建最小生成树(普里姆算法(将顶点归并)、克鲁斯卡尔算法(将边归并))、拓扑排序、关键路径、最短路径

6.1：有向图

6.2：无向图

 6.3：连通图

图中任意两个顶点都是连通的，则称G是连通图

6.4：关键路径

我们把顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。

AOE-网是一个带权的有向无环图，顶点表示事件，弧表示活动，权表示活动持续的时间

关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。关键路径长度是整个工程所需的最短工期

关键活动：关键路径上的活动称为关键活动。

6.5：最短路径

从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径

迪杰斯塔拉算法--单源最短路径

所有顶点间的最短路径—用Floyd（弗洛伊德）算法

7.查找

8.内部排序

 

 

数据结构的基本运算：修改、插入、删除、查找、排序、判空