算法

顺序表性能分析

搜索：
平均比较次数ACN(Average Comparing Number)
ACN=\sum_{i=1}^n\frac in=\frac{n+1}2
二分搜索：
平均比较次数
ACN=\log_2(n)
插入和删除：
平均移动次数AMN(Average Moving Number)
插入ANM=\sum_{i=0}^n\frac{n-i}{n+1}=\frac{n}{2}
删除AMN=\sum_{i=1}^n\frac{n-i}{n}=\frac{n-1}{2}

栈的应用——利用栈将中缀表达式转化为后缀表达式

算数操作符的栈内栈外优先级
操作符ch
#
（
* / %
+ -
）
栈内优先级isp（in stack priority）
0
1
5
3
6
栈外优先级icp（in coming priority）
0
6
4
2
1
扫描中缀表达式，将之转化为后缀表达式的算法：
初始化后的栈中只有操作符#
重复执行如下操作直到只剩下栈底操作符#
1）若扫描到的是操作数则直接输出，否则转2）
2）若扫描到的是操作符，比较当前操作符的icp与栈顶操作符的isp优先级，若icp>isp当前操作符进栈；若icp[InvalidCharacterError: "ISP弹出栈顶元素到输出序列；若ICP==ISP弹出栈顶元素但是不输出到输出序列<" did not match the Name production]