數(shù)據(jù)結(jié)構(gòu)第08講-串的定義、表示和實(shí)現(xiàn)c

1、期中考試Class 1 4月16日 10,11,12課時(shí)Class 3 4月17日 6,7,8課時(shí)期中考試內(nèi)容第一章 緒論第二章 線性表第三章 棧和隊(duì)列第四章 串第五章 數(shù)組和廣義表第六章 樹和二叉樹帶星號的不考第4章 串4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn)4.3 串的模式匹配算法4.4 串操作應(yīng)用舉例4.1 串類型的定義1.串的概念 由零個(gè)或多個(gè)字符組成的有限序列，記作 s = a1a2an 其中：s 為串的名字；用成對的單引號括起來的字符序列為串的值，但兩邊的單引號不算串值，不包含在串中；ai(1in)可以是字母、數(shù)字或其它字符；n為串中字符的個(gè)數(shù)，稱為串的長度。空串：不含任何字符的

2、串。長度n=0，記為 s= ； 空格串：含有空格的串，長度n0， 記為s= 。子串、主串: 串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時(shí)，該子串的首字符對應(yīng)的主串中的序號稱為子串在主串中的位置。 例：A 和 B 分別為 A=This is a string B=is 空串是任意串的子串，任意串是其自身的子串。串的比較大?。?aab， abcabd兩串相等：當(dāng)且僅當(dāng)這兩個(gè)串的值相等（長度相等,對應(yīng)位置上的字符也相等）時(shí)。2.串的抽象類型定義ADT String 數(shù)據(jù)對象：D ai |aiCharacterSet, i=1,2,n, n0

3、數(shù)據(jù)關(guān)系：R1 | ai-1, ai D, i=2,n 基本操作：ADT String串的常用操作(1) StrAssign (&T, chars) 條件：chars是字符串常量；結(jié)果：把chars賦為T的值(2) StrCopy (&T, S) 條件：串S存在； 結(jié)果：將串S的值復(fù)制到串T(3) DestroyString (&S) 條件：串S存在； 結(jié)果：串S被銷毀(4) StrEmpty (S) 條件：串S存在； 結(jié)果：若S為空串，返回真，否則假(5) pare (S, T) 條件：串S和T存在； 結(jié)果：若S T，則返回值0；若S = T，則返回值=0 若S T，則返回值 0) n =

4、StrLength(S); m = StrLength(T); i = p; while ( i = n-m+1) SubString (&sub, S, i, m); if ( pare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在與T相等的子串 / Index;算法4.1第4章 串4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn) 4.2.1 定長順序存儲表示 4.2.2 堆分配存儲表示 4.2.3 串的塊鏈存儲表示4.3 串的模式匹配算法4.4 串操作應(yīng)用舉例4.2 串的表示和實(shí)現(xiàn) 串是一種特殊的線性表，特殊在于

5、每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成，因此，存儲串的方法也是存儲線性表的一般方法，則串的存儲表示有三種形式：定長順序存儲表示、堆分配存儲表示、串的塊鏈存儲表示。4.2.1 定長順序存儲表示 用一組地址連續(xù)的存儲單元存儲串值的字符序列。使用定長字符數(shù)組來定義，數(shù)組的上界預(yù)先給出，故也稱靜態(tài)存儲分配。 定義說明： #define MAXSTRLEN 255 / 用戶可在255以內(nèi)定義最大串長 typedef unsigned char SStringMAXSTRLEN+1; / 0號單元存放串的長度 串的實(shí)際長度可在預(yù)定義長度的范圍內(nèi)隨意設(shè)定，超過預(yù)定義長度的串值則被舍去，稱之為“截?cái)唷?。1.串的聯(lián)接需考慮

6、三種情況： (1) 聯(lián)接后的串長度未超過預(yù)定義長度； (2) 聯(lián)接后的串長度超過預(yù)定義長度；又分： a：第一個(gè)串長度小于預(yù)定義長度； b：第一個(gè)串長度等于預(yù)定義長度。Status Concat(SString S1, SString S2, SString &T) / 用T返回由S1和S2聯(lián)接而成的新串。若未截?cái)喾祷卣妫駝t假 if (S10+S20 = MAXSTRLEN) / 未截?cái)?T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; else if (S10 MAXSTRSIZE) / 截?cái)?T1

