BeyondTechnology數(shù)據(jù)結(jié)構(gòu)東軟信息學(xué)院9.1串一、定義及相關(guān)術(shù)語(yǔ)串/String

是由零個(gè)或多個(gè)字符組成的有限序列。一般記為：s=‘a(chǎn)1a2……an’（n

0），ai（1

i

n）可以是字母、數(shù)字或其它字符。串的長(zhǎng)度

串中字符的數(shù)目稱(chēng)為串的長(zhǎng)度。零個(gè)字符的串稱(chēng)為空串，記為“

”，其長(zhǎng)度為零。子串串中任意個(gè)連續(xù)的字符組成的子序列稱(chēng)為該串的子串，包含子串的串相應(yīng)地稱(chēng)為主串。字符在串中的位置

字符在序列中的序號(hào)稱(chēng)為該字符在串中的位置。子串在主串中的位置以第一個(gè)字符在主串中的位置來(lái)表示。例：

a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEIJING’

串相等

兩個(gè)串相等，當(dāng)且僅當(dāng)這兩個(gè)串的值相等。即，只有當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等?？崭翊?/p>

由一個(gè)或多個(gè)空格組成的串‘

’稱(chēng)為空格串，其長(zhǎng)度為串中空格字符的個(gè)數(shù)。注意：串值必須用一對(duì)單引號(hào)括起來(lái)，但單引號(hào)‘

’不屬于串二、字符串的操作串的基本操作中，通常以串的整體作為操作對(duì)象。1.StrCopy(&T,S)

初始條件:串S存在.

操作結(jié)果:由串S復(fù)制到串T.2.StrCompare(S,T)

初始條件：串Ｓ和Ｔ存在．操作結(jié)果：若Ｓ＞Ｔ，則返回＞０；若Ｓ＝Ｔ，則返回值＝0;

若Ｓ＜Ｔ，則返回值＜０．３.StrLength(S)

初始條件：串Ｓ存在．操作結(jié)果：返回Ｓ的元素個(gè)數(shù)，稱(chēng)為串的長(zhǎng)度．４.Concat(&T,S1,S2)

初始條件：串S1和S2存在．操作結(jié)果：用Ｔ返回由S1和S2聯(lián)接而成的新串．５.SubString(&Sub,S,i,len)

初始條件：串Ｓ存在，1<=i<=StrLength(S),且

0<=len<=StrLength(S)-i+1.

操作結(jié)果：用Sub返回串Ｓ的第i個(gè)字符長(zhǎng)度為len的子串．６.Index(S,T)

初始條件：串Ｓ和Ｔ存在，Ｔ是非空串，操作結(jié)果：若主串S中存在和串Ｔ值相同的子串，則返回它在子串T在Ｓ中第一次出現(xiàn)的位置；否則函數(shù)值為０．７.Replace(&S,T,V)

初始條件：串S,T和V存在，T是非空串．操作結(jié)果：用V替換主串S中出現(xiàn)的所有與T相等的不重疊的串．８.ClearString(&S)

初始條件：串Ｓ存在．操作結(jié)果：將Ｓ清為空串．９.DestroyString(&S)

初始條件：串Ｓ存在．操作結(jié)果：串Ｓ被銷(xiāo)毀．10.StrInsert(&S,i,T)

初始條件：串S和T存在，1<=i<=StrLength(S)+1.

操作結(jié)果：在串S的第i個(gè)字符之前插入串Ｔ．11.StrDelete(&S,i,len)

初始條件：串S存在，1<=i<=StrLength(S)-len+1.

操作結(jié)果：從串S中刪除第i個(gè)字符起長(zhǎng)度為len的子串．例：定位函數(shù)Index（S，T，pos）算法：在主串S中從第i（pos）個(gè)字符起，取長(zhǎng)度和T相等的子串和T比較。若相等，求得函數(shù)值為i，否則i值增1直到串S中不存在和串T相等的子串為止。

intIndex(StringS,StringT,intpos){if(pos>0) n=StrLength(S); m=StrLength(T); i=pos; while(i<=n-m+1) { SubString(sub,S,i,m); if(StrCompare(sub,T)!=0)++i; elsereturni; }}return0;}二、串的表示和實(shí)現(xiàn)串有三種機(jī)內(nèi)表示方法：1.定長(zhǎng)順序存儲(chǔ)表示用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列。按照予定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)，可用定長(zhǎng)數(shù)組描述.#defineMAXSTRLEN255typedefunsignedcharSstring[MAXSTRLEN+1];

