數(shù)據(jù)結構與算法字符串

1、數(shù)據(jù)結構與算法第三章 字符串,主講人 張銘http://db.pku.edu.cn/mzhang/dsmzhang@db.pku.edu.cn北京大學信息科學與技術學院網(wǎng)絡與信息系統(tǒng)研究所?版權所有，轉載或翻印必究,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 2,主要內容,3.1 字符串抽象數(shù)據(jù)類型3.2

2、字符串的存儲結構和類定義3.3 字符串運算的算法實現(xiàn)3.4 字符串的模式匹配,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 3,3.1字符串抽象數(shù)據(jù)類型,3.1.1 基本概念3.1.2 String抽象數(shù)據(jù)類型,北京大學信息學院 ?版權所有，轉載或翻印必究

3、 Page 4,3.1.1 基本概念,字符串，由0個或多個字符的順序排列所組成的復合數(shù)據(jù)結構，簡稱“串”。串的長度：一個字符串所包含的字符個數(shù)?？沾洪L度為零的串，它不包含任何字符內容。,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 5,3.1.1.1字符串常數(shù)和變量,字符串常數(shù)例如： "

4、;\n"字符串變量,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 6,3.1.1.2 字符,字符(char) ：組成字符串的基本單位 。在C和C＋＋中單字節(jié)（8 bits）采用ASCII碼對128個符號（字符集charset）進行編碼,北京大學信息學院 ?版權所有，轉載或翻印必究

5、 Page 7,3.1.1.3 字符的編碼順序,為了字符串間比較和運算的便利，字符編碼表一般遵循約定俗成的“偏序編碼規(guī)則”。字符偏序：根據(jù)字符的自然含義，某些字符間兩兩可以比較次序。其實大多數(shù)情況下就是字典序中文字符串有些特例，例如“筆劃”序,北京大學信息學院 ?版權所有，轉載或翻印必究

6、 Page 8,3.1.1.4 C++標準string,標準字符串：將C++的函數(shù)庫作為字符串數(shù)據(jù)類型的方案。例如：char S[M];串的結束標記：'\0''\0'是ASCII碼中8位BIT全0碼，又稱為NULL符。,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 9,3.1

7、.1.4 C++標準string(續(xù)),1. 串長函數(shù) int strlen(char *s);2. 串復制 char *strcpy(char *s1, char*s2);3．串拼接 char *strcat(char *s1, char *s2);4．串比較 int strcmp(char *s1, char *s2);,北京大學信息學院 ?版權所有

8、，轉載或翻印必究 Page 10,3.1.1.4 C++標準string(續(xù)),5．輸入和輸出函數(shù)6．定位函數(shù) char *strchr(char *s, char c);7．右定位函數(shù) char *strrchr(char *s, char c);,北京大學信息學院 ?版權所有，轉載或翻印必究

9、 Page 11,3.1.1.4 C++標準string(續(xù)),,,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 12,3.1.2 String抽象數(shù)據(jù)類型,字符串類（class String）：不采用char S[M]的形式而采用一種動態(tài)變長的存儲結構。,北京大學信息學院

10、 ?版權所有，轉載或翻印必究 Page 13,3.1.2 String抽象數(shù)據(jù)類型(續(xù)),,,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 14,,,,北京大學信息學院 ?版權所有，轉載或翻印必究

11、 Page 15,,,,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 16,3.1.2.3 賦值算子、拼接算子和比較算子,賦值算子＝拼接算子＋比較算子 >= != 和 ==,北京大學信息學院 ?版權所有，轉載或翻印必究

12、 Page 17,3.1.2.4 輸入輸出算子>,輸入算子>>輸出算子<<,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 18,3.1.2.5 處理子串(Substring)的函數(shù),簡稱“子串函數(shù)”提取子串插入子串尋找子串刪

13、除子串…,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 19,3.1.2.6 字符串中的字符,重載下標算子[] char& operator[] (int n);按字符定位下標 int Find(char c,int start);反向尋找，定位尾部出現(xiàn)的字符 int FindLast(ch

14、ar c);,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 20,3.2 字符串的存儲結構和類定義,3.2.1字符串的順序存儲3.2.2字符串類class String的存儲結構,北京大學信息學院 ?版權所有，轉載或翻印必究 Pag

