《第4章串》习题解答论述.doc

第四章 串存储与基本操作的实现 本章学习要点 ◆熟悉串的相关概念以及串与线性表的关系 ◆重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现 ◆了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题 “串”(string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。 4.1串的基本概念 4.1.1串的概念 1．串的定义 串(string) 是由n个字符组成的有限序列，记为：S=”a0a1a2…an-1” (n≥0)。 其中，S是串的名字，字符序列a0a1a2…an-1是串的值，ai(0≤i≤n-1)可以是字母、数字或其他字符元素；由于在C语言系统中数组元素的下标是从0开始的，所以串中所含元素的序号等于该元素的下标值加1；串中所含字符的个数n称为该串的长度，长度为0的字符串称为空串（null string）。 从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。 例如： （1）A=“X123” (长度为4的串) （2）B=“12345654321” (长度为11的串) （3）C=“Bei Jing” (长度为8的串) （4）D=“” (长度为0的空串) （5）E=“This is a string” (长度为16的串) （6）F=“ is a ” (长度为6的串) 2．子串、主串和位置 串中任意连续的字符组成的子序列称为该串的子串；相应地，包含子串的串称为主串。串中的字符在串序列中的序号称为该字符在该串中的位置；子串的第一个字符在主串中的位置称为子串在主串中的位置。显然，串为其自身的子串，并规定空串为任何串的子串。显然，在不考虑空子串的情况下，一个长度为n的字符串具有n(n+1)/2个子串。 例如： 在上例的(6)中串F就是(5)中串E的子串，且子串F在主串E中的位置是5。由于空格符也是一个字符，所以在串G=“abc defghne”中包含有子串“c def”,而串 “cdef”不是串G的子串。串G中第一个字符‘e’的位置是6，第二个字符‘e’的位置是11。 3．串的比较 如果两个串的长度相等且对应位置上的字符相同，则称这两个串相等。两个串A、B的比较过程是：从前往后逐个比较对应位置上的字符的ASCII码值，直到不相等或有一个字符串结束为止，此时的情况有以下几种： （1）两个串同时结束，表示A等于B； （2）A中字符的ASCII码值大于B中相应位置上字符的ASCII码值或B串结束，表示A大于B； （3）B中字符的ASCII码值大于A中相应位置上字符的ASCII码值或A串结束，表示A小于B。 例如： “abc”=“abc”，“abc”“abcd”，“abxy”“abcdefg”，“132”“123456”，“ABab”“abAB”，“3+2”“2+3”。 4．空格串 由一个或多个空格字符组成的串称为空格串，空格串的长度为串中所含空格字符的个数。在串操作中不要将空格串和空串混淆。 4.1.2串的基本操作 尽管串的定义和线性表极为相似，但是串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以单个元素作为操作对象，比如对线性表的查找、访问、插入、删除和排序等；而在串的基本操作中，通常以串整体或串的一部分（子串）作为操作对象，比如子串的查找、截取子串、删除一个子串、插入子串和子串替换等操作。 串的基本操作主要有： （1）初始化串StrAssign(T,chars) 由字符串常量chars生成字符串T的操作。 （2）串复制StrCopy(T,S) 由串S复制生成串T的操作。 （3）串比较StrCompare(S,T) 若S=T返回0，ST返回正数，ST返回负数。 （4）求串长度StrLength(S) 返回串S的长度。 （5）串连接Concat(T,S1,S2) 将串S1和S2连接起来生成串T的操作。 （6）求子串SubString(Sub,S,pos,len) 以串S中pos位置开始的len个字符生成子串Sub的操作。 （7）串查找Index(S,T,pos) 返回子串T在S中pos个字符以后出现的位置。 （8）串替换Replace(S,T,V) 将串S中所有不重叠子串T替换为串V的操作。 （9）串插入StrInsert(S,pos,T) 在串S中第pos个字符前插入串T的操作。 （10）删除子串StrDelete(S,pos,len) 删除串S中第pos个字符开始的le