串的實(shí)際長(zhǎng)度可在予定義長(zhǎng)度的范圍內(nèi)隨意,超過(guò)予定義長(zhǎng)度的串值則被舍區(qū)去，稱(chēng)為“截?cái)唷?串長(zhǎng)度表示：1)[0]下標(biāo)分量存放串的實(shí)際長(zhǎng)度；2)串尾后加入一個(gè)不計(jì)入串長(zhǎng)的結(jié)束標(biāo)識(shí)符“\0”voidSubString(SString&sub,SStringS,intpos,intlen){ if(pos<1||pos>s[0]||len<0||len>S[0]-pos+1) returnERROR; Sub[1..len]=S[pos..pos+len-1]; Sub[0]=len; returnOK;}voidConcat(SString&T,SStringS1,SStringS2){ if(S1[0]+S2[0]<=MAXSTRING) { T[1..S1[0]]=S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]]; T[0]=S1[0]+S2[0]; Uncut=TRUE; } elseif(S1[0]<MAXSTRING) { T[1..S1[0]=S1[1..S1[0]]; T[S1[0]+1..MAXSTRING]=S2[1..MAXSTRING-S1[0]]; T[0]=MAXSTRING;uncut=FALSE;} else{ T[0..MAXSTING]=S1[0..MAXSTRING];uncut=FALSE;} returnuncut;}2.堆分配存儲(chǔ)表示仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得：malloc（）、free（）

typedefstruct{char*ch;intlength;}HString;例1：串復(fù)制StrCopy（&T，S）算法：若串T存在，則先釋放串T所占空間free（T）。當(dāng)串S不空時(shí)，首先為串T分配大小和串S長(zhǎng)度相等的存儲(chǔ)空間，然后將串S的值復(fù)制到串T中。例2：串插入StrInsert（&S，pos，T）算法：為串S重新分配大小等于串S和串T長(zhǎng)度之和

S.length+T.length的存儲(chǔ)空間，然后進(jìn)行串值復(fù)制。特點(diǎn)：1）具有順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，處理方便；

2）對(duì)串長(zhǎng)沒(méi)有限制，操作靈活。3、串的塊鏈存儲(chǔ)表示采用鏈表方式存儲(chǔ)串值

“結(jié)點(diǎn)大小”：每個(gè)結(jié)點(diǎn)既可以存放一個(gè)字符，也可以存放多個(gè)字符.

headABCDEFGHI###^headABI^C…塊鏈存儲(chǔ)表示

#defineCHUNKSIZE80typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{chunk*head,*tail;intcurlen;}Lstring;

以鏈表存儲(chǔ)串時(shí)，除頭指針外還可附設(shè)一個(gè)尾指針指示鏈表中的最后一個(gè)結(jié)點(diǎn)，并給出當(dāng)前串的長(zhǎng)度

塊鏈結(jié)構(gòu)。

設(shè)置尾指針的目的是為了便于進(jìn)行聯(lián)結(jié)操作，但需要處理第一個(gè)串尾的無(wú)效字符。三、串的模式匹配算法例：求子串位置的定位函數(shù)Index(S,T,pos)

intIndex(SStringS,SStringT,Intpos){i=pos;j=1;while(i<=S[0]s的長(zhǎng)度&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j>T[0])return(i-T[0]);elsereturn0;}/*i=i-(j-1)+1指針后退*/練習(xí)1、設(shè)s=‘IAMASTUDENT’，t=‘GOOD’，q=‘WORKER’。求：StrLength(s),14StrLength(t),4SubString(s,8,7),STUDENTSubString(t,2,1),OIndex(s,’A’),3Index(s,t),0Replace(s,’STUDENT’,q)，IAMAWORKER

Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))AGOODSTUDENT2、已知下列字符串:a=‘THIS’，f=‘ASAMPLE’，c=‘GOOD’，d=‘NE’，b=‘

’，s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))),t=Replace(f,SubString(f,3,6),c),u=Concat(SubString(c,3,1),d)，g=‘IS’,v=Concat(s,Concat(b,Concat(t,Concat(b,u)))),試問(wèn):s=THISSAMPLEISt=AGOODv=THISSAMPLEISAGOODONE,StrLength(s),14Index(v,g),3Index(u,g)0

各是什么?5.2數(shù)組一、數(shù)組的定義和特點(diǎn)定義:由一組名字相同,下標(biāo)不同的變量構(gòu)成.數(shù)組運(yùn)算給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)，修改數(shù)據(jù)元素的值()()()()()()()()()數(shù)組的特點(diǎn):