7、.S10 = S11.S10; TS10+1.MAXSTRLEN = S21.MAXSTRLEN S10; T0 = MAXSTRLEN; uncut = FALSE; else / 截?cái)?僅取S1) T0.MAXSTRLEN = S10.MAXSTRLEN; uncut = FALSE; return uncut; / Concat2.求子串 思路：求子串的過程即為復(fù)制字符序列的過程，將串 S 中從第 i 個(gè)字符開始長度為 L的字符序列復(fù)制到新串中。顯然，此操作不存在截?cái)嗟膯栴}，但與順序表類似，會出現(xiàn)參數(shù)錯(cuò)誤的情形： (1)子串的位置非法； (2)子串的位置加上子串長已經(jīng)超出原串長。Stat

8、us SubString (SString &Sub, SString S, int pos, int len) /用Sub返回S的第pos個(gè)字符起長度為len的子串。/ 1=pos=StrLength(S)且0=len= StrLength(S)-pos+1 if (posS0 | lenS0-pos+1) return ERROR; Sub1.len = Spos.pos+len-1; Sub0=len; return OK; / SubString4.2.2 堆分配存儲表示 由于多數(shù)情況下串是以整體形式參與操作，而在實(shí)際應(yīng)用中，各種串變量的長度的不同，并且操作中串值長度的也會發(fā)生變化，故

9、為串變量設(shè)定固定大小空間不盡合理。 串的堆分配存儲表示特點(diǎn)： 仍以一組地址連續(xù)的存儲單元存放串值字符序列，但串變量的存儲空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得，程序中出現(xiàn)的所有串變量可用的存儲空間是一個(gè)稱之為“堆”的共享空間。定義說明：typedef struct char *ch; / 若是非空串，則按串長分 / 配存儲區(qū)，否則ch為NULL int length; / 串長度 HString;稱之為“堆”的共享空間 通常，C語言中提供的串類型就是以該存儲方式實(shí)現(xiàn)。系統(tǒng)利用函數(shù) malloc( )和 free( )進(jìn)行串值空間的動(dòng)態(tài)管理，為每個(gè)新產(chǎn)生的串分配一個(gè)存儲區(qū)，稱串值共享的存儲空間為“堆

10、”。 C 語言中的串以 0 為結(jié)束符，串長是一個(gè)隱含值。Status StrInsert ( HString &S, int pos, HString T ) /在串S的第pos個(gè)字符之前（包括尾部）插入串T if ( posS.length+1 ) return ERROR; if (T.length) /T非空，需重新分配空間，以便插入T S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char) if (!S.ch) exit(OVERFLOW); for (i=S.length-1;i=pos-1;-i) /為插入T騰出pos后的

11、位置 S.chi+T.length = S.chi; /從pos起全部字符均后移 S.chpos-1.pos+T.length-2 = T.ch0.T.length-1; /插入T S.length + = T.length; /刷新S串長度 return OK; /StrInsert1.串插入算法4.4Status StrAssign(HString &T, char *chars) if (T.ch) free(T.ch); /釋放T原有空間 for (i=0, c=chars; *c; +i, +c); /求串長 if (!i) T.ch = NULL; T.length = 0; el

