一.算法

算法的基本概念（笼统）：

解答某一类问题的任意一种特殊的方法。

　　一组又穷的规则，它规定了解决某一特定类型的问题的一系列运算。简而言之，就是解决问题的方法的步骤，是解题方案准确为完整的描述。

根据算法编写出相应的计算机语言的程序，让计算机去执行完成它，就可以提高工作效率。

　　　　　　　　　　　　　　算法是程序设计的核心

重要特性：

1. 确定性
2. 可行性
3. 输入
4. 输出
5. 有穷性

1.确定性

　　确定性指的是算法的每一个运算步骤必须有确切的定义，必须是清楚的，无二义性的（没有歧义的）。

2.可行性

可行性指的是算法中将要执行的运算都是基本运算，每一种运算至少在原理上能由人用纸和笔在有限时间内完成。

3.输入

一个算法有0个或者多个输入，这些输入是在算法开始之前给出的。

4.输出

　　一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量

5.

　　一个算法总是在执行了有穷步的运算之后，终止。在有限时间内完成。

 

算法的表示

设计出来的算法，我们可以用采用的自然语言、计算机程序设计语言、流程图、NS图、伪代码等来描述它，是就是算法的表示。

程序

用计算机语言将算法描述出来，称为程序。它可以存放在计算机储存器上，需要的时候可以去执行它。

伪代码语言

伪代码语言指的是一种用高级程序语言和自然语言组成的面型读者的语言，是为了方便阅读或者交流算法而使用的一种工具，在描述数据结构中的算法时经常采用伪代码语言或者流程图的形式。

流程图

流程图与实现算法的语言无关，直观、清晰地表示算法流程，易于掌握。

常用符号有：

起止框、判断框、处理框、输入输出框、流程线、注释框、连接点

可以直观的反映算法的逻辑执行顺序。

NS图

NS图又称为盒图，是一种不允许破坏结构化原则的图形算法描述工具，在NS图中去掉了流程图中容易隐去麻烦的流程线，全部算法写在一个框内，每一种基本结构作为一个框。

NS图的特点：

1. 功能域明确，可以从框图中直接反映出来
2. 不可能任意转移控制，符合结构化原则
3. 很容易确定局部和全程数据的作用域
4. 很容易表示嵌套关系方便管理模块的层次结构

评价一个算法优劣的主要标准：

　　　　　　　　　　　　　　　　算法的执行效率和储存需求

算法的时间复杂度：

　　是指执行这个算法所需要的计算工作量

算法的空间复杂度：

是指一个算法在计算机储存器上所占用的储存空间，包括储存算法本身所占用的存储空间，算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三部分

1. 1. 算法中输入输出数据所占用的存储空间，是由要解决的问题所决定的，它不随算法的改变所改变。
   2. 存储算法本身所占用的存储空间，与算法书写的长度有关，算法越长，所占用的存储空间越多。
   3. 算法在运行过程中临时占用的存储空间随算法的不同而改变，有的算法只需要占用少量的临时工作单元，与待解决问题的规模无关（此种算法称为原地工作），有的算法需要占用的临时工作单元，与待解决问题的规模有关，即随问题的规模的增大而增大。

评价一个算法的各种指标往往是相互矛盾、相互影响的：

当追求较短的运行时间，可能带来较多的存储空间和编写出较繁琐的算法；当追求算法的简单性时，可能需要占用较长的运行时间和较多的存储空间等。

所以，

在设计个算法时，要从多个方面综合考虑。还要考虑到算法的使用频率以及所使用机器的软硬件环境等诸多因素，这样才能设计出好的算法。

用计算机解决问题：

1. 1. 有解决问题的一套算法
   2. 描述出算法后，进行算法复杂性评估
   3. 选择合适的算法方案

两个待解决的任务：

1. 程序设计语言的选择
2. 算法设计时我们选择的是抽象数据模型，而程序实现部分，就需要完成：

