4.1串類型的定義
1.串：（或字符串）
串是由多個字符組成的有限序列，記作：S=‘c1c2c3…cn’ (n>0)
其中S是串的名字，‘c1c2c3…cn’ 是串值
ci是串中字符
n是串的長度，表示字符的數目
空串：零個字符的串稱為空串，記作“”（空）
2.子串
子串：串中任意連續字符組成的子序列
主串：包含子串的串
注意：空串是任意串的子串，任意串是他自身的子串。除它本身外，一個串的其他子串都是它的真子串
*字符在串中的位置：字符在序列中的序號
*子串在串中的位置：子串的第一個字符在子串中的位置
3.串相等
兩個串長度相等且各個對應位置的字符串都相等時才相等
4.空格串
由一個或多個空格組成的串，長度不為0
【串和線性表的區別：
1：數據對象：串的約束對象為字符集
2 串的操作：線性表大多以“單個元素”為操作對象；串通常以“串的整體”作為操作對象
4.2.1串的表示和實現
【1.定長順序存儲表示
*靜態分配：為每個串預先分配一個固定長度的存儲區域
*用定長數組描述
#define MAXSTRLEN 255 //最大串長
typedef unsigned char SString[MAXSTRLEN+1]
// +1個單元為 0號單元存放串的長度
【圖】
【串的連接：
status Concat(SSting&T,SString S!,SString S2)
{//用T返回由S1和S2連接而成的新串。若未截斷，則返回TURE，否則返回FALSEif(S1[0]+S2[0]<=MAXSTRLEN)\
{//未截斷T[1,...,S1[10]]=S1[1,....S1[0]]; //S1[0]表示S1的0號單元，里面是串的長度 T[S1[0]+1,...,S2[0]+S2[0]];T[0]=S1[0]+S2[0]; //長度之和uncut=TURE; //未截斷
}else if(S1[0]<MAXSTRSIZE)
{//截斷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個字符起長度為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位置開始，取長度為len的子串
Sub[0]=len; //子串的長度
return OK;}
【總結：
操作特點：
1.實現串操作特點的原操作為：“字符序列的復制”
2.在操作中當出現串的長度超過MAXSTRLEN時，約定用截斷法處理
4.2.2串的表示和實現
2.堆分配存儲表示
動態分配
仍以一組地址連續的存儲單元存放串值字符序列，但存儲空間是在程序執行過程中動態分配而得的，也稱為【動態存儲分配的順序表】。用malloc（）和free（）來分配和釋放
堆分配的存儲表示
typedef struct
{char *ch; //地址指向存儲空間 按需分配//若是非空串，則按串實用長度分配存儲區，否則ch為NULLint lentgh; //串長度} HString; 串插入
status strInsert(HString &S,int pos,HString T)
//在串S的第pos個位置前插入串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的長度之和exit(OVERFLOW); //分配失敗溢出for(i=S.length-1;i>=pos-1;--1) //length-1是節點序數，因為長度有一個0節點{ 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;
}求串長
int StrLength(HString S)
//求串長
{return S.length
}串比較
int StrCompare(HString S,HString T)
//比較兩個串，若相等返回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個字符開始長度為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;
}
時間復雜度：
最好情況：
最壞情況：
