串答案(2)

printf（“共有%d个整数，它们是：”i）； for（j=０；j

［算法讨论］假定字符串中的数均不超过32767，否则，需用长整型数组及变量。 3、[题目分析]设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。

int LongestString(char s[],int n)

//串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。

{int index=0,max=0; //index记最长的串在s串中的开始位置，max记其长度 int length=1,i=0,start=0; //length记局部重复子串长度，i为字符数组下标 while(i

if(s[i]==s[i+1]) {i++; length++;} else //上一个重复子串结束

{if(max

i++;start=i;length=1; //初始化下一重复子串的起始位置和长度

}

printf(“最长重复子串的长度为%d，在串中的位置%d\\n”，max,index); return(max); }//算法结束

[算法讨论]算法中用i

算法的时间复杂度为O(n），每个字符与其后继比较一次。

4、[题目分析]教材中介绍的串置换有两种形式：第一种形式是replace（s,i,j,t），含义是将s串中从第i个字符开始的j个字符用t串替换,第二种形式是replace(s,t,v)，含义是将s串中所有非重叠的t串用v代替。我们先讨论第一种形式的替换。因为已经给定顺序存储结构，我们可将s串从第（i+j-1）到串尾（即s.curlen）移动t.curlen-j绝对值个位置（以便将t串插入）：若j>t.curlen，则向左移；若j

int replace(strtp s,t,int i,j)

//s和t是用一维数组存储的串，本算法将s串从第i个字符开始的连续j个字符用t串置换，操作成功返回1，否则返回0表示失败。 {if(i<1 || j<0 || t.curlen+s.curlen-j>maxlen)

{printf(“参数错误\\n”);exit(0);} //检查参数及置换后的长度的合法性。 if(j=i+j-1;k--) s.ch[k+t.curlen-j]=s.ch[k]; else if (j>t.curlen) //s串中被替换子串的长度小于t串的长度。 for(k=i-1+j;k<=s.curlen-1;k++) s.ch[k-(j-t.curlen)]=s.ch[k];

for(k=0;kt.curlen) s.curlen=s.curlen-(j-t.curlen);else s.curlen=s.curlen+(t.curlen-j); }//算法结束

[算法讨论]若允许使用另一数组，在检查合法性后，可将s的第i个（不包括i）之前的子串复制到另一子串如s1中，再将t串接到s1串后面,然后将s的第i+j直到尾的部分加到s1之后。最后将s1串复制到s。主要语句有：

for(k=0;k

for(k=0;k

for(k=s.curlen-1;k>i-1+j;k--);//将子串第i+j-1个字符以后的子串复制到s1

s1.ch[l--]=s.ch[k]

for(k=0;k

下面讨论replace（s,t,v）的算法。该操作的意义是用串v替换所有在串s中出现的和非空串t相等的不重叠的子串。本算法不指定存储结构，只使用串的基本运算。

void replace(string s,t,v)

//本算法是串的置换操作，将串s中所有非空串t相等且不重复的子串用v代替。 {i=index(s,t);//判断s是否有和t相等的子串 if(i!=0)//串s中包含和t相等的子串

{creat(temp,”); //creat操作是将串常量（此处为空串）赋值给temp。 m=length(t);n=length(s); //求串t和s的长度 while(i!=0)

{assign(temp,concat(temp,substr(s,1,i-1),v));//用串v替换t形成部分结果

assign(s,substr(s,i+m,n-i-m+1)); //将串s中串后的部分形成新的s串

n=n-(i-1)-m; //求串s的长度

i=index(s,t); //在新s串中再找串t的位置

}

assign(s,contact(temp,s)); //将串temp和剩余的串s连接后再赋值给s }//if结束 }//算法结束

5、[题目分析]本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。 对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。

void insert(char *s,char *t,int pos)

//将字符串t插入字符串s的第pos个位置。

{int i=1,x=0; char *p=s,*q=t; //p，q分别为字符串s和t的工作指针 if(pos<1) {printf(“pos参数位置非法\\n”);exit(0);} while(*p!=’\\0’&&i

//若pos小于串s长度，则查到pos位置时，i=pos。

if(*p == '/0') {printf(\位置大于字符串s的长度\ else //查找字符串的尾 while(*p!= '/0') {p++; i++;} //查到尾时，i为字符‘\\0’的下标，p也指向‘\\0’。 while(*q!= '\\0') {q++; x++; } //查找字符串t的长度x，循环结束时q指向'\\0'。 for(j=i;j>=pos ;j--){*(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置。

q--; //指针q回退到串t的最后一个字符

for(j=1;j<=x;j++) *p--=*q--; //将t串插入到s的pos位置上

[算法讨论] 串s的结束标记('\\0')也后移了，而串t的结尾标记不应插入到s中。 6.[题目分析]本题属于查找，待查找元素是字符串（长4），将查找元素存放在一维数组中。二分检索（即折半查找或对分查找），是首先用一维数组的“中间”元素与被检索元素比较，若相等,则检索成功，否则，根据被检索元素大于或小于中间元素，而在中间元素的右方或左方继续查找，直到检索成功或失败（被检索区间的低端指针大于高端指针）。下面给出类C语言的解法

typedef struct node

{char data[4];//字符串长4 }node;

非递归过程如下：

int binsearch(node string [];int n;char name[4])

//在有n个字符串的数组string中，二分检索字符串name。若检索成功，返回name在string中的下标，否则返回-1。

{int low = 0,high = n - 1;//low和high分别是检索区间的下界和上界 while(low <= high)

{mid = (low + high) /2; //取中间位置

if(strcmp(string[mid],name) ==0) return (mid); //检索成功

else if(strcmp(string[mid],name)<0) low=mid+1; //到右半部分检索

else high=mid-1; //到左半部分检索 }

return 0; //检索失败 }//算法结束

最大检索长度为log2n。

7. [题目分析]设字符串存于字符数组X中，若转换后的数是负数，字符串的第一个字符必为 '-'，取出的数字字符，通过减去字符零（'0'）的ASCII值，变成数，先前取出的数乘上10加上本次转换的数形成部分数，直到字符串结束，得到结果。

long atoi(char X[])

//一数字字符串存于字符数组X中，本算法将其转换成数 {long num=0;

int i=1; //i 为数组下标

while (X[i]!= '\\0') num=10*num+(X[i++]-'0');//当字符串未到尾，进行数的转

换

if(X[0]=='-') return (-num); //返回负数

else return ((X[0]-'0')*10+num); //返回正数，第一位若不是负号，则是数字 }//算法atoi结束

[算法讨论]如是负数，其符号位必在前面，即字符数组的x[0]，所以在作转换成数时下标i从1 开始，数字字符转换成数使用X[i]-'0',即字符与'0'的ASCII值相减。请注意对返回正整数的处理。

8.[题目分析]本题要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按给定长度n格式化成两端对齐的字符串”，即长度为n且首尾字符不得为空格字符。算法从左到右扫描字符串s1，找到第一个非空格字符，计数到n，第n个拷入字符串s2的字符不得为空格，然后将余下字符复制到字符串s3中。 void format (char *s1,*s2,*s3)

//将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n且两端对齐 {char *p=s1, *q=s2; int i=0;

while(*p!= '\\0' && *p== ' ') p++;//滤掉s1左端空格

if(*p== '\\0') {printf(\字符串s1为空串或空格串\\n\

while( *p!='\\0' && i

while(*p==' '&&*p!='\\0') p++;//往后查找一个非空格字符作串s2的尾字符 if(*p=='\\0') {printf(\串没有%d个两端对齐的字符串\\n\} *q=*p; //字符串s2最后一个非空字符 *(++q)='\\0'; //置s2字符串结束标记 }

*q=s3;p++; //将s1串其余部分送字符串s3。 while (*p!= '\\0') {*q=*p; q++; p++;} *q='\\0'; //置串s3结束标记 }

9.[题目分析]两个串的相等，其定义为两个串的值相等，即串长相等，且对应字符相等是两个串相等的充分必要条件。因此，首先比较串长，在串长相等的前提下，再比较对应字符是否相等。

int equal(strtp s,strtp t)

//本算法判断字符串s和字符串t是否相等，如相等返回1，否则返回0 {if (s.curlen!=t.curlen) return (0);

for (i=0; i

10.［问题分析］由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符 ‘0’的ASCII代码值，得出其数值(0..9)，字母的ASCII代码值减去字符‘A’的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。

void Count（）

//统计输入字符串中数字字符和字母字符的个数。 ｛int i，num[36]；

char ch；

for（i＝0；i<36；i++）num[i]＝０；// 初始化 while（（ch＝getchar（））!=‘#’） //‘#’表示输入字符串结束。 if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝ // 数字字符 else if（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝// 字母字符

for（i=0；i<10；i++） // 输出数字字符的个数 printf（“数字％d的个数＝％d\\n”，i，num[i]）； for（i＝10；i<36；i++）// 求出字母字符的个数 printf（“字母字符％c的个数＝％d\\n”，i＋55，num[i]）； ｝// 算法结束。

11.[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。

void InvertStore(char A[]) //字符串逆序存储的递归算法。 { char ch;

static int i = 0;//需要使用静态变量 scanf (\

if (ch!= '.') //规定'.'是字符串输入结束标志 {InvertStore(A);

A[i++] = ch;//字符串逆序存储 }

A[i] = '\\0'; //字符串结尾标记 }//结束算法InvertStore。

12. 串s'''可以看作由以下两部分组成：'caabcbca...a'和 'ca...a'，设这两部分分别叫串s1和串s2，要设法从s,s' 和s''中得到这两部分，然后使用联接操作联接s1和s2得到s''' 。

i=index(s,s'); //利用串s'求串s1在串s中的起始位置 s1=substr(s,i,length(s) - i + 1); //取出串s1

j=index(s,s''); //求串s''在串s中的起始位置，s串中'bcb'后是'ca...a') s2=substr(s,j+3,length(s) - j - 2); //形成串s2 s3=concat(s1,s2); 13．[题目分析]对读入的字符串的第奇数个字符，直接放在数组前面，对第偶数个字符，先入栈，到读字符串结束，再将栈中字符出栈，送入数组中。限于篇幅，这里编写算法，未编程序。

void RearrangeString()

//对字符串改造，将第偶数个字符放在串的后半部分，第奇数个字符前半部分。 {char ch,s[],stk[]; //s和stk是字符数组（表示字符串）和字符栈 int i=1,j; //i和j字符串和字符栈指针 while((ch=getchar())!=’#’)// ’#’是字符串结束标志 s[i++]=ch; //读入字符串

s[i]=’\\0’; //字符数组中字符串结束标志 i=1;j=1;