15、e 21,3.2.1字符串的順序存儲,對于串長變化不大的字符串，可以有三種處理方案：（1）用S[0]作為記錄串長的存儲單元。缺點：限制了串的最大長度不能超過256。,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 22,3.2.1字符串的順序存儲(續(xù)),（2）為存儲串的長度，另辟一個存儲的地方。缺點：串的最大長度一般是靜態(tài)給

16、定的，不是動態(tài)申請數(shù)組空間。,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 23,3.2.1字符串的順序存儲(續(xù)),（3）用一個特殊的末尾標記'\0'。例如：C++語言的string函數(shù)庫（＃include ）采用這一存儲結構。,北京大學信息學院 ?版權所有，轉載或翻印必究

17、 Page 24,3.2.2 字符串類class String的存儲結構,抽取子串函數(shù) 例如： String s1 = "value-"; s2 = s1.Substr(2,3); 上述語句涉及的存儲形式如下頁所示。,,北京大學信息學院 ?版權所有，轉載或翻印必究

18、 Page 25,3.2.2 字符串類class String的存儲結構(續(xù)),,,,,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 26,3.2.2 字符串類class String的存儲結構(續(xù)),微軟VC＋＋的CString類介紹自動的動態(tài)存儲管理，串的最大長度不超過2GB 容器型不必使用ne

19、w和delete 使用特點：變量申明CString s6( 'x', 6 ); // s6 = "xxxxxx"CString city = "Philadelphia"; // 串常數(shù)作為初值賦值語句s1 = s2 = "hi there";變量比較 if( s1 == s2 ) 方法調用 s1.MakeUpper();

20、 內部字符比較 if( s2[0] == 'h' ),,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 27,3.3 字符串運算的算法實現(xiàn),1. 串長函數(shù) int strlen(char *s);2. 串復制 char *strcpy(char *s1, char*s2);3．串拼接

