數(shù)據(jù)結(jié)構(gòu)章串

完成第4章自測卷有關(guān)內(nèi)容，算法設(shè)計題建議上機驗證。作業(yè)2補充：C語言中常用的串運算串比較，intstrcmp(char*s1,char*s2);//StrCompare(S,T)求串長，intstrlen(char*s);

//

StrLength(S)串連接，charstrcat(char*to,char*from)//Concat(&T,S1,S2)子串T定位，charstrchr(char*s,charc);//Index(S,T,pos)……Concat

＝concatenation，在字符串處理中,把多個短字符串合成為長字符串的操作。注：用C處理字符串時，要調(diào)用標準庫函數(shù)#include<string.h>3第三章（棧和隊）問題討論問題：①順序隊的假溢出可否通過后部元素不斷前移來解決？②順序隊的實現(xiàn)可否直接開辟數(shù)組V[n]，而不必用Q.base？③循環(huán)順序隊中，隊尾指針的移動用rear=(rear+1)%N，rear值會不會超出N？⑤教材中在進行函數(shù)定義時，有時形參用L，e，有時又用&L，&e？，區(qū)別何在？可以效率低不會雙向傳送的參量才用&打頭，見教材P8。④循環(huán)順序隊在內(nèi)存中是怎樣實現(xiàn)“循環(huán)”的？“環(huán)”在哪里？4問1：左圖中隊列容量

maxsizeN=？隊空條件:front=rear(初始化時：front=rear)隊滿條件：front=(rear+1)%N(N=maxsize)隊列長度（即數(shù)據(jù)元素個數(shù)）：L=（N＋rear－front）%N

J2J3 J1J4

J5frontrear

選用空閑單元法：即front和rear之一指向?qū)嵲?，另一指向空閑元素。

問3：在具有n個單元的循環(huán)隊列中，隊滿時共有多少個元素？n-1個6

問2：左圖中隊列長度L=？55對這4個數(shù)據(jù)元素進行的隊操作是進隊2次，出隊1次，再進隊2次，出隊1次；這時，第1次出隊得到的元素是？，第2次出隊得到的元素是？。經(jīng)操作后，最后在隊中的元素還有？個，隊尾指針指向？。解：此題用V[3]大小數(shù)組即可,即N=4。a3a2a10123N-1rearfro臆造循環(huán)隊列循環(huán)順序隊f=rr0123例：對4個數(shù)據(jù)元素進行隊操作。在進隊操作時，按a1、a2、a3、a4次序每次進入一個元素（假設(shè)隊的初態(tài)為空）。①進隊2次②出隊1次③再進隊2次④出隊1次rrff……注：r＝(r＋1)%Na22v[0]a1a2

a3a4

a1a2

r

a16遞推與遞歸的區(qū)別：遞推：由“小”到“大”遞進；遞歸：由“大”到“小”嵌套。例如：求f(n)=n!①遞推法：Fact=1;for(i=1;i<=n;i++)Fact*=i;②遞歸法（參見第1章自測卷4.2題）：longintfact(n)intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}7數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容8第4章串（String）4.2串的表示和實現(xiàn)4.3串的模式匹配算法1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運算規(guī)則5.實現(xiàn)方式4.1串類型的定義9記為：

s=‘a(chǎn)1,a2,……..,an’(n≥0)

串名串值（用‘’括起來）串中字符個數(shù)（n≥0）.n=0時稱為空串

。由一個或多個空格符組成的串。串s中任意個連續(xù)的字符序列叫s的子串;S叫主串。子串的第一個字符的序號。字符在串中的序號。串長度相等，且對應(yīng)位置上字符相等。

串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。4.1串類型的定義若干術(shù)語：串長：空白串：子串：子串位置：字符位置：串相等：隱含結(jié)束符‘/0’，即ASCII碼NUL10練1：串是由

字符組成的序列，一般記為

。練2：現(xiàn)有以下4個字符串：a=‘BEI’ b=‘JING’c=‘BEIJING’d=‘BEIJING’問：①他們各自的長度？②a是哪個串的子串？在主串中的位置是多少？a=3，b=4，c=7，d=8a是c和d的子串，在c和d中的位置都是1練3：空串和空白串有無區(qū)別？答：有區(qū)別?？沾?NullString)是指長度為零的串；而空白串(BlankString),是指包含一個或多個空白字符‘

’(空格鍵)的字符串.0個或多個S=’a1a2……an’11ADTSting{Objects:D={ai|ai∈CharacterSet,i=1,2,…，n,n≥0}Relations:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…，n}functions://有13種之多

