习题4
1.名词解释：串、空串、空格串、子串。
解：串是有限的字符序列，从数据结构角度讲，串属于线性结构。与线性表的不同之处在于串的元素是字符。
空串是不含任何字符的串，其长度为0。
空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。
串中任意连续的若干字符组成的子序列称为该串的子串。
2.已知三个字符串分别为，，。利用串的基本运算得到结果串为，要求写出得到结果串所用的函数及执行算法。
解：串可看作由以下两部分组成：和，设这两部分分别叫串s1和s2，要设法从、、中得到这两部分，然后使用连接操作连接s1和s2得到。
i=index();//
s1=substr(,i,length()-i+1);//取出串s1
j=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'&&i<n){*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 T[100]; //用结构数组T存储统计结果
      for(i=1;i<=S[0]+1;i++)T[i-1].ch='\0';
      for(i=1;i<=S[0];i++){
        c=S[i];j=0;       
        while(T[j].ch&&T[j].ch!=c)j++; //查当前字符c是否已记录过
        if(T[j].ch) T[j].num++;
        else {T[j].ch=c;T[j].num=1;}
      }//for
      for(j=0;T[j].ch;j++)
        printf("%c:  %d\n",T[j].ch,T[j].num);
}//StrAnalyze
5.假设采用定长顺序存储结构表示串，编写算法，从串中删除所有和串相同的子串。
解：
void SubString_Delete(SString &s,SString t,int &num){//从串s中删除所有与t相同的子串,num为删除次数
      int i,j,k;
      for(i=1;i<=s[0]-t[0]+1;i++){
        for(j=1;j<=t[0]&&s[i+j-1]==t[j];j++);
        if(j>t[0]){//到了与t匹配的子串
            for(k=i;k<=s[0]-t[0];k++)s[k]=s[k+t[0]]; //左移删除
            s[0]-=t[0];num++;
        }
      }//for
}//Delete_SubString
6.编写算法，实现堆存储结构的串的置换操作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;k<T.length&&S.ch[j]==T.ch[k];j++,k++);
        if(k==T.length) { //到了与T匹配的子串:分三种情况处理
            if(T.length==V.length)
                for(m=1;m<=T.length;m++) S.ch[i+m-1]=V.ch[m-1];
//新子串长度与原子串相同时:直接替换
        else if(T.length<V.length) { //新子串长度大于原子串时:先将后部右移
                  for(m=S.length-1;m>=i+T.length;m--)
S.ch[m+V.length-T.length]=S.ch[m];
                  for(m=0;m<V.length;m++)S.ch[i+m]=V.ch[m];
                }
            else{ //新子串长度小于原子串时:先将后部左移
                for(m=i+V.length;m<S.length+V.length-T.length;m++)
                    S.ch[m]=S.ch[m-V.length+T.length];
                for(m=0;m<V.length;m++)S.ch[i+m]=V.ch[m];
            }
            S.length+=V.length-T.length;
            i+=V.length;num++;
        }//if
      }//for
}//HString_Replace
7.编写算法，实现堆存储结构的串基本操作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 char[s1.length+s2.length];
      for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];
      for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1];
      t.length=s1.length+s2.length;
}//HString_Concat
8字符串长度17模式串长度.假设以块链结构表示串，试编写判别给定字符串是否具有对称性的算法，并要求算法的时间复杂度为。
解：
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(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串
    else if(k>(S.curlen+1)/2){
      Pop(S,c); //将后半段的字符与栈中的元素相匹配
      if(p->ch[i]!=c) return 0; //失配
    }
    if(++i==CHUNKSIZE) { //转到下一个元素,当为块中最后一个元素时,转到下一块
      p=p->next;
      i=0;
    }
  }//for
  return 1; //成功匹配
}//LString_Palindrome
9.令，，试分别求出它们的next函数值和nextval函数值。
解：
j
1
2
3
4
5
6
7
串S
a
b
c
a
b
a
a
next[j]
0
1
1
1
2
3
2
nextval[j]
0
1
1
0
1
3
2
j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
串T
a
b
c
a
a
b
b
a
b
c
a
b
a
a
c
b
a
c
b
a
next[j]
0
1
1
1
2
2
3
1
2
3
4
5
3
2
2
1
1
2
1
1
nextval[j]
0
1
1
0
2
1
3
0
1
1
0
5
3
2
2
1
0
2
1
0
10.已知主串，模式串，写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。
解：
j
1
2
3
4
5
6
7
8
9
10
串T
a
d
a
b
b
a
d
a
d
a
nextval[j]
0
1
0
2
1
0
1
0
4
0
匹配过程略。

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