第4章习题答案.doc

第4章 串习题41.名词解释：串、空串、空格串、子串。解：串是有限的字符序列，从数据结构角度讲，串属于线性结构。与线性表的不同之处在于串的元素是字符。空串是不含任何字符的串，其长度为0。空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。串中任意连续的若干字符组成的子序列称为该串的子串。2.已知三个字符串分别为，。利用串的基本运算得到结果串为，要求写出得到结果串所用的函数及执行算法。解：串可看作由以下两部分组成：和，设这两部分分别叫串s1和s2，要设法从、中得到这两部分，然后使用连接操作连接s1和s2得到。i=index();/s1=substr(,i,length()-i+1);/取出串s1j=index(,);/求串在串中的起始位置，串中后是s2=substr(,j+3,length()-j-2);/形成串s2=concat(s1,s2);3.已知字符串中存放一段英文，写出算法，将其按给定的长度格式化成两端对齐的字符串，其多余的字符存入。解：题目要求将字符串S1拆分成字符串S2和S3，要求字符串S2“按给定长度n格式化为两端对齐的字符串”，即长度为n且首尾字符不能为空格字符。算法从左到右扫描字符串S1，找到第一个非空格字符，计数到n，第n个拷入字符串S2的字符不能为空格，然后将余下字符复制到字符串S3中。void format(char *S1,char *S2,char *S3,int n) char *p=S1,*q=S2; int i=0; while(*p!= 0&*p= )p+;/滤掉S1左端空格 if(*p= 0)printf(字符串S1为空串或空格串n);exit(0); while(*p!= 0&in)*q=*p;q+;p+;i+;/字符串S1向字符串S2中复制 if(*p= 0)printf(字符串S1没有%d个有效字符n,n);exit(0); if(*(-q)= )/若最后一个字符为空格，则需要向后找到第一个非空格字符p-;/p指针也后退while(*p!= 0&*p= )p+;/往后查找一个非空格字符作为串S2的尾字符if(*p= 0)printf(串S1没有%d个两端对齐的字符串n,n);exit(0);*q=*p;/字符串S2最后一个非空字符*(+q)= 0;/S2字符串结束标记 q=S3;p+;/将S1串其余部分送字符串S3 while(*p!= 0)*q=*p;q+;p+; *q= 0;/置串S3结束标记4.假设采用定长顺序存储结构表示串，编写算法，求串的含不同字符的总数和每个字符的个数。解：typedef struct char ch; int num;mytype;void StrAnalyze(SString S)/统计串S中字符的种类和个数 int i,j; char c; mytype T100; /用结构数组T存储统计结果 for(i=1;i=S0+1;i+)Ti-1.ch=0; for(i=1;i=S0;i+)c=Si;j=0;while(Tj.ch&Tj.ch!=c)j+; /查找当前字符c是否已记录过if(Tj.ch) Tj.num+;else Tj.ch=c;Tj.num=1; /for for(j=0;Tj.ch;j+)printf(%c: %dn,Tj.ch,Tj.num);/StrAnalyze5.假设采用定长顺序存储结构表示串，编写算法，从串中删除所有和串相同的子串。解：void SubString_Delete(SString &s,SString t,int &num)/从串s中删除所有与t相同的子串,num为删除次数 int i,j,k; for(i=1;i=s0-t0+1;i+)for(j=1;jt0)/找到了与t匹配的子串for(k=i;k=s0-t0;k+)sk=sk+t0; /左移删除s0-=t0;num+; /for/Delete_SubString6.编写算法，实现堆存储结构的串的置换操作Replace(&S,T,V)。解：void HString_Replace(HString &S,HString T,HString V,int & num)/堆结构串上的置换操作,返回置换次数 int i,j,k,m; for(i=0;i=S.length-T.length;i+)for(j=i,k=0;kT.length&S.chj=T.chk;j+,k+);if(k=T.length) /找到了与T匹配的子串:分三种情况处理if(T.length=V.length)for(m=1;m=T.length;m+) S.chi+m-1=V.chm-1;/新子串长度与原子串相同时:直接替换 else if(T.length=i+T.length;m-)S.chm+V.length-T.length=S.chm; for(m=0;mV.length;m+)S.chi+m=V.chm; else /新子串长度小于原子串时:先将后部左移for(m=i+V.length;mS.length+V.length-T.length;m+)S.chm=S.chm-V.length+T.length;for(m=0;mV.length;m+)S.chi+m=V.chm;S.length+=V.length-T.length;i+=V.length;num+;/if /for/HString_Replace7.编写算法，实现堆存储结构的串基本操作Concat(&S,S1,S2)。解：void HString_Concat(HString s1,HString s2,HString &t) /将堆结构表示的串s1和s2连接为新串t int i,j; if(t.ch) free(t.ch); t.ch=new chars1.length+s2.length; for(i=1;i=s1.length;i+) t.chi-1=s1.chi-1; for(j=1;j=s2.length;j+,i+) t.chi-1=s2.chj-1; t.length=s1.length+s2.length;/HString_Concat8.假设以块链结构表示串，试编写判别给定字符串是否具有对称性的算法，并要求算法的时间复杂度为。解：int LString_Palindrome(LString L) /判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0 InitStack(S); p=S.head;i=0;k=1; /i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始) for(k=1;k=S.curlen;k+) if(kchi); /将前半段的字符入串 else if(k(S.curlen+1)/2) Pop(S,c); /将后半段的字符与栈中的元素相匹配 if(p-chi!=c) return 0; /失配 if(+i=CHUNKSIZE) /转到下一个元素,当为块中最后一个元素时,转到下一块 p=p-next; i=0; /for return 1; /成功匹配/LString_Palindrome9.令，试分别求出它们的next函数值和nextval函数值。解：j1234567串Sabcabaanextj0111232nextvalj0110132j1234567891011121314151617181920串Tabcaabb