第4章数据结构习题题目及答案串

一、基础知识题4.1简述下列每对术语的区别：空串和空格串；串常量与串变量；主串和子串；串变量的名字和串变量的值；静态分配的顺序串与动态分配的顺序串。【解答】不含任何字符的串称为空串，其长度为0。仅含有空格字符的串称为空格串，其长度为串中空格字符的个数。空格符可用来分割一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。用引号（数据结构教学中通常用单引号，而C语言中用双引号）括起来的字符序列称为串常量，其串值是常量。串值可以变化的量称为串变量。串中任意个连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。子串在主串中第一次出现时的第一个字符的位置称子串在主串中的位置。串变量与其它变量一样，要用名字引用其值，串变量的名字也是标识符，串变量的值可以修改。串的存储也有静态存储和动态存储两种。静态存储指用一维数组，通常一个字符占用一个字节，需要静态定义串的长度，具有顺序存储结构的优缺点。若需要在程序执行过程中，动态地改变串的长度，则可以利用标准函数malloc()和free()动态地分配或释放存储单元，提高存储资源的利用率。在C语言中，动态分配和回收的存储单元都来自于一个被称之为“堆”的自由存储区，故该方法可称为堆分配存储。类型定义如下所示：typedefstruct{char*str;intlength;}HString;4.2设有串S=’good’，T=’I︼am︼a︼student’，R=’！’，求：（1）StringConcat(T，R)（2）SubString(T，8，7）（3）StringLength(T)（4）Index(T，’a’)（5）StringInsert(T，8，S)（6）Replace(T，SubString(T，8，7)，’teacher’)【解答】(1)StringConcat(T，R)=’I︼am︼a︼student！’(2)SubString(T，8，7）=’student’(3)StringLength(T)=14(4)Index(T，’a’)=3(5)StringInsert(T，8，S)=’I︼am︼a︼goodstudent’(6)Replace(T，SubString(T，8，7)，’teacher’)=’I︼am︼a︼teacher’4.3若串S1=‘ABCDEFG’，S2=‘9898’，S3=‘###’，S4=‘012345’，执行concat(replace(S1，substr(S1，length(S2)，length(S3))，S3)，substr(S4，index(S2，‘8’)，length(S2)))操作的结果是什么？【解答】concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4，index(S2,‘8’),length(S2)))=concat(replace(S1,substr(S1,4,3),S3),substr(S4,2,4))=concat(replace(S1,’DEF’,S3),’1234’)=concat(‘ABC###G’,’1234’)=‘ABC###G1234’4.4设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数是多少？【解答】长度为n的字符串中互异的非平凡子串（非空且不同于S本身）的个数计算如下：长度为1的子串有n个，长度为2的子串有n-1个，长度为3的子串有n-2个，……，长度为n-1的子串有2个，长度为n的子串有1个（按题意要求这个子串就是S本身，不能计算在总数内）。故子串个数为:(2+n)*(n-1)/24.5KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?【解答】KMP算法的最大特点是主串指针不回溯，在整个匹配过程中，对主串从头到尾扫描一遍，对于处理存储在外存上的大文件是非常有效的。虽然Brute(朴素的字符串匹配)算法的时间复杂度是O(n*m)，但在一般情况下，其实际的执行时间近似于O(n+m)，因此至今仍被采用。KMP算法仅当主串与模式间存在许多“部分匹配”的情况下才显得比Brute(朴素的字符串匹配)算法快得多。4.6求串’ababaaababaa’的next函数值。【解答】4.7模式串t=’abcaabbcaabdab’，求模式串的next和nextval函数的值。【解答】4.8对S=’aabcbabcaabcaaba’，T=’bca’，画出以T为模式串，S为目标串的匹配过程。【解答】↓i=1第一趟匹配：aabcbabcaabcaabab↑j=1↓i=2第二趟匹配：ababcabcacbabbcj123456789101112t串ababaaababaanext[j]011234223456j1234567891011121314t串abcaabbcaabdabnext[j]01112231122312nextval[j]01102131021301↑j=2↓i=3第三趟匹配：ababcabcacbabb↑j=1↓i=7第四趟匹配：ababcabcacbabbca(匹配成功)↑j=44.9选择题：下面关于串的的叙述中，哪一个是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储【解答】B4.10选择题：串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？A．数据元素是一个字符B.可以顺序存储C.数据元素可以是多个字符D.可以链接存储【解答】A二、算法设计题4.11试写出用单链表表示的字符串结点类型的定义，并依次实现它的计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置的6个函数。要求每个字符串结点中只存放一个字符。【算法4.11】单链表结点的类型定义如下：typedefstructNode{chardata;structNode*next;}LNode，*LinkedString；(1)计算串长度intStringLength(LinkedStringL){∥求带头结点的用单链表表示的字符串的长度p=L-next;∥p指向串中第一个字符结点j=0;∥计数器初始化while(p){j++;p=p-next;}∥计数器加1，指针后移returnj;}(2)串赋值LinkedStringStringAssign(LinkedStringL){//将字符串L的值赋给串sLNode*s,*p,*r;s=(char*)malloc(sizeof(char));s-next=null;//头结点r=s;//r记住尾结点L=L-next;//串中第一字符while(L){p=(char*)malloc(sizeof(char));p-data=L-data;//赋值p-next=r-next;//插入链表中r-next=p;r=p;//指向新的尾结点L=L-next;}returns;}(3)判断两串相等intStringEqual(LinkedStrings,LinkedStringq){//判断字符串的相等LNode*p=s-next,*r=q-next;while(p&&r)if(p-data==r-data){p=p-next;r=r-next;}elsereturn0;if(!p&&!r)return1;elsereturn0;}(4)求子串LinkedStringSubstring(LinkedStringS,intstart,inti){//求串S从start开始的i个字符所组成的子串LNode*sub,*p,*r,*s=S-next;intj=1;if(start1||i0){printf(“参数错误\n”);exit(0);}sub=(char*)malloc(sizeof(char));sub-next=null;//头结点r=sub;while（s!=null&&jstart）//查找起始结点{s=s-next;j++;}if（s==null）{printf(“起始位置太大\n”);exit(0);}else{j=0;while（s!=null&&ji）//若i太大，则截取到串尾{p=(char*)malloc(sizeof(char));p-data=s-data;p-next=r-next;r-next=p;r=p;j++;}}returnsub;}∥算法结束(5)两串连接LinkedStringConcat(LinkedStringS,LinkedStringT){∥求串S和串T的连接，返回结果串LNode*p=S;while(p-next!=null)//查找串尾p=p-next;p-next=T-next;free(T);//释放头结点returnS;}(6)求子串在主串中位置intIndex(LinkedStringS,LinkedStringT){//求子串在主串中的位置，成功时返回其在主串的位序，否则返回0表示失败inti=1;j=1;∥i记主串当前结点，j记子串在主串中的位序p=S-next；∥p是每趟匹配时S中的起始结点的指针q=S-next；∥q是S中的工作指针r=T-next；∥r是T中的工作指针while（q&&r）if（q-data==r-data）{q=q-next;r=r-next;i++;}∥对应字母相等，指针后移else∥失配时,S起始结点后移,T从首字符结点开始{i++;j=i;∥j记子串在主串中的位序q=p-next；p=p-next；r=T-next；}if（r==null）return(j);∥j是子串在主串的位序，p是子串在主串第一字符结点的指针elsereturn0;∥T并未在S中出现}∥算法结束4.12用顺序结构存储的串S，编写算法删除S中第i个字符开始的j个字符。【题目分析】我们使用教材中定义的串的顺序存储结构。【算法4.12】voidStringDelete(STringS,inti,intj){//在顺序存储的串S中删除自第i个字符开始的j个字符if(i1||iS.curlen||j0){printf(“参数错误\n”);exit(0);}if(i+j-1S.curlen)//若j太大，则从第i个字符起，删除到串尾j=S.curlen-i+1;for(ii=i+j-1;iiS.curlen;ii++)S.ch[i++]=S.ch[ii];S.curlen-=j;}4.13输入一个字符串，内有数字和非数字字符，如：ak123x45617960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入a[0]，456放入ａ[1]，……。编写算法统计其共有多少个整数，并输出这些整数。【题目分析】在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。【算法4.13】intCountInt（）∥从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数｛charch;inti=0，a[]；∥整数存储到数组a，i记整数个数scanf(“％c”，&ch）；∥从左到右读入字符串while（ch!=‘#’）∥‘#’是字符串结束标记if(ch=’0’&&ch=’9’)∥是数字字符｛num=０；∥数初始化while（ch=’0’&&ch=’9’）∥拼数｛num=num＊10+‘ch’-‘０’；scanf(“％c”，&ch）；｝a[i++]=num；if（ch!=‘#’）∥若拼数中输入了‘#’，则不再输入scan