串-第4章-《数据结构题集》答案解析-严蔚敏吴伟民版习题集解析部分
第4章串
——《数据结构题集》-严蔚敏.吴伟民版
源码使⽤说明链接☛☛☛
课本源码合辑链接☛☛☛
习题集全解析链接☛☛☛
相关测试数据下载链接☛
本习题⽂档的存放⽬录：数据结构\▼配套习题解析\▼04 串字符串长度17模式串长度
⽂档中源码的存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04
源码测试数据存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04\Data
⼀、基础知识题
4.1❶简述空串和空格串（或称空格符串）的区别。
4.2❷对于教科书4.1节中所述串的各个基本操作，讨论是否可由其他基本操作构造⽽得，如何构造？
4.3❶设s = ‘I AM A STUDENT’，t = ‘GOOD’，q = ‘WORKER’。
求：StrLength(s)，StrLength(t)，SubString(s, 8, 7)，SubString(t, 2, 1)，Index(s, ‘A’)，Index(s, t)，Replace(s, ‘STUDENT’, q)，Concat(SubString(s, 6, 2), Concat(t, SubString(s, 7, 8)))。
4.4❶已知下列字符串
a = ‘THIS’,　f = ‘A SAMPLE’,　c = ‘GOOD’,　d = ‘NE’,
b = ‘ ’.
s = Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2)))),
t = Replace(f, SubString(f, 3, 6), c),
u = Concat(SubString(c, 3, 1), d),
g = ‘IS’,
v = Concat(s, Concat(b, Concat(t, Concat(b, u)))),
试问：s，t，v，StrLength(s)，Index(v, g)，Index(u, g)各是什么？
4.5❶试问执⾏以下函数会产⽣怎样的输出结果？
void demonstrate()
{
StrAssign(s, ‘THIS IS A BOOK’);
Replace(s, SubString(s, 3, 7), ‘ESE ARE’);
StrAssign(t, Concat(s, ‘S’));
StrAssign(u, ‘XYXYXYXYXYXY’);
StrAssign(v, SubString(u, 6, 3));
StrAssign(w, ‘W’);
printf(‘t=’, t, ‘v=’, v, ‘u=’, Replace(u, v, w));
}//demonstrate
4.6❷已知：s = ‘(XYZ)+*’,t = ‘(X+Z)*Y’。试利⽤联接、求⼦串和置换等基本运算，将s转化为t。
4.7❷令s = ‘aaab’,t = ‘abcabaa’,u = ‘abcaabbabcabaacbacba’。试分别求出它们的next函数值和nextval函数值。
4.8❷已知主串s = ‘ADBADABBAABADABBADADA’,
模式串pat = ‘ADABBADADA’,
写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。
4.9❸在以链表存储串值时，存储密度是结点⼤⼩和串长的函数。假设每个字符占⼀个字节，每个指针占4个字节，每个结点的⼤⼩为4的整数倍，已知串长的分布函数为f(l)且，求结点⼤⼩为4k，串长为l时的存储密度d(4k, l)（⽤公式表⽰）。
⼆、算法设计题
在编写4.10⾄4.14题的算法时，请采⽤StringType数据类型：
StringType是串的⼀个抽象数据类型，它包含以下五种基本操作：
void StrAssign (StringType &t, StringType s);    //将s的值赋给t。s的实际参数可以是串变量或者串常量（如：‘abcd’）。
int StrCompare (StringType s, StringType t);  //⽐较s和t。若s>t，返回值>0；若s=t，返回值=0；若s<t，返回值<0。
int StrLength (StringType s);          //返回s中的元素个数，即该串的长度。
StringType Concat (StringType s, StringType t);  //返回由s和t联接⽽成的新串。
StringType SubString (StringType s, int start, int len) ; //当1≤start≤StrLength(s)且0≤len≤StrLength(s)-start+1时，返回s中第start个字符起长度为len的⼦串，否则返回空串。
顺序串
4.10❸编写对串求逆的递推算法。
4.11❸编写算法，求得所有包含在串s中⽽不包含在串t中的字符（s中重复的字符只选⼀个）构成的新串r，以及r中每个字符在s中第⼀次出现的位置。
4.12❸编写⼀个实现串的置换操作Replace(&S, T, V)的算法。
4.13❸编写算法，从串s中删除所有和串t相同的⼦串。
4.14❹利⽤串的基本操作以及栈和集合的基本操作，编写“由⼀个算术表达式的前缀式求后缀式”的递推算法（假设前缀式不含语法错误）。
在编写4.15⾄4.20题的算法时，请采⽤教科书4.2.1节中所定义的定长顺序存储表⽰，⽽不允许调⽤串的基本操作。
4.15❸编写算法，实现串的基本操作StrAssign(&T, chars)。
4.16❸编写算法，实现串的基本操作StrCompare(S, T)。
4.17❸编写算法，实现串的基本操作Replace(&S, T, V)。
4.18❸编写算法，求串s所含不同字符的总数和每种字符的个数。
4.19❸在串的定长顺序存储结构上直接实现4.11题要求的算法。
4.20❸编写算法，从串s中删除所有和串t相同的⼦串。
块链串
4.21❹假设以结点⼤⼩为1（且附设头结点）的链表结构表⽰串。试编写实现下列六种串的基本操作
StrAssign，StrCopy，StrCompare，StrLength，Concat和SubString的函数。
4.22❹假设以块链结构表⽰串。试编写将串s插⼊到串t中某个字符之后的算法（若串t中不存在此字符，则将串s联接在串t的末尾）。
4.23❹假设以块链结构作串的存储结构。试编写判别给定串是否具有对称性的算法，并要求算法的时间复杂度为O(StrLength(S))。
堆串
在编写4.24⾄4.26题的算法时，请采⽤教科书4.2.2节中所定义的堆分配存储表⽰。
4.24❸试写⼀算法，在串的堆存储结构上实现串基本操作Concat(&T, s1，s2)。
4.25❸试写⼀算法，实现堆存储结构的串的置换操作Replace(&S, T, V)。
4.26❸试写⼀算法，实现堆存储结构的串的插⼊操作 StrInsert(&S, pos, T)。
顺序串
4.27❸当以教科书4.2.1节中定义的定长顺序结构表⽰串时，可如下所述改进定位函数的算法：先将模式串t中的第⼀个字符和最后⼀个字符与主串s中相应的字符⽐较，在两次⽐较都相等之后，再依次从t的第⼆个字符逐个⽐较。这样做可以克服算法Index（算法4.5）在求模式
串’a k b’（a k表⽰连续k个字符’a’）在主串’a n b’（k≤n）中的定位函数时产⽣的弊病。试编写上述改进算法，并⽐较这两种算法在作
Index（’a n b’,’a k b’）运算时所需进⾏的字符间的⽐较次数。
块链串
4.28❹假设以结点⼤⼩为1（带头结点）的链表结构表⽰串，则在利⽤next函数值进⾏串匹配时，在每个结点中需设三个域：数据域chdata、指针域succ和指针域next。其中chdata域存放⼀个字符；succ域存放指向同⼀链表中后继结点的指针；next域在主串中存放指向同⼀链表中前驱结点的指针；在模式串
中，存放指向当该结点的字符与主串中的字符不等时，在模式串中下⼀个应进⾏⽐较的字符结点（即与该字符的next函数值相对应的字符结点）的指针，若该节点字符的next函数值为0，则其next域的值应指向头结点。试按上述定义的结构改写求模式串的next函数值的算法。
4.29❹试按4.28题定义的结构改写串匹配的改进算法（KMP算法）。
顺序串
4.30❺假设以定长顺序存储结构表⽰串，试设计⼀个算法，求串s中出现的第⼀个最长重复⼦串及其（第⼀次出现的）位置，并分析你的算法的时间复杂度。
4.31❺假设以定长顺序存储结构表⽰串，试设计⼀个算法，求串s和串t的⼀个最长公共⼦串，并分析你的时间复杂度。若要求第⼀个出现的最长公共⼦串（即它在串s和串t的最左边的位置上出现）和所有的最长公共⼦串，讨论你的算法能否实现。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。