博客目的在于复习一些基础知识，尤其数据结构相关的知识

一、算法

1 定义：

解决问题完整准确的描述（程序 = 算法 + 数据）

例如：可以将勾股定理公式 a²+b²=c² 看成一个算法，知道了a 和 b的值求c

2 基本特性

特性	说明
可行性	计算机硬件可支持运算该算法
有穷性	不出现死循环的情况
足够的情报	应该有输入信息和输出信息

3 基本要素：

要素	举例
算术运算	加减乘除
逻辑运算	与或非
关系运算	大于小于等
数据传输	输入输出赋值等

4 基本结构：

• 顺序

• 选择

• 循环

5 时间复杂度：

执行算法的计算工作量（基本运算次数）

6 空间复杂度：

执行算法需要的内存空间

时间复杂度和空间复杂度无必然联系

二、数据结构

1 定义：

数据：数据元素的集合

数据元素：若干数据项组成，数据项为数据最小单位

结构：数据元素之间的关系

数据结构： 相互关联的数据元素的集合

例如：

一年由春夏秋冬四季组成

数据元素：春夏秋冬

  数据项：1~12的月份

   结构：春夏秋冬按顺序运转

一年按照春夏秋冬的顺序来运转，组成一年的光景，

我们将一年看成是一个存储了四季，四季包含各个相关月份的顺序数据结构。

2 数据结构的逻辑结构分类：

数据元素的逻辑关系（前后关系）

分类	代表项	说明
线性	栈，队列、线性表	其特点是所有数据在一条线上，只有一个头和一个尾
非线性	树、图	例如 - 父亲 和 儿子女儿的关系，他们可以看成是一个树关系，父亲是根节点，儿子女儿是子节点

3 数据结构的存储结构分类

数据的逻辑结构在计算机存储空间中的存放方式

分类	说明
顺序存储	一块连续的存储空间
链式存储	通过指针域进行关联起来的一块存储空间

4 数据结构的运算

• 插入
• 删除
• 查找
• 排序

5.1 数据结构的逻辑结构-》线性表

5.2 数据结构的逻辑结构-》栈

它是一种特定的线性表

5.3 数据结构的逻辑结构-》队列

队列也是一种特定的线性表
队尾插入元素，队头删除元素

在 rear端进行插入元素，在front进行删除元素
插入一个元素 rear指针向上移动
删除一个元素front指针向上移动

上面第（3）点，应该是s=容量或s=0

5.4 数据结构的逻辑结构-》线性链表

线性表的存储方式有两种： 顺序 和 链式 ， 一般采用顺序存储

1. 线性表的顺序存储结构又称为顺序表
2. 线性表的的链式存储结构又称为线性链表

5.5 数据结构的逻辑结构-》树

它是非线性结构

基本概念

概念	说明
根结点	图中的A点即为根结点，无父结点只有子结点的结点
结点的度	结点所拥有子树的个数称为结点的度，A的度是3
树的度	树中所有节点的度的最大值成为该树的度
叶子结点	度为0的结点 ，图中的 K L M N H J 都是叶子结点
树的深度（高度）	树中所有节点的层次的最大值称为该树的深度，图中为4层

二叉树

有限结点集合（可为空），每一个结点最多有两颗子树

完全二叉树，最多缺少右边结点

二叉树的特性

其中 log运算是向下取整

树的遍历

一共三种：

• 前序遍历 根左右
• 中序遍历 左根右
• 后序遍历 左右根

所谓前、中、后可以看成是针对根结点而言，可参考上面的图。
一开始就访问根结点的就是前序遍历。

前序遍历 第一个输出的一定是 根节点

6 查找技术

6.1 顺序查找

顺序查找适用于所有的线性表

6.2 二分查找

二分查找适用于顺序存储的有序线性表

注意：即使是有序线性表，如果采用链式存储，也只能顺序查找

7 排序

快速排序

第一个为划分基准
从右到左顺序找比基准小的数进行交换
从左到右顺序找比基准大的数进行交换
重复上面的动作

总结