串連接Concat（&T,S1,S2）

S1,S2為要連接的兩個串，T為連接后的串

串T值產(chǎn)生的三種結(jié)果：

1.S1[0]+S2[0]<=MAXSTRLEN。

2.S1[0]<MAXSTRLEN,而S1[0]+S2[0]>MAXSTRLEN，則將串S2的一部分截斷。

3.S1[0]=MAXSTRLEN，此時串T和S1[0]相同。

如下圖所示：

代碼如下所示：

Status Concat(SString &T, SString S1, SString S2){ 	// 用T返回由S1和S2聯(lián)接而成的新串。若未截斷，則返回TRUE，否則FALSE。	int i;	Status uncut;	if (S1[0] + S2[0] <= MAXSTRLEN)  // 未截斷	{		for (i = 1; i <= S1[0]; i++) T[i] = S1[i];		for (i = 1; i <= S2[0]; i++) T[i + S1[0]] = S2[i];		T[0] = S1[0] + S2[0];		uncut = TRUE;	}	else if (S1[0] < MAXSTRLEN)		// 截斷	{  		for (i = 1; i <= S1[0]; i++) T[i] = S1[i];		for (i = S1[0] + 1; i <= MAXSTRLEN; i++) T[i] = S2[i - S1[0]];		T[0] = MAXSTRLEN;		uncut = FALSE;	}	else // 截斷(僅取S1)	{                         		for (i = 0; i <= MAXSTRLEN; i++) T[i] = S1[i];		uncut = FALSE;	}	return uncut;} // Concat分析：
這里的MAXSTRLEN是宏，書上把他定義為255。這里，代碼是比較亂，畢竟書上只提供了思路和偽代碼，在此我只能說下思路。
他這個數(shù)組里面S1[0],和S2[0]，保存了整個字符串長度，從S1[1]，S2[1]開始才是存數(shù)據(jù)，
算法：4.3求子串SubString(&Sub,S,pos,len)
求子串過程即為復制字符串序列的過程，將串S中的從第pos個字符開始長度為len的字符序列復制到串Sub中。當參數(shù)非法是，返回ERROR
代碼如下：
Status SubString(SString &Sub, SString S, int pos, int len) {	// 用Sub返回串S的第pos個字符起長度為len的子串。	// 其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。	int i;	if (pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1)		return ERROR;	for (i = 1; i <= len; i++)		Sub[i] = S[pos + i - 1];	Sub[0] = len;	return OK;} // SubString下面來分析下：
這里的StrLength(S)意思就是S的長度。這里面len<=StrLength(S)-pos+1。大家可以舉個例子，如果Strlength(S)是5，pos也是5，那么就是在第五個位置開始尋址，所以要+1。
這里的pos+i-1也差不多，大家?guī)€數(shù)進去看看，就知道為什么要-1了。
4.2.2堆分配存儲表示：
用malloc()和free()來管理。分配成功則返回起始地址指針，作為串基址。
下面是他的結(jié)構(gòu)體：
typedef struct{	char *ch;	//若是非空串，則按串長分配存儲區(qū)，否則為NULL	int length;	//串長}HString;
算法4.3：串插入操作StrInsert(&S,pos,T)為串S重新分配大小等于串S和串T長度之和的存儲科技，然后進行串值復制。
代碼如下：
Status StrInsert(HString &S, int pos, HString T) { 	// 1≤pos≤StrLength(S)＋1。在串S的第pos個字符之前插入串T。	int i;	if (pos < 1 || pos > S.length + 1)  // pos不合法		return ERROR;	if (T.length) {    // T非空,則重新分配空間,插入T		if (!(S.ch = (char *)realloc(S.ch, (S.length + T.length + 1)*sizeof(char))))			return ERROR;		for (i = S.length - 1; i >= pos - 1; --i)  // 為插入T而騰出位置			S.ch[i + T.length] = S.ch[i];		for (i = 0; i < T.length; i++)         // 插入T			S.ch[pos - 1 + i] = T.ch[i];		S.length += T.length;	}	return OK;} // StrInsert分析：
這里的realloc當擴大堆區(qū)時，原數(shù)據(jù)沒有被破壞，當比以前小了后，才會被破壞。
算法4.4：
下面的代碼是對堆分配的存儲結(jié)構(gòu)的操作：
生成一個其值等于串常量chars的串T
 代碼如下：
Status StrAssign(HString& T, char* chars){	int i;	char *c;	if (T.ch)		free(T.ch);	for (i = 0, c = chars; *c; ++i, ++c);	//求chars的長度	if (!i)	{		T.ch = NULL;		T.length = 0;	}	else	{		if (!(T.ch = (char*)malloc(i*sizeof(char))))			exit(OVERFLOW);		for (int j = 0; i < i; j++)		{			T.ch[j] = chars[j];		}		T.length = i;	}	return Ok;}
這個程序的思路就是：
把char*型變量轉(zhuǎn)成HString。首先獲取chars長度，在到HString里面的 char*在堆區(qū)開辟空間，然后把chars依次給T.ch【x】。
求串S的長度：
int StrLength(HString S){	return S.length;}
字符串比較：
代碼如下：
int StrCompare(HString S, HString T){	//S>T返>0,S=T返0，S<T返<09	for (int 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;}分析下：
這里S.ch[i]-T.ch[i]這個地方是比較ASCII。前者大返回正，后者大返回負。
當某一個串比到最后，說明前面的都一樣，最后看長度，如果長度一樣就返回0，不一樣的話，大家懂的。
清空S串：
代碼如下：
Status ClearString(HString& S){	if (S.ch)	{		free(S.ch);		S.ch = NULL;	}	S.length = 0;	return Ok;}
4.23串的塊鏈存儲表示：
每個結(jié)點可以存放一個字符，或者存放多個字符
也可以是結(jié)點大小為1的鏈表
如下圖所示：
為了便于進行串的操作，當以鏈表存儲串時，除頭指針外還可以附設(shè)一個尾指針指示鏈表中的最后一個結(jié)點，并給出當前串的長度。稱如此定義的串存儲結(jié)構(gòu)為塊鏈結(jié)構(gòu)，說明如下：
#define CHUNKSZIE 80typedef struct Chunk{	char ch[CHUNKSZIE];	struct Chunk* next;}Chunk;typedef struct{	Chunk* head, *tail;		//串頭和串尾指針	int curlen;		//串的當前長度}LString;
下面是一個存儲密度的概念：
存儲密度=串值所占的存儲位/實際分配的存儲位
密度?。哼\算處理方便，存儲占用大