算數(shù)提高課件ds 2 3字符串

第二章線性表—字符串數(shù)據(jù)結構與算法張路

內(nèi)容提要字符串及其運算字符串的存儲表示順序存儲鏈式存儲模式匹配串操作應用示例基本概念-1字符串：簡稱為串，是零個或多個字符組成的有限序列。一般記為：s=“s0s1…sn-1”（n≥0）,s為串名，每個字符si(0<=i<=n-1)可以是字母、數(shù)字或其它字符一般用一對雙引號“”將串括起來，避免和其他變量混淆

串的長度：一個字符串中字符個數(shù)空串：長度為零的字符串，記為s=“”[注意與空格串“”的區(qū)別]

基本概念-2主串與子串：字符串s1中任意個連續(xù)字符組成的子序列s2被稱為s1的子串，稱s1為s2的主串。假設S1和S2是兩個串

S1=“a1a2…an”S2=“b1b2…bm”，其中ai和bj代表字符，0≤m≤n。如果存在整數(shù)i（0≤i≤n-m），使得

bj=ai+j

（j=1，2，…，m），則稱串S2是串S1的“子串”，又稱S1包含S2特別地,空串是任意串的子串，任意串s都是s本身的子串除s本身之外,s的其他子串稱為s的真子串.基本概念-3字符在串中的位置：該字符在串中第一次出現(xiàn)的位置。

子串在主串中的位置：該子串的第一個字符在主串中出現(xiàn)的字符序號。

兩個字符串相等的充分必要條件：長度相等，且對應位置上字符相同。字符串示例A=“123”B=“ABBABBC”C=“BB”D=“BB”E=“”字符字符(char)：組成字符串的基本單位在C中單字節(jié)（8bits）采用ASCII碼對128個符號（字符集charset）進行編碼字符的編碼順序為了字符串間比較和運算的便利，字符編碼表一般遵循約定俗成的“偏序編碼規(guī)則”。字符偏序：根據(jù)字符的自然含義，某些字符間兩兩可以比較次序，其實大多數(shù)情況下就是字典序。字符串字符串的邏輯結構與線性表的區(qū)別串的數(shù)據(jù)對象約束為字符集；線性表的基本操作大多以“單個元素”為操作對象，而串的基本操作通常以“串的整體”作為操作對象。字符串的基本運算定義抽象數(shù)據(jù)類型String的運算如下:創(chuàng)建一個空串;判斷一個串是否為空串，若為空串，則返回1，否則返回0；求一個串的長度；將兩個串拼接在一起構成一個新串在串s中求從第i個字符開始連續(xù)j個字符所構成的子串如果串S2是S1的子串，則可求串S2在串S1中第一次出現(xiàn)的位置內(nèi)容提要字符串及其運算字符串的存儲表示順序存儲鏈式存儲模式匹配串操作應用示例字符串的存儲表示字符串仍是一種特殊的線性表，其每個結點僅由一個字符組成，線性表的存儲方法同樣適用于字符串。在選擇存儲結構時，應根據(jù)不同情況選擇合適的存儲表示。例如，插入、刪除時，采用順序結構不方便，但訪問字符時（尤其連續(xù)多個）非常容易。順序串類型的定義字符數(shù)組存放串

#defineMAXNUM50<串允許的最大字符個數(shù)>structSeqString{ charc[MAXNUM]; /*字符數(shù)組*/ intn; /*串長n<=MAXNUM*/};typedefstructSeqString*PSeqString;順序串示例s=“abcdefg”s.n=7s.c數(shù)組元素下標abcdefg0123456MAXNUM-1順序存儲結構基本運算PSeqStringCreateNULLStr_Seq();

PSeqStringConcatStr_Seq(PSeqStrings1,PSeqStrings2);

PSeqStringSubStr_Seq(PSeqStrings,inti,intj);

voidDelSubStr_Seq(PSeqStrings,inti,intj);

voidInsertSubStr_Seq(PSeqStrings,inti,PSeqStringr);

intStrLen_Seq(PSeqStrings);

intLocSubStr_Seq(PSeqStrings,PSeqStringr);內(nèi)容提要字符串及其運算字符串的存儲表示順序表示鏈接表示模式匹配串操作應用示例字符串的鏈接存儲

鏈接存儲

C語言描述:structStrNode;/*鏈串的結點*/typedefstructStrNode*PStrNode;/*結點指針類型*/structStrNode/*鏈串的結點結構*/{ charc; PStrNodelink;};typedefstructStrNode*PLinkString;/*鏈串的類型*/sabcd^sabcd^不帶頭結點帶頭結點abcds循環(huán)鏈表

