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

串名串值（用‘’括起來）串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。記為：

s

=‘

a1

a2

……..an’ (n≥0

)4.1

串類型的定義隱含結(jié)束符‘\0’，即ASCII碼NULL為何要單獨

“串”類型？字符串操作比其他數(shù)據(jù)類型更復(fù)雜（如拷貝、連接操作）程序設(shè)計中，處理對象很多都是串類型。若干術(shù)語：串長：串中字符的個數(shù)（n≥0）.n=0時稱為空串

?？崭翊河梢粋€或多個空格符組成的串。問：空串和空格串有無區(qū)別？答：有區(qū)別?？沾?Null

String)是指長度為零的串；而空格串(Blank

String),是指包含一個或多個空白字符‘

’(空格鍵)的字符串.子串：串S中任意個連續(xù)的字符序列叫S的子串;S叫主串。子串位置：子串的第一個字符在主串中的序號。字符位置：字符在串中的序號。串相等：串長度相等，且對應(yīng)位置上字符相等。例1：現(xiàn)有以下4個字符串：a=‘BEI’ b

=‘JING’ c

=‘BEIJING’ d

=‘BEIJING’問：①

他們各自的長度？

a=3，b

=4，c

=

7，d=8②a是哪個串的子串？在主串中的位置是多少？

a是c和d的子串，在c和d中的位置都是1③空串是哪個串的子串？a是不是自己的子串？“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串?！薄稊?shù)據(jù)結(jié)構(gòu)與算法》中山大學(xué)ADT

String{Objects: D={ai

|ai∈CharacterSet,

i=1,

2,…，n,

n≥0}Relations:

R1={<ai-1,ai>

|

ai-1,ai

∈D,i=2,

…，n}functions://至少有13種基本操作StrAssign(&T,

chars)pare(S,T)StrLength(S)Concat(&T,

S1,

S2)//串賦值，生成值為chars的串T//串比較，若S>T，返回值大于0…//求串長，即返回串S中的元素個數(shù)//串連接，用T返回S1＋S2的新串SubString(&Sub,S,pos,

len)

//求S中pos起長度為len的子串StrCopy（&T,S）……Index(S,

T,

pos)//由串S 得到T//子串定位函數(shù)（模式匹配），返回位置//用子串V替換子串TReplace(&S,

T,V)}ADT

String串的抽象數(shù)據(jù)類型定義（參見P71）最小操作子集復(fù)習(xí)：C語言中常用的串運(yùn)算C串比較：int

strcmp(char

*s1,char

*s2);求串長：int

strlen(char

*s);串連接：char strcat(char

*to,char

*from)子串T定位：char

strchr(char

*s,char

*c);……參考C語言書注：用C處理字符串時，要調(diào)用標(biāo)準(zhǔn)庫函數(shù)#include<string.h>類Cpare(S,T)StrLength(S)Concat(&T,

S1,

S2)Index(S,

T,

pos)例如：可利用串比較、求串長和求子串等操作實現(xiàn)定位函數(shù)Index(S,T,

pos).算法基本思想：在主串S中取從第i（i=pos）個字符起，取長度和串T相等的子串和串T比較，若相等，則返回值為i否則i++，直到S中不存在和T相等的子串為止。Int

Index（String

S，String

T，int

pos）{//T為非空串，若主串S中第pos個字符之后存在與T相等的子串，//則返回第一個這樣的子串在S中的位置，否則返回0；if（pos>0）{n=StrLength（S）；m=StrLength（T）；i=pos；while(i<=n-m+1){pare

(SubString

(S,i,m),

T)!=0)

++i;return

i;if(else}//while}//ifreturn0;}//Index()pare（SubString（S，i，StrLength（T）），T）=？0sSnmi=posn-m+1subsubiTTReplace(&S,

T,V)//用子串V替換子串Tq=’WORKER’。求：例1：

設(shè)

s

=’I

AM

A STUDENT’,

t

=’GOOD’,StrLength(s)

＝StrLength(t)

＝Index(s,

‘A’)=Index(s,

t)=14 //參見P714SubString(&sub,

s,

8,

7)=

‘STUDENT’SubString(&sub,

t,2,1)=‘O’30

（

s中沒有t=’GOOD’?。㊣ndex(S,

T,

pos)//返回子串T在pos之后的位置Replace(&s,

‘STUDENT’,q

)=

’I

AM

A

WORKER’解：因為SubString(s,6,2)＝‘A

’；SubString(s,7,8)＝‘STUDENT’Concat(,t,SubString(s,7,8))＝’GOOD

STUDENT’所以：Concat(,SubString(s,6,2),

Concat(t,SubString(s,7,8)))＝‘A

GOOD

STUDENT’例2：設(shè)

s

=’I

AM

A STUDENT’,

t

=’GOOD’,求：Concat(

SubString(s,6,2), Concat(

t,SubString(s,7,8)

)

)

＝？串的特點：串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集；串的基本操作和線性表差別很大串的基本操作中，通常以“串的整體”作為操作對象。4.2