StrAssign(&T,chars)//串賦值，生成值為chars的串T StrCompare(S,T)//串比較，若S>T，返回值大于0…StrLength(S)//求串長，即返回S的元素個數(shù)

Concat(&T,S1,S2)//串連接，用T返回S1＋S2的新串

SubString(&Sub,S,pos,len)//求S中pos起長度為len的子串

……

Index(S,T,pos)

//返回子串T在pos之后的位置

Replace(&S,T,V)//用子串V替換子串T

}ADTSting串的抽象數(shù)據(jù)類型定義（參見教材P71）最小操作子集12

設(shè)s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’。求：練習(xí)：StrLength(s)＝

StrLength(t)＝

SubString(s,8,7)=SubString(t,2,1)=Index(s,‘A’)=Index(s,t)=Replace(s,‘STUDENT’,q)=144‘STUDENT’‘O’30（s中沒有t！）’IAMAWORKER’再問：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))＝？見本章自測題，或見嚴題集4.3①134.2 串的表示和實現(xiàn)定長順序存儲表示——用一組地址連續(xù)的存儲單元存儲串值的字符序列堆分配存儲表示——用一組地址連續(xù)的存儲單元存儲串值的字符序列,但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。串的塊鏈存儲表示——鏈式方式存儲首先強調(diào)：串與線性表的運算有所不同，是以“串的整體”作為操作對象，例如查找某子串，在主串某位置上插入一個子串等。串有三種機內(nèi)表示方法：順序存儲鏈式存儲14定長順序存儲特點：用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲分配。例如：#defineMaxstrlen255//用戶可用的最大串長

typedefunsignedcharSString[Maxstrlen＋1];

SStrings;//s是一個可容納255個字符的順序串。注：一般用SString[0]來存放串長信息；C語言約定在串尾加結(jié)束符‘\0’，以利操作加速，但不計入串長；若字符串超過Maxstrlen則自動截斷（因為靜態(tài)數(shù)組存不進去）。討論：想存放超長字符串怎么辦？——靜態(tài)數(shù)組有缺陷！實現(xiàn)方式：參見教材P73編程兩例，兩串連接和求子串改用動態(tài)分配的一維數(shù)組——“堆”！15例：用順序存儲方式實現(xiàn)求子串函數(shù)SubString(&Sub,S,pos,len)Status

SubString(SString&sub,SStringS,intpos,intlen){if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;//pos不合法則告警

Sub[1……len]=S[pos……pos+len-1];Sub[0]=len;returnOK;}將串S中從第pos個字符開始長度為len的字符序列復(fù)制到串Sub中（注：串Sub的預(yù)留長度與S一樣）s=‘a(chǎn)1,a2,……..,an’n＝串長poslen16思路：利用malloc函數(shù)合理預(yù)設(shè)串長空間。特點：

若在操作中串值改變，還可以利用realloc函數(shù)按新串長度增加(堆砌)空間。Typedefstruct{ char*ch;//若非空串,按串長分配空間;否則ch=NULL intlength;//串長度}HString堆分配存儲特點：仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。約定：所有按堆存儲的串，其關(guān)鍵信息放置在：17StatusStrInsert(HString&S,intpos,HStringT){

//在串S的第pos個字符之前（包括尾部）插入串Tif(pos<1||pos>S.length+1)returnERROR;//pos不合法則告警

if(T.length){

//只要串T不空，就需要重新分配S空間，以便插入Tif(!（S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))

))exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i)//為插入T而騰出pos之后的位置

S.ch[i+T.length]=S.ch[i];//從S的pos位置起全部字符均后移

S.ch[pos-1…pos+T.length-2]=T.ch[0…T.length-1];//插入T，略/0

S.length+=T.length;//刷新S串長度} returnOK;}//StrInsert例：用“堆”實現(xiàn)串插入操作(教材P75)18將字符串chars賦予“堆”T中StatusStrAssign(HString&T,char*chars){ if(T.ch)free(T.ch); for(i=0,c=chars;c;++i,++c);//求串長度

if(!i){T.ch=NULL;T.length=0;} else{ if(!(T.ch=(char*)malloc(i*sizeof(char)))) exit(OVERFLOW); T.ch[0..i-1]=chars[0..i-1]; T.length=i; } ReturnOK;}//StrAssign指針變量C也可以自增！意即每次后移一個數(shù)據(jù)單元。附：堆分配存儲表示直到終值為“假”停止，串尾特征是‘/0’＝NUL=019討論：法1存儲密度為

