常用數(shù)據(jù)結(jié)構(gòu)課件

常用數(shù)據(jù)結(jié)構(gòu)

7.1數(shù)組與內(nèi)存塊

數(shù)組是內(nèi)存中的一塊連續(xù)數(shù)據(jù)單元數(shù)組中的元素大小固定，類型相同

一組連續(xù)的數(shù)據(jù)單元稱為內(nèi)存塊

數(shù)組，字符串和結(jié)構(gòu)都可以看成是一個內(nèi)存塊7.1.1塊操作

塊操作指令一共有5種

塊操作指令的用法

1．操作數(shù)的大小指令后面的B,W,D分別代表字節(jié)、字、雙字2．源操作數(shù)和目的操作數(shù)源操作數(shù)是DS:[ESI]所指向的內(nèi)存單元；目標操作數(shù)是ES:[EDI]所指向的內(nèi)存單元3．方向標志和地址指針的修改塊操作指令會自動地修改ESI和EDI

操作數(shù)的大小決定增加或減小的單位4．重復(fù)前綴可以和塊操作指令聯(lián)合使用有3種形式：REP，REPZ，REPNZ放在塊操作指令的前面

5種塊操作指令的功能

（1）MOVSB/W/D將ESI所指向的字節(jié)/字/雙字復(fù)制到EDI所指向的字節(jié)/字/雙字。（2）CMPSB/W/D將ESI和EDI所指向的字節(jié)/字/雙字進行比較。（3）SCASB/W/D將EDI所指向的字節(jié)/字/雙字和AL/AX/EAX進行比較。（4）STOSB/W/D將AL/AX/EAX保存到EDI所指向的字節(jié)/字/雙字中。（5）LODSB/W/D將ESI所指向的字節(jié)/字/雙字讀入到AL/AX/EAX中。3種重復(fù)前綴的用法

（1）前綴為REP時，重復(fù)次數(shù)固定為ECX。REP和MOVS，STOS，LODS聯(lián)合使用。（2）前綴為REPZ時，重復(fù)次數(shù)最大為ECX。REPZ和CMPS，SCAS聯(lián)合使用。如果在比較或掃描時，ZF=0，不再重復(fù)。（3）前綴為REPNZ時，重復(fù)次數(shù)最大為ECX。REPNZ和CMPS，SCAS聯(lián)合使用。如果在比較或掃描時，ZF=1，不再重復(fù)。

7.1.2塊傳送指令MOVSB/W/D將操作數(shù)從一個內(nèi)存單元傳送到另一個內(nèi)存單元，它和REP前綴同時使用，將一個內(nèi)存塊（源數(shù)據(jù)塊）復(fù)制到另一個內(nèi)存塊（目標數(shù)據(jù)塊）。

1．數(shù)組的復(fù)制下面的程序?qū)?shù)組Array1復(fù)制給Array2

Array1 DWORD1,10,100,1000,10000Array2 DWORD5DUP(0)

LEA ESI,Array1LEA EDI,Array2CLDMOV ECX,5REP MOVSD每次，MOVSD傳送一個雙字，ESI，EDI自動加4，指向下一個雙字，ECX自動減1。

2．從字符串中刪除一個字符一行字符存儲在緩沖區(qū)InBuffer中InBufferBYTE'HelloxWorld!',0把X刪掉的指令代碼為LEAESI,InBuffer+6 ;ESI指向字符''LEAEDI,InBuffer+5 ;EDI指向字符'x'CLD ;地址由低至高MOVECX,8 ;傳送8次REPMOVSB ;以字節(jié)為單位傳送

3．向字符串中插入一個字符InBufferBYTE'HelloWrld!',0想要將O插入進去的代碼為：InBufferBYTE'HelloWrld!',0,?LEAESI,InBuffer+11;ESI指向字符00HLEAEDI,InBuffer+12;EDI指向?所在的位置STD;地址由高至低MOVECX,5;傳送5次REPMOVSB;以字節(jié)為單位傳送CLD;恢復(fù)為"地址由低至高"MOVInBuffer+7,'o';插入字符'o'4．塊傳送的3種情況

根據(jù)源數(shù)據(jù)塊和目標數(shù)據(jù)塊是否重疊，以及數(shù)據(jù)塊的地址前后順序，將數(shù)據(jù)塊的傳送分為：（1）源數(shù)據(jù)塊和目標數(shù)據(jù)塊不重疊。DF=0或DF=1均可。（2）源數(shù)據(jù)塊和目標數(shù)據(jù)塊重疊，目標數(shù)據(jù)塊地址較小。只能設(shè)置DF=0，ESI和EDI分別執(zhí)行源數(shù)據(jù)塊和目標數(shù)據(jù)塊的第1個單元的地址。（3）源數(shù)據(jù)塊和目標數(shù)據(jù)塊重疊，目標數(shù)據(jù)塊地址較大。只能設(shè)置DF=1，ESI和EDI指向源數(shù)據(jù)塊和目標數(shù)據(jù)塊的最后一個傳送單位。

