1 算法的基本概念

1.1 算法定义

两种定义：

解题方案的准确而完整的描述；

在有限时间内，利用已知序列明确目的地有效解决问题的完整指令；

注：算法不是程序

1.2 算法特征

1.有穷性、拥有足够的情报、确定性、可行性

根据第二种定义可以得知这四个特性：

1）有穷性意味着算法执行于有限的时间内；

2）拥有足够的情报表示算法拥有足够的输入信息和输出结果；

3）确定性是指算法中的每一步都是明确的且都不存在摸棱两可的解释，更不可能存在多义性；

4）可行性就是有效解决问题，每一步都能够实现。

  2.有限性、确定性、可行性、输入性、输出性

两种版本相比较来说，其实差异也不大，第二种版本中的有限性就是有穷性，而输入性是指0个输入或者多个输入，输出性是指必须输出。

1.3 算法基本要素

算法的两大基本要素：数据对象的运算和操作、算法控制的结构（运算和操作的顺序）

1.3.1 对数据对象的运算和操作

每一台设备上的算法各有不同，存在差异性，但是它们都共有如下四类型基本运算：

算术运算：加减乘除

逻辑运算：或、与、非

关系判断：大于、小于、等于、大于等于、小于等于、不等于

数据传输：输入、输出、赋值

1.3.2 算法的控制结构

算法各步骤之间的操作和运算顺序称为算法的控制结构。

三种基本结构：顺序、选择（分支）、循环（重复）

1.3.3 算法的描述工具

N-S结构化流程图、伪代码、流程图、自然语言、程序设计语言

1.4 算法设计的基本方法

递推法、减半递推法、递归法、列举法、回溯法、归纳法

递推法：从已知初始条件出发，退出中间结果以及最后结果，一步一步的归纳；

减半递推法：将问题规模中不改变问题性质的减半，重复此流程；

递归法：将复杂的问题分解成若干简单的问题，对这些简单的问题求解，逐层向上，最终攻破复杂问题；

列举法：将所有可能的结果一一列举；

回溯法：对一个问题逐层分析，从上到下的依次尝试，尝试失败则返回上一步骤，对另外一条支路进行尝试；

归纳法：通过少量的特殊关系找到一般关系。

1.5 算法的复杂度

算法的复杂度是衡量算法效率的标准。它包括两类型：算法时间复杂度、算法空间复杂度

  1.5.1 算法时间复杂度

并非算法执行所消耗的时间，而是指执行算法所需要的计算工作量，该工作量与问题规模（输入语言的存储空间）有关。其实时间复杂度可以用运算过程中的基本运算次数来度量。

  1.5.2 算法空间复杂度

执行算法所需的内存空间：程序本身的内存空间、输入数据所占的内存空间、算法执行所需要的额外空间。

额外空间包含算法执行过程中的工作单元以及某种数据结构所需要的存储空间。

注：算法的时间复杂度与空间复杂度没有任何直接和间接的关系，二者相互独立。

2 数据结构的基本概念

2.1 数据结构定义以及一些小概念

数据：待处理的数据元素集合；

数据元素：数据的基本单位，也就是数据集合的个体；

数据项：数据的最小单位，它是数据元素的组成项；

结构：各个数据元素的关系。

综上所述，数据结构就是互有关联的数据元素的集合。

数据结构大概可分成4种类型：线性结构、树形结构、网状结构、集合

2.2 数据结构的图形表示

除了这种线性的一对一结构，还有一对多的树形结构的图示等等。

早上叫做中午的前件，中午是早上的后件。

以上这些中间标有元素值的方框称为结点，结点又有根结点、内部结点、终端结点（叶子结点）

根结点就是没有前件的结点，内部结点就是除了根结点和终端结点的结点，终端结点也称叶子结点，它没有后件，对此很好理解，你可以想象一颗树，树根、树干、树叶这是与其对应的。

2.3 数据结构的研究内容

1.数据逻辑结构

2.数据存储结构

3.对数据结构运算（插入、删除、查找、排序）

2.3.1 数据逻辑结构

逻辑必然就是联系，那是指什么的联系呢，根据数据结构的定义可知，数据元素之间所固有的逻辑联系（前后件关系）就是数据逻辑结构。

数据的逻辑结构由两个组成部分：元素的集合、元素的逻辑关系体现；