；法2存儲密度為

；顯然，若數(shù)據(jù)元素很多，用法2存儲更優(yōu)—稱為塊鏈結(jié)構(gòu)鏈式存儲特點：用鏈表存儲串值，易插入和刪除。法1：鏈表結(jié)點（數(shù)據(jù)域）大小取1法2：鏈表結(jié)點（數(shù)據(jù)域）大小取n(例如n=4)1/29/15=3/5

A

B

C

I

NULLheadheadABCD

EFGH

I###NULL20#defineCHUNKSIZE

80

//可由用戶定義的塊大小typedefstructChunk{//首先定義結(jié)點類型

charch[CHUNKSIZE];//結(jié)點中的數(shù)據(jù)域

structChunk*next;//結(jié)點中的指針域}Chunk;塊鏈類型定義：例略typedefstruct{//其次定義用鏈式存儲的串類型

Chunk*head;//頭指針

Chunk*tail;//尾指針

intcurLen;//結(jié)點個數(shù)

}Lstring;//串類型只用一次，前面可以不加Lstring21再次強調(diào)：串與線性表的運算有所不同，是以“串的整體”作為操作對象，例如查找某子串，在主串某位置上插入一個子串等。這類操作中均涉及到定位問題，稱為串的模式匹配。它是串處理系統(tǒng)中最重要的操作之一。算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）

——即如何實現(xiàn)Index(S,T,pos)函數(shù)（見教材P71）4.3串的模式匹配算法模式匹配(PatternMatching)即子串定位運算（Index函數(shù)）。初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(s)操作結(jié)果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0。注：S稱為被匹配的串，T稱為模式串。若S包含串T，則稱“匹配成功”。否則稱“匹配不成功”。22①BF算法設(shè)計思想：將主串的第pos個字符和模式的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串的下一字符（pos+1）起，重新與第一個字符比較。BF算法

（又稱古典或經(jīng)典的、樸素的、窮舉的）

KMP算法（特點：速度快）算法

種類：直到主串的一個連續(xù)子串字符序列與模式相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值0.S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’pos=523IntIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i,++j}//繼續(xù)比較后續(xù)字符

else{i=i-j+2;j=1;}//指針回溯到下一首位，重新開始匹配

}if(j>T[0])returni-T[0];//子串結(jié)束，說明匹配成功

elsereturn0;}//Index②BF算法的實現(xiàn)—即Index（）操作的實現(xiàn)

（見教材P79）

S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’pos=5相當(dāng)于子串向右滑動一個字符位置匹配成功后指針仍要回溯！因為要返回的是被匹配的首個字符位置。ij24例：

S=‘a(chǎn)babcabcacbab’，T=‘a(chǎn)bcac’，pos=1，

求：串T在串S中第pos個字符之后的位置。