• 抽象数据模型的具体表示
• 定义在该数据模型上的运算的具体实现，这属于数据结构及运算问题。

二.程序设计基础

　　　　　　　　　　　　一个好的算法最终要用计算程序设计语言来实现

“指令集”：操作码+操作数

程序设计语言分类：

• • 机器语言
  • 汇编语言
  • 高级语言

机器指令：‘0’ 和 ‘1’ 组成的二进制编码表示命令（直接执行，执行速度快，无需翻译）

机器语言：

由机器指令组成的语言称为及其语言。

　　　　    （难以记忆，难以书写，更加难懂）

汇编语言：

为了使语言更容易被程序员或者计算机使用者理解，人们用助记符代替二进制的操作码，用符号地址代替二进制的操作数，称之为汇编语言。

（安排存储、规定寄存器、运算器的次序，难度较高）

高级语言：

高级语言是一种接近于人们习惯用的语言的计算机程序设计语言，它允许用英文词汇书写解题的程序，程序中所使用的运算符号和运算式都和我们日常中所用的数学表达式差不多。

程序设计方法：

• 结构化程序设计
• 面向对象程序设计

结构化程序设计 -- 模块化：

1. 采用自顶向下，逐步求精的程序设计方法。
2. 使用三种基本控制结构构造程序，形成“单入口单出口”的程序。

　　　　　　（顺序结构　　选择结构　　循环结构）

面向对象程序设计：

1. 认为客观世界是由各种对象组成，任何事物都是对象，复杂的对象可以由比较简单的对象以某种方式组合而成。
2. 把所有对象划分为不同的对象类（简称为类。Class），每一个类都定义了一组数据和方法。
3. 按照子类（或派生类）与父类（或称基类）的关系，把若干个对象类组成一个层次结构的系统。
4. 对象彼此之间仅能通过传递信息相互联系。

对象：

是由描述该对象的属性的数据以及可以对这些数据施加的所有操作封装在一起的一个统一体。

具有以下特点：

1. 以数据为中心
2. 对象是主动的
3. 实现了数据的封装
4. 模块独立性好

具有以下优点：

1. 开发时间短
2. 效率高
3. 可靠性高
4. 所开发的程序可维护性强

数据结构基础

计算机应用领域：

• 控制
• 管理
• 数据处理

加工处理的对象： “数值” ==> “字符” “表格” “图像”

数据结构：

1. 数据的逻辑结构
2. 数据的物理结构（储存结构）
3. 对数据的操作（或算法）

相关术语：

1. 数据是对客观事物的符号表示、在计算机中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
2. 数据元素是数据的基本单位，在计算机程序中通常对一个整体进行考虑和处理。有时，一个数据元素可以由多个数据项组成。
3. 数据结构（也就是数据的逻辑结构）是指相互之间存在着一种或多种特定关系的集合。

常见结构：

• 集合结构
• 线性结构
• 树形结构
• 图形结构

　　或

• 线性结构
• 非线性结构

数据元素之间的关系表示：顺序映像 和 非顺序映像

顺序映像：

借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，也就是说，逻辑关系中相邻的两个元素，在存储器中也是相邻的。

非顺序映像：

结束指示元素存储地址的指针表示数据元素之间的逻辑关系，也就是说，存储器中相邻存放的两个数据元素，其逻辑关系未必是相邻的。

数据的运算：

对数据结构中的数据元素进行的操作处理。

         （查找 排序 插入 删除 修改）

前件结点指向后件结点，没有前间结点称为根节点，没有后间结点称为叶子结点

线性表的基本概念

若一个非空的数据结构满足一下条件：

1. 有且只有一个根结点；
2. 每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构，线性结构又称为线性表。

线性表的存储结构：

顺序存储结构

链式存储结构

具有顺序存储结构的线性表称为顺序表。

具有链式存储结构的线性表称为线性链表。

线性表的顺序存储结构

顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，顺序存储结构只能存储结点的值，不存储结点间的关系，结点间的关系由存储单元的邻接关系来体现。

