1、第4章字符串的結(jié)構(gòu)分析與應(yīng)用 學(xué)習(xí)目標(biāo) 了解串的基本概念和基本運算。 熟練掌握串的順序存儲結(jié)構(gòu)。 掌握串的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 熟練掌握串的匹配和算法設(shè)計與實現(xiàn)。4.1串的定義及其運算 一、串的基本概念 1、串(string)是零個或多個字符組成的有限序列。 4、串的表示方法：S=“a1a2an” ，其中S是串名；雙引號括起的字符序列是串值； 5、主串和子串 設(shè)A和B分別為A=This is a string B=is 若A是主串，則B是A的子串。2、空串(string)是長度為零的串，它不包含任何字符。例如： 3、空白串(string)是由一個或多個空格組成的串。 例如： 4.1串的定義及其運算

2、二、串的基本運算 1、求串長 int strlen(char *s); 2、串復(fù)制 char *strcpy(char *to,char *from);/將from串復(fù)制到to串中 3、串聯(lián)接 char *strcat(char *to,char *from);/將from聯(lián)接到to末尾例如：printf(%d,strlen(s1);/輸出3例如：strcpy(s3,s1); /s3=www,s1串不變例如：strcat(s1,s2); /s1=4.1串的定義及其運算 二、串的基本運算 4、串比較 int strcmp(char *s1,char *s2); 比較s1和s2的大小， 當(dāng)s1s2

3、和s1=s2時，分別返回 小于0、大于0和等于0的值例如： result=strcmp(that,this); /result04.2串的存儲結(jié)構(gòu) 一、串的順序存儲結(jié)構(gòu) 1、串的順序存儲就是把串所包含的字符序列依次存入連續(xù)的 存儲單元中去，也就是用向量來存儲串。 2、順序串的存儲結(jié)構(gòu)類型定義如下： typedef struct char chMAXLEN; int len; SeqString; 01234DATA04.2串的存儲結(jié)構(gòu) 二、串的鏈?zhǔn)酱鎯Y(jié)構(gòu) 1、串的鏈?zhǔn)酱鎯褪遣捎脝捂湵矸绞絹泶鎯Υ?。方便插?和刪除操作。 2、鏈串的存儲結(jié)構(gòu)類型定義如下： typedef struct no

4、de char data; struct node *next; LinkStrNode;4.2串的存儲結(jié)構(gòu) 三、子串的定位運算 1、串模式匹配或串匹配的定義：找子串在主串中首次出現(xiàn)的位置。子串定位運算又稱串的模式匹配或串匹配。假設(shè)T 為目標(biāo)串，P為模式串，且不妨設(shè)： T=t0t1t2tn-1 P=p0p1p2pm-1(0mn)串匹配就是對于合法的位置（又稱合法的位移）0in-m，依次將目標(biāo)串中的子串 titi+1ti+m-1和模式串p0p1p2pm-1進行比較。 4.2串的存儲結(jié)構(gòu) 三、子串的定位運算 2、順序串匹配具體算法如下：int StrMatch(SeqString T,SeqString P) int i,j,k; int m=P.len,n=T.len; for(i=0;i=n-m;i+)/0=i=n-m是合法的位移 j=0;k=i; while(jm&T.chk=P.chj)k+;j+; if(j=m)