解：因pos=1，可利用演示系統(tǒng)看BF算法執(zhí)行過程此題的BF算法：intIndexBF(SstringS,SstringT){i=1;j=1;while(i<=s[0]&&j<=T[0]){if(s[i]=t[j]){++i;++j;}else{i=i-j+2;j=1;}if(j>T[0])returni-T[0];elsereturn0;}討論：若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*m＝O(n*m)最惡劣情況是：主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！BF匹配算法的最壞時間復(fù)雜度但一般情況下BF算法的時間復(fù)雜度為O(n+m)25討論：若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*m＝O(n*m)最惡劣情況是：主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位各比較了m次，再加上最后m位也各比較了1次，所以總次數(shù)為：(n-m)*m+m＝(n-m+1)*m一般的情況是：O(n+m)

要從最好到最壞情況統(tǒng)計總的比較次數(shù)，然后取平均。BF算法的時間復(fù)雜度最好的情況是：一配就中！26KMP算法（特點：速度快）①

KMP算法設(shè)計思想②

KMP算法的推導(dǎo)過程③KMP算法的實現(xiàn)

（關(guān)鍵技術(shù):計算next[j]）④KMP算法的時間復(fù)雜度27能否利用已經(jīng)部分匹配的結(jié)果而加快模式串的滑動速度？能！而且主串S的指針i不必回溯！可提速到O(n+m)！例：①KMP算法設(shè)計思想：(參見教材P80-84）S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)b

abca

bcacbab’T=‘a(chǎn)bca

c’S=‘a(chǎn)b

abca

bcacbab’T=‘a(chǎn)

bcac’Index_kmp的返回值應(yīng)為i=6需要討論兩個問題：①如何“記憶”部分匹配結(jié)果？②如何由“記憶”結(jié)果計算出主串S第i個字符應(yīng)該與模式T中哪個字符再比較？即確定模式T中的新比較起點k.iiikk

a

b

aa

b

c演示程序28②

KMP算法的推導(dǎo)過程：（見教材P81）抓住部分匹配結(jié)果的兩個特征：兩式聯(lián)立可得：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’注意：j為當(dāng)前已知的失配位置，我們的目標是計算新起點k，僅剩一個未知數(shù)k，理論上已可解，且k僅與模式串T有關(guān)！則S前i-1～i-(k-1)位＝T的j-1～j-(k-1)位即(4-3）式含義S=‘a(chǎn)babca

b

cacbab’T=‘a(chǎn)

b

cac’ik則T的k-1～1位＝S前i-1～i-(k-1)位即(4-2）式含義ikjS=‘a(chǎn)babca

bcacbab’T=‘a(chǎn)bca

c’剛才肯定是在S的i處和T的第j字符處失配設(shè)目前應(yīng)與T的第k字符開始比較29②

KMP算法的推導(dǎo)過程(續(xù)）：根據(jù)模式串T的規(guī)律：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’和已知的當(dāng)前失配位置j

，可以歸納出計算新起點

k的表達式。令k

=

next[j]，則next[j]＝0當(dāng)j＝1時max{

k

|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況討論：①

next[j]有何意義？一旦失配，應(yīng)從模式串T中第next[j]個字符開始與S的失配點i

重新匹配!②next[j]怎么求？后面會舉例（參見教材P81）30第一步，先把模式T所有可能的失配點j所對應(yīng)的next[j]計算出來；第二步：執(zhí)行定位函數(shù)index_kmp（與BF算法模塊非常相似）③KMP算法的實現(xiàn)—即Index()操作的實現(xiàn)

（見教材P82）

IntIndex_KMP(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i,++j}//不失配則繼續(xù)比較后續(xù)字符

else{j=next[j];}//S的i指針不回溯，從T的k位置開始匹配

}if(j>T[0])returni-T[0];//子串結(jié)束，說明匹配成功

elsereturn0;}//Index_KMP31怎樣計算模式T所有可能的失配點j所對應(yīng)的next[j]？例：模式串T：abaabcac

可能失配位j：12345678新匹配位next[j]:next[j]＝0當(dāng)j＝1時max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況01122312討論：j=1時,next[j]≡0；因為屬于“j=1”;j=2時,next[j]≡1；因為屬于“其他情況”；剛才已歸納：j=3時,k={2}，只需查看‘T1’=‘T2’；j=4時,k={2，3}，要查看‘T1’=‘T3’和‘T1T2’=‘T2T3’j=5時,k={2，3，4}，要查看‘T1’=‘T4’、‘T1T2’=‘T3T4’和‘T1T2T3’=‘T2T3T4’以此類推，可得后續(xù)next[j]值。演示程序32討論：

next[j]有何物理意義？next[j]函數(shù)表征著模式中兩段字符之間相匹配的最大子串的長度（除串本身外）?？梢姡Ｊ街邢嗨撇糠衷蕉?，則next[j]函數(shù)越大，它既表示模式T字符之間的相關(guān)度越高，也表示j位置以前與主串部分匹配的字符數(shù)越多。即：next[j]越大，模式串向右滑動得越遠，與主串進行比較的次數(shù)越少，時間復(fù)雜度就越低。next[j]＝max{

k

|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}模式串從首位往右直到K-1位模式串從j的前一位往左直到K-1位想一想：如果主串和模式均為二進制碼流，用KMP算法效果如何？33討論兩個有關(guān)next[j]的問題：①怎樣簡捷計算next[j]？可用遞推法編程實現(xiàn)?。▍⒁奝83簡捷算法）計算next[j]的時間為O(m)voidget_next(SStringT,int&next[]){//next函數(shù)值存入數(shù)組nexti=1;next[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];}}//get_nextvoidget_nextval(SStringT,int&nextval[]){//next函數(shù)修正值存入數(shù)組nextvali=1;nextval[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;If(T[i]!=T[j])nextval[i]=j;elsenextval[i]=nextval[j];

}elsej=nextval[j];}}//get_nextval②next[j]是否完美無缺？答：未必，例如當(dāng)S=‘a(chǎn)baaaab’,T=‘a(chǎn)aaab’時仍有多余動作（參見P84改進算法,

稱為nextval[j]）34④KMP算法的時間復(fù)雜度

因為計算next[j]的時間為O(m);