7.1.3塊存儲指令塊存儲指令包括：STOSB，STOSW，STOSD將AL，AX或EAX的內(nèi)容存入由EDI指向的存儲單元，然后EDI自動增減1,2或4?？梢院蚏EP前綴一起使用，連續(xù)執(zhí)行ECX次塊存儲指令。LODS指令一般不帶REP前綴。

7.1.4塊裝入指令塊裝入指令包括LODSB,LODSW,LODSD

將由ESI指向的存儲單元讀入累加器AL,AX或EAX中，然后ESI自動增減1,2或4?？梢院蚏EP前綴一起使用，連續(xù)執(zhí)行ECX次讀入操作，但一般不帶REP前綴。

7.1.5塊比較指令塊比較指令包括CMPSB,CMPSW,CMPSD較由EDI指向的目標操作數(shù)和由ESI指向的源操作數(shù)，然后EDI和ESI自動增減1,2或4。CMPS指令可以和REPZ或REPNZ前綴一起使用。CMPS指令一般與REPZ前綴配合使用。比較完成后，根據(jù)ZF標志位來決定是否兩個數(shù)據(jù)塊是否相等。

7.1.6塊掃描指令塊掃描指令包括SCASB,SCASW,SCASD在EDI指向的目標數(shù)據(jù)塊中查找AL,AX或EAX，然后EDI自動增加或減小1,2或4SCAS指令可以和REPZ或REPNZ前綴一起使用SCAS指令一般與REPNZ前綴配合使用

7.2字符串處理字符串是特殊的數(shù)據(jù)塊，以00H字符結(jié)尾。字符串中可以包括一些控制字符，在匯編語言中，需要直接寫出這些字符的ASCII碼值。

7.2.1常用字符串處理函數(shù)部分字符串函數(shù)的實現(xiàn)原理

程序示例程序strfunc.asm中用塊指令實現(xiàn)了3個字符串函數(shù)strlen，strcpy和strcat

其執(zhí)行結(jié)果為：strlen("Hello")=6strcat("Hello","World!")="HelloWorld!"

7.2.2常用內(nèi)存塊處理函數(shù)

內(nèi)存塊函數(shù)的功能memcpy的功能是從dest指向的數(shù)據(jù)塊復(fù)制count字節(jié)到src中。memmove的功能是從dest指向的數(shù)據(jù)塊傳送count字節(jié)到src中。memcmp的功能是比較兩個數(shù)據(jù)塊是否相等。memset的功能是初始化數(shù)據(jù)塊的內(nèi)容。memchr的功能是在數(shù)據(jù)塊中查找指定的數(shù)據(jù)，找到后返回該數(shù)據(jù)的地址；未找到則返回NULL。

部分內(nèi)存塊函數(shù)的實現(xiàn)方法程序示例用塊指令實現(xiàn)內(nèi)存塊處理函數(shù)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字符串操作指令字符串操作指令特點：可以操作字符串和內(nèi)存數(shù)據(jù)塊；字符串是以00H字符結(jié)尾的數(shù)據(jù)塊，但這些指令并不要求最后一個單元為00H可高效地實現(xiàn)塊操作函數(shù)，而用塊操作指令來實現(xiàn)字符串操作函數(shù)卻效率不高。7.3結(jié)構(gòu)

結(jié)構(gòu)將若干相聯(lián)的數(shù)據(jù)項組合成一個整體。有以下幾個優(yōu)點：（1）結(jié)構(gòu)的復(fù)制（2）作為函數(shù)參數(shù)（3）增加代碼的可讀性C語言中有兩種形式來訪問成員結(jié)構(gòu)變量.成員結(jié)構(gòu)指針->成員

7.3.1表示時間的結(jié)構(gòu)使用結(jié)構(gòu)之前，先聲明這個結(jié)構(gòu)，再定義這個結(jié)構(gòu)。聲明結(jié)構(gòu)時指定結(jié)構(gòu)的類型名以及每個成員的類型和大小

定義結(jié)構(gòu)時用該結(jié)構(gòu)的類型名定義結(jié)構(gòu)變量結(jié)構(gòu)變量要在數(shù)據(jù)區(qū)（或堆棧區(qū)）占用內(nèi)存空間，結(jié)構(gòu)變量的成員中可以存放具體的數(shù)據(jù)

7.3.2結(jié)構(gòu)的聲明和定義1．結(jié)構(gòu)的聲明格式為：結(jié)構(gòu)名struc