何为元素的集合呢，将数据一一列举出来，我们将该集合用字母D表示，而D中列举出来的元素，根据二元关系一一表示（我们用R表示），关系体现部分来说是两个元素前后关系，总体来说反映了元素的前前后后（顺序），而部分表示成（前件，后件）。综上可知，数据逻辑结构由D和R组成，即逻辑结构

B=（D，R）。

比如：早上、晚上、中午是三个数据元素，那么D={早上，晚上，中午}，R={（早上，中午），（中午，晚上）}

试想一下，如果把R中（中午，晚上）改成（早上，晚上），可行否？当然不可行了，这样会存在中午与晚上前后逻辑不清的问题。

生活中的数据元素很多，比如四季、十二月、三餐等等。

2.3.1.1 线性结构

线性结构必然同时满足以下两个条件：

大条件：非空，就是数据结构中的数据元素必然存在；

小条件：有且仅有一个根结点，其余结点最多只有一个前、后件。

线性结构有：队列（包括循环队列）、栈、线性表（包括双向链表）、矩阵等。

2.3.1.2 非线性结构

不满足以上任意条件的则为非线性结构，如上的例子（早上、中午、晚上）就是一个线性结构，而网状结构、树形结构就是非线性结构。

2.3.2 数据存储结构

数据的逻辑结构在存储空间中的存放形式就是数据存储结构，一种逻辑结构可有多种存储结构，数据的存储结构另称数据物理结构（依赖计算机），常见的存储结构有：顺序、链式、索引、散列，不同的存储结构其处理数据效率和接受访问能力不同。数据元素之间的逻辑关系不等于存储结构中的顺序。

顺序存储结构：这种存放方式主要勇于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单位，必定连续。

链式存储结构：每一个结点至少包含一个指针域，用指针的指向来体现数据元素之间的逻辑关系，是否线性取决于指针走向。

以上两种适用在内存中，而以下的两种结构适用在外存与内存交互结构。

索引存储结构：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。

散列存储结构：散列存储，又称hash存储，是一种将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

注：与算法空间复杂度定义不要混淆。

3 线性表及顺序存储结构

3.1 线性表定义

由n个是数据元素a1、a2、a3……an组成的有限序列组，是一种简单常用的数据结构。

线性表的数据元素个数n为该线性表的长度，一个线性表可以用L表示：L=（a1，a2，a3……an），n＝0时，称之为空表，以L=（）表示。常见的线性表有英文字母表、表格等，线性表中的每一个数据元素即为一个结点，a1无前件，an无后件，其他元素有且仅有一个前件和一个后件，由此可见线性表是一种线性结构。需要注意的是，一些复杂的线性表并非如此简单，比如矩阵，但其实也很好理解，矩阵的每一行我们都视为数据元素，亦或者每一列视为数据元素，不就是一个线性表中，简单的来说，矩阵、向量、二维表等等都是线性结构。

3.2 线性表的顺序存储结构——顺序表

线性表中存放元素最简单的方法，那就是按顺序存放，由此可知顺序存储结构是如何分配元素的，线性表中的元素是连续且按照逻辑顺序依次排列的，可以随机访问。

那么，在线性表的顺序存储结构中，我们如何对某个数据元素寻找存储地址呢？经历过高中数学的同学可能知道等差数列，an=a1+（n-1）d，a1为首项，d为公差，公差就是相邻的两项后项减去前项之差。那这个有什么用呢？

假设，L=（a1，a2，a3，a4，a5，a6……an），每一个元素占K个字节（那么存储地址上相邻两个元素相差K），a1的存储地址已知，那对于第i个字节来说，ai的存储地址就是a1+（n-1）K。

顺便提一下，线性表也可以采用链式存储，但是一般都是采用顺序存储。

3.3 线性表中的运算

3.3.1 插入操作

插入就意味着数据元素将要增加

a1，a2，a3，a4，a5，a6……an

向以上线性表中a4，a5之间插入一个t元素，那么就意味着a5及其后面的数据的存储地址都要往后移动相同的单位。

特别地，一般线性表的存储空间要小于整体的存储空间，比如线性表的存储长度为4，整体的存储空间为4，如果此时向线性表增加一个元素，其长度变为5>4，那么就会造成错误，称之为“上溢”现象。

3.3.2 删除操作

删除就意味着数据元素将要减少

a1，a2，a3，a4，a5，a6……an

向以上线性表中a4元素发出删除的指令，那么就意味着a5及其后面的数据的存储地址都要往前移动相同的单位，特别地，删除a1，所有数据元素全部移动。

