数据结构与算法的基本概念

算法：是指解题方案的准确而完整的描述。（或者，编写程序的方案，解决问题的方案。）

算法的基本特征：
1 可行性：编写的程序能够执行
2 确定性：明确功能
3 有穷性：算法必须在有限的时间内完成
4 拥有足够的情报：要有输入和输出

算法的复杂度：
1 时间复杂度：执行这份算法需要计算的工作量，执行算法的基本运算的执行次数（但是并不是执行算法所需要的时间）
2 空间复杂度：执行这个算法所需要的内存空间

数据结构：数据在计算机中的存储形式

数据结构存储到计算机当中有两种结构: 数据的逻辑结构，数据的存储结构。

1 数据的逻辑结构：打开我的电脑，在我的电脑中有C盘D盘E盘F盘等，每个盘里面有不同的文件夹，每个文件夹包含一个或多个文件夹，能够看到数据元素，并且能够看到数据元素前后件之间的关系，我们可以把这些理解为数据结构。但是对于计算机的硬盘来讲，在硬盘当中有没有文件夹的概念呢？没有！只不过是我们逻辑上这么认为的，方便我们理解。
2 数据的存储结构：正真数据是存储在硬盘的盘道上的，叫物理存储结构，或者叫数据的存储结构。

数据的存储结构有：顺序、链接、索引等

1 顺序存储：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，节点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序储存结构
2 链接存储：它不要求辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的，由此得到的储存表示称为链式存储结构
3 索引存储：除建立存储结点信息外，还建立附加索引来标识结点的地址。

数据结构分为两大类型：线性结构和非线性结构

• 线性结构：（非空的数据结构）有且只有一个结点，每个结点最多有一个前件，也最多有一个后件

常见的线性结构有线性表、栈、队列和线性链表等

栈
栈：是限定在一端进行进行插入和删除运算的线性表。
在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底，栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素，即栈是按照“先进后出”或“后进先出”的原则组织数据的。 队列
队列：是允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表，尾指针（rear）指向队尾元素，头指针（front）指向排头元素的前一个位置（队头）。。队列是“先进先出”或者是“后进后出 ”的线性表。

• 非线性结构：不满足线性结构条件的数据结构

常见的非线性结构有树、二叉树和图等

树：是一种简单的非线性结构，在树这种数据结构中，所有元素之间的关系具有明显的层次特性。每一个结点只有一个前件，称为父节点，没有前件的结点只有一个，称为树的根结点，每一个结点可以有多一个后件，称为该节点的子节点，没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该节点的度。所有结点中最大的度称为树的度。树的最大层次称为树的深度。

树的结构

在上面的图片中A为根结点，BC为A的子节点以此类推，B、C、D、G为父节点，E、F、H、I、J、K、L、M、N为叶子节点。
A结点的度为2
B结点的度为2
D结点的度为3
G结点的度为4
...
那么树的度为4、树的深度为4

什么是二叉树？
二叉树是一种很有用的非线性结构，它具有以下两个特点：

1. 非空二叉树只有一个根结点

2. 每个结点最多有两颗子树，且分别称为该结点的左子树与右子树

   
   二叉树结构图

二叉树的遍历是指不重复地访问二叉树中的所有结点，二叉树的遍历可以分为以下三种：

1. 前序遍历（DLR）：根-左-右
2. 中序遍历（LDR）：左-根-右
3. 后序遍历（LRD）：左-右-根
提示：遍历的时候对于任何非空节点我们都把它看成根结点

就拿上边图中的满二叉树为例：

前序遍历：1-2-4-5-3-6-7
中序遍历：4-2-5-1-6-3-7
后序遍历：4-5-2-6-7-3-1

排序技术：
排序是指将一个无序序列整理成按值非递减序列排序的有序序列。即是将无序的记录序列调整为有序记录的一种操作。

1. 交换类排序法（方法：冒泡排序，最坏需要排序n(n-1)/2次；快速排序，最坏需要排序n(n-1)/2次）
2. 插入类排序法（方法：简单插入排序n(n-1)/2；希尔排序n的1.5次方次）
3. 选择类排序法（方法：简单选择排序n(n-1)/2；堆排序nlog2n）
排序次数最少的是谁？ 堆排序

OK.