《《算法與數(shù)據(jù)結構》教學課件第3章 字符串C語言描述（第2版）張乃孝編著》由會員分享，可在線閱讀，更多相關《《算法與數(shù)據(jù)結構》教學課件第3章 字符串C語言描述（第2版）張乃孝編著（19頁珍藏版）》請在裝配圖網上搜索。

1、3 字符串 3.1 字符串及其抽象數(shù)據(jù)類型字符串及其抽象數(shù)據(jù)類型3.2 字符串的實現(xiàn)字符串的實現(xiàn) 3.3 模式匹配模式匹配 字符串：簡稱串，是特殊的線性表，其特殊性主要在于表中的每個元素是一個字符，以及由此而要求的一些特殊操作。 3.1 字符串及其字符串及其抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型3.1.1 基本概念基本概念 長度：一個串中包括的字符個數(shù)。長度為零的串稱為空串。 子串：字符串s1中任意個連續(xù)的字符組成的子序列s2被稱為是s1的子串，而稱s1是s2的主串。 位置：子串在主串中的位置是以子串的第一個第一個字符在主串中的字符序號(下標+1)。 相等：兩個串的長度相等，并且對應位置上的字符都 相等。A

2、DT3.1 字符串的抽象數(shù)據(jù)類型ADT String isoperationsstring createNullStr(void) 創(chuàng)建一個空串 int isNullstr(String s) 判斷一個串是否為空串 int length(String s) 求一個串的長度 String concat(String s1, String s2) 將兩個串拼接在一起構成一個新串 String subStr(String s, int i, int j) 在串s中，求從串的第i個字符開始連續(xù)j個字符所構成的子串 int index(String s1,String s2) 求串S2在串S1中第一次出

3、現(xiàn)的位置位置End ADT String3.1.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型3.2.1 順序表示順序表示 3.2.2 鏈接表示鏈接表示 3.2.1 順序表示順序表示struct SeqString /* 順序串的類型 */ int MAXNUM /* 串允許的最大字符個數(shù) */ int n;/* 串的長度，nMAXNUM */ char *c; typedef struct SeqString *PSeqString; 順序串的定義 例 算法算法3.1 3.1 創(chuàng)建空順序串創(chuàng)建空順序串 PSeqString createNullStr_seq( intPSeqString createNull

4、Str_seq( int m ) m ) PSeqString pstr=new struct SeqString PSeqString pstr=new struct SeqString; ;/申請串空間申請串空間 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 delet

5、e 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)個字符開始連續(xù)取個字符開始連續(xù)取j j個字符所構成的子串個字符所構成的子串 PSeqStrin

6、g 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個字符個字符, ,則能取幾個就取幾個則能取幾個就取幾個* */ /

7、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) 不帶頭結點 a b f.(b) 帶頭結點ss a b f . 圖3. 2 串的鏈接表示例s(c) 循環(huán)表

8、表示 算法算法3.3 3.3 創(chuàng)建帶頭結點的空鏈串創(chuàng)建帶頭結點的空鏈串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 =

9、 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所指的帶頭結點的鏈串中第所指的帶頭結點的鏈串中第i(ii(i0)0)個字符開始個字符開始/ / 連續(xù)取連續(xù)取j j個字符所構

10、成的子串個字符所構成的子串 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 ) re

11、turn(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 =

12、NULL; t-link = q; t-link = q;/ /* * 結點放入子鏈串中結點放入子鏈串中 * */ / t = q; t = q; p = p-link; p = p-link; return(s1); return(s1); 模式匹配：子串在主串中的定位操作(mn)。 t=t0 t1 t2 . . . . . . tn-1 目標 p=p0 p1 p2 pm-1 模式 從目標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 樸素的

13、模式匹配樸素的模式匹配 模式匹配的最簡單的做法是：用p中的字符依次與t中的字符比較：如果t0 = p0，t1 = p1，tm-1 = pm-1，則匹配成功，調用求子串的操作subStr(t,1,m)即是找到的子串。否則必有某個i（0im-1），使得ti pi，這時可將p右移一個字符，用p中字符從頭開始與t中字符依次比較；如此反復執(zhí)行，直到下面兩種情況之一：或者到達某步時，ti = p0，ti+1 = p1，ti+m-1 = pm-1，匹配成功，subStr(t,i+1,m)即是找到的（第一個）與模式p相同的子串；或者一直將p移到無法與t繼續(xù)比較為止，則匹配失敗。 算法算法3.5 3.5 樸素的

14、模式匹配算法樸素的模式匹配算法int index(PSeqString t, PSeqStringint index(PSeqString t, PSeqString p) p)/ / 求求p p所指的串在所指的串在t t所指的串中第一次出現(xiàn)時，所指的串中第一次出現(xiàn)時，/ p/ p所指的串的第一個元素在所指的串的第一個元素在t t所指的串中的序號所指的串中的序號 int i,j;/i,jint i,j;/i,j分別為分別為p p串、串、t t串中當前字符的下標，串中當前字符的下標， i=0;j=0;i=0;j=0; while(i while(in & jn)n & jn) if(p-ci =

15、 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” 樸素匹配算法簡單，易于理解，但效率不高，主要原因是執(zhí)行中有回溯，一旦比較不等，就將p所指的串右移一個字符，并從p0（算法中用p-c0表示）開始比較。在最壞的情況下，每趟比較都在最后出現(xiàn)不等，最多比較nm1趟，總比較次數(shù)為m*(nm1)，由于在一般情況下mn，所以算法運行時間為O(m*n)。 小 結 串是特殊的線性表，是由字符作元素組成的。它和線性表一樣有順序存儲和鏈式存儲兩種方式。串作為一種抽象數(shù)據(jù)類型，有它自己的操作，在對串處理時，要抓住它的特殊要求。模式匹配是一個比較復雜的串操作，是子串在主串中的定位操作。樸素的模式匹配算法比較直觀，易于理解。 網絡課堂測試：3 字符串作業(yè)p.83 算法題1、2實驗二 2.1串的復制 2.2求子串