3 字符串 3.1 字符串及其抽象數(shù)據(jù)類型字符串及其抽象數(shù)據(jù)類型3.2 字符串的實(shí)現(xiàn)字符串的實(shí)現(xiàn) 3.3 模式匹配模式匹配 字符串：簡(jiǎn)稱串，是特殊的線性表，其特殊性主要在于表中的每個(gè)元素是一個(gè)字符，以及由此而要求的一些特殊操作。 3.1 字符串及其字符串及其抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型3.1.1 基本概念基本概念 長(zhǎng)度：一個(gè)串中包括的字符個(gè)數(shù)。長(zhǎng)度為零的串稱為空串。 子串：字符串s1中任意個(gè)連續(xù)的字符組成的子序列s2被稱為是s1的子串，而稱s1是s2的主串。 位置：子串在主串中的位置是以子串的第一個(gè)第一個(gè)字符在主串中的字符序號(hào)(下標(biāo)+1)。 相等：兩個(gè)串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符都 相等。ADT3.1 字符串的抽象數(shù)據(jù)類型ADT String isoperationsstring createNullStr(void) 創(chuàng)建一個(gè)空串 int isNullstr(String s) 判斷一個(gè)串是否為空串 int length(String s) 求一個(gè)串的長(zhǎng)度 String concat(String s1, String s2) 將兩個(gè)串拼接在一起構(gòu)成一個(gè)新串 String subStr(String s, int i, int j) 在串s中，求從串的第i個(gè)字符開始連續(xù)j個(gè)字符所構(gòu)成的子串 int index(String s1,String s2) 求串S2在串S1中第一次出現(xiàn)的位置位置End ADT String3.1.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型3.2.1 順序表示順序表示 3.2.2 鏈接表示鏈接表示 3.2.1 順序表示順序表示struct SeqString /* 順序串的類型 */ int MAXNUM /* 串允許的最大字符個(gè)數(shù) */ int n;/* 串的長(zhǎng)度，nMAXNUM */ char *c; typedef struct SeqString *PSeqString; 順序串的定義 例 算法算法3.1 3.1 創(chuàng)建空順序串創(chuàng)建空順序串 PSeqString createNullStr_seq( intPSeqString createNullStr_seq( int m ) m ) PSeqString pstr=new struct SeqString PSeqString pstr=new struct SeqString; ;/申請(qǐng)串空間申請(qǐng)串空間 if (pstrif (pstr!=NULL)!=NULL) pstr-c=new charmpstr-c=new charm;if(pstr-c) pstr-n=0; pstrif(pstr-c) pstr-n=0; pstr-MAXNUM=m;-MAXNUM=m; return (pstr return (pstr);); else delete pstrelse delete pstr; ; printf(“Out printf(“Out of space! n”); of space! n”); return NULL; return NULL; 算法算法3.2 3.2 求順序表示的串的子串求順序表示的串的子串PSeqString subStr_seq(PSeqString s,int i,intPSeqString subStr_seq(PSeqString s,int i,int j) j)/ / 求從求從s s所指的順序串中第所指的順序串中第i(ii(i0)0)個(gè)字符開始連續(xù)取個(gè)字符開始連續(xù)取j j個(gè)字符所構(gòu)成的子串個(gè)字符所構(gòu)成的子串 PSeqString s1; int PSeqString s1; int k; k; s1 = createNullStr_seq(j s1 = createNullStr_seq(j);); / /* * 創(chuàng)建一空串創(chuàng)建一空串 * */ / if (s1=NULL) return (NULL); if (s1=NULL) return (NULL); if ( i0 & in & j0 ) if ( i0 & in & j0 ) if ( s-nn-i+1; if ( s-nn-i+1; / /* *若從若從i i開始取不了開始取不了j j個(gè)字符個(gè)字符, ,則能取幾個(gè)就取幾個(gè)則能取幾個(gè)就取幾個(gè)* */ / for (k=0;kj;k+) for (k=0;kcks1-ck=s-ci+k-1;=s-ci+k-1; s1-n=j; s1-n=j; return(s1); return(s1); struct StrNode ;typedef struct StrNode *PStrNode; struct StrNode charc;pStrNodelink; ;typedef struct StrNode *LinkString;3.2.2 鏈接表示鏈接表示 鏈接串的定義 a b f .(a) 不帶頭結(jié)點(diǎn) a b f.(b) 帶頭結(jié)點(diǎn)ss a b f . 圖3. 2 串的鏈接表示例s(c) 循環(huán)表表示 算法算法3.3 3.3 創(chuàng)建帶頭結(jié)點(diǎn)的空鏈串創(chuàng)建帶頭結(jié)點(diǎn)的空鏈串LinkString createNullStr_linkLinkString createNullStr_link( void )( void ) LinkString pst LinkString pst; ; pst=(LinkString)malloc( sizeof(struct StrNode pst=(LinkString)malloc( sizeof(struct StrNode) );) ); if (pst if (pst!=NULL)!=NULL) pst pst-link = NULL;-link = NULL; else else printf(“Out printf(“Out of space! n”); of space! n”); return (pst return (pst);); 算法算法3.4 3.4 求單鏈表示的串的子串求單鏈表示的串的子串LinkString subStr_link(LinkString s,int i,intLinkString subStr_link(LinkString s,int i,int j) j)/ / 求從求從s s所指的帶頭結(jié)點(diǎn)的鏈串中第所指的帶頭結(jié)點(diǎn)的鏈串中第i(ii(i0)0)個(gè)字符開始個(gè)字符開始/ / 連續(xù)取連續(xù)取j j個(gè)字符所構(gòu)成的子串個(gè)字符所構(gòu)成的子串 LinkStringLinkString s1; s1; PStrNode p,q,t PStrNode p,q,t; ; int int k; k; s1 = createNullStr_link s1 = createNullStr_link( ); /( ); /* * 創(chuàng)建空鏈串創(chuàng)建空鏈串 * */ / if( s1 = NULL ) if( s1 = NULL ) printfprintf( Out of space!n );( Out of space!n ); return (NULL); return (NULL); if (i1 | j1 ) return(s1); / if (i1 | j1 ) return(s1); /* * i,j i,j值不合適，返回空串值不合適，返回空串 * */ / p = s; p = s; for (k=1;k=i;k for (k=1;klink; p = p-link; else else return(s1); return(s1); if (p=NULL) return(s1); if (p=NULL) return(s1); t = s1; t = s1; for (k=1;k=j;k for (k=1;kc = p-c; q-c = p-c; q-link = NULL; q-link = NULL; t-link = q; t-link = q;/ /* * 結(jié)點(diǎn)放入子鏈串中結(jié)點(diǎn)放入子鏈串中 * */ / t = q; t = q; p = p-link; p = p-link; return(s1); return(s1); 模式匹配：子串在主串中的定位操作(mn)。 t=t0 t1 t2 . . . . . . tn-1 目標(biāo) p=p0 p1 p2 pm-1 模式 從目標(biāo)t中查找與模式p完全相同子串的過程。 3.3.1 樸素的模式匹配樸素的模式匹配 t a b b b a a p圖3.3 樸素的模式匹配過程 a b a a b a a b a a b a 3.3.1 樸素的模式匹配樸素的模式匹配 模式匹配的最簡(jiǎn)單的做法是：用p中的字符依次與t中的字符比較：如果t0 = p0，t1 = p1，tm-1 = pm-1，則匹配成功，調(diào)用求子串的操作subStr(t,1,m)即是找到的子串。否則必有某個(gè)i（0im-1），使得ti pi，這時(shí)可將p右移一個(gè)字符，用p中字符從頭開始與t中字符依次比較；如此反復(fù)執(zhí)行，直到下面兩種情況之一：或者到達(dá)某步時(shí)，ti = p0，ti+1 = p1，ti+m-1 = pm-1，匹配成功，subStr(t,i+1,m)即是找到的（第一個(gè)）與模式p相同的子串；或者一直將p移到無法與t繼續(xù)比較為止，則匹配失敗。 算法算法3.5 3.5 樸素的模式匹配算法樸素的模式匹配算法int index(PSeqString t, PSeqStringint index(PSeqString t, PSeqString p) p)/ / 求求p p所指的串在所指的串在t t所指的串中第一次出現(xiàn)時(shí)，所指的串中第一次出現(xiàn)時(shí)，/ p/ p所指的串的第一個(gè)元素在所指的串的第一個(gè)元素在t t所指的串中的序號(hào)所指的串中的序號(hào) int i,j;/i,jint i,j;/i,j分別為分別為p p串、串、t t串中當(dāng)前字符的下標(biāo)，串中當(dāng)前字符的下標(biāo)， i=0;j=0;i=0;j=0; while(i while(in & jn)n & jn) if(p-ci = t-cj if(p-ci = t-cj) i+;j i+;j+ else else j=j-i-1; j=j-i-1; i=0; i=0; if(i=p-n) return(j-p if(i=p-n) return(j-p-n+1);-n+1); else return 0; else return 0; 主串：“000000000000000000000000000000000000000000001”模式串：“00000001” 樸素匹配算法簡(jiǎn)單，易于理解，但效率不高，主要原因是執(zhí)行中有回溯，一旦比較不等，就將p所指的串右移一個(gè)字符，并從p0（算法中用p-c0表示）開始比較。在最壞的情況下，每趟比較都在最后出現(xiàn)不等，最多比較nm1趟，總比較次數(shù)為m*(nm1)，由于在一般情況下mn，所以算法運(yùn)行時(shí)間為O(m*n)。 小 結(jié) 串是特殊的線性表，是由字符作元素組成的。它和線性表一樣有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式。串作為一種抽象數(shù)據(jù)類型，有它自己的操作，在對(duì)串處理時(shí)，要抓住它的特殊要求。模式匹配是一個(gè)比較復(fù)雜的串操作，是子串在主串中的定位操作。樸素的模式匹配算法比較直觀，易于理解。 網(wǎng)絡(luò)課堂測(cè)試：3 字符串作業(yè)p.83 算法題1、2實(shí)驗(yàn)二 2.1串的復(fù)制 2.2求子串