串的表示首先強(qiáng)調(diào)：串與線性表的運(yùn)算有所不同，是以“串的整體”作為操作對象，例如查找某子串，在主串某位置上 一個子串等。串有三種機(jī)內(nèi)表示方法：定長順序

表示——用一組地址連續(xù)的 單元 串值的字符序列，屬靜態(tài) 方式。堆分配

表示——用一組地址連續(xù)的 單元 串值的字符序列,但

空間是在程序執(zhí)行過程中動態(tài)分配而得。串的塊鏈

表示——鏈?zhǔn)椒绞巾樞蜴準(zhǔn)蕉ㄩL順序

特點：用一組連續(xù)的單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲分配。例如：#define

Maxstrlen

255

//用戶可用的最大串長typedefunsigned

char

SString[

Maxstrlen＋1]

;

//P73SString

s; //s

是一個可容納255個字符的順序串。注：一般用SString[0]來存放串長信息;C語言約定在串尾加結(jié)束符‘\0’，以利操作加速，但不計入串長若字符串超過Maxstrlen

則自動截斷（因為靜態(tài)數(shù)組存不進(jìn)去）。例：用順序方式編寫求子串函數(shù)SubString(&Sub,S,pos,len)Status

SubString(SString

&sub,SString

S,

int

pos,intlen

){ if(pos<1

||

pos>S[0]

||

len<0

||

len>S[0]-pos+1)

return

ERROR;//若pos和len參數(shù)越界，則告警Sub[1……len]=S[pos……pos+len-1];Sub[0]=len; return

OK;}將串S中從第pos個字符開始、長度為len的字符序列 到串Sub中。（

慮到函數(shù)的通用性，應(yīng)當(dāng)讓串Sub的預(yù)留長度與S一樣）子串長度s

=‘

a1

a2

……..an’pos

lenSub[

]：想存放超長字符串怎么辦？改用動態(tài)分配的一維數(shù)組——堆堆分配

特點：仍用一組連續(xù)的單元來存放串，但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。思路：利用malloc函數(shù)合理預(yù)設(shè)串長空間。特點：

若在操作中串值改變，還可以利用realloc函數(shù)按新串長度增加空間（即動態(tài)數(shù)組概念）

。堆T的 結(jié)構(gòu)描述：Typedef

struct

{char

*ch;

//若非空串,按串長分配空間;否則ch=NULLint

length;

//串長度}HStringC是指針變量，可以自增！意即每次后移一個數(shù)據(jù)單元。直到終值為“假”停止，串尾特征是c＝‘\0’＝NULL＝Status

StrAssign(HString

&T,

char

*chars){

//生成一個串T,T值←串常量charsif(T.ch)

free(T.ch);

// T原有空間for(i=0,c=chars;

c; ++i,++c);

//求chars的串長度i例1：編寫建堆函數(shù)(參見

P76）此處T.ch[0]沒有用來裝串長，因為另有T.length分量if

(

!i

)

{T.ch

=

NULL;

T.length

=

0;}else{if

(!(T.ch

=

(char*)malloc(

i

*sizeof(ch0ar))))exit(OVERFLOW);T.ch[0..i-1]

=

chars[0..i-1];T.length

=i;}Return

OK;}

//StrAssignStatus

StrInsert

(HString

&S, int

pos, HString

T

){

//在串S的第pos個字符之前（包括尾部）

串Tif

(pos<1||pos>S.length+1)

return

ERROR;if(T.length){if

(!（S.ch=(char*)realloc(S.ch,

(S.length+T.length)*sizeof(char))

))exit(OVERFLOW);for

(i=S.length-1;

i>=pos-1;

--i

)

S.ch[i+T.length]

=

S.ch[i];S.ch[pos-1…pos+T.length-2]

=

T.ch[0…T.length-1];S.length

+

=

T.length;} return

OK;}

//StrInsert例2：用“堆”方式編寫串 函數(shù)(參見

P75)：法1密度為

；法2顯然，若更優(yōu)—稱為塊鏈結(jié)構(gòu)鏈?zhǔn)?/p>

特點

：用鏈表

串值，易

和刪除。法1：鏈表結(jié)點的數(shù)據(jù)分量長度取1（個字符）1/2密度為

4/5

；ABCINULLhead法2：鏈表結(jié)點（數(shù)據(jù)域）大小取n(例如n=4)headABCDEFGHI###NULL元素很多，用法2串值所占的

位置密度=實際分配的

位#define

CHUNKSIZE

80typedef

struct Chunk

{//每塊大小，可由用戶定義//首先定義結(jié)點類型char ch[CHUNKSIZE

];

//每個結(jié)點中的數(shù)據(jù)域struct Chunk

*next;

//每個結(jié)點中的指針域}Chunk;塊鏈類型定義：的串類型//其次定義用鏈?zhǔn)?/頭指針//尾指針//結(jié)點個數(shù)typedef struct

{Chunk

*head;Chunk

*tail;int

curLen;}Lstring;4.3

串的模式匹配算法