數(shù)據(jù)結(jié)構(gòu)串PPT學(xué)習(xí)教案

1、會計學(xué)1數(shù)據(jù)結(jié)構(gòu)串?dāng)?shù)據(jù)結(jié)構(gòu)串 串（或字符串），是由零個或多個字符組成的有窮序列。含零個字符的串稱為空串，用表示。 串中所含字符的個數(shù)稱為該串的長度（或串長）。 通常將一個串表示成“a1a2an”的形式。其中最外邊的雙引號本身不是串的內(nèi)容，它們是串的標(biāo)志，以便將串與標(biāo)識符（如變量名等）加以區(qū)別。每個ai（1in）代表一個字符。4.1 串的基本概念第1頁/共66頁 當(dāng)且僅當(dāng)兩個串的長度相等并且各個對應(yīng)位置上的字符都相同時，這兩個串才是相等的。 一個串中任意個連續(xù)字符組成的子序列（含空串）稱為該串的子串。例如，“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（真子串是指不包含自身

2、的所有子串）。第2頁/共66頁思考題：串和線性表有什么異同？第3頁/共66頁例4.1 問題: “abcde”有多少個真子串?解:空串?dāng)?shù):1含1個字符的子串?dāng)?shù):5含2個字符的子串?dāng)?shù):4含3個字符的子串?dāng)?shù):3含4個字符的子串?dāng)?shù):2共有1+2+3+4+5=15個子串。推廣：含有n個相互相同字符的串有n(n+1)/2個真子串。第4頁/共66頁 串的基本運算如下: StrAssign(&s,cstr)：將字符串常量cstr賦給串s，即生成其值等于cstr的串s。StrCopy(&s,t)：串復(fù)制。將串t賦給串s。StrEqual(s,t)：判串相等。若兩個串s與t相等則返回真；否則返回假

3、。StrLength(s)：求串長。返回串s中字符個數(shù)。Concat(s,t)：串連接:返回由兩個串s和t連接在一起形成的新串。SubStr(s,i,j)：求子串。返回串s中從第i（1in）個字符開始的、由連續(xù)j個字符組成的子串。第5頁/共66頁InsStr(s1,i,s2)：插入。將串s2插入到串s1的第i（1in+1）個字符中，即將s2的第一個字符作為s1的第i個字符，并返回產(chǎn)生的新串。DelStr(s,i,j)：刪除。從串s中刪去從第i（1in）個字符開始的長度為j的子串，并返回產(chǎn)生的新串。RepStr(s,i,j,t)：替換。在串s中，將第i（1in）個字符開始的j個字符構(gòu)成的子串用串

4、t替換，并返回產(chǎn)生的新串。DispStr(s)：串輸出。輸出串s的所有元素值。第6頁/共66頁4.2.1 串的順序存儲及其基本操作實現(xiàn) 4.2 串的存儲結(jié)構(gòu) 在順序串中，串中的字符被依次存放在一組連續(xù)的存儲單元里。一般來說，一個字節(jié)（8位）可以表示一個字符（即該字符的ASCII碼）。因此，一個內(nèi)存單元可以存儲多個字符。例如，一個32位的內(nèi)存單元可以存儲4個字符（即4個字符的ASCII碼）。 第7頁/共66頁串的順序存儲有兩種方法：一種是每個單元只存一個字符，這稱為非緊縮格式（其存儲密度?。?；另一種是每個單元存放多個字符，這稱為緊縮格式（其存儲密度大）。 A B C D E F G H I J

5、K L M N 1001 1002 1003 1004 1005 1006 1007 1008 1009 100a 100b 100c 100d 100e A B C D E F G H I J K L M N 1000 1001 1002 1003 非緊縮格式示例 緊縮格式示例 第8頁/共66頁對于非緊縮格式的順序串，其類型定義如下： #define MaxSize 100typedef struct char dataMaxSize; int length; SqString; 其中data域用來存儲字符串，length域用來存儲字符串的當(dāng)前長度，MaxSize常量表示允許所存儲字符串的最

