MASM中标号和变量的命名规范
MASM中标号和变量的命名规范是相同的，如下：
1) 可以用字母、数字、下划线及符号@、$和?。
2) 第一个符号不能是数字。
3) 长度不能超过240个字符。
4) 不能使用指令名等关键字。
5) 在作用域内必须是唯一的。
全局变量
全局变量的作用域是整个程序
Win32汇编的全部变量定义在.data或.data?段内，这两个段都是可写的。可以同时定义变量的类型和长度。
全局变量的定义格式如下：
变量名 类型 初始值1,初始值2,……
变量名 类型 重复数量 dup （初始值1,初始值2,……）
MASM支持的变量类型如下表：
名称
表示方式
缩写
长度(字节)
字节
Byte
db
1
字
word
dw
2
双字(double word)
dword
dd
4
三字(far word)
fword
df
6
四字(quad word)
qword
dq
8
10字节BCD码(ten byte)
tbyte
dt
10
有符号字节(sign byte)
sbyte
1
有符号字(sign word)
sword
2
有符号双字(sign dword)
sdword
4
单精度浮点数
Real4
4
双精度浮点数
Real8
8
10字节浮点数
Real10
10
注意：只有定义全局变量的时候，类型才可以用缩写。
在byte类型变量的定义中，可以用引号定义字符串和数值定义的方法混用。
例如：szText db ‘Hello,world!’,0dh,0ah,’Hello again’,0dh,0ah,0
全局变量的初始化：
全局变量在定义中既可以指定初值，也可以只用问号预留空间。
全局变量定义在.data?段中时，只能用问号预留空间，因为.data?段不能指定初始值。
定义时用问号指定的全局变量的初始值是0。
局部变量
局部变量的好处是使程序的模块结构更加分明。
局部变量的缺点是因为空间是临时分配的，所以无法定义含有初始化值的变量，对局部变量的初始化一般在子程序中由指令完成。
局部变量的作用域是单个子程序。
局部变量定义在堆栈中。
局部变量的定义格式如下：
local 变量名1[[重复数量]][:类型],变量名2[[重复数量]][:类型] ……
local是MASM提供的伪指令，用于支持局部变量的定义。有了local伪指令降低不少难度。
定义局部变量需注意以下几点：
a) local伪指令必须紧接在子程序定义的伪指令proc后、其它指令开始之前，因为局部变量的数目必须在子程序开始的时候就确定下来；
b) 定义局部变量时数据类型不能用缩写。如果要定义数据结构，可以用数据结构的名称当作类型；
c) Win32汇编中，参数的默认类型是dword，如果定义dword类型的局部变量，类型可以省略；
d) 当定义数组类型的局部变量时，重复数量可以用“[]”括起来，不能使用定义全局变量的dup伪指令。
e) 局部变量不能和已定义的全局变量同名。
f) 局部变量的作用域是当前的子程序，所以在不同的子程序中可以有同名的局部变量。
局部变量的初始化：
局部变量无法在定义的时候指定初始化值，因为local伪指令只是为局部变量留出空间。
局部变量的初始值是随机的，所以，对局部变量的值一定要初始化。
一般在子程序中使用指令来初始化局部变量。
使用局部变量时的注意点：
a) ebp寄存器是关键，它起到保存原始esp寄存器值的作用；
b) 另外，ebp寄存器随时用做存取局部变量的指针基址，所以绝不能把ebp寄存器用于别的用途；
c) ebp寄存器的值绝对不能被改变，把ebp寄存器的值改掉，程序就玩完；
数据结构
数据结构相当于一种自定义的数据类型，类似C语言中的struct定义。
汇编中，数据结构的定义方法如下：
结构名 struct
字段1 类型 ？
字段2 类型 ？
……
结构名 ends
定义数据结构并不会在某个段中产生数据，只有使用数据结构在数据段中定义数据后，才会产生数据。
使用数据结构在数据段中定义数据的两种方法如下：
第一种定义方法是未初始化的定义方法：
.data?
stWndClass WNDCLASS <>
……
第二种定义方法是定义的同时指定结构中个字段的初始值：
.data
stWndClass WNDCLASS <1,1,1,1,1,1,1,1,1,1>
……
汇编中，对数据结构变量的几种引用方法如下：
a) 最直接的方法：
mov eax,stWndClass.lpfnWndProc
如果stWndClass结构变量在内存中的起始地址是403000h，那么这句指令会被编译成mov eax,[403004h]
b) 在实际使用中，常有使用指针存取数据结构变量的情况：
[...]
单源最短路径
Dijkstra 算法复杂度 O(V^2 + E)
有向加权图， 所有边非负
Bellman-Ford 算法复杂度O(VE)
有向加权图, 权可为负, 可存在负回路
代码 for (int i = 0; i < N - 1; ++i)
for (int j = 0; j < SIZE; ++j)
d[paths[j][1]] = min(d[paths[j][0]] + paths[j][2],d[paths[j][1]]);
bool avbl = false;
for (int j = 0; j < SIZE; ++j)
if (d[paths[j][1]] > d[paths[j][0]] + paths[j][2])
{
avbl = true;
break;
};
每对节点的最短路径
Floyd-Warshall算法复杂度 O(V^3)
有向加权图, 权可为负, 但不存在负回路
代码 for (int k = 0; k < currencies; ++k)
for (int i = 0; i < currencies; ++i)
for (int j = 0; j < currencies; ++j)
d[i][j] = max(d[i][k] * d[k][j],d[i][j]);
最小代价生成树
Prim 算法复杂度 O(V^2 + E) 实现与Dijkstra 类似
代码 //init for prim
l[0] = 0;
memset(used, 0, sizeof(used));
used[0] = true;
for (int i = 0; i < lines; ++i) l[i] = d[0][i];
for (int i = 1; i < lines; ++i)
{
// select available V with min len
int pos = 0;
int len = 8;
for (int j = 0; j < lines; ++j)
if (used[j] == false && len > l[j])
{
len = l[j];
pos = j;
};
//update l[]
used[pos] = true;
for (int j = 0; j < lines; ++j)
if (used[j] == false && l[j] > d[pos][j]) l[j] = d[pos][j];
}
贪心算法
1．贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能作出选择。而在贪心算法中，仅在当前状态下作出最好选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。贪心算法所作的贪心选择可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。通常可以用我们在证明活动安排问题的贪心选择性质时所采用的方法来证明。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。
2．最优子结构性质
当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。问题所具有的这个性质是该问题可用动态规划算法或贪心算法求解的一个关键特征。在活动安排问题中，其最优子结构性质表现为：若a是对于正的活动安排问题包含活动1的一个最优解,则相容活动集合a’=a—{1}是对于e’={i∈e:si≥f1}的活动安排问题的一个最优解。
动态规划
动态规划的动机是消除递归过程中产生的大量重叠子问题, 两种方法 : 记忆化搜索 和 自底向上递推.
无后效性,决策只取决于当前状态的特征因素, 而和到达此状态的方式无关.
最优子结构, 在问题转化为子问题时, 原问题最优当且仅当子问题最优.
决策, 状态转移方程就是决策, 对于多阶段的决策问题, 如果具备最优子结构和无后效性, 就可以用动态规划来解决它
多阶段策略问题利用递归的思想, 把规模为n的问题转化为规模为n-1的问题, 直到转化为可以直接求解的原子问题. 一般情况下, 这样的递归方法的时间复杂度是指数级别的, 但是如果所有不同的子问题的数目是多项式级别的, 那么只需要多项式时间就可以解决这个问题, 这就是动态规划的本质. 动态规划算法有三个要素:
1) 所有不同的子问题所组成的表(他包含的问题数目成为问题的大小).
2)问题解决得依赖关系可以看成是一个图.
3) 填充子问题的顺序(实际上是2所得到的图的拓扑排序).
如果子问题数目为O(n^t), 且每个子问题需要依赖O(n^e)个其他子问题, 则称这个问题为tD/eD的.
方程一(1D/1D):最长上升子序列
定义一个实函数w(i, j)(1<=i<j<=n)已知D[0], 状态转移方程为
E[j] = min{D[i] + w(i, j)}, 1<=i<j<=n
其中D[i]可以根据E[i]在常数时间里计算出来.
方程二(2D/0D):最长公共子序列
已知D[i,0]和D[0,j](0<=i, j<=n), 状态转移方程为
E[i, j]=min{D[i-1,j]+xi, D[i,j-1]+yj, D[i-1][j-1]+zii}
其中xi, yj, zij都可以在常数时间里算出来
方程三(2D/1D)
定义实函数w(i, j)(1<=i<j<=n), 已知d[i, i] = 0 (1<=i<=n), 状态转移方程为
C[i, j] = w(i, j) + [...]
1. 队列
广度优先搜索
2. 堆栈
深度优先搜索
3. 二叉树，二叉搜索树 & 平衡二叉搜索树
Binary Search
4. 哈希表
POJ 3349, Snowflake Snow Snowflakes
POJ 3274, Gold Balanced Lineup
POJ 1840, Eqs
POJ 2002, Squares
POJ 2503, Babelfish
5. 堆
POJ 3253, Fence Repair
6. Tries
POJ 2513, Colored Sticks
7. 并查集
POJ 2524, Ubiquitous Religions
POJ 2513, Colored Sticks
8. 线段树
栈是一种特殊的线性表，所以在前面讨论的线性表的各种存储结构都可以作为栈的存储结构，因此，栈也有两种存储表示方法：顺序存储和链式存储。
栈的顺序结构简称顺序栈，是利用一组地址连续的存储单元一次存放紫栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。用一维数组表示栈的顺序存储结构，一般以top=0表示空栈，由于C语言中数组的小标约定从0开始，因此用C做描述语言时，这样设定会带来很大不便，因此用top=-1表示栈空，顺序存储结构可表示为：
typedey struct
{
int stacksize;
datatype *bottom;
datatype *top;
}SqlStack; //顺序栈类型定义
Sqlstack *S//S是顺序栈类型指针
其中stacksize 是指栈的当前可使用的最大容量，top为栈顶指针，其初值指向栈顶，即top=-1可作为栈空的标记，每当插入新的站定元素时，指针top增加1，删除栈顶元素时，top减1.
约定top指向真正的栈顶位置上面的一个空单元，即新数据将要插入的位置。
置空栈的操作（栈的初始化）
Initstack(seqstack *s)
{
s->top=0;
s->base=0;
}
判栈空操作
int Empty(seqstack *s)
{
if(s->top==s->base)
return true;
else
return false;
}
进栈操作
datatype Push(seqstack *s,datatype x)//将元素x插入顺序栈s的顶部
{
if(s->top==maxsize)
{
printf(“overflow”);
return NULL;
}
else
{
s->data[s->top]=x;
s->top++;
}
return true;
}
出栈操作
datatype Pop(seqstack *s,datatype e)//若栈非空，删除栈顶元素，用e返回其值
{
if(Empty(s))
{
printf(“underflow”);return NULL;
}
else
{
s->top–;
e=s->data[s->top];
return (e);
}
}
取栈顶操作
datatype GetTop(seqstack *s)
{
if(Empty(s))
{
printf(“stack is empty”);//空栈
return NULL;
}
else
return (s->data[s->(top-1)]);
}
在实际工作中可能会用到多个栈，在使用一个数组存储栈时。数组中一般都会有剩余 的空间，如果给每个栈都定义一个数组，则有时会出现一个栈上溢，而另一个栈剩余很多空间的情况。为了合理地使用这些存储单元，可以采用将多个栈存储在同一数组中的方法，即多栈共享空间。
假设两个栈共享一个一维数组s【0，。。。。maxsize-1】，根据栈操作的特点，可使第一个栈使用数组空间的前面空间，并使栈底在前，而使用第二个栈使用数组空间的后面部分，并使栈底在后。
这样处理可以使两个栈最大限度地使用数组空间，下面给出这种空间存储结构的定义：
typedef datatype [...]
一、算法效率的度量
算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：
1、事后统计的方法。
缺点：不利于较大范围内的算法比较。（异地，异时，异境）
2、事前分析估算的方法。
程序在计算机上运行所需时间的影响因素
算法本身选用的策略
问题的规模
规模越大，消耗时间越多
书写程序的语言
语言越高级，消耗时间越多
编译产生的机器代码质量
机器执行指令的速度
综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 （原操作在所有该问题的算法中都相同）
T(n)=O(f(n))
上示表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。
求4*4矩阵元素和，T(4)=O(f(4))
f=n*n;
sum(int num[4][4])
{ int i,j,r=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
r+=num[i][j]; /*原操作*/
return r;
}
最好情况：
T（4）=O（0）
最坏情况：
T（4）=O（n*n）
ispass(int num[4][4])
{ int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)
return 0;
return 1;
}
原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。
语句
频度
时间复杂度
{++x;s=0;}
1
O(1)
for(i=1;i<=n;++i)
{++x;s+=x;}
n
O(n)
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
{++x;s+=x;}
n*n
O(n*n)
O(log n)
基本操作的执行次数不确定时的时间复杂度
平均时间复杂度
依基本操作执行次数概率计算平均
最坏情况下时间复杂度
在最坏情况下基本操作执行次数
二、算法的存储空间需求
类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。
记作：
S(n)=O(f(n))
若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。
三、总结
渐近时间复杂度
空间复杂度