第4章 串要求：逻辑结构和顺序存储表示算法（顺序串）
1、简述空串和空格串（或称空格字符串）的区别。
2、已知下列字符串
a=’THIS’,f=’A SAMPLE’,c=’GOOD’,d=’NE’,b=’ ‘,
s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))),
t=Replace(f,SubString(f,3,6),c),u=Concat(SubString(c,3,1),d),
g=’IS’,v=Concat(s,Concat(b,Concat(t,Concat(b,u))))
其中Concat(a,b)为将串b联接到串a之后，其他操作与教材P71页串的抽象数据类型中定义的操作一致，试问：s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么？
3、已知：s=’(XYZ)+*’,t=’(X+Z)*Y’。试用联接、求子串和置换等操作，将s转化为t。
4、编写算法，求串s所含不同字符的总数和每种字符的个数。
5、两个字符串相等的充要条件是 和 。
6、设字符串S1=’ABCDEF’,S2=’PQRS’,则运算S=CONCAT(SUB(S1,2,LEN(S2)),SUB(S1,LEN(S2),2))后的串值为 。
参考解答：
1、空串是指长度为零的串，而空格串是指串中字符是空格的字符串。
2、s= ‘THIS SAMPLE IS’ t=’A GOOD’ u=’ONE’ v=’THIS SAMPLE IS A GOOD ONE’ 14,3,0
3、Replace(s,Substring(s,3,5),Concat(Substring(3,6,1),Concat(Substring(s,4,2),Concat(Substring(s,7,1),Substring(s,3,1)))))
4、算法1：
void count(String T)
{ StrCopy(S,T);
m=Strlength(S);
num=0;
for(i=1;i<=m;i++)
{ n=1;
Substring(Sub1,S,i,1);
if(!StrCompare(Sub1,’#’))continue;
for(j=i+1;j<=m;j++)
{ Substring(Sub2,S,j,1);
if(!StrCompare(Sub1,Sub2))
n++;
}
Replace(S,sub1,’#’);
num++;
printf(Sub1,n);
}
printf(num);
}
5、长度相等 每一对应位置字符相等
6、BCDEDE
教材习题4.8
#include <stdio.h>
#define MAXLEN 30
typedef struct
{
char ch[MAXLEN];
int len;
}SString;
//串的初始化
void Init(SString *pS)
{
pS->len = 0;
}
//串赋值
void StrAssign(SString *pS,char *p)
{
int i;
for(i = 0; p[i] !='\0'; i++);
if(i>MAXLEN)
i = MAXLEN;
pS->len = i;
for(i = 0; i < pS->len; i++)
pS->ch[i] = p[i];
}
//将串中所有值尉ch1的字符替换为ch2
void Replace(SString *r,char ch1,char ch2)
{
int i;
for(i = 0; i < r->len; i++)
if(r->ch[i] == ch1)
r->ch[i] = ch2;
}
//将串中所有字符颠倒
void Diandao(SString *r)
{
int i,j;
char temp;
for(i = 0,j = r->len-1; i < j; i++,j--)
{
temp = r->ch[i];
r->ch[i] = r->ch[j];
r->ch[j] = temp;
}
}
//删除串中所有等于ch的字符
void Delechar(SString *r,char ch)
{
int i,j;
for(i = 0; i < r->len; )
{
if(r->ch[i] == ch)
{
for(j = i+1; j < r->len; j++)
r->ch[j-1] = r->ch[j];
r->len--;
}
else
i++;
}
}
//删除串中所有等于ch的字符——改进算法
void Delechar1(SString *r,char ch)
{
int i,j;
for(i = 0,j = 0; i < r->len; )
{
if(r->ch[i] == ch)
i++;
else
{
i++;
j++;
if(j != i)
r->ch[j] = r->ch[i];
}
}
r->len = j;
}
//在串r1中的第index位置开始寻找子串r2
int StrIndex(SString *r1,SString *r2,int index)
{
int i,j;
for(i = index-1; i < r1->len-r2->len+1; i++)
{
for(j = 0; j < r2->len; j++)
if(r1->ch[i+j] != r2->ch[j])
break;
if(j == r2->len)
return(i+1);
}
return(0);
}
//删除r1中的所有子串r2
void Delestr(SString *r1,SString *r2)
{
int i,j;
int k;
for(i = 0; i < r1->len-r2->len+1; )
{
k = StrIndex(r1,r2,i+1);
if(k > 0)
{
for(j = k-1+r2->len; j < r1->len; j++)
r1->ch[j - r2->len] = r1->ch[j];
r1->len = r1->len - r2->len;
}
else
i++;
}
}
//输出串
void StrPrint(SString *pS)
{
int i;
for(i = 0; i < pS->len; i++)
printf("%c",pS->ch[i]);
printf("\n");
}
void main()
{
char s[31];
SString r1,r2;
char ch1,ch2,ch;
Init(&r1);
Init(&r2);
printf("请输入一个字符串：");
gets(s);
StrAssign(&r1,s);
/* printf("请输入要换的字符：");
ch1 = getchar();getchar();
printf("请输入要换为的字符：");
ch2 = getchar();
printf("转换前的字符串为：");
StrPrint(&r1);
Replace(&r1,ch1,ch2);
printf("转换后的字符串为：");
StrPrint(&r1);
printf("颠倒前的字符串为：");
StrPrint(&r1);
Diandao(&r1);
printf("颠倒后的字符串为：");
StrPrint(&r1);
printf("请输入要删除的字符：");
ch = getchar();getchar();
printf("删除前的字符串为：");
StrPrint(&r1);
Delechar(&r1,ch);
printf("删除后的字符串为：");
StrPrint(&r1);
printf("请输入要查找的一个字符串：");
gets(s);
StrAssign(&r2,s);
printf("位置是：%d\n",StrIndex(&r1,&r2,1));*/
printf("请输入要删除的一个字符串：");
gets(s);
StrAssign(&r2,s);
printf("删除前的字符串为：");
StrPrint(&r1);
Delestr(&r1,&r2);
printf("删除后的字符串为：");
StrPrint(&r1);
}