栈的特点是后进先出，所以常用来处理具有递归结构的数据 深度优先搜索 表达式求值 子程序 / 函数调用的管理 消除递归 表达式的递归定义 基本符号集：${0，1，…，9，+，-，*，/，（，）}$ 语法成分集：{<表达式> , <项> , <因子> , <常数>, <数字> } 中缀表达式：$23\ +\ (34\ *\ 45)\ /\ (5\ +\ 6\ +\ 7)$ 后缀表达式：$23\ 34\ 45\ *\ 5\ 6\ +\ 7\ +\ /\ +$ 中缀表达式 运算符在中间 需要括号改变优先级 例如：$4\ *\ x\ *\ (2\ *\ x\ +\ a)\ –\ c$ 后缀表达式...
栈的物理实现有 顺序栈 和 链式栈 一、顺序栈（Array-based Stack） 使用向量实现，本质上是顺序表的简化版 栈有固定大小 关键是确定哪一端作为栈顶 注意上溢、下溢问题 类定义： template <class T> class arrStack : public Stack <T> { private: // 栈的顺序存储 int mSize; // 栈中最多可存放的元素个数 int top; // 栈顶位置，应小于mSize T *st; // 存放栈元素的数组 public: // 栈的运算的顺序实现 arrStack(int size) { // 创建一个给定长度的顺序栈实例 mSize = size; top = -1; st = new T[mSize]; } arrStack() { // 创建一个顺序栈的实例 top = -1; } ~arrStack() { delete [] st; } void clear() { top = -1; } // 清空栈 }; bool arrStack<T>::push(const T item) { // 入栈 if (top == mSize-1) { // 栈已满 cout << "栈满溢出" << endl; return false; } else { // 新元素入栈并修改栈顶指针 st[++top] = item; return true; } } bool arrStack<T>::pop(T& item) { // 出栈 if (top == -1) { // 栈为空 cout << "栈为空，不能执行出栈操作"<< endl; return false; } else { item = st[top--]; // 返回栈顶，并缩减1 return true; } } 二、链式栈（Linked Stack） 用单链表方式存储，其中指针的方向是从栈顶向下链接 理论上没有大小限制 类定义：...
一、栈 后进先出 是一种限制访问端口的线性表 主要操作 进栈（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）的特殊处理 讨论 线性表的分类方法有哪些？各种线性表名称中，哪些跟存储结构相关？哪些跟运算相关？...