数据结构与算法

算法的基本概念

概念：算法是指一系列解决问题的清晰指令。
算法不等于程序也不等于计算方法。
4个基本特征
1. 可行性
2. 确定性
3. 有穷性
4. 拥有足够的情报
两种基本要素：对数据对象的运算和操作、算法的控制结构（运算和操作时间的顺序）。
设计的基本方法：列举法、归纳法、递推、递归、减半递推技术。
算法的时间复杂度：执行算法所需要的计算工作量。
算法的空间复杂度：执行算法所需要的内存空间。
算法的时间复杂度和算法的空间复杂度二者之间没有必然联系。

数据结构的基本概念

数据结构：是指相互有关联的数据元素的集合，即数据的组织形式。其中逻辑结构反映数据元素之间的逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放方式，有顺序存储、链式存储、索引存储和散列存储4种方式。
数据元素：数据元素是数据的基本单位。
数据对象：数据对象是性质相同的数据元素的集合。
数据的逻辑结构包括数据对象和数据对象之间的关系。
数据的存储结构包括数据元素的存储方式和关系的存储方式。
一种数据的逻辑结构可以表示成多种存储结构。
线性结构的条件（一个非空数据结构)：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。
栈、队列、双向链表是线性结构；树、二叉树为非线性结构。

线性表及其存储结构

线性表 是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。具有“ 一对一 ”逻辑关系的数据，最佳的存储方式是使用线性表。除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表的存储结构：顺序存储结构（顺序表） 和 链式存储结构（链表） 。
线性表的顺序存储结构有两个特点：
（1）线性表中所有元素所占的存储空间连续；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
线性表的链式存储结构存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。结点包含：数据域、指针域。（注：链式存储方式既可用于表示线性结构，也可用于表示非线性结构）。

栈和队列

栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。
栈具有记忆功能，队列没有记忆功能。栈的特点是先进后出,后进先出,所以对一个栈进行出栈操作,出来的元素肯定是最后存入栈中的元素,所以栈有记忆功能。而队列是先进先出,取队列的第一个元素,得到的是最先存入队列的元素,而不是上一个存入队列的元素,所以没有记忆功能。
栈、队列的存储结构：
（1）顺序存储结构：用一组地址连续的存储单元即一维数组来存储；
（2）链式存储：线性链表。
循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环形空间。
入队运算是指在循环队列的队尾加入一个新元素。当循环队列非空（s=1）且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。
退队运算是指在循环队列的队头退出一个元素并赋给指定的变量。首先将队头指针进一，然后将排头指针指向的元素赋给指定的变量。当循环队列为空（s=0）时，不能进行退队运算，这种情况称为“下溢”。
队列元素：尾指针-头指针

线性链表

在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。
在链式存储方式中，要求每个节点有两部分组成：一部分用与存放数据元素值，称为数据域；另一部分用与存放指针，称为指针域。其中指针用与指向该节点的前一个或后一个节点（即前件或后件）。

树和二叉树

树是 n(n>0) 个结点的有限集合，是一种非线性结构。
结点的度：结点所拥有的子树的个数。
叶子结点：度为0 的结点。
分支结点：除叶子结点以外的结点。
结点的层次：根结点在第一层。
树的深度：所处层次最大的那个结点的层次。
树的度：树中所有结点的度的最大值。
二叉树每个结点最多只有两棵子树，且有左右之分，不能互换，二叉树有五种不同的形态。
在二叉树的第 k 层上，最多有 $2^k−1(k>=1)$ 个结点。
深度为 m 的二叉树最多有 $2^m−1$ 个结点。
在任意一棵二叉树中，度为 0 的结点（叶子结点）总是比度为 2 的结点多一个。
具有 n 个结点的二叉树，其深度不小于 $log_2 n + 1$ ，其中 $log_2 n$ 表示为 $log_2 n$ 的整数部分。
满二叉树：每一层上的结点数都达到最大值，即在满二叉树的第 k 层上有 2k−1 个结点。
完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
具有 n 个结点的完全二叉树的深度为 $log_2 n + 1$ 。
完全二叉树中度为 1 的结点数为 0 或 1 。
前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

查找技术

顺序查找是从表的一端开始，依次扫描表中的各个元素，并与所要查找的数进行比较。
只能采用顺序查找：
（1）线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。
（2）有序线性表，如果采用链式存储结构，也只能用顺序查找。
二分查找的条件：
（1）用顺序存储结构，
（2）线性表是有序表。
对于长度为 n 的有序线性表，在最坏情况下，二分法查找只需比较 $log_2 n$ 次，而顺序查找需要比较 n 次。

排序技术

排序算法
1、交换类排序
（1）冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为 $$\frac{n(n-1)}{2}$$
（2）快速排序法，在最坏的情况下，快速排序需要比较次数为 $$\frac{n(n-1)}{2}$$
2、插入类排序：
（1）简单插入排序法，最坏情况需要 $$\frac{n(n-1)}{2}$$ 次比较；
（2）希尔排序法，最坏情况需要**$$O(n^{1.5})$$**

次比较。
3、选择类排序：
（1）简单选择排序法，最坏情况需要 $$\frac{n(n-1)}{2}$$ 次比较；
（2）堆排序法，最坏情况需要 $$O(nlog_2 n)$$ 次比较。相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。