大话数据结构——串

串（String）：由零个或多个字符组成的有限序列。

串的抽象数据类型：

ADT 串(string)
Data   串中元素仅有一个字符组成，相邻元素具有前驱和后继关系。
Operation
	  StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T。
	  StrCopy(T,S):串S存在，由串S复制得串T。
	  ClearString(S):串S存在，将串复制得串T。
	  StringEmpty(S):若串S为空，返回true，否则返回false。
	  StrLength(S):返回串S的元素个数，即串的长度。
	  StrCompare(S,T):若S>T,返回值>0,若S=T,返回0，若S<T,返回值<0。
	  Concat(T,S1,S2):用T返回由S1和S2联接成的新串。
	  SubString(Sub,S,pos,len):串S存在，1<=pos<=StrLength(S),且0<=len<=StrLength(S)-pos+1,用Sub返回串S的第pos个字符起长度为len的子串。
	  Index(S,T,pos):串S和T存在，T是非空串，1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0.
	  Replace(S,T,V):串S、T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串。
	  StrInsert(S,pos,T):串S和T存在，1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串T。
	  StrDelete(S,pos,len):串S存在，1<=pos<=STrLength(S)-len+1,从串S中删除第pos个字符起长度为len的子串。
endADT

串的存储结构：

串的顺序存储结构：

用一组地址连续的存储单元来存储串中的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，一般使用定长数组来定义。一般数组的第一个元素存储串的长度值。

存在的问题：两串的联接Conact，新串的插入StrInsert以及字符串的替换Replace都有可能使得串序列的长度超过数组的长度MAXSIZE，出现上溢。因此串值的存储空间可在程序执行过程中动态分配。如：利用计算机的*存储区堆，堆可以利用分配函数malloc()和free()来管理。

串的链式存储结构：

一个结点可以存放一个字符，也可以存放多个字符，最后一个结点若是未被占满时，可以用#或其他非串值字符补全。一个结点存放了多少个字符，会直接影响着串处理的效率。

串的链式存储结构的优势：连接串和串时比较方便，缺点：不如顺序存储灵活，性能不如顺序存储结构好。

字符串匹配：