4.2串的表示和实现

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

S1,S2为要连接的两个串，T为连接后的串

串T值产生的三种结果：

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联接而成的新串。若未截断，则返回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。这里，代码是比较乱，毕竟书上只提供了思路和伪代码，在此我只能说下思路。
他这个数组里面S1[0],和S2[0]，保存了整个字符串长度，从S1[1]，S2[1]开始才是存数据，
算法：4.3求子串SubString(&Sub,S,pos,len)
求子串过程即为复制字符串序列的过程，将串S中的从第pos个字符开始长度为len的字符序列复制到串Sub中。当参数非法是，返回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也差不多，大家带个数进去看看，就知道为什么要-1了。
4.2.2堆分配存储表示：
用malloc()和free()来管理。分配成功则返回起始地址指针，作为串基址。
下面是他的结构体：
typedef struct{	char *ch;	//若是非空串，则按串长分配存储区，否则为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当扩大堆区时，原数据没有被破坏，当比以前小了后，才会被破坏。
算法4.4：
下面的代码是对堆分配的存储结构的操作：
生成一个其值等于串常量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*型变量转成HString。首先获取chars长度，在到HString里面的 char*在堆区开辟空间，然后把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串的块链存储表示：
每个结点可以存放一个字符，或者存放多个字符
也可以是结点大小为1的链表
如下图所示：
为了便于进行串的操作，当以链表存储串时，除头指针外还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称如此定义的串存储结构为块链结构，说明如下：
#define CHUNKSZIE 80typedef struct Chunk{	char ch[CHUNKSZIE];	struct Chunk* next;}Chunk;typedef struct{	Chunk* head, *tail;		//串头和串尾指针	int curlen;		//串的当前长度}LString;
下面是一个存储密度的概念：
存储密度=串值所占的存储位/实际分配的存储位
密度小：运算处理方便，存储占用大