串

定义

串是一种内容受限的线性表。

• 串/字符串：由零个或多个字符组成的有限序列
• 子串：串的任意个连续的字符组成的子序列
• 主串：包含子串的串
• 位置：字符在序列中的序号（子串在主串中的位置则以子串的第一个字符在主串中的位置来表示）
• 空格串：由一个或多个空格组成的串“ ” 空格串不等于空串，其长度为串中空格字符的个数

s=“a1 a2...an”(n>=0)

s:串名
n:串的长度（n=0时为空串）
（双引号中的字符序列为串值，其可以是字母、数字或其他字符）

抽象类型定义

线性表的基本操作：大多以“单个元素”作为操作对象。在线性表中查找某个元素，求取某个元素，在某个位置上插入一个元素或删除一个元素。
串的基本操作：通常以“串的整体”作为操作对象。在串中查找某个子串，求取一个子串，在串的某个位置上插入一个子串，以及删除一个子串。

• StrAssign (&T,chars)
  (chars是字符串常量)
  生成一个其值等于chars的串 T 。

• StrCopy (&T,S)
  由串S复制得串T

• StrEmpty (S)
  若S为空串，则返回 true ，否则返回 false

• StrCompare (S,T)
  若 S>T，则返回值 >0；若 S=T，则返回值 =0；若 S<T，则返回值 <0

• StrLength (S)
  返回S的元素个数，即串的长度

• ClearString (&S)
  将S清为空串

• Concat (&T,S1,S2)
  用T返回由S1和S2联接而成的新串

• SubString (&Sub,S,pos,len)
  ( 1<=pos<=StrLength (S) 且 0<=len<=StrLength (S) - pos + 1 )
  用Sub返回串S的第pos个字符起长度为len的子串

• Index (S,T,pos)
  (T是非空串，1<=pos<=StrLrngth (S) )
  若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0

• Replace (&S,T,V)
  (T是非空串)
  用V替换主串S中出现的所有与T相等的不重叠的子串

• StrInsert (&S,pos,T)
  ( 1<=pos<=SreLength (S) + 1 )
  在串S的第pos个字符之前插入串T

• StrDelete (&S,pos,len)
  ( 1<=pos<=StrLength (S) - len + 1 )
  从串S中删除第pos个字符起长度为 len 的子串

• DestroyString (&S)
  销毁串S

存储结构

串值的链式存储结构对某些串操作，如联接操作等，有一定方便之处，但它占用存储量大且操作复杂，不如顺序存储结构灵活。

顺序存储

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值得字符序列。
在此可回顾一下 线性表存储结构

定长顺序存储结构

根据预定义的大小，为每个定义的串变量分配一个固定长度的存储区

#define MAXLEN 255  //串的最大长度
typedef struct 
{
   char ch [ MAXLEN + 1 ];  //存储串的一维数组
   int length;  //串的当前长度
}SString;

堆式顺序存储结构

堆可以为每个新产生的串动态分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时约定串长作为存储结构的一部分。

typedef struct
{
  char *ch;  //若是非空串，则按串长分配存储区，否则 ch 为 NULL
  int length;  //串的当前长度
}HString;

链式存储

顺序串的插入和删除操作不方便，需要移动大量的字符，所以可采用单链表方式存储串。因为串结构的特殊性——结构中的每个数据元素是一个字符，则在用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。

• 当结点大小大于 1 时，由于串长不一定是结点大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上“ # ”或其他的非串值字符（通常“ # ”不属于串的字符集，是一个特殊的符号 ）。

串的链式存储结构

为进行串操作的方便，当以链表存储串值时，除头指针外，还可附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。

#define CHUNKSIZE 80  //可由用户定义的块大小
typedef struct Chunk
{
  char ch [ CHUNKSIZE ] ;  
  struct Chunk *next;
}Chunk;
typedef struct
{
  Chunk *head,*tail;  //串的头和尾指针
  int length;  //串的当前长度
}LString;

• 结点大小的选择直接影响着串处理的效率。
• 存储密度小（如结点大小为 1 时 ），运算处理方便，但存储占用量大。（ 如果在串处理过程中需进行内、外存交换的话，则会因为内、外存交换操作过多而影响处理的总效率。）一般来说，字符集小，则字符的机内编码就短，这也影响串值存储方式的选取。