一、栈 后进先出 是一种限制访问端口的线性表 主要操作 进栈（push） 出栈（pop） 应用 表达式求值（中缀表达式、后缀表达式） 消除递归 深度优先搜索（树、图） 二、栈的抽象数据类型 template <class T> class Stack { public: // 栈的运算集 void clear(); // 变为空栈 bool push(const T item); // item入栈，成功返回真，否则假 bool pop(T& item); // 返回栈顶内容并弹出，成功返回真，否则假 bool top(T& item); // 返回栈顶但不弹出，成功返回真，否则假 bool isEmpty(); // 若栈已空返回真 bool isFull(); // 若栈已满返回真 }; 三、思考题 若入栈顺序为 1,2,3,4 的话，则出栈的顺序可以有哪些?...
一、暴力算法 $\mathcal{O}(n^3)$ 遍历数组的所有子数组集合，并对其求和，筛选出和的最大值 int maxSumOfSub1(int* array, int length){ int maxSum = 0; int startIndex = 0, endIndex = 0; for(int i = 0; i < length; i++){ for(int j = i; j < length; j++){ int sum = 0; for(int k = i; k <= j; k++) sum += array[k]; if(maxSum < sum){ maxSum = sum; startIndex = i; endIndex = j; } } } cout << "Begin:" << startIndex << " End:" << endIndex << " Num:" << maxSum << endl; return maxSum; } 二、前缀和 $\mathcal{O}(n^2)$ 先把数组的前 i 项和求出来并将其保存到数组中，然后计算所有子数组集合的和，筛选其中最大的...
线性结构 二元组 B = (K, R) , K = {a0, a1, …, an-1 }, R = {r}，其中 r 为前驱后继关系，具有反对称性和传递性 唯一的开始结点（表头）：没有前驱，只有一个唯一的后继 唯一的终止结点（表尾）：没有后继，只有一个唯一的前驱 内部结点：一个唯一的前驱和一个唯一的后继 线性表 线性表简称表，是零个或多个元素的有穷序列 表目：线性表中的元素 文件：含有大量记录的线性表又称为文件 索引（下标） 表的长度 空表：长度为零的线性表(n=0) 线性表分类 按访问方式划分： 直接访问型 顺序访问型 目录索引型 按存储方式： 顺序表（数组） 链表 按操作： 线性表：不限操作 栈：在同一端操作，在深度优先搜索、递归等算法中有很好的应用 队列：在两端操作，在宽度优先搜索、层次化处理中有很好的应用 顺序表 顺序表俗称向量，是用数组实现的（固定长度的一维数组） 按索引值从小到大存放在一片相邻的连续区域 结构紧凑，存储密度为1（存储密度 = 数据本身所占存储 / 整个数据结构所占存储） 物理存储关系就能表示逻辑关联关系 链表 链表需要指针表示逻辑关联关系，存储效率不如顺序表 有头链表和无头链表 在一些边界处理的时候，要注意头结点（head）和尾结点（tail）的特殊处理 讨论 线性表的分类方法有哪些？各种线性表名称中，哪些跟存储结构相关？哪些跟运算相关？...
算法的时间和空间性能非常重要 一、算法的渐近分析 当 n 增大到一定值后，其他的常数项和低幂次项都可以忽略，只需确定是在什么量级（线性、n 方、指数级等） 1. 大 $\mathcal{O}$ 表式法 函数增长率上限 2. 大 $\Omega$ 表式法 函数增值率的下限 3. 大 $\Theta$ 表示法 当上、下限相同时则可用 $\Theta$ 表示法 二、增长率曲线 三、数据结构和算法的选择 仔细分析所要解决的问题 特别是求解问题所涉及的数据类型和数据间逻辑关系（问题抽象、数据抽象） 数据结构的初步设计往往先于算法设计 注意数据结构的可扩展性 考虑当输入数据的规模发生改变时，数据结构是否能够适应求解问题的演变和扩展 三、思考题 数据结构的三个要素任何一个发生改变，都是不同的数据结构，请举例讨论 双向链表和二叉树的存储结构其实是一样的，他们的不同在于逻辑结构。 数组和向量都是线性表，其存储形式不同，成为不同的数据结构。 算法设计目标是什么？ 时间和空间的权衡 易读 易编码 易调试 易维护 易扩展 算法选择的过程？ 要求在时间复杂度 $\mathcal{O}(n)$、空间复杂度 $\mathcal{O}(1)$，使数组元素循环向右移动 K 位
一、问题——算法——程序 问题：一个函数，从输入到输出在一种映射 算法：对特定问题求解过程的描述，是指令的有限序列 程序：算法在计算机程序设计语言中的具体实现 二、算法的特性 通用性：参数化的，能对一类问题进行参数化输入并问题求解 有效性：有限条有效指令组成的指令序列，保证计算结果的正确性 确定性：算法的下一步执行步骤必须明确 有穷性：执行必须在有限步内结束，不能有死循环 三、基本算法分类 穷举法： 遍历每一个元素，比较低效，但是是一种万能的算法；对于一个问题，如果一时想不出好的算法的话，可对小规模数据采用穷举法剖析问题的特性和数据的特性，进而寻求更高效的算法 回溯、搜索： 能进则进，不能进则换，不能换则退，如树和图的遍历 递归分治： 二分查找，以及快速排序、归并排序，都是经典的分治算法思想 贪心法： 其数据具有贪心性质，每次求解的时候都采用当前的最佳解，最终得到最优解，如 Huffman 编码树、最短路径 Dijkstra 算法、最小生成树 Prim 算法 动态规划： 得到小规模问题的最优解，然后在更大规模的时候去组合这些最优解，最后得到全局的最优解，如图的两两结点之间最短路 Floyd 算法。要求具有最优子结构性质以及无后效性，动态规划的子结构有重叠，而递归分治子结构不重叠。 四、“监视哨”顺序检索 设置“监视哨”后，在查找过程中不用判断 i 是否越界，少一次判断，算法的运行效率会更高