1.數(shù)組中各元素具有統(tǒng)一的類(lèi)型.2.數(shù)組元素的下標(biāo)一般具有固定的上界和下界,即數(shù)組一旦被定義,它的維數(shù)和維界就不再改變3.數(shù)組可以看成是一種特殊的線性表，元素的值并非原子類(lèi)型,可以再分解,即線性表中數(shù)據(jù)元素本身也是一個(gè)線性表.4.數(shù)組的基本操作比較簡(jiǎn)單,除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外,只有存取元素和修改元素值的操作.二、數(shù)組的順序存儲(chǔ)結(jié)構(gòu)討論:計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是一維的,而數(shù)組一般是多維的,怎樣存放?解決辦法:事先約定按某種次序?qū)?shù)組元素排成一列序列,然后將這個(gè)線性序列存入存儲(chǔ)器中.例如:在二維數(shù)組中,我們既可以規(guī)定按行存儲(chǔ),也可以規(guī)定按列存儲(chǔ).注意:

若規(guī)定好了次序,則數(shù)組中任意一個(gè)元素的存放地址便有規(guī)律可尋,可形成地址計(jì)算公式.約定的次序不同,則計(jì)算元素地址的公式也有所不同.次序約定以行序?yàn)橹餍蛞粤行驗(yàn)橹餍?/p>

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序?yàn)橹餍虼娣臿mn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序?yàn)橹餍虼娣?1m-1m*n-1mamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

a1n

a21

a22a2n

am1

am2

amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

課堂練習(xí):1.一個(gè)二維數(shù)組A,行下標(biāo)的范圍是1到6,列下標(biāo)的范圍是0到7,每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ),存儲(chǔ)器按字節(jié)編址.那么,這個(gè)數(shù)組的體積是___個(gè)字節(jié).2.數(shù)組A中,每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié),行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器中,該數(shù)組按行存放時(shí),元素A[8,5]的起始地址為_(kāi)____.A.SA+141B.SA+144C.SA+222D.SA+2253.設(shè)數(shù)組a[0…5,0…6]的基地址為1000,每個(gè)元素占5個(gè)存儲(chǔ)單元,若以列序?yàn)橹餍?順序存儲(chǔ),則元素a[4][5]的存儲(chǔ)地址為_(kāi)___.

4.二維數(shù)組X的行下標(biāo)范圍為0-5,列下標(biāo)的范圍為1-8,每個(gè)數(shù)組占6個(gè)字節(jié),則該數(shù)組的存儲(chǔ)容量為_(kāi)____個(gè)字節(jié).若已知X的最后一個(gè)元素的起始字節(jié)地址為382,則X的首地址為_(kāi)___,計(jì)為Xd.若按行存儲(chǔ),則X[1,5]的起始地址為_(kāi)__,

結(jié)束字節(jié)地址為_(kāi)____,若按列存儲(chǔ),則X[4,8]的起始字節(jié)地址為_(kāi)_____.X中第3行的元素和第4列的元素共占用_____個(gè)字節(jié).3矩陣的壓縮存儲(chǔ)

討論:1.什么是壓縮存儲(chǔ)?

若多個(gè)數(shù)據(jù)元素的值都相同,則只分配一個(gè)元素值的存儲(chǔ)空間,且零元素不占存儲(chǔ)空間.2.什么樣的矩陣具備以上壓縮條件?

一些特殊矩陣,如:對(duì)稱(chēng)矩陣,對(duì)角矩陣,三角矩陣,稀疏矩陣等.3.矩陣壓縮存儲(chǔ)的主要目的是什么?

為了節(jié)省存儲(chǔ)空間對(duì)稱(chēng)矩陣定義:若n階矩陣A中的元滿足aij=aji,則稱(chēng)為n階對(duì)稱(chēng)矩陣.

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍喝蔷仃嚩x:下(上)三角矩陣是指矩陣的上(下)三角(不包括對(duì)角線)中的元均為常數(shù)c或零的n階矩陣.

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0Loc(aij)=Loc(a11)+[(+(j-1)]*l

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍簩?duì)角矩陣定義:所有的非零元都集中在以主對(duì)角線為中心的帶狀區(qū)域中,即除了主對(duì)角線上和直接在對(duì)角線上下方若干條對(duì)角線上的元之外,所有其它元素都為0

a11

a120

…………….0

a21

a22

a23

0

……………0

0

0

…an-1,n-2an-1,n-1

an-1,n

0

0