串的鏈接表示示例串s=“abcdef”，按單鏈表存儲時，定義s為指向鏈串的指針

PLinkStrings；單鏈表表示循環(huán)表表示ss鏈接存儲結構基本運算PLinkStringCreateNULLStr_link(void);PLinkStringConcatStr_link(PLinkStringr1,PLinkStringr2);

PLinkStringSubStr_link(PLinkStrings,inti,intj);

voidDelSubString_link(PLinkStringr,inti,intj);

intInsertSubStr_link(PLinkStringr,inti,PLinkStringr1);

intLocSubStr_link(PLinkStringr1,PLinkStringr2);

intLenStr_link(PLinkStrings);

Notice上述鏈接存儲結構雖然操作實現(xiàn)簡單，但存儲密度太低。改進辦法：每個結點存放多個字符。改進后雖然提高了存儲密度，但操作實現(xiàn)變的復雜。每個結點存放多少個字符？最后結點存放字符的個數(shù)與前面的不同，操作實現(xiàn)需要特殊處理。存儲密度=串值所占的存儲位/實際分配的存儲位串值的鏈式存儲方式ABCDEFGHI###^ABI^C…存儲密度小,運算處理方便,但是存儲占用量大.C對字符串支持把串中的字符順序地存儲在一組地址連續(xù)的存儲單元中，最后一個字符后面可加一個特定的結束標志（‘\0’）該結束標志占用存儲空間但不計入串長。<string.h>例如：charS[M];定義了字符串變量

e.g.,chars1[7]=“value”;串的結束標記：'\0'‘\0’是ASCII碼中8位BIT全0碼，又稱為NULL符，專門用來作結束標志字符串的實際長度為M-1C的字符串函數(shù)串長函數(shù)

intstrlen(char*s);串復制

char*strcpy(char*s1,char*s2);串拼接

char*strcat(char*s1,char*s2); char*strncat(char*str1,constchar*str2, size_tn);串比較(注意)

intstrcmp(char*s1,char*s2);C的字符串函數(shù)定位函數(shù)

char*strchr(char*s,charc);char*strrchr(char*s,charc);子串

char*strstr(constchar*str1,constchar*str2);……

內(nèi)容提要字符串及其運算字符串的存儲表示順序存儲鏈式存儲模式匹配串操作應用示例問題定義設有兩個串t和p:t=t0t1…tn-1，p=p0p1…pm-1,其中1<m<=n(通常m<<n)模式匹配的目的是在t中找出和p相同的子串。此時，t稱為“目標”，而p稱為“模式”。模式匹配的結果有兩種：匹配成功：t中存在等于p的子串，返回子串在t中的位置匹配失?。悍祷匾粋€特定的標志（如-1）。兩種方法模式匹配是一個比較復雜的字符串操作，用于在大文本（諸如，句子、段落，或書本）中定位（查找）特定的模式對于大多數(shù)的算法而言，匹配的主要考慮在于其速度和效率下面的討論是基于字符串的順序存儲結構進行。樸素的模式匹配(BruteForce)方法無回溯的模式匹配Knuth-Morris-Pratt(KMP)方法樸素的模式匹配思想用p中的字符依次與t中的字符比較：

t0t1…tm-1…tn-1p0p1…pm-1p0p1…pm-1t0t1t2…tm…tn-11,如果t0=p0，t1=p1，…，tm-1=pm-1，則匹配成功;2,否則，必有某個i（0≤i≤m-1），使得ti≠pi

，將p右移一個字符，用p中字符從頭開始與t中字符依次比較。如此反復執(zhí)行，直到下面兩種情況之一：樸素的模式匹配(續(xù))到達某步時，ti=p0，ti+1=p1，…，ti+m-1=pm-1，匹配成功，subStr(t,i,m)即是找到的第一個與模式p相同的子串；將p移到無法與t繼續(xù)比較為止，則匹配失敗樸素的模式匹配算法intindex(PSeqStringt,PSeqStringp)

