数据结构答案 第5章 串学习指导.docx
- 文档编号:9376261
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:16
- 大小:20.34KB
数据结构答案 第5章 串学习指导.docx
《数据结构答案 第5章 串学习指导.docx》由会员分享,可在线阅读,更多相关《数据结构答案 第5章 串学习指导.docx(16页珍藏版)》请在冰点文库上搜索。
数据结构答案第5章串学习指导
第5章串
5.1知识点分析
1.串的定义
串(String)是由零个或多个任意字符组成的有限序列。
一般记作:
s="a1a2…ai…an"。
其中s是串名,用双引号括起来的字符序列为串值,但引号本身并不属于串的内容。
ai(1<=i<=n)是一个任意字符,它称为串的元素,是构成串的基本单位,i是它在整个串中的序号;n为串的长度,表示串中所包含的字符个数。
2.几个术语
(1)长度
串中字符的个数,称为串的长度。
(2)空串
长度为零的字符串称为空串。
(3)空格串
由一个或多个连续空格组成的串称为空格串。
(4)串相等
两个串相等,是指两个串的长度相等,且每个对应字符都相等。
(5)子串
串中任意连续字符组成的子序列称为该串的子串。
(6)主串
包含子串的串称为该子串的主串。
(7)模式匹配
子串的定位运算又称为串的模式匹配,是一种求子串的第一个字符在主串中序号的运算。
被匹配的主串称为目标串,子串称为模式。
3.串的基本运算
(1)求串长:
LenStr(s)。
(2)串连接:
ConcatStr(s1,s2)。
(3)求子串:
SubStr(s,i,len)。
(4)串比较:
EqualStr(s1,s2)。
(5)子串查找:
IndexStr(s,t),找子串t在主串s中首次出现的位置(也称模式匹配)。
(6)串插入:
InsStr(s,t,i)。
(7)串删除:
DelStr(s,i,len)。
4.串的存储
(1)定长顺序存储。
(2)链接存储。
(3)串的堆分配存储。
5.2典型习题分析
【例1】下面关于串的的叙述中,哪一个是不正确的?
( )
A.串是字符的有限序列B.空串是由空格构成的串
C.模式匹配是串的一种重要运算D.串既可以采用顺序存储,也可以采用链式存储
分析:
空串是不含任何字符的串,即空串的长度是零。
空格串是由空格组成的串,其长度等于空格的个数。
答案为B。
【例2】两个串相等的充分必要条件是()。
A.两个串长度相等B.两个串有相同字符
C.两个串长度相等且有相同字符D.以上结论均不正确
分析:
根据串相等定义,两个串是相等是指两个串的长度相等且对应字符都相等,故A、B、C均不正确,答案为D。
【例3】串链式存储的优点是
(1),缺点是
(2)。
分析:
由链式存储结点特点可以得到:
(1)插入、删除方便。
(2)浪费空间。
注意,这里串的链式存储是指结点元素为1个字符的链串,如果结点元素字符数大于1,插入和删除同样不方便,但空间利用率可以提高。
【例4】设S="abccdcdccbaa",T="dccb",则第7次匹配成功。
分析:
由字符串模式匹配概念,匹配过程如下:
S="abccdcdccbaa"
第一趟 d 不成功
S="abccdcdccbaa"
第二趟 d不成功
S="abccdcdccbaa"
第三趟 d不成功
S="abccdcdccbaa"
第四趟 d不成功
S="abccdcdccbaa"
第五趟 dcc不成功
S="abccdcdccbaa"
第六趟 d不成功
S="abccdcdccbaa"
第七趟 dccb成功
【例5】利用函数LenStr(s),SubStr(s,i,len)和ConcatStr(s1,s2)写一算法voidStrInsert(char*S,char*T,inti),将串T插入到串S的第i个位置上。
若i大于S的长度,则插入不执行。
请在处填写语句,完成此程序。
算法如下:
voidInsStr(char*S,char*T,inti)//将串T插入到串S的第i个位置上
{
char*Temp;
Temp=(char*)malloc(sizeof(char[Maxsize]));//设置一个临时串
if(i<=LenStr(S))
{
(1);//将第i位起以后的字符拷贝到临时串中
S=
(2);
//将串T拷贝到串S的第i个位置处,覆盖后面的字符
S=(3);//把临时串中的字符联接到串S后面
free(Temp);
}
分析:
(1)因为是将串S第i个位置起以后字符复制到临时串变量Temp中采用求子串方法即Temp=SubStr(s,i,LenStr(S))。
(2)因为将串T拷贝到串S的第i个位置处,覆盖后面的字符采用串连接方法,即ConcatStr(SubStr(S,0,i-1),T)。
(3)ConcatStr(SubStr(S,0,i-1),Temp)。
【例6】链式串上的子串定位。
分析:
由于是链式串,所以对元素的存储表示与顺序存储串不同,在链式串中不是用下标指示元素,而是用指针指向元素。
程序如下:
typedefstructnode
{chardata;
structnode*next;
}LinkStrNode;
LinkStr*LinkStrNode(LinkStrNode*t,LinkStrNode*p)
{LinkStrNode*pos,*qi,*qj;
pos=t;
qi=pos;qj=p;
while(qi&&qj)
{if(q1->data==qj->data)
{qi=qi->next;qj=qj->next;}
else
{pos=pos->next;//模式右移,继续判断pos是否为有校位移
qi=pos;
qj=p;
}
}
if(qj==NULL)
returnpos;//匹配成功
else
returnNULL;//匹配失败
}
【例7】一个文本串可用事先给定的字母映射表进行加密,例如,设字母映射表为:
abcdefghijklmnopqrstuvwxyz
ngzqtcobmuhelkpbawxfyIvrsj
则字符串“encrypt”被加密为“tkzwsdf”。
试写一算法将输入的文本串进行加密后输出;另写一算法,将输入的加密文本串进行加密后输出。
算法如下:
typedefstruct
{charch[2];[MaxStrSize];
intlength;
}SeqString;
voidEncoding(char*s,seqStringT)
{inti,j;
intm=T.length;//字母表长
intn=strlen(S);//求文本的长度
for(i=0;i {for(j=0;j if(S[i]==T.ch[0][j]) {printf("%c",T.ch[1][j]); break; } if(j==m) printf("%cisnotinalphabet",S[i]); } } voidDeCoding(char*S,seqStringT)//串S是待解密的文本 {inti,j; intm=T.length; intn=strlen(S); for(i=0;i {for(j=0;j if(S[i]==T.ch[1][j]) {printf("%c",T.ch[0][j]); break; } if(j==m) printf("%cisnotinalphabet",S[i]); } } 【例8】若S和T是用结点大小为1的单链表存储的两个串,试设计一个算法找出S中第一个不在T中出现的字符。 分析: 查找过程是这样的,取S中的一个字符(结点),然后和T中所有的字符一一比较,直到比完仍没有相同的字符时,查找过程结束,否则再取S中下一个字符,重新进行上述过程。 算法如下: typedefstructnode {chardata; structnode*next; }LinkStrNode; charSearchNo(LinkStrNode*S,LinkStrNode*T)//查找不在T中出现的字符 { LinkStrNode*p,*q; p=S; q=T; while(p)//取S中结点字符 {while(q&&p->data! =q->data)//进行字符比较 q=q->next; if(q==NULL) returnp->data;//找到并返回字符值 q=T;//指针恢复串T的开始结点 p=p->next; } printf("there'snosuchcharacter."); returnNULL; } 5.3单元练习5解答 一.判断题答案 题目 1 2 3 4 5 6 7 8 9 10 答案 × √ × × × √ × × √ √ 二.填空题答案 (1)字符串(或串) (2)堆分配存储 (3)顺序串 (4)空间利用率低 (5)效率低 (6)空间利用率低 (7)\0 (8)空格的个数 (9)空格串 (10)字符都相同 (11)8 (12)Todayis30July,2005 (13)July (14)<0 (15)0 (16)模式 (17)有效位移 (18)6 (19)0 (n-m+1)*m 三.选择题答案 题目 1 2 3 4 5 6 7 8 9 10 答案 B B C B A D D D A B 题目 11 12 13 14 15 16 17 18 19 20 答案 A A D D D B A B D C 四.程序题填空答案 (1)①MAXLEN ②r2->len ③r1->len+i ④'\0' ⑤r1->len+r2->len (2)①)! =或<> ②&& ③! = ④tag=0 ⑤i++ (3)①s->len ②s->len ③k ④ \0 ⑤ i-1 五.编程题答案 (1)①分析: 从头至尾扫描r串,对于值为ch1的元素直接替换成ch2即可。 【程序代码】 str*trans(str*r,charch1,charch2) {inti; for(i=0;i if(r->vec[i]==ch1) r-vec[i]=ch2; return(r); } 2分析: 将第一个元素与最后一个元素交换,第二个元素与倒数第二个元素交换,依次类推,便将该串的所有字符反序了。 【程序代码】 str*invert(str*r) {inti; charx; for(i=0;i<(r->len%2);i++) {x=r->vec[i]; r->vec[i]=r->[r->len-i+1]; r->vec[r->len-i+1]=x; } return(r); } ③分析: 从头到尾扫描r串,对于值为ch的元素用移动的方式进行删除。 【程序代码】 str*delall(str*r,charch) str*r; charch; {inti,j; for(i=0;i if(r->vec[i]==ch) {for(j=i;j r->vec[i]=r->vec[i+1]; r->len=r->len-1; } return(r); } ④分析: 从第index个元素开始扫描r1,当其元素值与r2的第一个元素的值相同时,判定它们之后的元素值是否依次相同,直到r2结束为止,若都相同则返回,否则继续上述过程直到r1扫描完为止。 【程序代码】 intpartposition(strr2,strr1,intindex) {inti,j,k; for(i=index;r1->vec[i];i++) for(j=i,k=0;r1->vec[j]==r2->vec[k];j++,k++) if(! r2->vec[k+1]) return(i); return(-1); } ⑤分析: 从位置1开始调用第(4)小题的函数partposition(),若找到了一个相同子串,则调用delsubstring(),再相同的方法查找后面位置的相同子串。 【程序代码】 str*delstringall(strr,strr3) {inti=0; while(i {if(partposition(r,r3,i)! =-1) delsubstring(r,i,r3->len) i++; } } ⑥分析: 两个串相等的条件是两个串的长度相等,且两个串的对应的字符必须都相同。 【程序代码】 intsame(strx,stry) {inti=0,tag=1; if(x->len! =y->len) return(0); else {while(i {if(x->vec[i]! =y->vec[i]) tag=0; i++; } return(tag); } } (2)【程序代码】 #include"stdio.h" typedefstruct {char*head; intlength; }Hstring; voidisPalindrome(Hstrings) { inti=0; intj=s.length-1; while(j-i>=1) { if(s.head[i]==s.head[j]) {i++;j--;continue;} else break; } if(j-i>=1) printf("Ttisnotapalindrome\n"); else printf("itisapalindrome\n"); } (3)【程序代码】 #include"stdio.h" #include"string.h" typedefstruct {char*head; intlength; }Hstring; char*DeleteSubString(HstringS,HstringT) { inti=0; intj,k; intSlength=S.length; intTlength=T.length; char*tail; while(i<=Slenght-Tlength) {j=0;k=i; while(j {j++;k++;} if(j==Tlength)//若匹配则执行下面的程序 {if(i==0)//若位于头位置则改变头指针 {S.head=S.head+Tlength; S.length-=Tlength; Slength-=Tlength; i=0; } else if(i+Tlength { tail=S.head+i+Tlength; strcpy(S.head+i,tail); S.length-=Tlength; Slength-=Tlength; } else//若位于尾部则割去 strncpy(S.head+i,”\0”,1); } else//若不匹配则i加1 i++; } returnS.head; } (4)【程序代码】 #include"stdio.h" #include"string.h" intFind_word(char*text,constchar*word) { inttextlength=strlen(text); intwordlength=strlen(word); inti,j,k; intcount=0; for(i=0;i {j=0;k=i;} while(j {j++;k++;} if(j==wordlength&&word[j]==’\0’)//匹配成功计数器加1 count++; returncount; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构答案 第5章 串学习指导 数据结构 答案 学习 指导