6、大長度。在C語言中每個字符串以0標(biāo)志結(jié)束。第9頁/共66頁 順序串中實現(xiàn)串的基本運算如下。 （1）StrAssign(s,cstr)將一個字符串常量賦給串s，即生成一個其值等于cstr的串s。void StrAssign(SqString &s,char cstr)/s為引用型參數(shù) int i; for (i=0;cstri!=0;i+)s.datai=cstri; =i;建立順序串的算法。第10頁/共66頁（2）StrCopy(s,t)將串t復(fù)制給串s。void StrCopy(SqString &s,SqString t)/s為引用型參數(shù) int i; for (i=0;i

7、t.length;i+)s.datai=t.datai; =;第11頁/共66頁（3）StrEqual(s,t) 判串相等：若兩個串s與t相等返回真（1）；否則返回假（0）。bool StrEqual(SqString s,SqString t) bool same=true; int i; if (!=)/長度不相等時返回0same=false; else for (i=0;is.length;i+) if (s.datai!=t.datai) same=false;break; return same;第12頁/共66頁（4）StrLength(s)求串長：返回串s中字符個數(shù)。int St

8、rLength(SqString s) return ;第13頁/共66頁（5）Concat(s,t)串連接：返回由兩個串s和t連接在一起形成的新串。SqString Concat(SqString s,SqString t) SqString str; int i; =; for (i=0;is.length;i+) /s.data0.s.length-1strstr.datai=s.datai; for (i=0;it.length;i+) /t.data0.t.length-1strstr.datas.length+i=t.datai; return str;第14頁/共66頁（6）Su

9、bStr(s,i,j) 求子串：返回串s中從第i（1iStrLength(s)）個字符開始的、由連續(xù)j個字符組成的子串。參數(shù)不正確時返回一個空串。SqString SubStr(SqString s,int i,int j) SqString str; int k; =0; if (i | j)return str;/參數(shù)不正確時返回空串 for (k=i-1;ki+j-1;k+) /s.datai.i+jstrstr.datak-i+1=s.datak; =j; return str; 第15頁/共66頁（7）InsStr(s1,i,s2) 將串s2插入到串s1的第i（1iStrLength

10、(s)+1）個字符中，即將s2的第一個字符作為s1的第i個字符，并返回產(chǎn)生的新串。參數(shù)不正確時返回一個空串。SqString InsStr(SqString s1,int i,SqString s2) int j; SqString str; =0; if (is1.length+1) /參數(shù)不正確時返回空串return str; for (j=0;ji-1;j+) /將s1.data0.i-2strstr.dataj=s1.dataj; for (j=0;js2.length;j+) /s2.data0.s2.length-1strstr.datai+j-1=s2.dataj; for (j

11、=i-1;js1.length;j+) /s1.datai-1.s1.length-1strstr.datas2.length+j=s1.dataj; =s1.length+s2.length; return str;第16頁/共66頁（8）DelStr(s,i,j) 從串s中刪去第i（1iStrLength(s)）個字符開始的長度為j的子串，并返回產(chǎn)生的新串。參數(shù)不正確時返回一個空串。SqString DelStr(SqString s,int i,int j) int k; SqString str; =0; if (i | i+js.length+1) return str; /參數(shù)不正

12、確時返回空串 for (k=0;ki-1;k+) /s.data0.i-2strstr.datak=s.datak; for (k=i+j-1;ks.length;k+) /s.datai+j-1.s.length-1strstr.datak-j=s.datak; =; return str;第17頁/共66頁（9）RepStr(s,i,j,t) 在串s中，將第i（1iStrLength(s)）個字符開始的j個字符構(gòu)成的子串用串t替換，并返回產(chǎn)生的新串。參數(shù)不正確時返回一個空串。SqString RepStr(SqString s,int i,int j,SqString t) int k;

13、SqString str; =0; if (i | i+j-1) return str; /參數(shù)不正確時返回空串 for (k=0;ki-1;k+)/s.data0.i-2strstr.datak=s.datak; for (k=0;kt.length;k+) /t.data0.t.length-1strstr.datai+k-1=t.datak; for (k=i+j-1;k0) for (i=0;is.length;i+) printf(%c,s.datai);printf(n); 第19頁/共66頁例 設(shè)計順序串上實現(xiàn)串比較運算Strcmp(s,t)的算法。 解：本例的算法思路如下: （

