1.数据结构和算法

文章目录

数据结构
- 逻辑结构
- - 集合结构
  - 线性结构
  - 树形结构
  - 图形结构
- 物理结构
- - 顺序存储结构
  - 链式存储结构
算法
- 基本特性
- 目标
总结
- 数据结构总结
- 算法总结

数据结构

「数据结构」指的是：数据的组织结构，用来组织、存储数据。

逻辑结构

逻辑结构（Logical Structure）：数据元素之间的相互关系。

集合结构

集合结构：数据元素同属于一个集合，除此之外无其他关系。
集合结构中的数据元素是无序的，并且每个数据元素都是唯一的，集合中没有相同的数据元素。集合结构很像数学意义上的「集合」。

线性结构

线性结构：数据元素之间是「一对一」关系。
线性结构中的数据元素（除了第一个和最后一个元素），左侧和右侧分别只有一个数据与其相邻。线性结构类型包括：数组、链表，以及由它们衍生出来的栈、队列、哈希表。

树形结构

树形结构：数据元素之间是「一对多」的层次关系。
最简单的树形结构是二叉树。这种结构可以简单的表示为：根，左子树，右子树。左子树和右子树又有自己的子树。当然除了二叉树，树形结构类型还包括：多叉树、字典树等。

图形结构

图形结构：数据元素之间是「多对多」的关系。
图形结构是一种比树形结构更复杂的非线性结构，用于表示物件与物件之间的关系。一张图由一些小圆点（称为「顶点」或「结点」）和连结这些圆点的直线或曲线（称为「边」）组成。
在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。图形结构类型包括：无向图、有向图、连通图等。

物理结构

物理结构（Physical Structure）：数据的逻辑结构在计算机中的存储方式。

顺序存储结构

顺序存储结构（Sequential Storage Structure）：将数据元素存放在一片地址连续的存储单元里，数据元素之间的逻辑关系通过数据元素的存储地址来直接反映。

在顺序存储结构中，逻辑上相邻的数据元素在物理地址上也必然相邻。
这种结构的优点是：简单、易理解，且实际占用最少的存储空间。缺点是：需要占用一片地址连续的存储单元；并且存储分配要事先进行；另外对于一些操作的时间效率较低（移动、删除元素等操作）。

链式存储结构

链式存储结构（Linked Storage Structure）：将数据元素存放在任意的存储单元里，存储单元可以连续，也可以不连续。

链式存储结构中，逻辑上相邻的数据元素在物理地址上可能相邻，可也能不相邻。其在物理地址上的表现是随机的。链式存储结构中，一般将每个数据元素占用的若干单元的组合称为一个链结点。每个链结点不仅要存放一个数据元素的数据信息，还要存放一个指出这个数据元素在逻辑关系的直接后继元素所在链结点的地址，该地址被称为指针。换句话说，数据元素之间的逻辑关系是通过指针来间接反映的。
这种结构的优点是：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比顺序存储结构高（插入、移动、删除元素）。缺点是：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链式存储结构比顺序存储结构的空间开销大。

算法

基本特性

输入、输出、有穷性、确定性、可行性

目标

时间更少、空间更少
正确性、可读性、健壮性

总结

数据结构总结

数据结构可以分为「逻辑结构」和「物理结构」。
逻辑结构可分为：集合结构、线性结构、树形结构、图形结构。
物理结构可分为：顺序存储结构、链式存储结构。
「逻辑结构」指的是数据之间的关系，「物理结构」指的是这种关系在计算机中的表现形式。
例如：线性表中的「栈」，其数据元素之间的关系是一对一的，除头和尾结点之外的每个结点都有唯一的前驱和唯一的后继，这体现的是逻辑结构。而对于栈中的结点来说，可以使用顺序存储（也就是顺序栈）的方式存储在计算机中，其结构在计算机中的表现形式就是一段连续的存储空间，栈中每个结点和它的前驱结点、后继结点在物理上都是相邻的。当然，栈中的结点也可以使用链式存储（也即是链式栈），每个结点和它的前驱结点、后继结点在物理上不一定相邻，每个结点是靠前驱结点的指针域来进行访问的。