21、 char *strcat(char *s1, char *s2);4．串比較 int strcmp(char *s1, char *s2);,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 28,3.3.1 C++標準串運算的實現(xiàn),【算法3-1 】字符串的復制char *strcpy(char *d, cha

22、r *s){ //這個程序的毛病是，如果字符串s比字符串d要長，//這個程序沒有檢查拷貝出界，沒有報告錯誤。//可能會造成d的越界 int i =0; while (s[i] != '\0') { d[i] = s[i]; i++; } d[i] = '\0'; return d;},北京大學信息學院 ?版權所有，轉載或

23、翻印必究 Page 29,3.3.1 C++標準串運算的實現(xiàn)(續(xù)),【算法3-2 】字符串的比較int strcmp( char *d, char *s){ int i =0; while (s[i] != '\0' && d[i] != '\0' ) { if (d[i] > s[i])

24、 return 1; else if (d[i] < s[i]) return -1;,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 30,3.3.1 C++標準串運算的實現(xiàn)(續(xù)),i ++; }if( d[i] = ='\0' && s[i] != &

25、#39;\0') return -1;else if (s[i] = = '\0'&& d[i] != '\0') return 1;return 0;},北京大學信息學院 ?版權所有，轉載或翻印必究 Page 31,3.3.1 C++標準串運算的實現(xiàn)(續(xù)),【算

26、法3-3 】求字符串的長度int strlen(char d[]){ int i =0; while (d[i] != 0) i++; return i;},北京大學信息學院 ?版權所有，轉載或翻印必究 Page 32,3.3.1 C++標準串運算的實現(xiàn)(續(xù)),【算法3- 4 】尋找字符char * strchr

27、(char *d , char ch){ //按照數(shù)組指針d依次尋找字符ch，//如果找到ch，則將指針位置返回，//如果沒有找到ch，則為0值。i = 0;,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 33,3.3.1 C++標準串運算的實現(xiàn)(續(xù)),//循環(huán)跳過那些不是ch的字符while (d[i] != 0 &

28、amp;& d[i] != ch ) i++; //當本串不含字符ch，則在串尾結束； //當成功尋找到ch，返回該位置指針if (d[i] = = 0) return 0; else return &d[i] ;},北京大學信息學院 ?版權所有，轉載或翻印必究 Page 34,3

29、.3.1 C++標準串運算的實現(xiàn)(續(xù)),【算法3-5 】反向尋找字符char * strrchr(char *d , char ch){ //按照數(shù)組指針d，從其尾部反著尋找字符ch， //如果找到ch，則將指針位置返回， //如果沒有找到ch，則為0值。 i = 0; //找串尾 while (d[i] != '\0' )i++;,北京大學信息學院

30、 ?版權所有，轉載或翻印必究 Page 35,3.3.1 C++標準串運算的實現(xiàn)(續(xù)),//循環(huán)跳過那些不是ch的字符while (i >= 0 && d[i] != ch ); //當本串不含字符ch，則在串尾結束； //當成功尋找到ch，返回該位置指針if (i < 0) return 0; el

31、se return &d[i] ; },北京大學信息學院 ?版權所有，轉載或翻印必究 Page 36,3.3.2 String串運算的實現(xiàn)(續(xù)),【算法3-7 】創(chuàng)建算子(constructor)String::String(char *s){ //先要確定新創(chuàng)字符串實際需要的存儲空間，s的類

32、//型為(char *)，作為新創(chuàng)字符串的初值。確定 //s的長度，用標準字符串函數(shù)strlen(s)計算長度size = strlen(s) ; //然后，在動態(tài)存儲區(qū)域開辟一塊空間，用于存 //儲初值s，把結束字符也包括進來str ＝ new char [size＋1];,北京大學信息學院 ?版權所有，轉載或翻印必究

33、 Page 37,3.3.2 String串運算的實現(xiàn)(續(xù)),//開辟空間不成功時，運行異常，退出assert(str != '\0'); //用標準字符串函數(shù)strcpy，將s完全 //復制到指針str所指的存儲空間strcpy( str, s );},北京大學信息學院 ?版權所有，轉載或翻印必究

34、 Page 38,3.3.2 String串運算的實現(xiàn)(續(xù)),【算法3-8 】銷毀算子（destructor）String::~String(){ //必須釋放動態(tài)存儲空間delete [] str;},北京大學信息學院 ?版權所有，轉載或翻印必究 Page 39,3.3.2 String串運算的實現(xiàn)

35、(續(xù)),【算法3-9】拼接算子String String::operator+ (String& s){ //把字符串s和本實例拼接成為一個長串返回String temp; //創(chuàng)建一個串tempint len; //準備工作，計算拼接后的長串的長度len = size + s.size; //把temp串創(chuàng)建時申請的存儲空間全部釋放delete [] temp.str

36、; //準備工作，開辟空間，為存放長串之用temp.str= new char [len+1];,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 40,3.3.2 String串運算的實現(xiàn)(續(xù)),//若開辟動態(tài)存儲空間不成功，則退出assert(temp.str!= 0)；temp.size= len;

37、//字符串str（以’\0’結尾）存到tempstrcpy(temp.str, str); //再把參數(shù)s的str和本實例的str拼接為長串strcat(temp.str, s.str); return temp;},北京大學信息學院 ?版權所有，轉載或翻印必究 Page 41,3.3.2 String串運算的實現(xiàn)(續(xù))

38、,【算法3-10】賦值算子String String::operator= (String& s){ //參數(shù)s將被賦值到本串//若本串的串長和s的串長不同，則應該釋放本串的//str存儲空間，并開辟新的空間if(size != s.size){ delete [] str ; //釋放原存儲空間 str = new char [s.size+1];,北京大學信息學院

39、 ?版權所有，轉載或翻印必究 Page 42,3.3.2 String串運算的實現(xiàn)(續(xù)),//若開辟動態(tài)存儲空間失敗，則退出正常運行 assert(str != 0)； size = s.size;}strcpy(str , s.str );//返回本實例，作為String類的一個實例return *this;},北京大學信息學院

40、 ?版權所有，轉載或翻印必究 Page 43,3.3.2 String串運算的實現(xiàn)(續(xù)),【算法3-11】抽取子串函數(shù)String String::Substr(int index , int count ){ //取出一個子串返回，自下標index開始，長度為count int i; //本串自下標index開始向

41、右數(shù)直到串尾，長度為leftint left = size – index ; String temp;char *p, *q; //若下標index值太大，超過本串實際串長，則返回空串if(index >= size) // 注意不是 index >= size - 1 return temp;,北京大學信息學院 ?版權所有，轉載或翻印必究

42、 Page 44,3.3.2 String串運算的實現(xiàn)(續(xù)),//若count超過自index以右的實際子串長度， // 則把count變小if(count > left ) count = left;//釋放原來的存儲空間delete [] temp.str; //張銘注釋：注意此語句！//若開辟動態(tài)存儲空間失敗，則退出temp.str = ne

43、w char [count+1]; assert(temp.str != 0)； //p的內容是一個指針， //指向目前暫無內容的字符數(shù)組的首字符處p = temp.str;,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 45,3.3.2 String串運算的實現(xiàn)(續(xù)),//q的內容是一個指針， //

44、指向本實例串的str數(shù)組的下標index字符q = &str[index]; //用q指針取出它所指的字符內容后，指針加1 // 用p該指針所指的字符單元接受拷貝，該指針也加1for (i =0; i < count; i++) *p++ = *q++; //循環(huán)結束后，讓temp.str的結尾為’\0’*p = 0; temp.size = count;return

45、temp;},北京大學信息學院 ?版權所有，轉載或翻印必究 Page 46,3.3.2 String串運算的實現(xiàn)(續(xù)),【算法 3-12 】查找字符int String::Find(char c,int start){ //在本實例字符串尋找字符c，如果找到，則//將其下標位置作為整數(shù)函數(shù)值返回，如果//c沒有找到，則為

46、負值。參數(shù)start是下標，//從start下標開始尋找c的工作,若start為//0，則從頭尋找int i = start;assert( i < size);,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 47,3.3.2 String串運算的實現(xiàn)(續(xù)),//循環(huán)跳過那些不是c的字符while (str[i] !

47、= 0 && str[i] != c ) i++; //當本串不含字符c，則尋找到串尾結束， //返回－1表示失?。划敵晒ふ业絚，返回它的 //下標位置if (str[i] == 0) // 注意：不要搞成“= =” return -1; else return i ; },北京大學信息學院 ?版權所有，轉載或翻印必究

48、 Page 48,3.4 字符串的模式匹配,模式匹配(pattern matching)一個目標對象S（字符串）一個模板（pattern）P（字符串）任務：用給定的模板P，在目標字符串S中搜索與模板P全同的一個子串，并求出S中第一個和P全同匹配的子串（簡稱為“配串”），返回其首字符位置。,北京大學信息學院 ?版權所有，轉載或翻印必究

49、 Page 49,,S s0 s1 … sisi+1 si+2 … si+m-2 si+m-1 … sn-1 ‖‖ ‖ ‖ ‖ P p0 p1 p2 … pm -2 pm-1為使模式 P 與目標 S 匹配，必須滿足 p0 p1

50、 p2 …pm-1 = si si+1 si+2 … si+m-1,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 50,樸素模式匹配,S=ababababababb…P=abababb X abababb X abababb

51、 X abababb X abababb X abababb X abababb ?,北京大學信息學院 ?版權所有，轉載或翻印必究

52、 Page 51,【算法3-13 】模式匹配原始算法（其一）,#include “String.h” // 不是 #includeint FindPat_1(String S, String P, int startindex) { // 從S末尾倒數(shù)一個模板長度位置 int LastIndex = S.strlen() - P.strlen(); if (L

53、astIndex < startindex) return (-1); //g為S的游標，用模板P和S第g位置子串比較， //若失敗則繼續(xù)循環(huán) for (int g= startindex; g <= LastIndex; g++) if ( P == S.Substr(g, P.strlen() )) return g; //若for循環(huán)

54、結束，則整個匹配失敗，返回值為負， return (-1);},北京大學信息學院 ?版權所有，轉載或翻印必究 Page 52,3.4.1 模式匹配原始算法(續(xù)),【算法3-13】模式匹配原始算法（其二）int FindPat_2(String S, String P,int startindex){ // 從S末尾倒數(shù)

55、一個模板長度位置 int LastIndex = S.strlen() - P.strlen(); //開始匹配位置startindex的值過大，匹配無法成功 if (LastIndex < startindex) return (-1); // i 是指向S內部字符的游標， // j 是指向P內部字符的游標 int i=startindex, j = 0;,北京大學信息學院

56、 ?版權所有，轉載或翻印必究 Page 53,3.4.1 模式匹配原始算法(續(xù)),//下面開始循環(huán)匹配while (i <LastIndex && j <=P.strlen() ) if( P[j] == S[i]) { i++; j++;} else

57、{ i = i - j + 1; j = 0; },北京大學信息學院 ?版權所有，轉載或翻印必究 Page 54,3.4.1 模式匹配原始算法(續(xù)),//如果匹配成功，則返回該S子串的開 //始位置；如果P和S匹配失敗，函數(shù) //返回值為負 if ( j > P.

58、strlen()) // “>” 可以嗎？ return (i - 1); else return -1; },北京大學信息學院 ?版權所有，轉載或翻印必究 Page 55,3.4.1 樸素模式匹配 (糾錯),【算法3-13】模式匹配原始算法（糾錯）int FindPat_2(String S, S

59、tring P,int startindex){ // 從S末尾倒數(shù)一個模板長度位置 int LastIndex = S.strlen() - P. strlen() ; //開始匹配位置startindex的值過大，匹配無法成功 if (LastIndex < startindex) return (-1); // i 是指向S內部字符的游標， // j 是指向P內部字符的游

60、標 int i=startindex, j = 0;,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 56,3.4.1 樸素模式匹配糾錯(續(xù)),//下面開始循環(huán)匹配while (i<S.strlen() && j<P.strlen() ) // “<=”呢？ if( P[j]

61、== S[i]) { i++; j++;} else { i = i - j + 1; j = 0; },錯誤1：如果“i < LastIndex”，那么后面的就匹配不到。例如，abababababb abababb S.strlen()=11，P.strlen()=7，LastIndex

62、 = 4;“i = 4，j = 0”, 匹配‘a’，接著， “i = 5，j = 1”就進行不了。,錯誤2： 如果“j <=P.strlen()”，則P的結束符號‘\0’也拿來比較，除非正好匹配S的末端，否則出錯！,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 57,3.4.1樸素模式匹配糾錯(續(xù)),//如果匹配成

63、功，則返回該S子串的開 //始位置；如果P和S匹配失敗，函數(shù) //返回值為負 if ( j >= P.strlen() ) // “>” 可以嗎？ return (i - j); else return -1; },錯誤3： 如果“j >P.strlen”，其實匹配結束時，正好j==P.size （因為匹配最后一個字符后，還j++）出錯！其實 “j ==

64、 P.strlen” 就可以！,錯誤4： return (i-1); 匹配完成后，i指向S中最后一個字符的下一位，減去匹配串的長度，才是開始位。,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 58,3.4.1 模式匹配原始算法(續(xù)),例如，aaaaaaaaaab aaaaaab分析假定

65、目標S的長度為n，模板P長度為m， m≤n 在最壞的情況下，每一次循環(huán)都不成功，則一共要進行比較（n-m+1）次每一次“相同匹配”比較所耗費的時間，是P和S逐個字符比較的時間，最壞情況下，共m次。因此，整個算法的最壞時間開銷估計為O(m ? n)。,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 59,,例1， a a a

66、a a a a a a a b a a a a a a b ? a a a a a a b ¦ a a a a a a b例2， a b c d e f a b c d e f f a

67、b c d e f f ? a b c d e f f,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 60,KMP算法思想,S s0 s1 … si-j-1 si-j si-j+1 si-j+2 … si-2 s

68、i-1 si … sn-1 ‖ ‖ ‖ ‖ ‖ ? P p0 p1 p2 … pj-2 pj -1 pj 則有 si-j si-j+1 si-j+2 … si-1 = p0 p1 p2 …pj-1 (1) 如果 p0 p

69、1 …pj-2 ? p1 p2 …pj-1 (2) 則立刻可以斷定 p0 p1 …pj-2 ? si-j+1 si-j+2 … si-1 (樸素匹配的)下一趟一定不匹配，可以跳過去,北京大學信息學院 ?版權所有，轉載或翻印必究 Page 61,,同樣，若 p0 p1 …pj-3

70、? p2 p3 …pj-1則再下一趟也不匹配，因為有 p0 p1 …pj-3 ? si-j+2 si-j+3 … si-1直到對于某一個“k”值(首尾串長度)，使得 p0 p1 …pk ? pj-k-1 pj-k …pj-1 且 p0 p1 …pk-1 = pj-k pj-k+1 …pj-1則 p0 p1 …pk-1 = si-

71、k si-k+1 … si-1 si ‖ ‖ ‖ ? pj-k pj-k+1 … pj-1 pj ‖ ‖ ‖ ?