算法与数据结构 C语言版 第二版 (陈守孔 孟佳娜 武秀川 著) 机械工业出版社 课后答案 第4章 串

课后答案网 4 章 串 一、基础知识题 述下列每对术语的区别： 空串和空格串； 串常量与串变量；主串和子串；串变量的名字和串变量的值；静态分配的顺序串与动态分配的顺序串。 【解答】 不含任何字符的串称为空串，其长度为 0。仅含有空格字符的串称为空格串，其长度为串中空格字符的个数。空格符可用来分割一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。 用引号（数据结构教学中通常用单引号，而 C 语言中用双引号）括起来的字符序列称为串常量，串值可以变化的 量称为串变量。 串中任意个连续的字符组成的子序列被称为该串的 子串 。包含子串的串又被称为该子串的 主串 。子串在主串中第一次出现的第一个字符的位置称子串在主串中的 位置 。 串变量的与其它变量一样，要用名字引用其值，串变量的名字也是标识符，串变量的值可以修改。 串的存储也有静态存储和动态存储两种。静态存储指用一维数组，通常一个字符占用一个字节，需要静态定义串的长度，具有顺序存储结构的优缺点。若需要在程序执行过程中，动态地改变串的长度，则可以利用标准函数 和动态地分配或释放存储单元，提高存储资 源的利用率。在 态分配和回收的存储单元都来自于一个被称之为“堆”的自由存储区，故该方法可称为 堆分配存储 。类型定义如下所示： 有串 S= T= I a R=！，求： （ 1） ， R) （ 2） ， 8， 7） （ 3） ) （ 4） ， a ) （ 5） ， 8， S) （ 6） ， ， 8， 7)， ) 【解答】 (1) ， R)= I a (2) ， 8， 7） = (3) )=14 (4) ， a )=3 (5) ， 8， S)= I a (6) ， ， 8， 7)， )= I a 串 9898 ， #， 012345，执行 课后答案网 1， 1， 2)， 3)， 4，2， 8 )， 2) 操作的结果是什么？ 【解答】 1,1,2),3),4，2, 8 ),2) = 1,1,4,3),4,2,4) = 1, , 1234 ) = #G , 1234 ) = # S 为一个长度为 中的字符各不相同，则 空且不同于 个数是多少？ 【解答】 长度为 空且 不同于 个数计算如下： 长度为 1 的子串有 n 个，长度为 2 的子串有 度为 3 的子串有 ，长度为 个，长度为 个（按题意要求这个子串就是 S 本身，不能计算在总数内）。故子串个数为 :(2+n)*(2 法 (字符串匹配算法 )较 素的字符串匹配 )算法有哪些改进 ? 【解答】 法的最大特点是主串指针不回溯，在整个匹配过程中，对主串从头到尾扫描一遍，对于处理存储在外存上的大文件是非常有效的。 虽然 素的字符串匹配 )算法 的时间复杂度是 O(n*m)，但在一般情况下，其实际的执行时间近似于 O(n+m)，因此至今仍被采用。 法仅当主串与模式间存在许多“部分匹配”的情况下才显得比 素的字符串匹配 )算法快得多。 串 的 数值。 【解答】 式串 t=求模式串的 数的值。 【解答】 j 1 2 3 4 5 6 7 8 9 10 11 12 t 串 a b a b a a a b a b a a j 0 1 1 2 3 4 2 2 3 4 5 6 j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 t 串 a b c a a b b c a a b d 课后答案网 S= T= 画出以 S 为目标串的匹配过程。 【解答】 i=1 第一趟匹配 ： a a b c b a b c a a b c a a b a b j=1 i=2 第二趟匹配： a b a b c a b c a c b a b b c j=2 i=3 第三趟匹配： a b a b c a b c a c b a b b j=1 i=7 第四趟匹配： a b a b c a b c a c b a b b c a (匹配成功 ) j=4 择题： 下面关于串的的叙述中，哪一个是不正确的？ A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储 【解答】 B 择题： 串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？ A数据元素是一个字符 B. 可以顺序存储 a b j 0 1 1 1 2 2 3 1 1 2 2 3 1 2 j 0 1 1 0 2 1 3 1 0 2 1 3 0 1 课后答案网 . 数据元素可以是多个字符 D. 可以链接存 储 【解答】 A 二、算法设计题 写出用单链表表示的字符串结点类型的定义，并依次实现它的计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置的 6个函数。要求每个字符串结点中只存放一个字符。 【解答】单链表结点的类型定义如下： * (1) 计算串长度 ) 求带头结点的用单链表表示的字符串的长度 p=L- j=0; 计数器初始化 p) j+; p=p- 计数器加 1，指针后移 j; (2) 串赋值 ) /字符串赋值 s,*p,*r; s=(); s-; /r 记住尾结点 L=L- /串中第一字符 !=p=(); p- /赋值 p-r- /插入链表中 r-p; r=p; /指向新的尾结点 L=L- s; (3) 判断两串相等 s, q) /判断字符串的相等 p=s-r=q-课后答案网 p & r) if(p-r-p=p-r=r- ; p & !r) ; ; (4) 求子串 , i) /求串 S从 始的 p,*r,*s=S-j=1; if(; s!=& j+; s= 起始位置太大 n” ); ); j=0; s!=& s-p-r-r-p; r=p; j+; 算法结束 (5) 两串连接 , ) 求串 的连接，返回结果串 p=S; 课后答案网 p- /查找串尾 p=p-p-); /释放头结点 ; (6) 求子串在主串中位置 , ) /求子串在主串中的位置，成功时返回其在主串的位序，否则返回 0表示失败 i=1,j=1; p=S- 中的起始结点的指针 q=S- 中的工作指针 r=T- 中的工作指针 q & r） q-r- q=q-r=r-i+; 对应字母相等，指针后移 失 配时 ,S 起始结点后移 ,T 从首字符结点开始 j=i; p=p-q=p-r=T- r=j); p 是子串在主串第一字符结点的指针 ; 中出现 算法结束 顺序结构存储的串 S，编写算法删除 S 中第 i 个字符开始的 j 个字符 。 【 题目分析】 我