串與表的處理程序設(shè)計

單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,*,第七章 串與表的處理程序設(shè)計,7.1,串操作指令,“,串,”,是指存儲器中的一段連續(xù)的字或字節(jié)單元。這些單元中存放的內(nèi)容可以是字符或數(shù)據(jù)。,“,串操作,”,就是對這些單元進(jìn)行某種相同的操作。比如將一段數(shù)據(jù)從一個存儲區(qū)傳送到另一個存儲區(qū)。,1,（3,）當(dāng)標(biāo)志位,DF=0,時，,SI,和,DI,的修改為遞增，即加,2,（字操作）或加,1,（字節(jié)操作）。當(dāng),DF=1,時，,SI,和,DI,的修改為遞減，即減,2,或減,1,。,（2,）串操作指令每次只對串中的一個字或一個字節(jié)單元進(jìn)行操作，并自動修改,SI,和(或),DI，,使其指向下一個字或字節(jié)單元。,（1,）串操作指令使用專用的尋址方式：源操作數(shù)地址由,DS:SI,提供，目的操作數(shù)由,ES:DI,提供。,串,操作指令具有以下共有特點：,2,1.,取串指令,由于源串是由,SI,指定，如果程序中在執(zhí)行該指令時已經(jīng)明確是字或字節(jié)，則可以用無操作數(shù)指令,LODSB（,字節(jié)操作）或,LODSW（,字操作）替代。,該指令執(zhí)行后對標(biāo)志無影響。,指令格式：,LODS,源串,將源串中的一個字或字節(jié)內(nèi)容送入,AX,或,AL,中，并根據(jù),DF,修改,SI。,功能：,3,2.,存串指令,同樣，指令可以用無操作數(shù)指令,STOSB,或,STOSW,替代。,該指令對標(biāo)志無影響。,STOS,目的串,指令格式：,功能：,將,AX,或,AL,中的內(nèi)容送入目的串中的一個字單元或字節(jié)單元，并根據(jù),DF,修改,DI。,4,3.,串傳送指令,MOVS,目的串，源串,同樣，指令可以用無操作數(shù)指令,MOVSB,或,MOVSW,替代。,指令對標(biāo)志無影響,指令格式：,功能：,將由,SI,指向的源串的一個字或字節(jié)傳送到,DI,所指向的目的串中。并根據(jù),DF,修改,SI,和,DI。,5,4.,串比較指令,CMPS,源串，目的串,將源串中的一個字節(jié)或字減去目的串中的一個字或字節(jié)，結(jié)果不回送。但將影響標(biāo)志寄存器。同時，將根據(jù),DF,修改,SI,和,DI。,指令格式：,同樣，指令可以用無操作數(shù)指令,CMPSB,或,CMPSW,替代。,功能：,6,5,、串搜索指令,SCAS,目的串,查找的方法：,用,AX,或,AL,的內(nèi)容減去目的串中的一個字或字節(jié)，相減的結(jié)果反映在標(biāo)志寄存器中。每查找一次，將按照,DF,修改,DI。,指令格式：,功能：,在目的串中查找,AX,或,AL,指定的內(nèi)容。,同樣，指令可以用無操作數(shù)指令,SCASB,或,SCASW,替代。,7,6,、重復(fù)前綴指令,REP,重復(fù)操作的次數(shù)由,CX,控制，每執(zhí)行一次串操作指令，,CX,內(nèi)容減,1,，直到,CX,內(nèi)容為,0。,指令格式：,為了方便對若干個字或字節(jié)進(jìn)行多次同樣的操作，可在上述各種指令的前面加上,REP,指令。,8,例如：,REP MOVSB,設(shè)在執(zhí)行該指令前,DF=0,(SI)=0020H,(DI)=100H,(CX)=0030H。,LOP:MOV AL,SI,MOV ES:DI,AL,INC SI,INC DI,LOOP LOP,執(zhí)行該指令將使數(shù)據(jù)段中從,0020,H,開始的,30,H,個字節(jié)傳送到附加段從,0100,H,開始的存儲區(qū)。,如果改用不使用串操作指令，則它相當(dāng)于下面的程序段：,9,REPE/REPZ,重復(fù)執(zhí)行串操作指令的條件是：（,CX）,0,和,ZF=1,由于這兩條指令的執(zhí)行要由標(biāo)志位,ZF,來控制結(jié)束，而,LODS、STOS,和,MOVS,三條指令不影響標(biāo)志，因此不適合與這些指令配合使用。,另外還有兩條重復(fù)前綴指令：,REPNE/REPNZ,重復(fù)執(zhí)行串操作指令的條件是：（,CX）,0,和,ZF=0,10,7.2,串操作指令應(yīng)用舉例,例1：試編制一程序，在,TXTBUF,字符串中查找,STRING,變量指定的字符。若查到，則把該字符所在位置（,1,n）,送入,INDEX,單元中。若未查到，則把,0,FFH,送,INDEX,單元中。,DATA SEGMENT,TXTBUF DB ABCDEFGHIJKLMNOP,CUNT EQU$-TXTBUF,STRING DB G,INDEX DB?,DATA ENDS,STACK1 SEGMENT PARA STACK,DW 20H DUP(0),STACK1 ENDS,11,CODE SEGMENT,ASSUME CS:CODE,DS:DATA,SS:STACK1,START:MOV AX,DATA,MOV DS,AX MOV ES,AX,MOV DI,OFFSET TXTBUF;,取目的串首址,MOV CX,CUNT,MOV AL,STRING,；初始化,DI，CX，AL,CLD;DF=0，,遞增方式,REPNE SCASB ;,查找字符,MOV BL,0FFH,JNE END0 ;,條件判斷：未查到，,ZF=0,轉(zhuǎn)移,SUB DI,OFFSET TXTBUF,MOV BX,DI,END0:MOV INDEX,BL,MOV AH,4CH,INT 21H,CODE ENDS,END START,12,例,2,試編寫一程序，確定某子字符串是否在另一字符串中存在。若在，則記錄其所在起始位置。若不在則設(shè)置標(biāo)志,0,FFH。,該例是例,1,的更一般情況。,A B C D E F G H I J K L M N O P,E F,第,1,次比較：,A B C D E F G H I J K L M N O P,E F,第,2,次比較：,E F,A B C D E F G H I J K L M N O P,第,3,次比較：,13,DATA SEGMENT,TXTBUF DB ABCDEFGHIJKLMNOP,CUNT1 EQU$-TXTBUF,STRING DB EF,CUNT2 EQU$-STRING；,子串長度,INDEX DB 0FFH,DATA ENDS,STACK1 SEGMENT PARA STACK,DW 20H DUP(0),STACK1 ENDS,14,開始,BX=,比較次數(shù),SI,AX=,源串首址,CX=,子串長度,DI=,子串首址,DF=0,源串與子串比較,相同？,AX=,子串位置,INDEX=(AL)+1,AX=(AX)+1,SI=,源串新起點,BX=(BX)-1,(BX)=0?,INDEX=0FFH,結(jié)束,Y,Y,N,N,比較次數(shù)=源串長度-子串長度+1,15,CODE SEGMENT,ASSUME CS:CODE,DS:DATA,SS:STACK1,START:MOV AX,DATA,MOV DS,AX,MOV ES,AX,MOV BX,CUNT1-CUNT2+1;,比較次數(shù),MOV SI,OFFSET TXTBUF;,取源串首址,MOV AX,SI,LOP:,LEA DI,STRING;,取子串首址,MOV CX,CUNT2,CLD,REPZ CMPSB;,比較,JZ MATCH ;（CX)=0,且,ZF=1,相同,轉(zhuǎn),INC AX ;,未匹配，比較位置往后移一位,MOV SI,AX,DEC BX ；,比較次數(shù)計數(shù),JNZ LOP,16,MOV INDEL,0FFH,JMP EXIT,MATCH:SUB AX,OFFSET TXTBUF;,位置為0,n,INC AL ;,位置為1,n,MOV INDEX,AL,EXIT:,MOV AH,4CH,INT 21H,CODE ENDS,END START,17,7.3,排序與查找,為了節(jié)省數(shù)據(jù)查找的時間，一般應(yīng)先將無序表排列成有序表。,排序與查找是程序設(shè)計中經(jīng)常遇到的問題。如統(tǒng)計學(xué)生的考試成績，了解部門工作人員的工作業(yè)績，總結(jié)實驗結(jié)果等等。,排序是指將一組沒有規(guī)律的無序數(shù)據(jù)，排列成有序數(shù)據(jù)。查找是從一組數(shù)據(jù)中搜索指定的數(shù)據(jù)。,排序和查找一般都是在表中進(jìn)行的。所謂數(shù)據(jù)表，是指一組連續(xù)存放在存儲器中的數(shù)據(jù)。數(shù)據(jù)表分為有序表和無序表。,有序表,各數(shù)據(jù)項在存儲器中按順序（遞增或遞減）排列。否則稱為無序表。,18,一、氣泡排序算法,1,、將表中第一個數(shù),b,1,與第二數(shù),b,2,比較，若,b1b2，,則交換兩數(shù)，否則不交換。然后將,b2,與,b3,比較，這樣重復(fù)比較，直至最后兩個數(shù)。,2,、重復(fù)執(zhí)行上述步驟，直至一次循環(huán)中沒有數(shù)據(jù)交換為止。,設(shè)有一組無序數(shù)據(jù)為,b,1,、b,2,、.b,n-1,、,b,n,，,要求以遞減順序排列，則氣泡排序法,、,為：,19,如果采用遞增方式進(jìn)行排序，其處理方法與上述遞減排列方法類似，只需將交換條件變?yōu)榍懊娴臄?shù)大于后面的數(shù)。,在上述方法中，第一次執(zhí)行比較循環(huán)，將使得最小一個數(shù)移動到最后，就象一個氣泡上浮一樣。以后每次循環(huán)比較將使一個較小的數(shù)上浮。并且比較的次數(shù)將依次遞減。這樣直至整個表排列成一個有序表為止。,20,例如有,10,個數(shù)，經(jīng)過,5,次循環(huán)比較后，第,6,次循環(huán)比較時已沒有數(shù)據(jù)交換，為此，設(shè)置一個標(biāo)識，以確定依次循環(huán)比較中是否有數(shù)據(jù)交換。,21,DATA SEGMENT,DA DB 80,3,-20,116,9,120,-6,62,-32,42,COUNT EUQ$-DA,DATA ENDS,STACK1 SEGMENT PARA STACK,DW 20H DUP(0),STACK1 ENDS,源程序的數(shù)據(jù)段和堆棧安排如下：,22,開始,置交換標(biāo)志初值：,BL=0,置比較次數(shù)計數(shù)：,CX=(DX),SI(SI)+1)?,交換數(shù)據(jù)：(,SI),(SI)+1),置,交換標(biāo)志,：,BL=0FFH,修改指針：,SI=,(SI)+1,CX=(CX)-1,(CX)=0？,DX=(DX)-1,有交換？,DX=,比較次數(shù)(數(shù)據(jù)項數(shù)-1),結(jié) 束,Y,N,Y,N,N,Y,SORT1,SORT2,NOXCHG,MOV DX,COUNT-1,MOV BL,0,MOV CX,DX,MOV SI,0,MOV AL,DASI CMP AL,DASI+1,JGE NOXCHG,XCHG AL,DASI+1 MOV DASI,AL,MOV BL,0FFH,INC SI,LOOP SORT2,DEC DX,CMP BL，0,JNE SORT1,23,COSEG SEGMENT,ASSUME CS:COSEG,DS:DATA,SS:STACK1,SORT:,MOV AX,DATA,MOV DS,AX,MOV DX,COUNT-1 ;,置比較次數(shù)初值,SORT1:,MOV BL,0 ;,置交換標(biāo)志初值,MOV CX,DX ;,置內(nèi)循環(huán)比較次數(shù),MOV SI,0 ;,置數(shù)據(jù)指針初值,SORT2:MOV AL,DASI,CMP AL,DASI+1;,比較,JGE NOXCHG ;,大于等于則轉(zhuǎn)不交換,XCHG AL,DASI+1;,交換,MOV DASI,AL,MOV BL,0FFH ;,置已交換標(biāo)志,NOXCHG:INC SI ;,修改地址,LOOP SORT2,DEC DX ;,修改比較次數(shù),CMP BL,0 ;,檢查交換標(biāo)志,JNE SORT1 ;,有交換,繼續(xù),MOV AH,4CH,INT 21H,COSEG,ENDS,END SORT,24,二.,二分法查找算法,二分法查找算法是對有序表進(jìn)行的查找方法。如果是一個無序表，則必須先將其排列成一個有序表。,算法要點,：將整個數(shù)據(jù)表對分成兩個部分，判斷所查找的數(shù)據(jù)屬于哪個部分。然后再將所屬部分對分成兩個區(qū)域，并判斷所查找數(shù)據(jù)屬于哪個區(qū)域。如此重復(fù)操作，直至找到數(shù)據(jù)或區(qū)域長度,1。,二分法查找算法與順序查找算法相比，可以減少查找次數(shù)，特別是對數(shù)據(jù)表很大的查找特別明顯。對于數(shù)據(jù)項為,N,的數(shù)據(jù)表，二分法查找算法的最多查找次數(shù)為：,Log,2,N。,例如當(dāng),N=1024,時，采用順序查找的平均查找次數(shù)為,1024/2=512,，而二分查找算法的最多查找次數(shù)為,Log,2,2,10,=10 。,25,為了達(dá)到對數(shù)據(jù)表的合理對分，數(shù)據(jù)表的長度應(yīng)為,2,n,。,為此，對不滿足該長度要求的數(shù)據(jù)表，將其延長至,2,n,。,