成員1類型初值成員2類型初值

…結(jié)構(gòu)名ends

結(jié)構(gòu)的聲明和定義（續(xù)）2．結(jié)構(gòu)的定義格式為：結(jié)構(gòu)變量名結(jié)構(gòu)名<成員初值表>3．結(jié)構(gòu)成員的使用格式為：結(jié)構(gòu)變量名.成員名(結(jié)構(gòu)名PTR[寄存器]).成員名顯示當前時間的程序：tm.asm

7.3.3結(jié)構(gòu)數(shù)組1．結(jié)構(gòu)的嵌套結(jié)構(gòu)中的成員可以是另外一個結(jié)構(gòu)。2．結(jié)構(gòu)的大小size操作符后面跟結(jié)構(gòu)名，可以得到該結(jié)構(gòu)所占用的字節(jié)數(shù)。3．結(jié)構(gòu)數(shù)組采用dup操作符，可以定義結(jié)構(gòu)數(shù)組。

如：st_arraystudent60dup(<>)

4．結(jié)構(gòu)變量之間的復(fù)制

可以用塊操作指令將一個結(jié)構(gòu)變量所占用的內(nèi)存復(fù)制到另一個結(jié)構(gòu)中，這樣比較簡單。舉例（包含結(jié)構(gòu)嵌套、復(fù)制、結(jié)構(gòu)數(shù)組）：student.asm

5．結(jié)構(gòu)數(shù)組的排序與數(shù)組排序相似要將整個結(jié)構(gòu)相互交換

7.4鏈表鏈表在插入、刪除元素時，效率很高單向鏈表的結(jié)構(gòu)如下單向鏈表有一個頭指針，它指向第1個節(jié)點每一個節(jié)點包含兩部分：一是實際需要保存的數(shù)據(jù)；二是next指針，即下一個節(jié)點的地址?？罩羔樣肗ULL表示

7.4.1動態(tài)分配和釋放內(nèi)存鏈表中一般使用malloc和free來動態(tài)分配和釋放內(nèi)存空間。格式為：分配空間void*malloc(intsize);釋放空間voidfree(void*p);7.4.2鏈表中元素的插入與刪除

1．鏈表中元素的插入插入的數(shù)據(jù)作為鏈表的最后一個元素如果頭指針為空，則將該結(jié)構(gòu)的地址保存到頭指針中，頭指針指向該結(jié)構(gòu)；如果頭指針不為空，順序取出鏈表中的各個元素，最后元素的后繼指針為空，再指定結(jié)構(gòu)的地址后繼指針。

結(jié)構(gòu)作為鏈表的第一個元素

最后輸入的數(shù)據(jù)放在鏈表的最前面比較簡單鏈表以及動態(tài)分配/釋放內(nèi)存示例：

linklist.asm

2．鏈表中元素的刪除

從鏈表中刪除一個元素

首先要確定指向該元素的節(jié)點將該節(jié)點的后繼指針修改為待刪除節(jié)點的后繼指針

如果待刪除節(jié)點是鏈表中的首節(jié)點，則修改首指針為待刪除節(jié)點的后繼指針。

7.4.3鏈表的排序

對鏈表中的元素進行排序，不需要進行內(nèi)存塊復(fù)制，僅對鏈表中的指針進行調(diào)整。例如：在排序過程中交換節(jié)點x和節(jié)點y的順序要分3步完成：（1）指向節(jié)點x的指針替換為指向節(jié)點y的指針；（2）節(jié)點x的后繼指針設(shè)置為節(jié)點y的后繼指針；（3）節(jié)點y的后繼指針設(shè)置為節(jié)點x的地址。鏈表中元素順序的交換過程

兩層循環(huán)對鏈表的排序

在編程中，[EDI]單元中保存的內(nèi)容為指向節(jié)點x的指針，EBX是節(jié)點x的地址，ESI是節(jié)點y的地址。以上3個步驟為：（1）令[EDI]單元等于ESI；（2）令（[EBX].next）等于（[ESI].next）；（3）令（[ESI].next）等于EBX。子程序示例：sortlink.asm

7.4.4雙向鏈表雙向鏈表的節(jié)點包括兩個指針：后繼指針和前趨指針節(jié)點的刪除比較方便，可以對鏈表進行從尾到頭的遍歷

節(jié)點的插入、排序等操作比較復(fù)雜7.5函數(shù)指針

指針變量可以指向一個子程序（函數(shù)）可以將子程序的地址存入一個指針中，然后通過該指針來調(diào)用子程序。

7.5.1指向子程序（函數(shù)）的指針

CALL指令后面可以接：子程序的地址，直接去調(diào)用子程序變量，變量的內(nèi)容是子程序的地址

舉