计算机二级算法与数据结构

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法空间复杂度是指执行该算法所需要的内存空间。时间复杂度是实现该算法需要的计算工作量，用大写的字母“O”来表示，O（n）表示针对问题规模是n 的情况下的时间复杂度。一般不特别说明的情况下，复杂度指的就是时间复杂度。在计算复杂度的时候，忽略常数项、低阶项和高阶项前面的系数。

算法的四个特征：①可行性：算法中的操作可以通过已经实现的基本运算执行有限次来实现；②确定性：算法的每一个步骤都有明确的定义，不允许有模糊的解释，不允许有二义性；③有穷性：算法在执行有穷个步骤之后结束，且每一步都在有穷时间内完成；④有足够的情报：算法的执行和输入数据和初始条件有关，不同的输入或初始条件会有不同的输出结果；数据结构是计算机存储、组织数据的方式。数据的逻辑结构是指数据在逻辑上的前后件关系。数据的物理结构指的是数据在存储设备上的存放方式。

数据结构用图形表示，一般用带有元素值的方框来表示数据元素，用有向线段表示数据元素之间的前后件关系。

线性结构要满足两个条件：①有且只有一个根节点；②每一个节点最多只有一个前件，也最多只有一个后件。不满足这两个条件的称为非线性结构。

线性表的顺序存储结构的特点：①线性表中所有元素的占用的存储空间是连续的；②所有元素在存储空间的位置是按逻辑顺序存放的。

线性表的插入：插入位置及后的所有元素都依次后移一位。

线性表的删除：删除位置之后的所有元素都依次前移一位。

栈是一种操作受限的线性表，只允许在一端插入或删除数据，另一端不能进行任何操作。允许操作的一端称为栈顶，另一端称为栈底。栈中的元素遵循“先进后出”或“后进先出”原则。

队列也是一种操作受限的线性表，一端只允许插入数据，另一端只允许删除数据。允许插入的一端称为队尾，用rear 指针表示，允许删除的一端称为队头，用front 指针表示。

队列遵循“先进先出”或“后进后出”的原则。

链式存储结构中，要求每一个节点有两部分组成：一部分存放数据元素，称为数据域；另一部分存放指针，称为指针域。指针域中的指针用于指向前驱或后继节点的位置。链式存储相比较于顺序存储，链式存储占用更多的内存空间，充分利用内存碎片内存利用率高，插入和删除效率高但是读取效率低。

树是一种简单的非线性结构，和自然界中的树结构很类似，用于表示层次结构。树的顶层的节点叫作根节点，一棵树最多只有一个根节点。没有子节点的节点称为叶子节点。节点子树的个数称为节点的度，节点的度的最大值就是树的度。

树的深度：树的层次数。

二叉树：节点的度最大为2 的树，即每个节点最多只有2 个子树，分别为左子树和右子树。

满二叉树：除叶子节点外其他所有节点的度都为2 的树。(https://www.xing528.com)

完全二叉树：除最后2 层节点外，其他所有节点的度都为2，并且最后一层叶子节点按从左到右的顺序分布。

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

二叉树的三条性质：①第n 层的节点数不超过2n－1；②深度为h 的二叉树最多有2h－1 个节点。反过来具有n个节点的二叉树的深度至少为［log2n］＋1，［log2n］是log2n 的整数部分；③对于任意一棵二叉树，如果其叶节点数为N0，度数为2 的节点总数为N2，则N0＝N2＋1。

二叉树可以用顺序存储，也可以用链式存储。当是完全二叉树或满二叉树时，可以采用顺序存储，当不是完全二叉树时，用顺序存储比较浪费内存空间，此时应该采用链式存储。

遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。

●前序遍历：首先访问根节点，再前序遍历左子树，最后前序遍历右子树；

●中序遍历：先中序遍历左子树，再访问根节点，最后中序遍历右子树；

●后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问根节点。

从上面的定义可以看出，前序、中序和后序只是跟访问根节点的时机有关，无论采用何种方式遍历，左子树都先于右子树遍历。

顺序查找就是从第一个元素开始，将每一个元素都与要查找的元素比较，如果相等则查找成功，如果不等则继续往后查找，直到所有元素都比较完。

二分法也称折半查找，就是每次比较都能排除一半的可能。二分法查找的过程：先取中间的数据和要查找的数据比较，如果中间数据大于要查找的数据，则在前半部分继续执行二分法查找，如果中间数据小于要查找的数据，则在后半部分继续执行二分法查找。二分法查找的前提是顺序存储的有序表。

排序方法有交换类排序、选择类排序和插入类排序。交换类排序包括冒泡排序和快速排序，冒泡排序是每次交换相邻的两个元素，平均时间复杂度是O（n2），最坏情况下也是O（n2）。快速排序每次选定一个值作为中枢值，小于这个值的分在一组，大于这个值的分在另一组，然后再分别对这两个组进行快速排序，平均时间复杂度是O（nlog2n），在最坏情况下会退化为冒泡排序，时间复杂度是O（n2）。

插入类排序包括简单插入和希尔排序。简单插入就是把第一个元素作为有序列表，然后把后面的元素依次插入这个有序列表中合适的位置，平均情况和最坏情况下时间复杂度都是O（n2）。希尔排序是按一个增量h 把序列分成若干个组，在每个组中应用简单插入排序，然后逐渐减小h，在新生成的分组中继续用简单插入排序，直到h 变为1。希尔排序的复杂度和选取的h 值有关，在最坏的情况下复杂度也小于O（n2）。

选择类排序包括简单选择和堆排序。简单选择是从序列中选择最小的值和第一个元素交换位置，然后再从剩下的元素中选择最小的值和第二个元素交换位置，依此类推。时间复杂度在平均和最坏情况下都是O（n2）。堆排序是用完全二叉树表示一个序列，分为大顶堆和小顶堆，大顶堆是所有节点的值都大于左右子节点的值，反之则称为小顶堆。堆排序在平均和最坏情况下的复杂度都是O（nlog2n）。