数据结构考研分类复习真题 第四章 答案[21]

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

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

{ char ch;

static int i = ;//需要使用静态变量

scanf (%c&ch);

if (ch!= ) //规定是字符串输入结束标志

{InvertStore(A);

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

}

A[i] = \; //字符串结尾标记

}//结束算法InvertStore

串s可以看作由以下两部分组成caabcbcaa和 caa设这两部分分别叫串s和串s要设法从ss 和s中得到这两部分然后使用联接操作联接s和s得到s

i=index(ss); //利用串s求串s在串s中的起始位置

s=substr(silength(s) i + ); //取出串s

j=index(ss); //求串s在串s中的起始位置s串中bcb后是caa)

s=substr(sj+length(s) j ); //形成串s

s=concat(ss);

[题目分析]对读入的字符串的第奇数个字符直接放在数组前面对第偶数个字符先入栈到读字符串结束再将栈中字符出栈送入数组中限于篇幅这里编写算法未编程序

void RearrangeString()//对字符串改造将第偶数个字符放在串的后半部分第奇数个字符前半部分

{char chs[]stk[]; //s和stk是字符数组（表示字符串）和字符栈

int i=j; //i和j字符串和字符栈指针

while((ch=getchar())!=#)// #是字符串结束标志

s[i++]=ch; //读入字符串

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

i=;j=;

while(s[i]) //改造字符串

{if(i%==) stk[i/]=s[i]; else s[j++]=s[i];

i++; }//while

i; i=i/; //i先从\后退是第偶数字符的个数

while(i>) s[j++]=stk[i] //将第偶数个字符逆序填入原字符数组

}

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []