数据结构课后练习 - 第4章

1、第四章第四章 串串4.1 串类型的定义串类型的定义4.2 串的表示和实现串的表示和实现4.3 串的模式匹配算法串的模式匹配算法4.4 串操作应用举例串操作应用举例学习要点学习要点熟悉串的熟悉串的7种基本操作的定义，并能利用这些基本操种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作。作来实现串的其它各种操作。熟练掌握串的熟练掌握串的定长顺序存储结构定长顺序存储结构上实现串的上实现串的各种操作各种操作的方法的方法。掌握串的堆存储结构以及在其上实现串操作的基本方掌握串的堆存储结构以及在其上实现串操作的基本方法。法。一、判断对错题一、判断对错题1. 串中不可以包含有空白字符。（串中不可以包

2、含有空白字符。（ ）2. 子串是主串中字符构成的有限序列。（子串是主串中字符构成的有限序列。（ ）二、单项选择题二、单项选择题1. 串是一种特殊的线性表，其特殊性体现在串是一种特殊的线性表，其特殊性体现在_。A. 可以顺序存储可以顺序存储B. 数据元素是一个字符数据元素是一个字符C. 可以链接存储可以链接存储D. 数据元素可以任意数据元素可以任意B二、单项选择题二、单项选择题2. 求字符串求字符串T在字符串在字符串S中首次出现的位置的操作为中首次出现的位置的操作为_。A. 求串的长度求串的长度 B. 求子串求子串 C. 串的模式匹配串的模式匹配 D. 串的连接串的连接3. 若串若串S=”sof

3、tware”，其子串数目是，其子串数目是_。A. 8 B. 37 C. 36 D. 94. 字符串字符串”VARTYPE int”，若采用动态分配的顺序存储方，若采用动态分配的顺序存储方法需要法需要_个字节（设每种数据均占用个字节（设每种数据均占用2个字节）。个字节）。A. 22 B. 11 C. 10 D. 动态产生，视情况而定动态产生，视情况而定CBA三、填空题三、填空题1. 串的两种最基本的存储方式是串的两种最基本的存储方式是_和和_ 。2. 串的链式存储结构是将存储区域分成一系列大小相同串的链式存储结构是将存储区域分成一系列大小相同的节点，每个节点有两个域：的节点，每个节点有两个域：_

4、域和域和_域。其中前者用于存储数据，后者用于域。其中前者用于存储数据，后者用于存储下一个节点的指针。存储下一个节点的指针。顺序存储结构顺序存储结构链式存储结构链式存储结构数据数据指针指针四、简答题四、简答题1. 简述串的存储结构及各自的特点。简述串的存储结构及各自的特点。 定长顺序存储表示（静态存储分配的顺应表）定长顺序存储表示（静态存储分配的顺应表）：是用一组：是用一组连续的存储单元来存放串中的字符序列。连续的存储单元来存放串中的字符序列。 所谓定长顺序存储结构，是直接使用定长的字符数组来定所谓定长顺序存储结构，是直接使用定长的字符数组来定义，义，数组的上界预先给出数组的上界预先给出： #d

5、efine MAXSTRLEN 255 typedef unsigned char SStringMAXSTRLEN+1;/0号单元存串长号单元存串长 在顺序存储结构中，实现串操作的原操作为在顺序存储结构中，实现串操作的原操作为“字符序字符序列的复制列的复制”，操作的时间复杂度基于复制的字符序列操作的时间复杂度基于复制的字符序列的长度。的长度。 在在定长顺序存储表示定长顺序存储表示中，如果在操作中出现串值序列中，如果在操作中出现串值序列的长度超过上界的长度超过上界MAXSTRLEN时，约定用时，约定用截尾法处理截尾法处理； 这种情况不仅在求联接串时可能发生，在串的其它操这种情况不仅在求联接串时

6、可能发生，在串的其它操作中，如插入、置换等也可能发生。克服这个弊病只作中，如插入、置换等也可能发生。克服这个弊病只有有不限定串长的最大长度，即不限定串长的最大长度，即动态分配串值动态分配串值的存储空的存储空间间。四、简答题四、简答题1. 简述串的存储结构及各自的特点。简述串的存储结构及各自的特点。 堆分配存储表示的特点是，仍以一组地址连续的存储单元堆分配存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但存储空间是在程序执行过程中存放串值字符序列，但存储空间是在程序执行过程中动态动态分配分配而得。所以也称为而得。所以也称为动态存储分配的顺序表动态存储分配的顺序表。 在在C语言中，利

7、用动态存储管理函数语言中，利用动态存储管理函数malloc()和和free()，来，来根据实际需要根据实际需要动态分配动态分配和和释放字符数组空间释放字符数组空间。 若分配成功，则返回若分配成功，则返回一个指向起始地址的指针，作为一个指向起始地址的指针，作为串的串的基址基址，同时，为了以后处理方便，同时，为了以后处理方便，约定串长也作为存储结约定串长也作为存储结构的一部分构的一部分。 这种存储结构表示时的串操作仍是基于这种存储结构表示时的串操作仍是基于“字符序列的字符序列的复制复制” 。例如例如，串复制操作串复制操作StrCopy(&T, S)的实现算的实现算法是，若串法是，若串T已存

