专升本数据结构试题解析(21)

第2部分 习题解析 亱店↘打烊oO

【算法源代码】

int index(char s[ ], char t[ ],int m,int n)

{int i=0,j=0;

while (i<=m-n && j<=n-1)

if (s[i]==t[j]){i++;j++;} /*对应字符相等，指针后移*/

else {i=i-j+1;j=0;} /*对应字符不相等，i回溯，j仍为0*/

if(i<=m-n && j==n)

{printf("t在s串中位置是%d",i-n+1);

return(i-n+1);

}/*匹配成功*/

else return(0); /*匹配失败*/

}

2．函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。请用c语言实现该函数。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）

【算法分析】

本题是字符串的插入问题，要求在字符串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,j; char *p=s,*q=t; /*p，q分别为字符串s和t的工作指针*/

if(pos<1)

{printf("pos参数位置非法\n");exit(0);}

while(*p!='\0'&&i<pos) {p++;i++;} /*查pos位置*/

if(*p=='/0')

{printf("%d位置大于字符串s的长度",pos);exit(0);}

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位置上*/

}

3．设计一个算法，统计在输入字符串中各个不同字符出现的频度。（字符串中的合法字符为'A'-'Z'这26个字母和'0'-'9'这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]=0;/* 初始化*/