根据以上运算操作可知，顺序存储结构牵一发而动全身，方法很简单，但是存储效率很低，不灵活。

4 “弹夹”和队列

4.1 栈的定义

限定只能在一端进行插入和删除的线性表。

4.1.1 栈的特点

栈只能在栈顶插入和删除；

栈的数据元素进出原则是：“先进后出（FILO）”或者“后进先出（LIFO）”；

栈底指针：bottom，栈顶指针：top，栈中无元素（空栈）时两指针在最底部，栈底指针不变，栈中元素跟随栈顶指针的变化而动态变化。

栈具有记忆功能；

栈支持子程序调用。

注：生活中最常见的栈结构就是子弹夹！

4.1.2 栈的元素进出

以下将以一个长度为6的栈进行举例：

入栈（压栈或者进栈）操作：

现处空栈，top和bott om指针指向最底部；

从顶端放入一个元素，bottom指针不变，top指针指向1；

……之后移动了5个元素，bottom指针不变，top指针向上移动5指向6；

此时栈满，即元素已满。

出栈（退栈）操作：

此时满栈，元素共6个，满的状态；

顶部6的元素退出去，bottom指针不变，top指针向下移动1指向5；

……之后退出了5个元素，bottom指针不变，top指向到最底端；

此时空栈，即无元素。

注：处理栈中含有多少元素的题型时，首先要了解到栈的长度、然后确定bottom的指向、最后由top的指向来确定栈中有多少元素，理清思路，才能计算。其次，处理出栈顺序题型时，一定要利用好出入栈的规律，一出一进，松弛有度！

4.2 队列的定义

只允许在一端插入，而在另一端进行删除的线性表。

4.2.1 队列的特点

只能在队尾插入，队头删除；

数据元素进出原则是：“先进先出（FIFO）”或者“后进后出（LILO）”；

队尾指针：rear，队头指针：front，队空时rear=front，队列元素跟随队尾指针和队头指针的变化而动态变化。

4.2.2 队列的进出描述

以下以长度为6的队列进行举例：

入队操作：

此时队空，rear和front指向1；

从队尾放入一个元素，rear+1；

……再放入4个元素，rear此时指向6，front指向1；

出队操作：

2的元素从队头跑出，front+1；

……全部依次从队头跑出来，rear和front此时共同指向6.

4.2.3循环队列

队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

以下的s为循环队列中元素个数

队尾rear>队头front -----s==rear-front

队尾rear<队头front----- s==容量+rear-front

队尾rear=队头front----- s=1（元素满）或s=0（元素空）

从以上三种情况可得知：循环队列元素个数由队头指针与队尾指针共同决定！

循环队列的进出描述：

假设3-6，分别有元素A，B，C，D，rear指向6，front指向3；

根据循环队列定义，最后绕到最前；

那么，从队尾放一个E，则这个F绕到1，rear指向1，front指向3；

再放F，F放到2，此时循环队列满了，rear=front共同指向3；

现在要退出元素，3的元素A退出，front指向4，rear指向3；

同理，B，C，D，E依次退出，front此时指向2，此时剩下F；

最后，退出2的元素F，front回到3，此时front=rear共同指向3，此时队列空。

5 线性链表

5.1 线性链表定义

线性表可以采用顺序存储和链式存储，采用顺序存储的叫做顺序表，采用链式存储结构的就是线性链表。

5.2线性链表的特点

1.各数据结点的存储空间可以不连续；

2.各数据元素的存储顺序与逻辑顺序绝大多数情况下不一致，逻辑顺序依靠指针域的指向；

3.线性表中，链式所占存储空间＞顺序所占存储空间，因为链式存储结构每一个结点至少有一个指针域的存在。

4.查找结点时，链式的速度＜顺序的速度；

5.数据结构运算时，链式的灵活度＞顺序的灵活度，因为链式存储结构插入、删除时只需要改变指针域的指向即可，无需移动线性链表中的元素。

5.3 双向链表和循环链表

双向链表和循环链表均属于线性结构！

6 树与二叉树

6.1 树

树是n（n>0）个元素的有限集合。

树是一个非线性结构，它有且仅有一个称为根的元素，其余元素是互不相交的子树。

如图所示，A是B的前件，E是B的后件：

A称为B的子结点，B是A的父结点；

A是整个树的根节点，没有后件的结点（K，L，F，M，H，N，J）是叶子结点；

一个结点所拥有后件的个数称为结点的度，比如B的度为2；