……an,n-1ann.

0

a32a33

a34

0

………0

……………Loc(aij)=Loc(a11)+2(i-1)+(j-1)

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍合∈杈仃嚩x：非零元較零元少，且分布沒(méi)有一定規(guī)律的矩陣問(wèn)題:

如果只存儲(chǔ)稀疏矩陣中的非零元素,那這些元素的位置信息該如何表示?解決思路:

對(duì)每個(gè)非零元素增開(kāi)若干存儲(chǔ)單元,例如存放其所在的行號(hào)和列號(hào),便可準(zhǔn)確反映該元素所在位置.實(shí)現(xiàn)方法:

將每個(gè)非零元素用一個(gè)三元組(i,j,aij)來(lái)表示,則每個(gè)稀疏矩陣可用一個(gè)三元組表來(lái)表示.

M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩陣維數(shù)（6,7）唯一確定稀疏矩陣的壓縮存儲(chǔ)方法順序存儲(chǔ)結(jié)構(gòu)三元組表#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)其中t為非零元個(gè)數(shù)6

7

8

121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)行列下標(biāo)非零元值帶輔助行向量的二元組表增加一個(gè)輔助數(shù)組NRA[m+1],其物理意義是第i行第一個(gè)非零元在二元組表中的起始地址（m為行數(shù)）顯然有：NRA[1]=1NRA[i]=NRA[i-1]+第i-1行非零元個(gè)數(shù)(i2)0123456NRA1335676

7

8

212391-36143242181154-7majv012345678矩陣列數(shù)和非零元個(gè)數(shù)列下標(biāo)和非零元值NRA[0]不用或存矩陣行數(shù)二元組表需存儲(chǔ)單元個(gè)數(shù)為2(t+1)+m+1偽地址表示法偽地址：本元素在矩陣中（包括零元素在內(nèi)）按行優(yōu)先順序的相對(duì)位置

6

7

2123915-3201424243018361539-7maaddrv偽地址非零元值矩陣行列維數(shù)012345678偽地址表示法需存儲(chǔ)單元個(gè)數(shù)為2(t+1)求轉(zhuǎn)置矩陣問(wèn)題描述：已知一個(gè)稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表問(wèn)題分析一般矩陣轉(zhuǎn)置算法：for(col=0;col<n;col++)for(row=0;row<m;row++)n[col][row]=m[row][col];T(n)=O(mn)6

7

8

121213931-3361443245218611564-7ijv012345678maijv7

6

8

13-3161521122518319342446-76314012345678mb?解決思路：只要做到

將矩陣行、列維數(shù)互換將每個(gè)三元組中的i和j相互調(diào)換重排三元組次序，使mb中元素以N的行(M的列)為主序方法一：按M的列序轉(zhuǎn)置即按mb中三元組次序依次在ma中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。為找到M中每一列所有非零元素，需對(duì)其三元組表ma從第一行起掃描一遍。由于ma中以M行序?yàn)橹餍?所以由此得到的恰是mb中應(yīng)有的順序算法分析：T(n)=O(M的列數(shù)n

非零元個(gè)數(shù)t)

若t與mn同數(shù)量級(jí)，則稀疏矩陣的三元組順序表存儲(chǔ)表示#defineMAXSIZE12500typedefstruct{inti,j;ElemTypee;}Triple;Typedefunion{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;StatusTransposeSMatrix(TSMatrixM,TSMtrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){k=1;for(col=1,col<=M.nu;++col)for(p=1;p<=M.tu;++p)if(M.data[p].j==col){T.data[k].i=M.data[p].j;T.data[k].j=M.data[p].i;T.data[k].e=M.data[p].e;++k;}}returnOK;}//678

121213931-3361443245218611564-7ijv012345678ma76

8

13-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2方法二：快速轉(zhuǎn)置即按ma中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入b中恰當(dāng)位置此法關(guān)鍵是要預(yù)先確定M中每一列第一個(gè)非零元在mb中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個(gè)數(shù)實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組num[col]：表示矩陣M中第col列中非零元個(gè)數(shù)cpot[col]：指示M中第col列第一個(gè)非零元在mb中位置顯然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889colnum[col]cpot[col]12223241506170StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1,col<=M.nu;++col)num[col]=0;for(t=1,t<=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}//for}//ifreturnOK;}//算法分析：T(n)=O(M的列數(shù)n+非零元個(gè)數(shù)t)

若t與mn同數(shù)量級(jí)，則T(n)=O(mn)6

7

8

121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907

6

8

13-3161