数据结构知识回顾（基础数据结构-绪论）

数据结构-绪论（一）

1. 存储
2. 数据结构
3. 算法
4. 概述

数据结构-线性表（二）

1. 数组
1. 删除
2. 插入
3. 交换
4. 移动
2. 链表
1. 单/双，循环，静态链表
2. 单链表逆序
3. 单链表的，从尾部输出（单次遍历）
4. 求单链表的中间节点（不知道链表的长度）
5. 单链表求得倒数第K个元素
6. 单链表插入排序
7. 两个顺序单链表的，合并（顺序）
8. 两个单链表的，公共点
9. 判读单链表是否带环
10. 求环的长度
11. 得到环的切入节点
12. 求带环链表的长度
13. 求出环中的任意，节点的最长距离节点
14. 求带环链表的相交点
3. 栈
1. 递归
2. 共享栈
3. 斐波那契数列
4. 用两个栈，实现一个队列
5. 求最新栈元素，要求时间复杂度是O（1）
6. 一个数组实现两个栈，本质上就是顺序存储的共享栈
7. 如何实现逆序栈
8. 如何实现栈的排序
9. 内存栈的构成，栈区和堆区的说明
4. 队列
1. 循环队列
2. 优先队列
3. 两个队列实现，栈
4. 猫狗队列

数据结构-串（三）

1. KMP模式匹配算法
2. BM算法
3. Sunday算法
4. 最长公共子串

数据结构-树（四）

1. 搜索二叉树
2. 红黑树
3. B 树
4. B-树
5. 默克尔树
6. 赫夫曼树

数据结构-图（五）

1. 广度优先遍历
2. 深度优先遍历
3. 最小生成树-Prim（普利姆算法）
4. 最小生成树-Kruskal（克鲁斯卡尔）
5. 最短路径-Dijkstra（迪杰特斯拉）
6. 最短路径-Floyd（弗洛伊德算法）
7. A*路径搜索算法
8. 关键路径算法

---

基础数据结构，总共分为5篇文章，依次来介绍说明，今天介绍第一篇绪论

数据结构-绪论

存储

数据结构

算法

程序 = 数据结构 算法；

一切程序的来源都是数据之间的关系存储。

1、数据是什么呢？

数据，通俗的讲就是整型123，字符串ABC等数值类型，以及声音，图片，视频等等，最终以二级制数据存储到磁盘中；数据是计算机操作的对象，所有可输入的处理符号，且可被计算机识别的对象都成为数据

数据元素：是一个数据的集合，也成为"记录"

数据项：一个数据元素由若干个数据项组成

数据对象：性质相同的数据元素的集合

数据关系：相互之间存在的一种或是多种关系的数据元素集合

2、数据之间的关系有哪些？

无关系

一对一关系

一对多关系

多对多关系

3、算法及与数据结构之间的关系？

算法是解决问题求解步骤的描述，一条条的序列指令的步骤集合；

就像，如何炒一盘菜？

那么算法就可以理解为“菜谱”，那么数据结构就可以理解为“食材”，有了食材，有了菜谱，才能做出一份“程序”

接下来分别描述一下，数据结构和算法

数据结构

数据结构，也就是数据之间的关系，分为结构：逻辑结构和物理结构（也就是如何存储的）

• 逻辑结构

1. 集合结构 == 无关系
1. 定义：数据元素之间没有关系，只是存储在一个集合
2. 特点：数据元素是平等的
2. 线性结构 == 一对一的关系
1. 定义：数据元素之间是一对一线性关系
2. 特点：每个数据元素都有前驱或是后驱
3. 树形结构 == 一对多的关系
1. 定义：数据元素之间是一对多的层次关系
2. 特点：数据元素都有一个前驱或多个后驱
4. 图形结构 == 多对多的关系
1. 定义：数据元素之间是多对多的关系
2. 特点：数据元素之间相互之间

• 存储结构

又叫做物理结构，是指数据元素的逻辑结构在计算机中的存储形式。

1. 顺序存储结构
1. 定义：是把数据元素存放在连续的存储单元里
2. 例如：创建一个长度为10的整型数组，计算机就在内存中，按照一个整型（4个Btye）所占位置的大小乘以9，开辟一段连续的空间，然后第一个数据元素放在第一个位置，第二个数据放在第二个位置，依次存放
3. 特点：开辟的空间是连续的，索引查询比较快，会浪费多余的空间，需要预制数据元素的大小，空间扩展比较麻烦，插入/删除数据元素，则需要大量元素跟着移动
2. 链式存储结构
1. 定义：是把数据元素发在任意的存储单元里，每个数据元素中含有其对应逻辑关系的存储地址，也就是链式存储结构在分配空间的时候不是连续的，当然了也可以是连续的
2. 例如：现在医院排队系统，每个人过去先领取一个号，等着叫好，叫到的时候去看病，在等待的时候，可以爱去哪儿去哪儿；“号”就是一个指针存放数据元素的地址，通过“号”找到关联数据元素的位置
3. 特点：插入/删除数据元素比较灵活，查询效率较低，数据元素复杂的关系用链式存储可以更好的表示

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条特定指令都表示一个或多个操作

• 特性

1. 正确的输入和输出
2. 有穷性
3. 确定性
4. 可行性

• 设计要求

1. 正确性
2. 可读性
3. 健壮性
4. 时间复杂度低和空间复杂度低

• 时间复杂度

定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的数量级，算法的时间复杂度，就是算法的时间量度T(n)=O(f(n))

常数阶 > 对数阶 > 线性阶 > nLogn阶 > 平方阶 > 立方阶 > 2^n > N! > 指数阶

• 空间复杂度

算法空间复杂度是通过计算算法所需的存储空间实现，算法空间复杂度的计算公式:S(n) = O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占用的存储空间的函数

例如：求证1 2 3 4 ... 100？

基本的算法，遍历1到100个数，进行相加，时间复杂度O(n)

换成高斯算法，时间复杂度O(1)

1 2 3 ... 98 99 100 = a;

100 99 98 ... 3 2 1 = a;

上面两个表达式相加求证：2a =（100 1）* 100

a =（100 1）* 100 / 2

那么求，∑i = 1 2 3 … n，得出∑i =（n 1）* n/ 2

就好像上面说的算法，就像炒菜的菜谱（算法），在一定的食材（数据）中，如何做出一份又快又好吃的饭菜；

数据结构和算法

线性表

树

图

,