14、1）比較s和t兩個串共同長度范圍內(nèi)的對應(yīng)字符: 若s的字符t的字符，返回1； 若s的字符t的字符，返回-1； 若s的字符=t的字符,按上述規(guī)則繼續(xù)比較。 （2）當(dāng)（1）中對應(yīng)字符均相同時，比較s和t的長度: 兩者相等時，返回0； s的長度t的長度，返回1； s的長度t的長度，返回-1。第20頁/共66頁int Strcmp(SqString s,SqString t) int i,comlen; if (t.length)comlen=;/求s和t的共同長度 else comlen=; for (i=0;it.datai)return 1;else if (s.datait.length)/s

15、treturn 1; else return -1;/sdata=cstri;r-next=p;r=p; r-next=NULL;第25頁/共66頁（2）StrCopy(s,t) 將串t復(fù)制給串s。以下采用尾插法建立復(fù)制后的鏈串s。void StrCopy(LiString *&s,LiString *t) LiString *p=t-next,*q,*r; s=(LiString *)malloc(sizeof(LiString); r=s;/r始終指向尾節(jié)點 while (p!=NULL)/將t的所有節(jié)點復(fù)制到s q=(LiString *)malloc(sizeof(LiStri

16、ng);q-data=p-data;r-next=q;r=q;p=p-next; r-next=NULL;第26頁/共66頁（3）StrEqual(s,t)判串相等：若兩個串s與t相等則返回真；否則返回假。bool StrEqual(LiString *s,LiString *t) LiString *p=s-next,*q=t-next; while (p!=NULL & q!=NULL & p-data=q-data) p=p-next;q=q-next; if (p=NULL & q=NULL)return true; elsereturn false;第27頁/

17、共66頁（4）StrLength(s)求串長：返回串s中字符個數(shù)。int StrLength(LiString *s) int i=0; LiString *p=s-next; while (p!=NULL) i+;p=p-next; return i;第28頁/共66頁（5）Concat(s,t) 串連接：返回由兩個串s和t連接在一起形成的新串。以下采用尾插法建立鏈串str并返回其地址。LiString *Concat(LiString *s,LiString *t) LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(L

18、iString); r=str; while (p!=NULL)/將s的所有節(jié)點復(fù)制到str q=(LiString *)malloc(sizeof(LiString);q-data=p-data;r-next=q;r=q;p=p-next; p=t-next;第29頁/共66頁 while (p!=NULL)/將t的所有節(jié)點復(fù)制到str q=(LiString *)malloc(sizeof(LiString);q-data=p-data;r-next=q;r=q;p=p-next; r-next=NULL; return str;第30頁/共66頁（6）SubStr(s,i,j) 求子串：

19、返回串s中從第i（1iStrLength(s)）個字符開始的、由連續(xù)j個字符組成的子串，參數(shù)不正確時返回一個空串。以下采用尾插法建立鏈串str并返回其地址。LiString *SubStr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建鏈表的尾節(jié)點 if (iStrLength(s) | jStrLength(s)return str;/參數(shù)不正確時返回空串 for (k=0;kn

20、ext;第31頁/共66頁 for (k=1;kdata=p-data;r-next=q;r=q;p=p-next; r-next=NULL; return str;第32頁/共66頁（7）InsStr(s1,i,s2) 將串s2插入到串s1的第i（1iStrLength(s)+1）個字符位置，即將s2的第1個字符作為s1的第i個字符，s2的第2個字符作為s1的第i+1個字符，等等，并返回產(chǎn)生的新串, 參數(shù)不正確時返回一個空串。以下采用尾插法建立鏈串str并返回其地址。LiString *InsStr(LiString *s,int i,LiString *t) int k; LiString

21、 *str,*p=s-next,*p1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建鏈表的尾節(jié)點 if (iStrLength(s)+1)return str; /參數(shù)不正確時返回空串第33頁/共66頁 for (k=1;kdata=p-data; r-next=q;r=q; p=p-next; while (p1!=NULL)/將t的所有節(jié)點復(fù)制到str q=(LiString *)malloc(sizeof(LiString); q-data=p1-data; r-nex

22、t=q;r=q; p1=p1-next; while (p!=NULL)/將*p及其后的節(jié)點復(fù)制到str q=(LiString *)malloc(sizeof(LiString); q-data=p-data; r-next=q;r=q; p=p-next; r-next=NULL; return str;第34頁/共66頁（8）DelStr(s,i,j) 從串s中刪去從第i（1iStrLength(s)）個字符開始的長度為j的子串，并返回產(chǎn)生的新串, 參數(shù)不正確時返回一個空串。以下采用尾插法建立鏈串str并返回其地址。LiString *DelStr(LiString *s,int i,i

23、nt j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建鏈表的尾節(jié)點 if (iStrLength(s) | jStrLength(s)return str;/參數(shù)不正確時返回空串第35頁/共66頁 for (k=0;kdata=p-data;r-next=q;r=q;p=p-next; for (k=0;knext; while (p!=NULL)/將*p及其后的節(jié)點復(fù)制到str q=(LiString *)malloc(si

24、zeof(LiString);q-data=p-data;r-next=q;r=q;p=p-next; r-next=NULL; return str;第36頁/共66頁（9）RepStr(s,i,j,t) 在串s中，將第i（1iStrLength(s)）個字符開始的j個字符構(gòu)成的子串用串t替換，并返回產(chǎn)生的新串，參數(shù)不正確時返回一個空串。以下采用尾插法建立鏈串str并返回其地址。LiString *RepStr(LiString *s,int i,int j,LiString *t) int k; LiString *str,*p=s-next,*p1=t-next,*q,*r; str=(

25、LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建鏈表的尾節(jié)點 if (iStrLength(s) | jStrLength(s) return str; /參數(shù)不正確時返回空串第37頁/共66頁 for (k=0;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next; for (k=0;knext; while (p1!=NULL)/將t的所有節(jié)點復(fù)制到str q=(LiString *)malloc(sizeof(LiString);q-data=p1-data;q-next

26、=NULL;r-next=q;r=q;p1=p1-next; while (p!=NULL)/將*p及其后的節(jié)點復(fù)制到str q=(LiString *)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next; r-next=NULL; return str;第38頁/共66頁（10）DispStr(s)輸出串s的所有元素值。void DispStr(LiString *s) LiString *p=s-next; while (p!=NULL) printf(%c,p-data);p=p-next; pr

27、intf(n);第39頁/共66頁 例 在鏈串中,設(shè)計一個算法把最先出現(xiàn)的子串a(chǎn)b改為xyz。 解：在串s中找到最先出現(xiàn)的子串“ab”，p指向data域值為a的結(jié)點，其后為data域值為b的結(jié)點。將它們的data域值分別改為x和z，再創(chuàng)建一個data域值為y的結(jié)點，將其插入到*p之后。本例算法如下:第40頁/共66頁void Repl(LiString *&s) LiString *p=s-next,*q; int find=0; while (p-next!=NULL & find=0) /查找ab子串 if (p-data=a & p-next-data=b)/找到

28、子串 p-data=x;p-next-data=z;/替換為xyz q=(LiString *)malloc(sizeof(LiString); q-data=y;q-next=p-next;p-next=q; find=1;else p=p-next; 第41頁/共66頁4.3 串的模式匹配 設(shè)有主串s和子串t，子串t的定位就是要在主串s中找到一個與子串t相等的子串。通常把主串s稱為目標(biāo)串，把子串t稱為模式串，因此定位也稱作模式匹配。 模式匹配成功是指在目標(biāo)串s中找到一個模式串t；不成功則指目標(biāo)串s中不存在模式串t。 第42頁/共66頁4.4.1 Brute-Force算法 Brute-Fo

29、rce簡稱為BF算法，亦稱簡單匹配算法，其基本思路是: 從目標(biāo)串s=“s0s1sn-1”的第一個字符開始和模式串t=“t0t1tm-1”中的第一個字符比較，若相等，則繼續(xù)逐個比較后續(xù)字符；否則從目標(biāo)串s的第二個字符開始重新與模式串t的第一個字符進行比較。依次類推,若從模式串s的第i個字符開始，每個字符依次和目標(biāo)串t中的對應(yīng)字符相等，則匹配成功,該算法返回i；否則，匹配失敗，函數(shù)返回-1。 第43頁/共66頁int indexpos(SqString str,SqString substr) int i,j,k,idx=-1; for (i=0;istr.length;i+) for (j=i,

30、k=0;str.dataj=substr.datak; j+,k+); if (k=) /注意j每次從i開始,有回溯 return(i); return(-1);算法1第44頁/共66頁int index(SqString s,SqString t) int i=0,j=0; while (i & j=);/返回匹配的第一個字符的下標(biāo) elsereturn(-1);/模式匹配不成功算法2第45頁/共66頁 例如，設(shè)目標(biāo)串s=“aaaaab”，模式串t=“aaab”。s的長度為n（n=6），t的長度為m（m=4）。用指針i指示目標(biāo)串s的當(dāng)前比較字符位置，用指針j指示模式串t的當(dāng)前比較字符

31、位置。模式匹配過程如下圖所示。 第 1 趟匹配 s=a a a a a b i=3 t=a a a b j=3 失敗,修改為 第 2 趟匹配 s=a a a a a b i=4 t=a a a b j=3 第 3 趟匹配 s=a a a a a b i=6 t=a a a b j=4 成功，返回 i-t.length=2 i=i-j+1=1 j=0 失敗,修改為 i=i-j+1=2 j=0 第46頁/共66頁 這個算法簡單，易于理解，但效率不高，主要原因是主串指針i在若干個字符序列比較相等后，若有一個字符比較不相等，仍需回溯（即i=i-j+1）。 該算法在最好情況下的時間復(fù)雜度為O(m)，即主

32、串的前m個字符正好等于模式串的m個字符。在最壞情況下的時間復(fù)雜度為O(n*m)。 第47頁/共66頁 4.3.2 KMP算法 KMP算法是、和共同提出的，簡稱KMP算法。該算法較BF算法有較大改進，主要是消除了主串指針的回溯，從而使算法效率有了某種程度的提高。第48頁/共66頁目標(biāo)串s=aaaaab，模式串t=aaab。 a a a a a b0 1 2 3 4 5a a a b0 1 2 3 BF算法下一步是從s1開始其實沒有必要從s1開始，為什么？a a a a a b0 1 2 3 4 5a a a b0 1 2 3 a a a a a b0 1 2 3 4 5a a a b0 1 2

33、3 應(yīng)有一個數(shù)組next，使next3=2第49頁/共66頁模式串中究竟是什么信息呢？a a a a a b0 1 2 3 4 5a a a b0 1 2 3 nexti是指下標(biāo)為i的字符前有多少個真子串的字符。第50頁/共66頁 所謂真子串是指模式串t存在某個k（0kj），使得t0t1tk = tj-ktj-k+1tj 成立。 例如，t= abab, 即t0t1t2t3 也就是說， “ab”是真子串。 真子串就是模式串中隱藏的信息，利用它來提高模式匹配的效率。第51頁/共66頁模式串t=“abcac”，用next數(shù)組存放這些“部分匹配”信息 。j01234tjabcacnextj-10001

34、第52頁/共66頁 歸納起來，定義nextj函數(shù)如下: maxk|0kj,且“t0t1tk-1”=“tj-ktj-k+1tj-1” 當(dāng)此集合非空時 -1 當(dāng)j=0時 0 其他情況nextj=j0123tjababnextj-1001t=“abab”對應(yīng)的next數(shù)組如下:第53頁/共66頁void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (jt.length-1) if (k=-1 | t.dataj=t.datak) j+;k+; nextj=k;else k=nextk; 由模式串t求出next值：第54

35、頁/共66頁int KMPIndex(SqString s,SqString t) int nextMaxSize,i=0,j=0; GetNext(t,next); while (i & j=);/返回匹配模式串的首字符下標(biāo) elsereturn(-1);/返回不匹配標(biāo)志KMP算法：第55頁/共66頁 設(shè)主串s的長度為n，子串t長度為m。 在KMP算法中求next數(shù)組的時間復(fù)雜度為O(m)，在后面的匹配中因主串s的下標(biāo)不減即不回溯，比較次數(shù)可記為n，所以KMP算法總的時間復(fù)雜度為O(n+m)。第56頁/共66頁 第第 1 1 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=3,j=next3=2 失敗失敗 第第 2 2 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=2,j=next2=1 失敗失敗 第第 3 3 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=1,j=next1=0 失敗失敗 第第 4 4 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=0,j=next0=- -