常用數據結構

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指令后面可以接：子程序的地址，直接去調用子程序變量，變量的內容是子程序的地址

舉