线性表
线性表是一种常用的数据结构，其中的每一个元素（结点）都有唯一的前驱和唯一的后续。当然，第一个元素只有后续，最后一个元素只有前驱。
线性表一般分为“「顺序表」”和“「链表」”。
- 顺序表可以简单理解成前面学过的数组。它是一种逻辑上和物理上都是有序的、连续存储的静态结构。
- 链表是一种物理上不连续存储的动态结构，数据之间的逻辑顺序是通过链表中的指针链接关系实现的。
- 顺序表与链表比较
- 优：进行数据的删除和插入时只需要修改指针即可, 非常方便。当存储规模较大时, 动态分配不连续的内存空间,不会造成浪费。
- 缺：查找某个结点需要从头指针起顺着链扫描才能取到。
- 优：查找结点方便。
- 缺：进行插入和删除时,需要花费大量的时间来移动数据，存储规模过大时难于预先估计空间,过大造成空间浪费,过小又会使数据溢出。
- 顺序表(数组):
- 链表:
栈
「栈(stack)是限定仅在表的一端进行插入和删除操作的线性表。」
其插入和删除操作都限制在表的一端进行，这一端被称为“「栈顶 (top)」”，相对的另一端称为“「栈底 (bottom)」”。
插入操作称为 「进栈 (PUSH)」 或者 “压栈”
删除操作称为 「出栈 (POP)」。
栈的特点是 「先进后出 FILO First In Last Out」
NOIP 2017 第 12 题
表达式 a * (b + c) * d 的后缀形式是（ ）。
A. a b c d * + *
B. a b c + * d *
C. a * b c + * d
D. b + c * a * d正确答案：B
后缀构造方式:
- 从左到右依次读取表达式
- 数字时，加入后缀表达式；
- 运算符：
- 若为 ‘(‘，入栈；
- 若为 ‘)’，则依次把栈中的运算符加入后缀表达式中，直到出现'(‘，从栈中删除'(‘ ；
- 若为 除括号外的其他运算符， 当其优先级高于除'(‘以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级 「高和相等」 的运算符，直到一个比它优先级低的或者遇到了一个左括号为止，然后将其自身压入栈中（先出后入）。
- 当扫描的中缀表达式结束时，栈中的的所有运算符依次出栈；
做题示例:
- 建立空栈存放操作符
- 从左到右依次读取表达式, 非操作符直接输出, 输出a
- 号 栈顶入栈
- 直接入栈
- 直接输出
- 号 入栈
- 直接输出
- 括号, 完成配对, 弹出 , 弹出 , 输出
- 号 和栈顶优先级相同, 故栈顶的 出栈
- 号入栈
- 直接输出
- 表达式读取完毕, 栈依次弹出
最后输出结果: a b c + * d *
队列
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
- 允许删除的一端称为队头（head）。
- 允许插入的一端称为队尾（tail）。
- 当队列中没有元素时称为空队列。
- 队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表- 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许”加塞”），每次离开的成员总是队列头上的（不允许中途离队），即当前” 最老的”成员离队。
字符串
- 字符串是一串字符
- 子串：字符串中任意个连续的字符组成的子序列。
字符串子串个数的计算公式：（就是字符串长度等差数列）
- 包含1个字符的子串共n个
- 包含2个字符的子串共n-1个
- 包含3个字符的子串共n-2个
- 包含4个字符的子串共n-3个
- ……
- 包含n个字符的子串共1个
- 空串1个
- 综上所述：子串个数共：1+2+3+。。。+n+1（空串）=n(n+1)/2+1
例: 串中字符出现重复：字符串www.qq.com所有非空子串（两个子串如果内容相同则只算一个）个数是（）
答案：50
解析：包含重复子串共：（），减去重复：2个w，1个ww，1个q，1个.，所以共55-5=50个