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

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

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

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

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

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

塊操作指令一共有5種

塊操作指令的用法

1．操作數(shù)的大小指令后面的B,W,D分別代表字節(jié)、字、雙字2．源操作數(shù)和目的操作數(shù)源操作數(shù)是DS:[ESI]所指向的內(nèi)存單元；目標(biāo)操作數(shù)是ES:[EDI]所指向的內(nèi)存單元3．方向標(biāo)志和地址指針的修改塊操作指令會(huì)自動(dòng)地修改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é)/字/雙字進(jìn)行比較。（3）SCASB/W/D將EDI所指向的字節(jié)/字/雙字和AL/AX/EAX進(jìn)行比較。（4）STOSB/W/D將AL/AX/EAX保存到EDI所指向的字節(jié)/字/雙字中。（5）LODSB/W/D將ESI所指向的字節(jié)/字/雙字讀入到AL/AX/EAX中。3種重復(fù)前綴的用法

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

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

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

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

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

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

3．向字符串中插入一個(gè)字符InBufferBYTE'HelloWrld!',0想要將O插入進(jìn)去的代碼為：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ù)塊和目標(biāo)數(shù)據(jù)塊是否重疊，以及數(shù)據(jù)塊的地址前后順序，將數(shù)據(jù)塊的傳送分為：（1）源數(shù)據(jù)塊和目標(biāo)數(shù)據(jù)塊不重疊。DF=0或DF=1均可。（2）源數(shù)據(jù)塊和目標(biāo)數(shù)據(jù)塊重疊，目標(biāo)數(shù)據(jù)塊地址較小。只能設(shè)置DF=0，ESI和EDI分別執(zhí)行源數(shù)據(jù)塊和目標(biāo)數(shù)據(jù)塊的第1個(gè)單元的地址。（3）源數(shù)據(jù)塊和目標(biāo)數(shù)據(jù)塊重疊，目標(biāo)數(shù)據(jù)塊地址較大。只能設(shè)置DF=1，ESI和EDI指向源數(shù)據(jù)塊和目標(biāo)數(shù)據(jù)塊的最后一個(gè)傳送單位。

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

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

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

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

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

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

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

程序示例程序strfunc.asm中用塊指令實(shí)現(xiàn)了3個(gè)字符串函數(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的功能是比較兩個(gè)數(shù)據(jù)塊是否相等。memset的功能是初始化數(shù)據(jù)塊的內(nèi)容。memchr的功能是在數(shù)據(jù)塊中查找指定的數(shù)據(jù)，找到后返回該數(shù)據(jù)的地址；未找到則返回NULL。

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

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

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

定義結(jié)構(gòu)時(shí)用該結(jié)構(gòu)的類(lèi)型名定義結(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類(lèi)型初值成員2類(lèi)型初值

…結(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[寄存器]).成員名顯示當(dāng)前時(shí)間的程序：tm.asm

7.3.3結(jié)構(gòu)數(shù)組1．結(jié)構(gòu)的嵌套結(jié)構(gòu)中的成員可以是另外一個(gè)結(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ù)制

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

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

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

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

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

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

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

linklist.asm

2．鏈表中元素的刪除

從鏈表中刪除一個(gè)元素

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

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

7.4.3鏈表的排序

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

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

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

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

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

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

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

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

舉