所有结点的度中最大的度称为树的度；

树的深度即树的层数，比如A处第一层，K处第四层，总共4层，深度为4；

子树是树的其中一个结点以及其下面的所有结点所构成的树。

6.2 二叉树

具有规范性和确定性的树，它是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两颗互不相交的左右二叉子树所组成。

二叉树具有以下两个特点：

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

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

6.2.1 二叉树的五种基本形态

~空二叉树

~只有一个结点的二叉树

~只有左子树的二叉树

~只有右子树的二叉树

~左右子树双全的二叉树

6.2.2 特殊二叉树

满二叉树：除最后一层外，每一层上的结点数均达到最大值。

完全二叉树：除最后一层外，每一层上的结点数达到最大值，在最后一层上只缺少右边的若干结点。

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

6.2.3 二叉树性质

非空二叉树只有一个根节点，每个结点最多有两颗子树，分别称为左子树和右子树。

1.在二叉树的第K层上，最多有2的（K-1）次方个结点；

2.深度为M的二叉树最多有2的M次方-1个结点；

3.度为0的结点（叶子结点）总比度为2的结点多一个；

4.有n个结点的二叉树深度至少为[log2为底n]+1，[log2为底n]是向下取整，[log2为底11]=3；

5.二叉树中的每个结点度的可能性为：0，1，2。

6.2.4 二叉树的遍历

指访问二叉树中所有的结点，且每个结点只能被访问一次。

前序遍历：（根左右）

    访问根节点；

    前序遍历左子树；

    前序遍历右子树。

    比如这里，先访问A，然后访问B，之后访问DG，之后又访问E，然后C，最后F。

中序遍历：（左根右）

    中序遍历左子树；

    访问根节点；

    中序遍历右子树。

    比如这里，先访问DG，然后访问B，之后访问E，又访问A，然后访问F，最后C。

后序遍历：（左右根）

    后序遍历左子树；

    后序遍历右子树；

    访问根节点。

    比如这里，先访问G，然后访问D，之后访问E，又访问B，然后访问FC，最后A。

7 查找技术

7.1 顺序查找

按照序列原有顺序对数组进行遍历比较的基本查找算法。

对于长度为n的线性表，平均情况下要进行n/2次比较，最坏情况下要进行n次比较。

顺序查找适用于无序表或链式线性表（不管是无序还是有序），也就是说顺序查找适用于所有的线性表。

7.2 二分查找

也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分（折半）查找适用于顺序存储的有序表，对长度为n的线性表，在最坏情况下进行log(2为底)n的对数次比较，这个查找方法可以参考高中数学里的二分法。

以上是一个由小到大的顺序表，现在查找46，中间的值是37<46，则切半（5-9）来比较，这时候与中间值46比较，就是它了，查找成功！

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

8 排序技术

8.1 排序概念以及类型

将无序序列中的元素进行变换而形成有序序列的过程。

8.2 快速排序

基本思想：（前寻大后寻小--“前凸后翘”）

1.在要排序的序列中找一个数作为基准数（通常为第一个数）；

2.通过交换将这个序列中所有比基准数大的数放在右边，比基准数小的数放在左边；

3.以基准数为分割线分为两个子表，对两个子表重复上述步骤。

例子：45 30 61 82 74 12 26 49

答案：这里以45为基准数，49比45大，不交换，26比45小，交换，此时

26 30 61 82 74 12 45 49

然后，在45前面元素中找个比它大的，比如61，交换，此时

26 30 45 82 74 12 61 49

现在，45前面都是比它小的，往后面找比它小的，比如12，此时

26 30 12 82 74 45 61 49

现在，45往前面找比它大的，比如82，此时

26 30 12 45 74 82 61 49

此时，45前面就全是比它小的，后面全是比它大的，第一趟快速排序就完成了，若想完整排序，对子表寻找基准数，同理操作！

注：前寻大后寻小指的是从最前端开始寻找比基准数大的，从最后端开始寻找比基准数小的，两边夹击到中间。

8.3 选择排序

基本思想：（从前往后，逐层寻小，然后交换）

1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；

2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；

3.重复第二步，直到所有元素均排序完毕。

注：以上3和2互换就是第一趟选择排序

总算学完这一章了，感觉收获颇丰，学习计算机二级用心去学感觉能给自己很多的提升，毕竟本人非计算机专业，最后总结一下本章吧。

以上数据结构还有一些运算，插入，删除等，忘记整理上去了