第 7章 常用数据结构
7.1 数组与内存块
7.2 字符串处理
7.3 结构
7.4 链表
7.5 函数指针
7.6 程序执行环境
7.1 数组与内存块
数组是内存中的一块连续数据单元
数组中的元素大小固定，类型相同
一组连续的数据单元称为内存块
数组，字符串和结构都可以看成是一个内存块
7.1.1 块操作块操作指令一共有 5种块操作指令的用法
1,操作数的大小指令后面的 B,W,D分别代表字节,字,双字
2,源操作数和目的操作数源操作数是 DS:[ESI]所指向的内存单元；
目标操作数是 ES:[EDI]所指向的内存单元
3,方向标志和地址指针的修改块操作指令会自动地修改 ESI和 EDI
操作数的大小决定增加或减小的单位
4．重复前缀
可以和块操作指令联合使用
有 3种形式,REP,REPZ,REPNZ
放在块操作指令的前面
5种块操作指令的功能
（ 1） MOVSB/W/D将 ESI所指向的字节 /字 /双字复制到 EDI
所指向的字节 /字 /双字 。
（ 2） CMPSB/W/D将 ESI和 EDI所指向的字节 /字 /双字进行比较 。
（ 3 ） SCASB/W/D 将 EDI 所 指 向 的 字 节 / 字 / 双 字 和
AL/AX/EAX进行比较 。
（ 4） STOSB/W/D将 AL/AX/EAX保存到 EDI所指向的字节 /字
/双字中 。
（ 5） LODSB/W/D将 ESI所指向的字节 /字 /双字读入到
AL/AX/EAX中 。
3种重复前缀的用法
（ 1） 前缀为 REP时,重复次数固定为 ECX。
REP和 MOVS,STOS,LODS联合使用 。
（ 2） 前缀为 REPZ时,重复次数最大为 ECX。
REPZ和 CMPS,SCAS联合使用 。
如果在比较或扫描时,ZF=0,不再重复 。
（ 3） 前缀为 REPNZ时,重复次数最大为 ECX。
REPNZ和 CMPS,SCAS联合使用 。
如果在比较或扫描时,ZF=1,不再重复 。
7.1.2 块传送指令
MOVSB/W/D将操作数从一个内存单元传送到另一个内存单元，它和 REP前缀同时使用，将一个内存块（源数据块）复制到另一个内存块（目标数据块）。
1．数组的复制下面的程序将数组 Array1复制给 Array2
Array1 DWORD 1,10,100,1000,10000
Array2 DWORD 5 DUP (0)
LEA ESI,Array1
LEA EDI,Array2
CLD
MOV ECX,5
REP MOVSD
每次,MOVSD传送一个双字,ESI,EDI自动加 4，
指向下一个双字,ECX自动减 1。
2．从字符串中删除一个字符一行字符存储在缓冲区 InBuffer中
InBuffer BYTE 'Hellox World!',0
把 X删掉的指令代码为
LEA ESI,InBuffer+6 ; ESI指向字符 ' '
LEA EDI,InBuffer+5 ; EDI指向字符 'x'
CLD ; 地址由低至高
MOV ECX,8 ; 传送 8次
REP MOVSB ; 以字节为单位传送
3．向字符串中插入一个字符
InBuffer BYTE 'Hello Wrld!',0
想要将 O插入进去的代码为：
InBuffer BYTE 'Hello Wrld!',0,?
LEA ESI,InBuffer+11 ; ESI指向字符 00H
LEA EDI,InBuffer+12 ; EDI指向?所在的位置
STD ; 地址由高至低
MOV ECX,5 ; 传送 5次
REP MOVSB ; 以字节为单位传送
CLD ; 恢复为 "地址由低至高 "
MOV InBuffer+7,'o' ; 插入字符 'o'
4．块传送的 3种情况根据源数据块和目标数据块是否重叠，以及数据块的地址前后顺序，将数据块的传送分为：
（ 1）源数据块和目标数据块不重叠。 DF=0或 DF=1均可。
（ 2）源数据块和目标数据块重叠，目标数据块地址较小。
只能设置 DF=0,ESI和 EDI分别执行源数据块和目标数据块的第 1个单元的地址。
（ 3）源数据块和目标数据块重叠，目标数据块地址较大。
只能设置 DF=1,ESI和 EDI指向源数据块和目标数据块的最后一个传送单位。
7.1.3 块存储指令块存储指令包括,STOSB,STOSW,STOSD
将 AL,AX或 EAX的内容存入由 EDI指向的存储单元，然后 EDI自动增减 1,2或 4。
可以和 REP前缀一起使用，连续执行 ECX次块存储指令。
LODS指令一般不带 REP前缀 。
7.1.4 块装入指令块装入指令包括 LODSB,LODSW,LODSD
将由 ESI指向的存储单元读入累加器 AL,AX
或 EAX中,然后 ESI自动增减 1,2或 4。
可以和 REP前缀一起使用,连续执行 ECX次读入操作,但一般不带 REP前缀 。
7.1.5 块比较指令块比较指令包括 CMPSB,CMPSW,CMPSD
较由 EDI指向的目标操作数和由 ESI指向的源操作数，然后 EDI和 ESI自动增减 1,2或 4。
CMPS指令可以和 REPZ或 REPNZ前缀一起使用。
CMPS指令一般与 REPZ前缀配合使用。
比较完成后，根据 ZF标志位来决定是否两个数据块是否相等。
7.1.6 块扫描指令块扫描指令包括 SCASB,SCASW,SCASD
在 EDI指向的目标数据块中查找 AL,AX或 EAX，
然后 EDI自动增加或减小 1,2或 4
SCAS指令可以和 REPZ或 REPNZ前缀一起使用
SCAS指令一般与 REPNZ前缀配合使用
7.2 字符串处理
字符串是特殊的数据块，以 00H字符结尾。
字符串中可以包括一些控制字符，在汇编语言中，需要直接写出这些字符的
ASCII码值。
7.2.1 常用字符串处理函数部分字符串函数的实现原理程序示例程序 strfunc.asm中用块指令实现了 3个字符串函数 strlen,strcpy和 strcat
其执行结果为：
strlen("Hello ")=6
strcat("Hello ","World!")="Hello World!"
7.2.2 常用内存块处理函数内存块函数的功能
memcpy的功能是从 dest指向的数据块复制
count字节到 src中。
memmove的功能是从 dest指向的数据块传送
count字节到 src中。
memcmp的功能是比较两个数据块是否相等。
memset的功能是初始化数据块的内容。
memchr的功能是在数据块中查找指定的数据，
找到后返回该数据的地址；未找到则返回 NULL。
部分内存块函数的实现方法程序示例用块指令实现内存块处理函数 memfunc.asm
Array[ 0]= 1
Array[ 1]= 2
Array[ 2]= 4
Array[ 3]= 8
Array[ 4]= 16
Array[ 5]= 32
Array[ 6]= 64
Array[ 7]= 128
Array[ 8]= 256
Array[ 9]= 512
Array[10]=1024
字符串操作指令字符串操作指令包括：
MOVS
LODS
STOS
CMPS
SCAS
字符串操作指令字符串操作指令特点：
可以操作字符串和内存数据块；
字符串是以 00H字符结尾的数据块,但这些指令并不要求最后一个单元为 00H
可高效地实现块操作函数,而用块操作指令来实现字符串操作函数却效率不高 。
7.3 结构结构将若干相联的数据项组合成一个整体。
有以下几个优点：
（ 1）结构的复制
（ 2）作为函数参数
（ 3）增加代码的可读性
C语言中有两种形式来访问成员
结构变量,成员
结构指针 ->成员
7.3.1 表示时间的结构使用结构之前,先声明这个结构,再定义这个结构 。
声明结构时
指定结构的类型名以及每个成员的类型和大小
定义结构时
用该结构的类型名定义结构变量
结构变量要在数据区 （ 或堆栈区 ） 占用内存空间,
结构变量的成员中可以存放具体的数据
7.3.2 结构的声明和定义
1,结构的声明格式为：
结构名 struc
成员 1 类型 初值成员 2 类型 初值
…
结构名 ends
结构的声明和定义（续）
2,结构的定义格式为：
结构变量名 结构名 <成员初值表 >
3,结构成员的使用格式为：
结构变量名,成员名
(结构名 PTR [寄存器 ]).成员名显示当前时间的程序,tm.asm
7.3.3 结构数组
1,结构的嵌套结构中的成员可以是另外一个结构 。
2,结构的大小
size操作符后面跟结构名,可以得到该结构所占用的字节数 。
3,结构数组采用 dup操作符,可以定义结构数组 。
如,st_array student 60 dup (<>)
4．结构变量之间的复制可以用块操作指令将一个结构变量所占用的内存复制到另一个结构中,这样比较简单。
举例 （包含结 构嵌套、复制、结构数组 ）：
student.asm
5,结构数组的排序
与数组排序相似
要将整个结构相互交换
7.4 链表链表在插入、删除元素时，效率很高单向链表的结构 如下单向链表有一个头指针，它指向第 1个节点每一个节点包含两部分：一是实际需要保存的数据；
二是 next指针，即下一个节点的地址。
空指针用 NULL表示
7.4.1 动态分配和释放内存链表中一般使用 malloc和 free来动态分配和释放内存空间 。
格式为：
分配空间 void * malloc(int size);
释放空间 void free(void *p);
7.4.2 链表中元素的插入与删除
1,链表中元素的插入
插入的数据作为链表的最后一个元素
如果头指针为空，则将该结构的地址保存到头指针中，头指针指向该结构；
如果头指针不为空，顺序取出链表中的各个元素，最后元素的后继指针为空，再指定结构的地址后继指针 。
结构作为链表的第一个元素
最后输入的数据放在链表的最前面
比较简单
链表以及动态分配 /释放内存 示例：
linklist.asm
2．链表中元素的删除从链表中删除一个元素
首先要确定指向该元素的节点
将该节点的后继指针修改为待删除节点的后继指针如果待删除节点是链表中的首节点,
则修改首指针为待删除节点的后继指针。
7.4.3 链表的排序对链表中的元素进行排序,不需要进行内存块复制,仅对链表中的指针进行调整 。
例如,在排序过程中交换节点 x和节点 y的 顺序要分 3步完成：
（ 1） 指向节点 x的指针替换为指向节点 y的指针；
（ 2） 节点 x的后继指针设置为节点 y的后继指针；
（ 3） 节点 y的后继指针设置为节点 x的地址 。
链表中元素顺序的交换过程两层循环对链表的排序在编程中,[EDI]单元中保存的内容为指向节点 x的指针,EBX是节点 x的地址，
ESI是节点 y的地址。 以上 3个步骤为：
（ 1） 令 [EDI]单元等于 ESI；
（ 2） 令 （ [EBX].next） 等于 （ [ESI].next） ；
（ 3） 令（ [ESI].next） 等于 EBX。
子程序示例,sortlink.asm
7.4.4 双向链表双向链表的节点包括两个指针：
后继指针和前趋指针
节点的删除比较方便，可以对链表进行从尾到头的遍历
节点的插入、排序等操作 比较复杂
7.5 函数指针指针变量可以指向一个子程序（函数）
可以将子程序的地址存入一个指针中,
然后通过该指针来调用子程序 。
7.5.1 指向子程序（函数）的指针
CALL指令后面可以接：
子程序的地址，直接去调用子程序
变量，变量的内容是子程序的地址举例,func为指针变量，内容为 SubProc是一个子程序的地址，可以用 call指令如下调用：
CALL SubProc 或
CALL func
使用函数指针示例 pointerf.asm
7.5.2 结构中的函数指针指针可以放在一个结构中，作为结构的一个成员，
如单向链表中的 next成员以四则运算的程序为例，结构中包括两个成员：运算符和运算函数：运算符为加、减、乘、
除 4个字符，运算函数则分别初始化为各个子程序的入口地址。
程序示例,funcfld.asm
7.6 程序执行环境
7.6.1 输入 /输出重定向
1,输入重定向将要输入的内容先存在一个文件中,在执行程序时,在程序名后跟上,< 输入文件名
2,输出重定向在程序名后跟上 > 输出文件名
3.输入 /输出重定向可以同时使用
7.6.2 命令行参数及程序返回值
1,命令行参数
C语言中,main函数的原型为：
int main(int argc,char* argv[])
程序执行时,用户在命令行的输入被分为多个字符串,字符串的个数为 argc； 每个字符串的指针放在 argv数组中
2,程序返回值
main函数的返回值,作为整个程序执行的结果 。 程序正常结束时,应返回 0。
3.程序示例,cmdline.asm
7.1 数组与内存块
7.2 字符串处理
7.3 结构
7.4 链表
7.5 函数指针
7.6 程序执行环境
7.1 数组与内存块
数组是内存中的一块连续数据单元
数组中的元素大小固定，类型相同
一组连续的数据单元称为内存块
数组，字符串和结构都可以看成是一个内存块
7.1.1 块操作块操作指令一共有 5种块操作指令的用法
1,操作数的大小指令后面的 B,W,D分别代表字节,字,双字
2,源操作数和目的操作数源操作数是 DS:[ESI]所指向的内存单元；
目标操作数是 ES:[EDI]所指向的内存单元
3,方向标志和地址指针的修改块操作指令会自动地修改 ESI和 EDI
操作数的大小决定增加或减小的单位
4．重复前缀
可以和块操作指令联合使用
有 3种形式,REP,REPZ,REPNZ
放在块操作指令的前面
5种块操作指令的功能
（ 1） MOVSB/W/D将 ESI所指向的字节 /字 /双字复制到 EDI
所指向的字节 /字 /双字 。
（ 2） CMPSB/W/D将 ESI和 EDI所指向的字节 /字 /双字进行比较 。
（ 3 ） SCASB/W/D 将 EDI 所 指 向 的 字 节 / 字 / 双 字 和
AL/AX/EAX进行比较 。
（ 4） STOSB/W/D将 AL/AX/EAX保存到 EDI所指向的字节 /字
/双字中 。
（ 5） LODSB/W/D将 ESI所指向的字节 /字 /双字读入到
AL/AX/EAX中 。
3种重复前缀的用法
（ 1） 前缀为 REP时,重复次数固定为 ECX。
REP和 MOVS,STOS,LODS联合使用 。
（ 2） 前缀为 REPZ时,重复次数最大为 ECX。
REPZ和 CMPS,SCAS联合使用 。
如果在比较或扫描时,ZF=0,不再重复 。
（ 3） 前缀为 REPNZ时,重复次数最大为 ECX。
REPNZ和 CMPS,SCAS联合使用 。
如果在比较或扫描时,ZF=1,不再重复 。
7.1.2 块传送指令
MOVSB/W/D将操作数从一个内存单元传送到另一个内存单元，它和 REP前缀同时使用，将一个内存块（源数据块）复制到另一个内存块（目标数据块）。
1．数组的复制下面的程序将数组 Array1复制给 Array2
Array1 DWORD 1,10,100,1000,10000
Array2 DWORD 5 DUP (0)
LEA ESI,Array1
LEA EDI,Array2
CLD
MOV ECX,5
REP MOVSD
每次,MOVSD传送一个双字,ESI,EDI自动加 4，
指向下一个双字,ECX自动减 1。
2．从字符串中删除一个字符一行字符存储在缓冲区 InBuffer中
InBuffer BYTE 'Hellox World!',0
把 X删掉的指令代码为
LEA ESI,InBuffer+6 ; ESI指向字符 ' '
LEA EDI,InBuffer+5 ; EDI指向字符 'x'
CLD ; 地址由低至高
MOV ECX,8 ; 传送 8次
REP MOVSB ; 以字节为单位传送
3．向字符串中插入一个字符
InBuffer BYTE 'Hello Wrld!',0
想要将 O插入进去的代码为：
InBuffer BYTE 'Hello Wrld!',0,?
LEA ESI,InBuffer+11 ; ESI指向字符 00H
LEA EDI,InBuffer+12 ; EDI指向?所在的位置
STD ; 地址由高至低
MOV ECX,5 ; 传送 5次
REP MOVSB ; 以字节为单位传送
CLD ; 恢复为 "地址由低至高 "
MOV InBuffer+7,'o' ; 插入字符 'o'
4．块传送的 3种情况根据源数据块和目标数据块是否重叠，以及数据块的地址前后顺序，将数据块的传送分为：
（ 1）源数据块和目标数据块不重叠。 DF=0或 DF=1均可。
（ 2）源数据块和目标数据块重叠，目标数据块地址较小。
只能设置 DF=0,ESI和 EDI分别执行源数据块和目标数据块的第 1个单元的地址。
（ 3）源数据块和目标数据块重叠，目标数据块地址较大。
只能设置 DF=1,ESI和 EDI指向源数据块和目标数据块的最后一个传送单位。
7.1.3 块存储指令块存储指令包括,STOSB,STOSW,STOSD
将 AL,AX或 EAX的内容存入由 EDI指向的存储单元，然后 EDI自动增减 1,2或 4。
可以和 REP前缀一起使用，连续执行 ECX次块存储指令。
LODS指令一般不带 REP前缀 。
7.1.4 块装入指令块装入指令包括 LODSB,LODSW,LODSD
将由 ESI指向的存储单元读入累加器 AL,AX
或 EAX中,然后 ESI自动增减 1,2或 4。
可以和 REP前缀一起使用,连续执行 ECX次读入操作,但一般不带 REP前缀 。
7.1.5 块比较指令块比较指令包括 CMPSB,CMPSW,CMPSD
较由 EDI指向的目标操作数和由 ESI指向的源操作数，然后 EDI和 ESI自动增减 1,2或 4。
CMPS指令可以和 REPZ或 REPNZ前缀一起使用。
CMPS指令一般与 REPZ前缀配合使用。
比较完成后，根据 ZF标志位来决定是否两个数据块是否相等。
7.1.6 块扫描指令块扫描指令包括 SCASB,SCASW,SCASD
在 EDI指向的目标数据块中查找 AL,AX或 EAX，
然后 EDI自动增加或减小 1,2或 4
SCAS指令可以和 REPZ或 REPNZ前缀一起使用
SCAS指令一般与 REPNZ前缀配合使用
7.2 字符串处理
字符串是特殊的数据块，以 00H字符结尾。
字符串中可以包括一些控制字符，在汇编语言中，需要直接写出这些字符的
ASCII码值。
7.2.1 常用字符串处理函数部分字符串函数的实现原理程序示例程序 strfunc.asm中用块指令实现了 3个字符串函数 strlen,strcpy和 strcat
其执行结果为：
strlen("Hello ")=6
strcat("Hello ","World!")="Hello World!"
7.2.2 常用内存块处理函数内存块函数的功能
memcpy的功能是从 dest指向的数据块复制
count字节到 src中。
memmove的功能是从 dest指向的数据块传送
count字节到 src中。
memcmp的功能是比较两个数据块是否相等。
memset的功能是初始化数据块的内容。
memchr的功能是在数据块中查找指定的数据，
找到后返回该数据的地址；未找到则返回 NULL。
部分内存块函数的实现方法程序示例用块指令实现内存块处理函数 memfunc.asm
Array[ 0]= 1
Array[ 1]= 2
Array[ 2]= 4
Array[ 3]= 8
Array[ 4]= 16
Array[ 5]= 32
Array[ 6]= 64
Array[ 7]= 128
Array[ 8]= 256
Array[ 9]= 512
Array[10]=1024
字符串操作指令字符串操作指令包括：
MOVS
LODS
STOS
CMPS
SCAS
字符串操作指令字符串操作指令特点：
可以操作字符串和内存数据块；
字符串是以 00H字符结尾的数据块,但这些指令并不要求最后一个单元为 00H
可高效地实现块操作函数,而用块操作指令来实现字符串操作函数却效率不高 。
7.3 结构结构将若干相联的数据项组合成一个整体。
有以下几个优点：
（ 1）结构的复制
（ 2）作为函数参数
（ 3）增加代码的可读性
C语言中有两种形式来访问成员
结构变量,成员
结构指针 ->成员
7.3.1 表示时间的结构使用结构之前,先声明这个结构,再定义这个结构 。
声明结构时
指定结构的类型名以及每个成员的类型和大小
定义结构时
用该结构的类型名定义结构变量
结构变量要在数据区 （ 或堆栈区 ） 占用内存空间,
结构变量的成员中可以存放具体的数据
7.3.2 结构的声明和定义
1,结构的声明格式为：
结构名 struc
成员 1 类型 初值成员 2 类型 初值
…
结构名 ends
结构的声明和定义（续）
2,结构的定义格式为：
结构变量名 结构名 <成员初值表 >
3,结构成员的使用格式为：
结构变量名,成员名
(结构名 PTR [寄存器 ]).成员名显示当前时间的程序,tm.asm
7.3.3 结构数组
1,结构的嵌套结构中的成员可以是另外一个结构 。
2,结构的大小
size操作符后面跟结构名,可以得到该结构所占用的字节数 。
3,结构数组采用 dup操作符,可以定义结构数组 。
如,st_array student 60 dup (<>)
4．结构变量之间的复制可以用块操作指令将一个结构变量所占用的内存复制到另一个结构中,这样比较简单。
举例 （包含结 构嵌套、复制、结构数组 ）：
student.asm
5,结构数组的排序
与数组排序相似
要将整个结构相互交换
7.4 链表链表在插入、删除元素时，效率很高单向链表的结构 如下单向链表有一个头指针，它指向第 1个节点每一个节点包含两部分：一是实际需要保存的数据；
二是 next指针，即下一个节点的地址。
空指针用 NULL表示
7.4.1 动态分配和释放内存链表中一般使用 malloc和 free来动态分配和释放内存空间 。
格式为：
分配空间 void * malloc(int size);
释放空间 void free(void *p);
7.4.2 链表中元素的插入与删除
1,链表中元素的插入
插入的数据作为链表的最后一个元素
如果头指针为空，则将该结构的地址保存到头指针中，头指针指向该结构；
如果头指针不为空，顺序取出链表中的各个元素，最后元素的后继指针为空，再指定结构的地址后继指针 。
结构作为链表的第一个元素
最后输入的数据放在链表的最前面
比较简单
链表以及动态分配 /释放内存 示例：
linklist.asm
2．链表中元素的删除从链表中删除一个元素
首先要确定指向该元素的节点
将该节点的后继指针修改为待删除节点的后继指针如果待删除节点是链表中的首节点,
则修改首指针为待删除节点的后继指针。
7.4.3 链表的排序对链表中的元素进行排序,不需要进行内存块复制,仅对链表中的指针进行调整 。
例如,在排序过程中交换节点 x和节点 y的 顺序要分 3步完成：
（ 1） 指向节点 x的指针替换为指向节点 y的指针；
（ 2） 节点 x的后继指针设置为节点 y的后继指针；
（ 3） 节点 y的后继指针设置为节点 x的地址 。
链表中元素顺序的交换过程两层循环对链表的排序在编程中,[EDI]单元中保存的内容为指向节点 x的指针,EBX是节点 x的地址，
ESI是节点 y的地址。 以上 3个步骤为：
（ 1） 令 [EDI]单元等于 ESI；
（ 2） 令 （ [EBX].next） 等于 （ [ESI].next） ；
（ 3） 令（ [ESI].next） 等于 EBX。
子程序示例,sortlink.asm
7.4.4 双向链表双向链表的节点包括两个指针：
后继指针和前趋指针
节点的删除比较方便，可以对链表进行从尾到头的遍历
节点的插入、排序等操作 比较复杂
7.5 函数指针指针变量可以指向一个子程序（函数）
可以将子程序的地址存入一个指针中,
然后通过该指针来调用子程序 。
7.5.1 指向子程序（函数）的指针
CALL指令后面可以接：
子程序的地址，直接去调用子程序
变量，变量的内容是子程序的地址举例,func为指针变量，内容为 SubProc是一个子程序的地址，可以用 call指令如下调用：
CALL SubProc 或
CALL func
使用函数指针示例 pointerf.asm
7.5.2 结构中的函数指针指针可以放在一个结构中，作为结构的一个成员，
如单向链表中的 next成员以四则运算的程序为例，结构中包括两个成员：运算符和运算函数：运算符为加、减、乘、
除 4个字符，运算函数则分别初始化为各个子程序的入口地址。
程序示例,funcfld.asm
7.6 程序执行环境
7.6.1 输入 /输出重定向
1,输入重定向将要输入的内容先存在一个文件中,在执行程序时,在程序名后跟上,< 输入文件名
2,输出重定向在程序名后跟上 > 输出文件名
3.输入 /输出重定向可以同时使用
7.6.2 命令行参数及程序返回值
1,命令行参数
C语言中,main函数的原型为：
int main(int argc,char* argv[])
程序执行时,用户在命令行的输入被分为多个字符串,字符串的个数为 argc； 每个字符串的指针放在 argv数组中
2,程序返回值
main函数的返回值,作为整个程序执行的结果 。 程序正常结束时,应返回 0。
3.程序示例,cmdline.asm
