4-数据结构-串的学习
4.1串類(lèi)型的定義
1.串：（或字符串）
串是由多個(gè)字符組成的有限序列，記作：S=‘c1c2c3…cn’ (n>0)
其中S是串的名字，‘c1c2c3…cn’ 是串值
ci是串中字符
n是串的長(zhǎng)度，表示字符的數(shù)目
空串：零個(gè)字符的串稱(chēng)為空串，記作“”（空）
2.子串
子串：串中任意連續(xù)字符組成的子序列
主串：包含子串的串
注意：空串是任意串的子串，任意串是他自身的子串。除它本身外，一個(gè)串的其他子串都是它的真子串
*字符在串中的位置：字符在序列中的序號(hào)
*子串在串中的位置：子串的第一個(gè)字符在子串中的位置
3.串相等
兩個(gè)串長(zhǎng)度相等且各個(gè)對(duì)應(yīng)位置的字符串都相等時(shí)才相等
4.空格串
由一個(gè)或多個(gè)空格組成的串，長(zhǎng)度不為0
【串和線性表的區(qū)別：
1：數(shù)據(jù)對(duì)象：串的約束對(duì)象為字符集
2 串的操作：線性表大多以“單個(gè)元素”為操作對(duì)象；串通常以“串的整體”作為操作對(duì)象
4.2.1串的表示和實(shí)現(xiàn)
【1.定長(zhǎng)順序存儲(chǔ)表示
*靜態(tài)分配：為每個(gè)串預(yù)先分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)域
*用定長(zhǎng)數(shù)組描述
#define MAXSTRLEN 255 //最大串長(zhǎng)
typedef unsigned char SString[MAXSTRLEN+1]
// +1個(gè)單元為 0號(hào)單元存放串的長(zhǎng)度
【圖】
【串的連接：
status Concat(SSting&T,SString S!,SString S2) {//用T返回由S1和S2連接而成的新串。若未截?cái)?#xff0c;則返回TURE，否則返回FALSEif(S1[0]+S2[0]<=MAXSTRLEN)\ {//未截?cái)?/span>T[1,...,S1[10]]=S1[1,....S1[0]]; //S1[0]表示S1的0號(hào)單元，里面是串的長(zhǎng)度 T[S1[0]+1,...,S2[0]+S2[0]];T[0]=S1[0]+S2[0]; //長(zhǎng)度之和uncut=TURE; //未截?cái)?/span> }else if(S1[0]<MAXSTRSIZE) {//截?cái)?/span>T[1,...,S1[10]]=S1[1,....S1[0]]; T[S1[0]+1,...,MAXSTRLEN]=S2[1,...,MAXSTRLEN-S1[0] ]; //裝不下，只截取了S2的一部分T[0]=MAXSTRLEN; uncut=FALSE; }return uncat; } //Concat }【求子串：
status SubString(SString &Sub,SString S,int pos,int len) {//用sub返回串的第pos個(gè)字符起長(zhǎng)度為len的子串//其中，1<=pos<=StrLength(S) 且0<=len<=StrLength(S)-pos+1if (pos<1||pos>S[0]||len<0||len>S[0]-pos+1)return ERROR; //不合法Sub[1..len]=S[pos..pos+len-1]; //從S的第pos位置開(kāi)始，取長(zhǎng)度為len的子串 Sub[0]=len; //子串的長(zhǎng)度 return OK;}【總結(jié)：
操作特點(diǎn)：
1.實(shí)現(xiàn)串操作特點(diǎn)的原操作為：“字符序列的復(fù)制”
2.在操作中當(dāng)出現(xiàn)串的長(zhǎng)度超過(guò)MAXSTRLEN時(shí)，約定用截?cái)喾ㄌ幚?/p>
4.2.2串的表示和實(shí)現(xiàn)
2.堆分配存儲(chǔ)表示
動(dòng)態(tài)分配
仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得的，也稱(chēng)為【動(dòng)態(tài)存儲(chǔ)分配的順序表】。用malloc（）和free（）來(lái)分配和釋放
堆分配的存儲(chǔ)表示
typedef struct {char *ch; //地址指向存儲(chǔ)空間 按需分配//若是非空串，則按串實(shí)用長(zhǎng)度分配存儲(chǔ)區(qū)，否則ch為NULLint lentgh; //串長(zhǎng)度} HString;串插入
status strInsert(HString &S,int pos,HString T) //在串S的第pos個(gè)位置前插入串T { int i;if(pos<1||pos>S.length+1) //判斷合法范圍return ERROR;if(T.length) //判斷是否為0{if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)))) //S和T的長(zhǎng)度之和exit(OVERFLOW); //分配失敗溢出for(i=S.length-1;i>=pos-1;--1) //length-1是節(jié)點(diǎn)序數(shù)，因?yàn)殚L(zhǎng)度有一個(gè)0節(jié)點(diǎn){ S.ch[i+T.length]=S.ch[i];}for(i=0;i<=T.length-1;i++)S.ch[pos-1+i]=T.ch[i];S.length+=T.length;}return OK; }求串長(zhǎng)
int StrLength(HString S) //求串長(zhǎng) {return S.length }串比較
int StrCompare(HString S,HString T) //比較兩個(gè)串，若相等返回0 {int i;for (i=0;i<S.length && i<T.length; i++)if (S.ch[i]!=T.ch[i])return S.ch[i]-T.ch[i];return S.length-T.length; }串清空
status ClearString(HString &S) //將S清空為空串 {if(S.ch){free(S.ch);S.ch=NULL;}S.length=0;return OK; }串連接
status Concat(HString &S,HString S1,HString S2){ int j; if(!(S.ch=(char*)malloc((S1.length+S2.length)*sizeof(char))))exit(OVERFLOW); for (j=0;j<=S1.length-1;j++){S.length=S1.length+S2.length;} for(j=0;j<=S2.length-1;j++){ S.ch[S1.length+j]=S2.ch[j];} return OK; }求子串
status StubString(HString &Sub,HString S,int pos,int len) // 用Sub返回串S的dipos個(gè)字符開(kāi)始長(zhǎng)度為len的子串 {if(pos<1||pos>S.length||len<0||len>S.length-pos+1)return ERROR;if(!len) {Sub.cn=NULL;Sub.length=0;}else{sub.ch=(char*)malloc(len*sizeof(char));for(int j=0;j<=len-1;j++){Sub.ch[j]=S.ch[pos-1+j];} Sub.length=len; } return OK;4.3串的模式匹配算法
4.3.1 BF算法
模式匹配：
算法：
int Index(SString S,SString T,int pos) { i=pos;j=1; while(i<=S[0]&&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]; else return 0; }時(shí)間復(fù)雜度：
最好情況：
最壞情況：
總結(jié)
以上是生活随笔為你收集整理的4-数据结构-串的学习的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 京东金条不还会有什么后果
- 下一篇： 蚂蚁花呗怎么关闭 再次开通额度会降低