常用数据结构课件

常用数据结构

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 DWORD1,10,100,1000,10000Array2 DWORD5DUP(0)

LEA ESI,Array1LEA EDI,Array2CLDMOV ECX,5REP MOVSD每次，MOVSD传送一个双字，ESI，EDI自动加4，指向下一个双字，ECX自动减1。

2．从字符串中删除一个字符一行字符存储在缓冲区InBuffer中InBufferBYTE'HelloxWorld!',0把X删掉的指令代码为LEAESI,InBuffer+6 ;ESI指向字符''LEAEDI,InBuffer+5 ;EDI指向字符'x'CLD ;地址由低至高MOVECX,8 ;传送8次REPMOVSB ;以字节为单位传送

3．向字符串中插入一个字符InBufferBYTE'HelloWrld!',0想要将O插入进去的代码为：InBufferBYTE'HelloWrld!',0,?LEAESI,InBuffer+11;ESI指向字符00HLEAEDI,InBuffer+12;EDI指向?所在的位置STD;地址由高至低MOVECX,5;传送5次REPMOVSB;以字节为单位传送CLD;恢复为"地址由低至高"MOVInBuffer+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或4SCAS指令可以和REPZ或REPNZ前缀一起使用SCAS指令一般与REPNZ前缀配合使用

7.2字符串处理字符串是特殊的数据块，以00H字符结尾。字符串中可以包括一些控制字符，在汇编语言中，需要直接写出这些字符的ASCII码值。

7.2.1常用字符串处理函数部分字符串函数的实现原理

程序示例程序strfunc.asm中用块指令实现了3个字符串函数strlen，strcpy和strcat

其执行结果为：strlen("Hello")=6strcat("Hello","World!")="HelloWorld!"

7.2.2常用内存块处理函数

内存块函数的功能memcpy的功能是从dest指向的数据块复制count字节到src中。memmove的功能是从dest指向的数据块传送count字节到src中。memcmp的功能是比较两个数据块是否相等。memset的功能是初始化数据块的内容。memchr的功能是在数据块中查找指定的数据，找到后返回该数据的地址；未找到则返回NULL。

部分内存块函数的实现方法程序示例用块指令实现内存块处理函数memfunc.asmArray[0]=1Array[1]=2Array[2]=4Array[3]=8Array[4]=16Array[5]=32Array[6]=64Array[7]=128Array[8]=256Array[9]=512Array[10]=1024字符串操作指令字符串操作指令包括：MOVSLODSSTOSCMPSSCAS字符串操作指令字符串操作指令特点：可以操作字符串和内存数据块；字符串是以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_arraystudent60dup(<>)

4．结构变量之间的复制

可以用块操作指令将一个结构变量所占用的内存复制到另一个结构中，这样比较简单。举例（包含结构嵌套、复制、结构数组）：student.asm

5．结构数组的排序与数组排序相似要将整个结构相互交换

7.4链表链表在插入、删除元素时，效率很高单向链表的结构如下单向链表有一个头指针，它指向第1个节点每一个节点包含两部分：一是实际需要保存的数据；二是next指针，即下一个节点的地址。空指针用NULL表示

7.4.1动态分配和释放内存链表中一般使用malloc和free来动态分配和释放内存空间。格式为：分配空间void*malloc(intsize);释放空间voidfree(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指令后面可以接：子程序的地址，直接去调用子程序变量，变量的内容是子程序的地址

举