第4章串 要求:逻辑结构和顺序存储表示算法(顺序串) 1、简述空串和空格串(或称空格字符串)的区别 2、已知下列字符串 a=THIS’,f=' A SAMPLE’,c=G00’,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) IS,, V=Concat(s, Concat(b, Concat(t, Concat(b, u)))) 其中 Concat(a,b)为将串b联接到串a之后,其他操作与教材P71页串的抽象数据类型中定 义的操作一致,试问:s,t,v, Strength(s), Index(v,g), Index(u,g)各是什么? 3、已知:s=(XYZ)+*,t='(X+Z)*Y。试用联接、求子串和置换等操作,将s转化为t 4、编写算法,求串s所含不同字符的总数和每种字符的个数 5、两个字符串相等的充要条件是 和 设字符串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) I StrCopy(S, T) =Strength(S) fc n=1 Substring(Subl, S, i, 1) if(! StrCompare(Sub1,’#”) continue for(j=i+1: j<=m: j++) I Substring (Sub2, S, j, 1) if(!StrCompare(Subl, Sub2)) Replace(s, subl, # printf(Subl, n) printf(num) 5、长度相等每一对应位置字符相等 6、 BCDEDE 教材习题48
第 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 pede struct char ch MAXLENI SString; ∥串的初始化 void Init(SString"pS) pS->len=0; ∥串赋值 void Str Assign(SString pS, char*p) for(=0,p[i]!=0,计++) if(i>MAXLEN) I= MAXLEN pS->len=i for (i=0; i<pS-len; 1++) pS->ch[i]=pi ∥将串中所有值尉chl的字符替换为ch2 void Replace(SString*r, char chl, char ch2) for(i=0; i<r->len; 1++) ∥将串中所有字符颠倒 int 1, J, for(i=0,j=r->len-1; 1<]; 1++, j--) r->ch[]=r->ch[l r->ch[]=temp ∥删除串中所有等于ch的字符
#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 J if(r->ch[i]==ch) for=i+l; j<r->len;j++) r->ch[j-1=r->ch0] ∥删除串中所有等于ch的字符——改进算法 void Delechar I(SString r, char ch) int 1,J, for(i=0,j=0; 1< r->len; if(r->chi==c r->ch[=r->ch(i J ∥在串r1中的第 index位置开始寻找子串r2 int StrIndex( sstring *rl, SString "r2, int index) for(i= index-1; i< rl->len-r2->len+1; 1++) forG=0; j<r2->len; j++) f(rl->ch[i+j]l=r2->chlD fG==r2->len) return(i+1);
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 *rl, SString *r2) Int int k. for(i=0; 1<rl->len-r2->len+1;) k=StrIndex(rl, r2, i+1) rg=k- rI->ch[j-r2->len]=rl->chl r1->len =rl->len -r2->len. else ∥输出串 oid StrPrint(SString ps) or(i=0; i<pS printf("%c",pS->ch(iD) printf("\n") oid maino char s311 SString rl, r 2 char ch1 ch2. ch Init(&rl printf("请输入一个字符串:"), StrAssign(&rl, s) /* printf(("请输入要换的字符:"), chI=getchar(: getchar( printf("请输入要换为的字符:") ch2
} 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();
printi("转换前的字符串为:") StrPrint(&r1) Replace(&rl, chl, ch2) printf("转换后的字符串为:") StrPrint(&r1) printf("颠倒前的字符串为:"), StrPrint(&r1) Diandao( &r1); printi("颠倒后的字符串为:") StrPrint(&rl) printf("请输入要删除的字符:") ch=getchar(; getchar printf("删除前的字符串为:") Str Print(&rl) Delechar(&rl, ch) printf("删除后的字符串为:"), StrPrint(&rl) printf("请输入要查找的一个字符串:") gets(s) Str Assign(&r 2, s) printi("位置是:%dn", StrIndex(&rl,&r2,1); printf("请输入要删除的一个字符串:") gets(s) Str Assign(&r 2, s) printi("删除前的字符串为:") StrPrint(&rl) Delestr(&rl, &r2 printf("删除后的字符串为:") StrPrint(&rl)
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); }