4.1 串类型的定义
随着计算机技术的不断发展，计算机被越来越多地用于解决非数值处理问题，这些问题中大量使用到字符串（或简称为串）。串是一种特殊的线性表，它的节点数据仅由字符组成。
在早期的程序设计语言中，串仅在输入或输出中以常量的形式出现，并不参与运算。随着计算机在各个领域的广泛应用，串在文字编辑、词法扫描、符号处理及定理证明等许多领域得到了越来越广泛的应用。在高级语言中也引入了串变量的概念，如同整型、实型变量一样，串变量也可以参与各种运算。
数组几乎是所有程序设计语言都支持的一种数据类型。
本章将讨论串的基本概念、存储表示、模式匹配算法以及串操作的简单应用举例，介绍数组的概念、数组的顺序表示、矩阵的存储、稀疏矩阵的运算等，最后是对广义表的定义、存储表示的介绍以及基本运算和递归算法的实现描述。
本章主要内容
& 串的特性
& 顺序串的各种基本运算的实现算法
& 串匹配的KMP算法
& 串操作的应用方法和特点
& 数组在按行和按列优先顺序存储结构中地址的计算方法
& 稀疏矩阵的定义、各种存储结构及基本运算实现算法
& 广义表及其递归算法
4.1 串类型的定义
串是由零个或多个字符组成的有限序列，一般记为：
s="
" （n≥0）
其中s是串名，用双引号括起来的字符序列是串的值；ai（1≤i≤n）可以是字母、数字或其他字符，串中的字符个数n称为串的长度。零个字符的串称为空串，其长度为0。
串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串，通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
例如，设A，B，C分别为：
A="This is a string"
B="string"
C=" "
其中，A串的长度为16；B串的长度为6；C串的长度为2。B串是A串的子串，B串在A串中的位置为11，而C串是长度为2的串，它不是A和B的子串。
串的基本运算如下。
（1）串赋值Assign(s,t)：将一个值赋给串s。
初始条件：串t存在。
操作结果：将串t的值赋给串s。
（2）串复制StrCopy(s,t)：将一个串t赋给串s。
操作结果：将串t的值赋给串s。
（3）求串长StrLength(s)：返回串s的长度。
初始条件：串s存在。
操作结果：返回串s的长度。
（4）判断串相等StrEqual(s,t)：两个串s和t相等时返回1，否则返回0。
初始条件：串s和串t存在。
操作结果：若串s和串t相等，则函数返回true，否则返回false。
（5）串连接Concat(s,t)：返回串s和串t连接的结果。
初始条件：串s和串t存在。
操作结果：串s和串t连接成一个新串，并赋值给串s。
（6）求子串SubStr (s,i,j)：返回串s的第i个位置开始的j个字符组成的串。
初始条件：s存在，0≤i<len(s)，0≤j≤len(s) ? start。
操作结果：从串s中第i个字符起，长度为j的字符序列。
（7）查找定位位置Index(s,t)：返回子串t在主串s中的位置。
初始条件：串s和串t存在，t为非空串。
操作结果：若主串s 中存在和t相等的子串，则返回它在主串s中第一次出现的位置，否则返回0。
（8）子串插入InsStr(s,i,t)：将子串t插入到串s的第i个位置。
初始条件：串s和t存在，1≤i≤len(s)+1。
操作结果：在串s中第i个字符前插入串t。
（9）子串删除DelStr(s,i,j)：删除串s中从第i个位置开始的j个字符。
初始条件：串s存在，1≤i≤len(s) ? j +1。
操作结果：从串s中删除第i个字符起长度为j的子串。
（10）子串替换RepStrAll(s,s1,s2)：将串s中子串s1的所有出现均替换成s2。
初始条件：串s、s1和s2存在，s1为非空串。
操作结果：用串s2置换串s中出现的所有与串s1相同的不重叠子串。
（11）输出串DispStr(s)：显示串s的所有字符。