12、seif (!(T.ch = (char*)malloc(i*sizeof(char) exit(OVERFLOW);T.ch0.i-1 = chars0.i-1;T.length =i; Return OK;/StrAssign指針變量C也可以自增！意即每次后移一個(gè)數(shù)據(jù)單元。2. 串賦值直到終值為“假”停止，串尾特征是0NULL=0Status Concat(HString &T,HString S1,HString S2) /用T返回S1和S2聯(lián)接而成的新串 if (T.ch) free(T.ch); / 釋放T原來占據(jù)的空間 T.ch =(char*)malloc(S1.length+S

13、2.length)*sizeof(char); /為T分配空間 if (!T.ch) return ERROR; / 連接兩個(gè)串的內(nèi)容 T.length = S1.length + S2.length; T.ch 0.S1.length-1=S1.ch0.S1.length-1; T.ch S1.length.T.length -1=S2.ch0.S2.length-1; return OK; / Concat3.串聯(lián)接status SubStr(HString &Sub,HString S,int pos,int len) /用Sub返回串S中第pos個(gè)字符起長度為len的子串 if(pos

14、S.length | lenS.length-pos+1) return ERROR /判斷i和len的合理性 if Sub.ch free(Sub.ch) /釋放舊空間 if (!len) Sub.ch = null; Sub.length = 0; /空子串 else /完整子串 Sub.ch = (char*) malloc( len*sizeof(char) ); if (!Sub.ch) exit(OVERFLOW); Sub.ch 0.len-1 = S.ch pos-1.pos+len -2 ; Sub.length = len; return OK; / SubStr4.求子串

15、20140318 Class34.2.3 串的塊鏈存儲表示 串的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈串。其存儲形式與一般的鏈表類似，每個(gè)結(jié)點(diǎn)包含字符域和指針域。 一個(gè)存儲結(jié)點(diǎn)可以存儲 1個(gè)或多個(gè)字符，通常將鏈串中每個(gè)結(jié)點(diǎn)所存儲的字符個(gè)數(shù)稱為結(jié)點(diǎn)大小。 為了便于進(jìn)行諸如串的聯(lián)接等操作，鏈表中還附設(shè)有尾指針。由于串的長度不一定是結(jié)點(diǎn)大小的整數(shù)倍，因此還需要一個(gè)指示串長的域。稱如此定義的存儲結(jié)構(gòu)為串的塊鏈存儲結(jié)構(gòu)。法1存儲密度為 ；法2存儲密度為 ；鏈?zhǔn)酱鎯μ攸c(diǎn) ：用鏈表存儲串值，易插入和刪除。單字符結(jié)點(diǎn)的串的鏈?zhǔn)酱鎯Y(jié)構(gòu)：結(jié)點(diǎn)大小取1多字符結(jié)點(diǎn)的串的鏈?zhǔn)酱鎯Y(jié)構(gòu)：結(jié)點(diǎn)大小取 n( 如n=4 )1/29/15=3/5

16、 A B C I NULLheadheadA B C D E F G H I # # # NULL存儲密度串值所占的存儲位/實(shí)際分配的存儲位定義說明：#define CHUNKSIZE 80 / 可由用戶定義的塊大小typedef struct Chunk / 結(jié)點(diǎn)結(jié)構(gòu) char chCHUNKSIZE; struct Chunk *next; Chunk;typedef struct / 串的鏈表結(jié)構(gòu) Chunk *head, *tail; / 串的頭和尾指針 int curlen; / 串的當(dāng)前長度 LString;性能分析： 在以鏈表存儲串值時(shí)，結(jié)點(diǎn)大小的選擇將直接影響串的處理效率。 顯

17、然，存儲密度小（如結(jié)點(diǎn)的大小為1），操作方便（結(jié)點(diǎn)的大小為1時(shí)），然而存儲占用量大。一般以塊鏈存儲時(shí)實(shí)現(xiàn)串的操作比較麻煩。例：在串中插入一個(gè)子串時(shí)，可能需要分割結(jié)點(diǎn)；聯(lián)接兩個(gè)串時(shí)，若第一個(gè)串的最后一個(gè)結(jié)點(diǎn)沒有填滿，還需要添加其他字符；但在應(yīng)用程序中，可將串的鏈?zhǔn)酱鎯Y(jié)構(gòu)和串的定長順序存儲結(jié)構(gòu)結(jié)合使用。例：在正文編輯系統(tǒng)中，整個(gè)“正文”可以看成是一個(gè)串，每一行是一個(gè)子串，構(gòu)成一個(gè)結(jié)點(diǎn)。即同一個(gè)行的串用定長結(jié)構(gòu)（80個(gè)字符），而行和行之間用指針相聯(lián)接。q例：若x和y是兩個(gè)單鏈表存儲的串，編寫一個(gè)函數(shù)找出x中第一個(gè)不在y中出現(xiàn)的字符。cf abecf habyxpq算法基本思想： 從頭到尾掃描x，對于x中的每一個(gè)結(jié)點(diǎn)P，判定是否在y中，若在，則繼續(xù)掃描x，否則給出該結(jié)點(diǎn)P的數(shù)據(jù)域并返回。ppqqqqq定義說明：typedef struct CNode / 結(jié)點(diǎn)結(jié)構(gòu) char data; struct CNode *next; Chunk,*LinkString;子函數(shù)編寫int found(char d, LinkString h) / 若h的鏈表中包含有data域?yàn)閤的結(jié)點(diǎn)則返回1，/ 否則返回 0 。 while ( h !=NULL & h-data != d) h =