8、在，则先释放串已存在，则先释放串T所占空间，当串所占空间，当串S不空时，首先为串不空时，首先为串T分配大小和串分配大小和串S长度相等的存储空长度相等的存储空间，然后将串间，然后将串S的值复制到串的值复制到串T中。中。 又如，又如，串插入操作串插入操作StrInsert(&S,pos,T)的实现算法是，的实现算法是，为串为串S重新分配大小等于串重新分配大小等于串S和串和串T长度之和的存储空长度之和的存储空间，然后进行串值复制。间，然后进行串值复制。typedef struct char *ch; int length; hsring;四、简答题四、简答题1. 简述串的存储结构及各自的特点

9、。简述串的存储结构及各自的特点。 串的块链存储表示串的块链存储表示：用链表存储串，每个结点存储串的：用链表存储串，每个结点存储串的n个个字符，当串长不是字符，当串长不是n的整数倍时最后一个结点剩余位置用空的整数倍时最后一个结点剩余位置用空字符补齐。字符补齐。 如串如串ABCDEFGHI当当n=4时：时： 当当n=1时：时：A B C DE F G HI # # # headABCI head 为了为了提高存储密度，可使每个结点存放多个字符提高存储密度，可使每个结点存放多个字符。通常将。通常将结点数据域存放的字符个数定义为结点大小结点数据域存放的字符个数定义为结点大小。 显然，当结点大小大于显然

10、，当结点大小大于1时，串的长度不一定正好是结点时，串的长度不一定正好是结点的整数倍，则链表中的最后一个结点不一定全被串值占满，的整数倍，则链表中的最后一个结点不一定全被串值占满，此时通常补上此时通常补上“#”或其它的非串值字符（一般情况下或其它的非串值字符（一般情况下“#”不属于串的字符集，是一个特殊的符号）。不属于串的字符集，是一个特殊的符号）。 这种存储形式这种存储形式优点优点是存储密度高于结点大小为是存储密度高于结点大小为1 的存储形的存储形式。式。不足之处不足之处是做插入、删除字符的操作时，可能会引起是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实现起来比较复杂。结点之

11、间字符的移动，算法实现起来比较复杂。SShenda#四、简答题四、简答题2. 字符串字符串s1=abcdefghijklmnopqrstuvw，由如下运算分别，由如下运算分别得到得到s2和和s3，请给出，请给出s2和和s3的值。的值。)1 ,20, 1(),1 ,14, 1(),2 , 4 , 1(),3 ,19, 1(2sSubstringsSubStringsSubStringsSubstringatStringConcs )2(),2(, 1(3sthStringLengsthStringLengsSubStrings 四、简答题四、简答题2. 字符串字符串s1=abcdefghijkl

12、mnopqrstuvw，由如下运算分别得，由如下运算分别得到到s2和和s3，请给出，请给出s2和和s3的值。的值。)1 ,20, 1(),1 ,14, 1(),2 , 4 , 1(),3 ,19, 1(2sSubstringsSubStringsSubStringsSubstringatStringConcs Substring(s1,19,3): stu; Substring(s1,4,2): de; Substring(s1,14,1): n; Substring(s1,20,1): t. 连接的结果：连接的结果： s2=student.四、简答题四、简答题2. 字符串字符串s1=abcd

13、efghijklmnopqrstuvw，由如下运算分别，由如下运算分别得到得到s2和和s3，请给出，请给出s2和和s3的值。的值。)2(),2(, 1(3sthStringLengsthStringLengsSubStrings StringLength(s2): 7; s3=Substring(s1, 7, 7): “ghijklm”.四、简答题四、简答题3. 分析下述两个算法的具体功能。分析下述两个算法的具体功能。 SEQSTRING fun1(SEQSTRING *S, seqstring *T) /S和和T为顺序存储的串变量为顺序存储的串变量 SEQSTRING *R; int i,j

14、; for(i=0;ilen;i+) R-chi=S-chi; for(j=0;jlen;j+) R-chS-len+j=T-chj; R-len=i+j; return(R); 将串将串S与串与串T联接后赋值给联接后赋值给R四、简答题四、简答题3. 分析下述两个算法的具体功能。分析下述两个算法的具体功能。 SEQSTRING fun2(SEQSTRING S, int n1, int n2) /S为顺序存储的串变量为顺序存储的串变量 SEQSTRING T; int i; for(i=0;ihead; while ( p!=NULL ) q=r2-head; while( q!=NULL ) if ( p-data=q-data ) p1=p-next; q1=q-next; while( p1-data=q1-data ) /当前字符相同当前字符相同 p1=p1-next; q1=q1-next; if ( q1=NULL ) pos=i+1; /匹配成功返回位置匹配成功返回位置 else q=q-next; p=p-next; /从主串的下一个字符开始重新比较从主串的下一个字符开始重新比较 i+; return pos;2. 设计一个链串上实现子串定位操作的算法。设计一个链串上实现子串定位操作的算法。 比较两个串的大小比较两