數(shù)據(jù)結(jié)構(gòu)-合肥工業(yè)大學(xué) 5

NorthChinaElectricPowerUniversity第五章串第五章串5.1串的基本概念5.2串的基本操作5.3

串的存儲(chǔ)結(jié)構(gòu)NorthChinaElectricPowerUniversity5.4關(guān)于串的幾個(gè)算法NorthChinaElectricPowerUniversity例如:

S1=〝abc

〞S2=〝FORTRAN_77〞

S3=〝

〞

=

(空串)S4=

〝

〞

由4個(gè)空格組成的空格串

串是由n0個(gè)字符組成的有限序列,通常記為

S=〝a1a2a3…an-1an〞

其中,S表示串名(也稱串變量),一對(duì)引號(hào)括起來(lái)的字符序列稱為串值,ai為串的元素，可以是字母、數(shù)字或其他允許的字符。n為串的長(zhǎng)度（即串中字符的個(gè)數(shù)）,長(zhǎng)度為0的串稱為空串。一.串的定義

5.1

串的基本概念華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity

1.串值須用一對(duì)引號(hào)括起來(lái)，但引號(hào)不屬于串值。說(shuō)明2.要區(qū)分空串與由空格字符組成的串的不同。例如：a=〝

beijing〞

其值為字符串序列beijing

。華電計(jì)算機(jī)系1.子串：串中若干個(gè)連續(xù)的字符組成的子序列。例如:S=〝Beijing&Shanghai〞

T=〝jing

〞2.主串:

包含子串的串。3.序號(hào)：(1).單個(gè)字符在主串中的位置

(2).子串在主串中的序號(hào)。定義為主串中首次出現(xiàn)的該子串的第一個(gè)字符在主串中的位置。被定義為該字符在串中的序號(hào)。例如:S=〝Beijing&Nanjing&Shanghai〞

T=〝jing

〞

位置為4二.幾個(gè)名詞概念華電計(jì)算機(jī)系

的充分必要條件為兩個(gè)字符串的長(zhǎng)度相等，4.兩個(gè)字符串相等〝abcd

〞

〝

bacd

〞〝

abcd

〞=〝

abcd

〞并且對(duì)應(yīng)位置上的字符相同。5.空格串:

僅由空格組成的串，串中空格字符的個(gè)數(shù)即為其長(zhǎng)度，為了清楚起見(jiàn)，經(jīng)常用符號(hào)Ф

來(lái)表示空格?？沾嚎沾袩o(wú)任何字符，記作s=〝〞，其長(zhǎng)度為0。5.空格串:

僅由空格組成的串，串中空格字符的個(gè)數(shù)即為其長(zhǎng)度，為了清楚起見(jiàn)，經(jīng)常用符號(hào)Ф

來(lái)表示空格。華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity

5.2

串的基本操作1.將串t的值賦給串s:String

Strassign(Strings,Stringt)2.判斷兩個(gè)串是否相等EQUAL(S1,S2).相等值為真，否則為假3.兩個(gè)字符串連接CONCAT(S1,S2)把S2的值放到S1的后邊如：a=〝bei

〞,b=〝jing

〞

Concat(a,b)=〝beijing

〞,Concat(b,a)=〝jingbei

〞4.求字符串的長(zhǎng)度LEN(S)。5.求子串SUBSTR(S,i,k)表示從S串的第i個(gè)字符開始起數(shù)k個(gè)字符的子串。6.求子串在主串中的序號(hào)

INDEX(S1,S2)，求子串S2在主串S1中的位置。7.串的替換REPLACE(S,S1,S2)，把S中的子串S1用S2替換，如果S1不是S的子串，則S不變。例：a=〝Monday

〞,b=〝Mon

〞,c=〝Thurs

〞REPLACE(a,b,c)=〝Thursday

〞華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity

1、求子串在主串中的序號(hào)運(yùn)算（index(a,b,k)）思想：在a串從第k個(gè)字符起進(jìn)行搜索看是否有和b相同的子串，若有則子串的第一個(gè)字符在a中的位置便是index(a,b)的結(jié)果，若無(wú)則結(jié)果為0。voidindex(a,b,k)//求b在a中的序號(hào)ind，從第k個(gè)字符開始，第一次k等于1{n=LEN(a);m=LEN(b);ind=0;if(n-k+1<m)return；//子串>主串時(shí)返回i=k;do{if(SUBSTR

(a,i,m)==b){ind=i;exit}elsei=i+1;}while(i>n-m+1)；}華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity

2、置換運(yùn)算（REPLACE(a,b,c)）思想：在a串中搜索和b串相同的子串，若有則以C串代替這個(gè)子串，在繼續(xù)往下搜索，直到在a串中找不到和b相同的子串為止。VoidREPLACE(a,b,c)\\將a中的所有子串b置換為串c{n=LEN(a);m=LEN(b);s=LEN(c);if(n<m)return；p=1;Do{

index(a,b,p);

switch(ind){case0:break;case1:ifn==m{a=c;break}elsea=concat(c,Substr(a,m+1,n-m));華電計(jì)算機(jī)系NorthChinaElectricPowerUniversitycasen-m+1:{a=concat(sub(a,1,n-m),c);break}default:a=concat(sub(a,1,ind-1),c,sub(a,ind+m,n-ind-m+1));}//casen=n-m+s;p=ind+s;while(p>n-m+1)}華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity1.非緊縮格式(設(shè)每個(gè)字有4個(gè)字節(jié))例如:S=〝DATASTRUCTURE〞DASTRUCTATURE@DATASTRUCTURE@2.緊縮格式(按字編址）3.單字節(jié)方式(按字節(jié)編址）

5.3

串的存儲(chǔ)結(jié)構(gòu)一.串的順序存儲(chǔ)結(jié)構(gòu)ATSATRUUTCDRE@華電計(jì)算機(jī)系(按字編址）順序存儲(chǔ)中三種方式比較顯然緊縮格式節(jié)省空間，但在進(jìn)行串運(yùn)算時(shí)，需要花費(fèi)較多的時(shí)間去分離同一個(gè)字中的字符，而非緊縮格式正相反。通常一個(gè)字節(jié)恰好存儲(chǔ)一個(gè)字符的ASCII碼，這就自然形成了一個(gè)字節(jié)存放一個(gè)字符的單字節(jié)存儲(chǔ)格式，既節(jié)省空間，又處理方便。他們的共性就是空間利用率高，訪問(wèn)方便，但插入刪除不方便，鏈表存儲(chǔ)恰好彌補(bǔ)了這一不足。華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity說(shuō)明：所謂鏈結(jié)點(diǎn)大小是指每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中存放的字符的個(gè)數(shù)。二.串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)DATASTRRE

……S^結(jié)點(diǎn)大小為4的鏈表SDATE^……結(jié)點(diǎn)大小為1的鏈表華電計(jì)算機(jī)系當(dāng)結(jié)點(diǎn)大小大于1時(shí)，一個(gè)串中最后結(jié)點(diǎn)不一定全部占滿，我們一般補(bǔ)上空格符填滿。我們用

來(lái)表示NorthChinaElectricPowerUniversity符號(hào)表包括:(1)串值的起始地址。(2)串值的末尾地址。確定末尾地址的方式有三種：

a、用串長(zhǎng)來(lái)代替末尾地址。

b、串值末尾設(shè)結(jié)束符。

c、直接寫末尾地址。(3)若字?jǐn)?shù)不多可直接寫串值本身。

我們用變量作各種運(yùn)算，是通過(guò)對(duì)變量名的訪問(wèn)，而找到它的內(nèi)容的，我們對(duì)串變量進(jìn)行運(yùn)算，也需要通過(guò)變量來(lái)找到它的內(nèi)容，因此在內(nèi)存中除了存儲(chǔ)串值本身，另外在內(nèi)存中需要設(shè)一個(gè)符號(hào)表。這種方式我們叫做串變量的存儲(chǔ)映像。三、串變量的存儲(chǔ)映像華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity５.4

串的幾個(gè)算法一.串的定義typedef

structstring{int

curlen;charch[1:maxlen];}二.串的連接華電計(jì)算機(jī)系假設(shè)r,s,t都是上面定義的string型變量，且r是s與t連接后得到的串，則連接運(yùn)算concat(r,s,t)是將s與t的串值分別傳送到r相應(yīng)的位置上。NorthChinaElectricPowerUniversity1)s.curlen+t.curlen≤maxlen，這時(shí)得到的串r是連接所要求的正確結(jié)果；2)s.curlen+t.curlen>maxlen，需要將t的一部分截?cái)啵玫降拇畆只包含s和t的一個(gè)子串；3)s.curlen>maxlen，這時(shí)需要對(duì)s進(jìn)行截?cái)?，得到的串r僅是

s的一個(gè)子串；voidconcat(string&r,&s,&t;bool&p);{if(s.curlen+t.curlen<=maxlen){p=false;movch(r,s,1,1,s.curlen);movch(r,t,s.curlen+1,1,t.curlen);

r.curlen=s.curlen+t.curlen;}if((s.curlen+t.curlen>maxlen)&&(s.curlen<maxlen)){p=true;movch(r,s,1,1,s.curlen);movch(r,t,s.curlen+1,1,maxlen-s.curlen);

r.curlen=maxlen;}華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity

if(s.curlen>=maxlen){p=true;movch(r,s,1,1,maxlen);

r.curlen=maxlen;}

}voidmovch(int

t,s,i,j,num)//movch表示將位于s[j]起始的num個(gè)字符依次送到t[i]位置上

{for(k=0;k<=num-1;k++)

t[i+k]=s[j+k];}三.求子串的運(yùn)算求子串的過(guò)程sub(r,s,fir,length)也是移動(dòng)字符序列的過(guò)程，它將串s中從第fir位置開始的長(zhǎng)度為length的子串賦給r。voidsub(r,s,fir,lenth);{if((fir+length-1>s.curlen)||(fir<1)||(length<0)){printf(“inproperlyspecifiedsubstringinsubproc”);exit;}else{movch(r,s,1,fir,length);r.curlen=length;}}華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity四.求子串在串中的序號(hào)的運(yùn)算（模式匹配）voidindex_bf(s,t,ind);{i=