數(shù)據(jù)結(jié)構(gòu)課件串

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)north china electric power universitydata structure華北電力大學(xué)計(jì)算機(jī)科學(xué)與工程系華北電力大學(xué)計(jì)算機(jī)科學(xué)與工程系dept. of computer science&engineering of north china electric power university第五章第五章 串串 串的基本概念串的基本概念 串的基本操作串的基本操作 串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)結(jié)構(gòu)north china electric power university 關(guān)于串的幾個(gè)算法關(guān)于串的幾個(gè)算法串的基本概念串的基本概念north china ele

2、ctric power university華電華電計(jì)算機(jī)系計(jì)算機(jī)系例如例如: : s1= abc s2= fortran_77 s3= = ( (空串空串) )s4= 由由4 4個(gè)空格組成的空格串個(gè)空格組成的空格串 串是由串是由n 0個(gè)字符組成的有限序列個(gè)字符組成的有限序列, , 通常記為通常記為 s = a1 a2 a3 an-1 an 其中其中, , s表示串名表示串名( (也稱串變量也稱串變量), ), 一對(duì)引號(hào)括起來(lái)的字一對(duì)引號(hào)括起來(lái)的字 符序列稱為串值符序列稱為串值, , ai可以是字母、數(shù)字或其他允許的字可以是字母、數(shù)字或其他允許的字 符。符。n 為串的長(zhǎng)度為串的長(zhǎng)度, , 長(zhǎng)度

3、為長(zhǎng)度為0的串稱為空串。的串稱為空串。一一. .串的定義串的定義north china electric power university華電計(jì)算機(jī)系華電計(jì)算機(jī)系 1. . 串值須用一對(duì)引號(hào)括起來(lái)，但引號(hào)不屬于串值。串值須用一對(duì)引號(hào)括起來(lái)，但引號(hào)不屬于串值。說(shuō)明說(shuō)明2. . 要區(qū)分空串與由空格字符組成的串的不同。要區(qū)分空串與由空格字符組成的串的不同。string = string north china electric power university華電華電計(jì)算機(jī)系計(jì)算機(jī)系1. . 子串：子串：串中若干個(gè)連續(xù)的字符組成的子序列串中若干個(gè)連續(xù)的字符組成的子序列。例如例如: : s= beij

4、ing&shanghai t= jing 2. . 主串主串: : 包含子串的串包含子串的串。3. . 位置：位置： ( (2).).子串在主串中的位置子串在主串中的位置被定義為該被定義為該 字符在字符在 串中的序號(hào)。串中的序號(hào)。 例如例如: : s= beijing&nanjing&shanghai t= jing 位置為位置為4 4二二. . 幾個(gè)名詞概念幾個(gè)名詞概念(1). 單個(gè)字符在主串中的位置單個(gè)字符在主串中的位置被定義為主串被定義為主串 中首次出現(xiàn)的該子串的第一個(gè)字符在主中首次出現(xiàn)的該子串的第一個(gè)字符在主 串中的位置。串中的位置。 north china e

5、lectric power university華電華電計(jì)算機(jī)系計(jì)算機(jī)系 的充分必要條件為兩個(gè)字符串的長(zhǎng)的充分必要條件為兩個(gè)字符串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同。度相等，并且對(duì)應(yīng)位置上的字符相同。4. . 兩個(gè)字符串相等兩個(gè)字符串相等 abcd bacd abcd = abcd north china electric power university華電華電計(jì)算機(jī)系計(jì)算機(jī)系 6.2 串的基本操作串的基本操作1. .給串變量賦值給串變量賦值 assign(s1,s2)strcpy(s2,s1)2. .判斷兩個(gè)串是否相等判斷兩個(gè)串是否相等 equal(s1,s2)strcmp(s1,s2)

6、3. .兩個(gè)字符串連接兩個(gè)字符串連接 concat(s1,s2)strcat(s1,s2)4. .求字符串的長(zhǎng)度求字符串的長(zhǎng)度 len(s)strlen(s)5. .求子串求子串 substr(s,i,k)6. .求子串在主串中的位置求子串在主串中的位置 index(s1,s2)strstr(s1,s2)7. .串的替換串的替換 replace(s,s1,s2)8. .串的復(fù)制串的復(fù)制 copy(s1,s2)strcpy(s2,s1)9. .串的插入串的插入 inserts(s1,i,s2) c函數(shù)函數(shù)north china electric power university華電華電計(jì)算機(jī)系計(jì)

7、算機(jī)系1. . 非緊縮格式非緊縮格式( (設(shè)每個(gè)字有設(shè)每個(gè)字有4 4個(gè)字節(jié)個(gè)字節(jié)) )例如例如: : s = data structure dastructatured a t as tru c t ur e2. . 緊縮格式緊縮格式3. . 單字節(jié)方式單字節(jié)方式 6.3 串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)結(jié)構(gòu)一一. .串的順序存儲(chǔ)結(jié)構(gòu)串的順序存儲(chǔ)結(jié)構(gòu)a tsat r uutcdr enorth china electric power universitysdate 說(shuō)說(shuō) 明：明： 所謂鏈結(jié)點(diǎn)大小是指每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中存放所謂鏈結(jié)點(diǎn)大小是指每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中存放 的字符的個(gè)數(shù)。的字符的個(gè)數(shù)。data

8、strure s二二. .串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)大小為結(jié)點(diǎn)大小為4 4的鏈表的鏈表結(jié)點(diǎn)大小為結(jié)點(diǎn)大小為1 1的鏈表的鏈表north china electric power university 6.4 串的幾個(gè)算法串的幾個(gè)算法一一. .串的定義串的定義type string=record curlen:integer; ch:array1.maxlen of char; end;二二. .串的連接串的連接 假設(shè)假設(shè)r,s,t都是上面定義的都是上面定義的string型變量，且型變量，且r是是s與與t連接后連接后得到的串，則連接運(yùn)算得到的串，則連接運(yùn)算concat(r,s,t)是將

9、是將s與與t的串值分別傳送的串值分別傳送到到r相應(yīng)的位置上。相應(yīng)的位置上。north china electric power university華電華電計(jì)算機(jī)系計(jì)算機(jī)系1) s.curlen+t.curlenmaxlen，這時(shí)得到的串這時(shí)得到的串r r是連接所要求的是連接所要求的 正確結(jié)果；正確結(jié)果；2) s.curlen+t.curlenmaxlen，需要將需要將t t的一部分截?cái)啵玫降牡囊徊糠纸財(cái)?，得到?串串r r只包含只包含s s和和t t的一個(gè)子串；的一個(gè)子串；3) s.curlenmaxlen，這時(shí)需要對(duì)這時(shí)需要對(duì)s s進(jìn)行截?cái)?，得到的串進(jìn)行截?cái)?，得到的串r r僅是僅是 s

10、s的一個(gè)子串；的一個(gè)子串；procedure concat(var r,s,t:string; var p:boolean);begin case s.curlen+t.curlenmaxlen and s.curlen=maxlen: p:=true; movch(r,s,1,1,maxlen); r.curlen:=maxlen; end caseend;procedure movch(t,s,i,j,num);begin for k:=0 to num 1 do ti+k:=sj+k;end;三三. .求子串的運(yùn)算求子串的運(yùn)算 求子串的過(guò)程求子串的過(guò)程sub(r,s,fir,length)也是移動(dòng)字符序列的過(guò)程，也是移動(dòng)字符序列的過(guò)程，它將串它將串s中從第中從第fir位置開始的長(zhǎng)度為位置開始的長(zhǎng)度為length的子串賦給的子串賦給r。procedure sub(r,s,fir,lenth);