数据结构简介
-
什么是数据结构？
- 计算机存储、组织数据的方式
- 相互之间存在的一种或多种特定关系的数据元素的集合
-
常见的数据结构
- 线性表(数组、链表、栈、队列)
- 数
- 图
-
逻辑结构
Snip20180311_11.png -
存储结构
- 顺序存储结构
- 链式存储结构
-
...
Snip20180311_12.png
-
数据运算
- 检索
- 排序
- 插入
- 删除
- ...
线性表简介：
- 什么是线性表
- 线性表是n个具有相同特性的数据元素(节点)a1,a2,...an组成的有序序列(n>=0)
- 当n=0时，成为空表。
- a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。
- 当a1,a2,...ai-1都是ai的前驱，其中ai-1是ai的直接前驱。
-
ai+1,ai+2...an是ai的后续，其中ai+1是ai的直接后续。
Snip20180311_13.png
线性表的顺序存储结构
-
用一组地址连续的存储单元依次存储线性表的数据元素Snip20180311_14.png
-
线性表的常见操作：
- 创建线性表
- 销毁线性表
- 获得线性表的当前长度
- 获得某个位置的节点数据
- 设置某个节点位置的节点数据
- 在某个位置插入节点数据
- 在最后位置添加节点数据
- 获得某个节点的索引位置
- 移除某个位置的节点数据
- 移除某个节点的数据
- 清空线性表
- ...
-
顺序线性表的内存分布
Snip20180311_15.png -
线性表的链式存储结构
-
用一组任意的存储单元存储线性表中的数据元素，它的存储单元可以是连续的，也可以是不连续的。
Snip20180311_16.png
-
链式线性表的内存分布
Snip20180311_17.png
栈：一种特殊的线性表，后进先出的原则(Last In First Out, LIFO)
-
常见操作：
- 创建
- 销毁
- 清空
- 压栈
- 出栈
- 获得栈顶元素
-
获得元素数量
Snip20180311_18.png
队列：一种特殊的线性表，先进先出的原则(First In First Out, LIFO)
-
常见操作：
- 创建
- 销毁
- 清空
- 入列
- 出列
- 获得头元素
- 获得元素数量
-
...
Snip20180311_19.png