顺序表的插入操作是指在顺序表的第 i -1 个数据元素和第 i 个数据元素之间插入一个新的数据元素。

顺序表中的删除第 i 个元素需将第 i + 1 至第 n 个元素依次向前移动一个位置。

线性表的链式存储结构

线性表的链式存储结构称为线性链表。

链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各节点的指针域指示。

链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：

　　　　　　　　　　　　　　　　   [数据域]　　　　  　　[指针域]

 栈是仅能在表尾进行插入或删除操作线性表

按照“先进后出”或“后进先出"的原则组织数据的线性表

物理存储结构可以采用顺序结构也可以采用链表结构。

顺序栈

按照其物理上相邻的存储单元，宇哥栈的所有元素储存在一片连续的存储空间，栈的数据结构有一个非常重要的标记：栈顶指针

　　栈的运算:

入栈（插入运算）

出栈（删除运算）

读栈顶元素

队列：

一种特殊的线性表。特点为所有的插入都在表的一端进行，所有的删除运算所在表的另一端进行。

按照“先进先出的”或“后进后出”的原则组织数据的线性表。

可以采用顺序存储结构，也可以采用链式存储结构

队列中的两个指针：

指向队首

指向队尾

用来确定队列的两端的位置

 顺序队列

按照逻辑顺序存储在物理上相邻的存储单元，一个队列中的所有元素存储在一片连续的存储空间里

入队运算：

在队伍指针向的位置插入一个新的元素，队尾指针后移一位。插入操作前要先判断队伍是否已满，如果已满，就不能进行入队运算。

出队运算：

删除对头元素，将队首指针向后移一位。删除操作之前，要先判断队伍是否为空，若为空，则不能进行删除运算。

循环队列：

把队列分配到的存储空间，在逻辑上看做一个环，当队尾指针指向存储空间的末端后，如果再发生插入操作，就把它重新至于队列存储空间的始端。

树

• 结点的度：一个结点许拥有的子树棵树称为结点的度
• 树的度：树值种所有结点度的最大值称为树的度。
• 终端结点(叶子结点)：树中度为9 的结点为叶子结点
• 非终端结点（分支结点）：度不为0的点为分支结点
• 结点的层次：树中根节点的层次为1，根节点子树的根为第二层，依次列推
• 树的深度：树中结点的最大层数为数的深度
• 有序树和无序树：如果树中每一棵子树从左向右排列拥有一定的顺序，不得交换，则称为有序树，否则称为无序树

二叉树

度为2的有序数.特点为树中每一个结点最对有两棵子树，并且子树有左右之分，次序不能颠倒

对于每一个节点，首先存它的值然后增加两个指针域，分别存放在其左子树和右子树根结点的地址，也就是分别指向其左子树和右子树

二叉树的性质：

1. 第 i 层最对多有2ⁱ + 1个结点
2. 深度为 2ⁿ +1 个结点（n >= 1）
   
3. 满二叉树：如果一个深度为 h 的二叉树拥有 2^h -1个结点，则为满二叉树
4. 二叉树上叶子结点数比度为 2 的结点多 1
5. 有 n 个结点的完全二叉树按从上到下，从左到右的编号，则编号为 i （1 <= i <= n ）的结点有：

• 若 i > 1，则当 i 为偶数时 i 的双亲结点编号为 i/2 
  •         当 i 为奇数时 i 的双亲结点编号为( i -1)/2
• 若  2*i <= n，则结点 i 的左孩子结点编号为 2 i
  •         否则无左孩子结点，即结点 i 为叶子结点
• 若 2*i +1 <= n，则结点 i 的右孩子结点的编号为 2i + 1
  •         否则无右孩子结点，即结点 i 为叶子结点

二叉树的遍历：

先序遍历：根节点 => 左结点 => 右节点

中序遍历：左节点 => 根节点 => 右节点

后序遍历：左节点 => 右节点 => 根节点