/*返回p所指的串的第一個元素在t所指的串中的序號*/{inti=0,j=0; while(i<p->n&&j<t->n) //反復比較

{if(p->c[i]==t->c[j]) {i++;j++;}//繼續(xù)匹配下一個字符

else {j=j-i+1;i=0;}//主串、子串i、j值回溯，重新開始

}if(i>=p->n)return(j-p->n+1); //匹配成功，返回位置

elsereturn-1; //匹配失敗}example-1

下標i01234567891011121314151617目標taabcbabcaabcaababc模式pabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababc算法時間效率分析匹配失敗最壞情況：每趟匹配皆在最后一個字符不等，且有n-m+1趟匹配(每趟比較m個字符），共比較m*(n-m+1)次，由于m<<n，因此最壞時間復雜度O(n*m)。最好情況：n-m+1次比較[每趟只比較第一個字符]。匹配成功最好情況：m次比較。最壞情況：與匹配失敗的最壞情況相同。綜上討論，樸素模式匹配算法的時間復雜度為O(m*n)。進一步的分析樸素模式匹配算法簡單，容易理解，但效率不高。主要原因是：一旦比較不等，p右移一個字符并且下次從p0開始重新進行比較，對于目標t，存在回溯現(xiàn)象。何減少或避免回溯？當某次匹配失敗時，下次匹配時是否可以利用前面已經(jīng)比較的結果？p0≠p1可以推出p0≠t1，所以p右移一位后的比較一定不等；p0=p2，可以推出p0≠t2因此，可以由第1趟匹配直接跳過2、3趟匹配進入第4趟匹配，此時消除了回溯問題，提高了模式匹配的時間效率。無回溯的模式匹配算法問題描述在前例中，一旦pi

與tj比較不等，有：SubStr_Seq(p,0,i-1)=SubStr_Seq(t,j-i+1,i-1)pi≠tj目標要能立即確定p右移的位數(shù)和繼續(xù)（無回溯）比較的字符，也就是說應該用p中的哪個字符和tj進行比較？設這個字符為PK,下標K與i密切相關，因此可表示為next[i]，則無回溯的模式匹配算法可實現(xiàn)為：無回溯的模式匹配算法/*已知next數(shù)組，返回p所指的串的第一個元素在t所指的串中的序號*/intpMatch(PSeqStringt,PSeqStringp,int*next){ inti=0,j=0;while(i<p->n&&j<t->n) //反復比較

{if(i==-1||p->c[i]==t->c[j]){i++;j++;}//繼續(xù)匹配下一個字符

elsei=next[i]; //j不變，i后退

}

//匹配成功，返回p中第一個字符在t中的位置

if(i>=p->n)return(j-p->n+1) elsereturn0; //匹配失敗}next[i]如何計算？在上述程序中，next[i]表示與i對應的k值：若next[i]≥0，表示一旦匹配過程中pi與tj比較不等，可用p中以next[i]為下標的字符與tj進行比較。若next[i]=-1，則表示p中任何字符都不必在與tj進行比較，下次比較從tj+1與p0開始。D.E.Knuth、V.R.Pratt和J.H.Morris同時發(fā)現(xiàn)：Pk的k值僅依賴于模式p本身前i個字符的組成，而與目標t無關。Next數(shù)組計算－1在p與任意的目標串t匹配時，若發(fā)現(xiàn)tj≠pi，則意味著p0、p1、…、pi-1已經(jīng)與t中對應的字符進行過比較，而且是相等的，否則輪不到tj與pi的比較，因此下面兩個圖是等價的。t0…tj-i-1tj-i…tj-1tj…p0…pi-1pi…t0…tj-i-1p0…pi-1tj…p0…pi-1pi…然后把p右移若干位，tj以前的比較工作相當于用p0…pi-1的一個前綴與它的一個長度相同的后綴進行比較，顯然比較的結果由p本身決定。t0…tj-i-1p0…pi-k…pi-1tj…p0…pk-1pk…?前綴后綴Next數(shù)組計算－2Next數(shù)組計算－3因此，可以在p0…pi-1中求出相同并且最大的前綴和后綴的長度k(0≤k<i-1)。此時，相同的前后綴恰好對齊，pk與tj也對齊，可以從pk和tj開始向右比較。不用去比較這一對前后綴，因為它們是相等的。通過上面分析，得到了初步的next計算方法：

(1)next[i]=p0…pi-1中最大相同的前綴和后綴的長度k;(2)當i=0時，令next[i]=-1;

顯然，對于任意i(0≤i<m)，有next[i]<i。Next數(shù)組計算－4假定已經(jīng)計算得到next[i],那么next[i+1]=?

對于next[i]=k，有：p0…pk-1=pi-k…pi-1(1)如果pk=pi，則有：p0…pk-1pk=pi-k…pi-1pi

next[i+1]=k+1=next[i]+1

p0…………

…pi-kpi-k+1…

pi-1

pip0p1…

pk-1pkpk+1Pi+1(2)如果pk≠pi，此時有：p0…pk-1=pi-k…pi-1

與模式匹配的思路一樣，應當將模式串往右滑動到模式串的第next[k]個字符與pi進行比較，即k=next[k]。如果pk≠pi則繼續(xù)滑動。Next數(shù)組計算－算法makeNext(PSeqStringp,int*next){inti=0,k=-1;next[0]=-1;while(i<p->n-1)/*計算next[i+1]*/{ while(k>=0&&p->c[i]!=p->c[k])k=next[k];/*p0…pi中最大的相同的前后綴長度k*/i++;k++;

next[i]=k;}}下標i012345678piabcaababck-100011212next[i]-100011212Next數(shù)組的計算－算法’makeNext(PSeqStringp,int*next){inti,k;next[0]=-1;for(i=0;i<p->n-1;i++)/*計算next[i+1]*/{ k=next[i]; while(k>=0&&p->c[i]!=p->c[k])k=next[k];/*p0…pi中最大的相同的前后綴長度k*/next[i+1]=k+1;}}下標i012345678piabcaababck-100011212next[i]-100011212Next數(shù)組計算按照上述方法求得的next數(shù)組已經(jīng)可以用于無回溯模式匹配中，但是還可以進一步改進。例如，若求得k后，有pk=pi，則當pi≠tj時,pk與tj的比較必然不等，應該繼續(xù)右移，用pnext[k]與tj比較。修改上面next計算的步驟如下：

(1)求p0…pi-1中最大相同的前綴和后綴的長度k;(2)if(pk==pi)next[i]=next[k];elsenext[i]=k;Next數(shù)組的計算－算法改進makeNext(PSeqStringp,int*next){inti=0,k=-1;next[0]=-1;while(i<p->n-1)/*計算next[i+1]*/{ while(k>=0&&p->c[i]!=p->c[k])k=next[k];/*p0…pi中最大的相同的前后綴長度k*/i++;k++;if(p->c[i]==p->c[k])next[i]=next[k];elsenext[i]=k;}}下標i012345678piabcaababc最大相同前后綴長度k-100011212Pk與pi比較≠≠=≠=≠==next[i]-100-110200Next數(shù)組的計算－算法改進’makeNext(PSeqStringp,int*next){inti,k;next[0]=-1;for(i=0;i<p->n-1;i++)/*計算next[i+1]*/{ k=next[i]; while(k>=0&&p->c[i]!=p->c[k])k=next[k];/*p0…pi中最大的相同的前后綴長度k*/if(p->c[i+1]==p->c[k+1])next[i+1]=next[k+1];elsenext[i+1]=k+1;}}下標i012345678piabcaababc最大相同前后綴長度k-100011212Pk與pi比較≠≠=≠=≠==next[i]-100-110200example-2

下標i01234567891011121314151617目標taabcbabcaabcaababc模式pabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababct=“aabcbabcaabcaababc”,n=18p=“abcaababc”,m=9-100-110200時間復雜性分析在無回溯的模式匹配算法中j值只增不減，由于j的初值為0，循環(huán)過程中保持j<n,所以循環(huán)體中j++語句的執(zhí)行次數(shù)不超過n,從而i++的執(zhí)行次數(shù)也不超過n。i的初始值為0，唯一使i減少的語句是i=next[i]。計算next數(shù)組的時間復雜度為O(m)[m為模式串長度］綜合上述情況，無回溯模式匹配的時間復雜度為O(m+n)。內(nèi)容提要字符串及其運算字符串的存儲表示順序存儲鏈式存儲模式匹配串操作應用示例1.文本編輯程序文本編輯程序?qū)嵸|(zhì)上就是一個字符串的操作應用?？梢园颜麄€文本看成是一個字符串，這樣文本的插入、刪除、查找、替換等就是字符串的各種操作的實現(xiàn)。文本編輯程序通常設立頁索引表、行索引表進行管理，并且附設頁指針、行指針和字符指針指示當前正在編輯的頁、行和字符。例如：插入、刪除行，首先需要通過頁索引表確定插入、刪除操作的頁，然后對該頁索引表進行操作。如果是插入、刪除字符，則除了確定頁之外，還需要通過行索引表確定操作的行，然后通過字符指針完成插入、刪除字符的操作，當然此時還需要修改行的長度等文本頁1頁2…頁n行1行2…行m字符1字符2…字符k頁指針行指針字符指針步驟：（1）輸入一本書名，提取關鍵詞（需要與常用詞表對比）（2）在索引表中查找該關鍵詞是否存在。如不存在，則加入該關鍵詞（按照字典有序原則進行，并建立書號索引；如存在，這在該關鍵詞項中加入書號索引。（3）繼續(xù)輸入下一本書名，重復上述操作。圖書檢索中，通常要建立“關鍵詞-書號索引表”：書號書名005010023034050067ComputerDataStructuresIntroductiontoDataStructuresFundamentalofDataStructuresTheDesignandAnalysisofComputerAlgorithmsIntroductiontoNumericalAnalysisNumericalAnalysis關鍵詞書號索引algorithms