计算机公共基础知识
«Index
第一章 | 数据结构与算法
1.1 算法
1.1.1 算法：指解题方案的准确而完整的描述，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。
算法不等于程序，也不等于计算方法，但程序可以算法的一种描述。
1.1.2 基本特征
- 可行性 ：算法中的每一个步骤必须能够实现；算法执行的结果要能够达到预期的目的；
- 确定性 ：算法中的每一个步骤都必须有明确定义的，不允许有多义性；
- 有穷性 ：算法必须能在有效的时间内做完，即算法必须能在执行有限个步骤之后终止，包含合理的执行时间的含义；
- 拥有足够的情报。
1.1.3 算法设计基本方法
- 列举法 ：根据提出的问题，列举所有可能的情况，检验需要或不需要；
- 归纳法 ：通过列举少量的特殊情况，找出一般的关系、结论；
- 递推 ：从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果；
本质上属于归纳 注意数值计算的稳定性问题
- 递归 ：一般总是将问题逐层分解，最后归纳为一些最简单的问题；
递归的基础是归纳
- 直接递归：一个算法P显式地调用自己
- 间接递归：算法P调用另一个算法Q，而算法Q又调用算法P
- 减半递推技术 ：“减半”指将问题的规模减半，而问题的性质不变；“递推”指重复“减半”的过程。
实际问题的复杂程度往往与问题的规模有着密切关系。因此利用分治法解决这类实际问题是有效的。
1.1.4 算法复杂度
- 时间复杂度
- 空间复杂度
1.1.4.1 时间复杂度
指执行算法所需要的计算工作量。
算法在执行过程中所需基本运算的执行次数可以度量算法的工作量
算法所执行的基本运算次数与问题的规模有关
在同一问题规模下，如果算法执行所需的基本次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：
- 平均性态 ：指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量；
- 最坏情况复杂度 ：指在规模为n时，算法所执行的基本运算的最大次数。
1.1.4.2 空间复杂度
一般是指执行算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
1.2 数据结构
指反映数据元素之间关系的数据元素的集合，即带有结构的数据元素的集合。
数据结构的主要问题：
- 数据的逻辑结构；
- 数据的存储结构；
- 对各种数据结构进行的运算。
提高数据处理的效率：
- 提高数据处理的效率；
- 尽量节省数据处理所占用的计算机存储空间。
一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。
1.2.1 数据的逻辑结构
一个数据结构应包含以下两方面的信息：
- 表示数据元素的信息；
- 表示各数据元素之间的前后件关系。
1.2.2 数据的存储结构
指数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。
常用的存储结构有顺序、链接、索引等。
1.2.3 线性结构与非线性结构
一般将数据结构分为两大类型：
- 线性结构；
- 非线性结构。
如果一个非空的数据结构满足下列两个条件：
- 有且只有一个根结点；
- 每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构。
线性结构又称线性表
1.3 线性表及其顺序存储结构
1.3.1 线性表的基本概念
线性表是（Linear List）是最简单、最常用的一种数据结构、是一种线性结构。
矩阵是一个比较复杂的线性表
非空线性表的结构特征：
- 有且只有一个根结点a1,它无前件；
- 有且只有一个终端结点an,它无后件；
- 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。
1.3.2 线性表的顺序存储结构
在计算机存放线性表，一种最简单的方法是顺序存储（顺序分配）。
线性表的顺序存储结构的基本特点：
- 线性表中所有元素所占的存储空间是连续的；
- 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中，可以对线性表进行各种处理。主要的运算有：
- 线性表的插入
- 线性表的删除
- 线性表的查找
- 线性表的排序
- 线性表的分解
- 线性表的合并
- 线性表的复制
- 线性表的逆转
1.4 栈与队列
1.4.1 栈
- 栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表
- 允许插入与删除的一端称为栈顶
- 不允许插入与删除的另一端称为栈底
栈的原则：先进后出（FILO），后进先出（LIFO）
栈的三种基本运算：入栈、退栈与读栈顶元素
1）入栈运算
入栈运算是指在栈顶位置插入一个新元素。操作过程：
- 首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。
- 然后将栈顶指针进一（即top加1）。
- 最后将新元素x插入栈顶指针指向的位置。
2）退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程：
- 首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。
- 然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
- 最后将栈顶元素指针退一（即top减1）。
3）读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程：
- 首先判断栈顶指针是否为0.如果是，则说明栈空，读不到栈顶元素，算法结束。
- 然后将栈顶元素赋给指定的变量y。
注意：该运算不删除栈顶元素，栈顶指针不会改变。
1.4.2 队列
- 队列（Queue）是指允许在一端进行插入、而在另一端进行删除的线性表
- 允许插入的一端称为队尾
- 允许删除的一端称为排头（队头）
队列的原则：先进先出（FIFO）、后进后出（LILO）
队列的两种基本运算：
- 入队运算：往队尾插入一个元素
- 退队运算：从排头删除一个元素
入队运算只涉及队尾指针rear的变化 退队运算只涉及排头指针front的变化
1.4.2.1 循环队列及其运算
队列的顺序结构一般采用循环队列的形式