河南零距离文化传播 网站建设,南京蓝牙app开发公司,创意工作室网站,wordpress百度云cdn题目展示#xff1a; 【问题描述】 从键盘输入包含扩展符-的字符串#xff0c;将其扩展为等价的完整字符#xff0c;例如将a-d扩展为abcd#xff0c;并输出扩展后的字符串。 要求#xff1a;只处理[a-z]、[A-Z]、[0-9]范围内的字符扩展#xff0c;即只有当扩展符前后的字…题目展示 【问题描述】 从键盘输入包含扩展符-的字符串将其扩展为等价的完整字符例如将a-d扩展为abcd并输出扩展后的字符串。 要求只处理[a-z]、[A-Z]、[0-9]范围内的字符扩展即只有当扩展符前后的字符同时是小写字母、大写字母或数字并且扩展符后的字符大于扩展符前的字符时才进行扩展其它情况不进行扩展原样输出。例如a-R、D-e、0-b、4-B等字符串都不进行扩展。 【输入形式】 从键盘输入包含扩展符的字符串 【输出形式】 输出扩展后的字符串 【输入样例1】 ADEa-g-m02 【输出样例1】 ADEabcdefghijklm02 【输入样例2】 cdeT-bcd 【输出样例2】 cdeT-bcd 【样例说明】 将样例1的输入ADEa-g-m02扩展为ADEabcdefghijklm02样例2的输入cdeT-bcd中扩展符前的字符为大写字母扩展符后的字符为小写字母不在同一范围内所以不进行扩展。 思路分析
首先我们明确一下这道题的目的即如果出现“-”且前后均为同类型的字符整数大写小写字母并且满足扩展的顺序前面的小于后面的则对其进行扩展将“-”替换为前后两个字符中间的字符。
所以我们要处理以下的问题
1.如何判断前后字符是否符合条件
2.如何进行替换选择什么样的数据结构来进行实现是否只需要对原来的字符串进行操作还是需要额外再申请空间
切入点是把“-”替换成为中间的字符那么首先想到的是读到“-”的时候就去把相应的位置替换。但是原来的字符串没有办法扩展空间当然如果是使用的动态内存申请另说而且就算使用的是动态内存申请那么每添加一个字符就会需要把后面所有的字符全部向后移动一位因此耗费时间很大并不划算。这里没有使用链表当然如果使用链表的话会非常简单
在不使用链表的情况下我们只能选择数组来进行数据的存储。这里我来谈谈第一个很重要的思想删除/替换不一定非要盯着原来的结构不放不妨换个思路使用另外一个数组来把符合条件的元素留下再把需要进行操作的元素进行相应的操作后再放进新的数组里面这样就会节省很多的时间。
因此我们使用新数组newstr来存储改变后的字符串。具体的操作如下
1.从头开始遍历当元素不是要被替换的元素时直接把他存储到新数组中。
2.当遇到“-”的时候把前面一个字符记为begin后面一个字符记为end然后对这两个字符进行是否符合条件的判断如果符合那么进行一个while循环把从begin到end的所有字符放入新数组中然后原数组继续前进如果不符合条件直接原数组前进跳过“-”。
3.最后在新数组后面加上“\0”代表他是一个字符串。
其实整个过程还是十分清晰的关键点有几个
1.使用新数组进行存储让时间复杂度为O(n).
2.最后要给新的字符串加上‘\0’让输出能够正常输出。
小小的延申
针对这道题其实还有一个很相像的操作即删除字符串中的指定字符这个由于我们一种思路是可以使用新数组来存储但是需要花费额外的空间还有一种的可行思路是只针对字符串的本身进行操作使用类似双指针的方法设置快慢指针即快慢下标如果是正常的字符快慢下标同时向前移动快指针给满指针赋值当遇到要被删除的指针时快指针还是正常向前但是慢指针则停在原处此时快指针已经跳过了待删除的字符直接将下一位字符赋值给仍然处在待删除位置的慢指针将原来的内容覆盖掉了巧妙地实现了覆盖。
那么如何实现快与慢呢快指针由于是全过程都需要遍历的因此我们可以把它放在循环的条件中不受条件的约束而慢指针则需要用if条件来判断他的向前是依靠于是否有条件出现的。在条件中赋值时把慢指针的前移用j放在数组下标中实现i则在循环的条件中当遇到指定字符时不执行慢指针向前并赋值的操作实现跳过。
void squeez(char s[],char c)
{int i,j;for(ij0;s[i]!\0;i)//i是正常移动的if(s[i]!c)s[j]s[i];//如果等于c时则不执行j操作意味着慢指针不移动s[j]\0;
}
代码实现
#include stdio.h
#include ctype.h
#include string.h
#include stdlib.h int main() { char s[1000]; char *newstr; int begin, end; gets(s); int len strlen(s); newstr (char *)malloc(sizeof(char)*(len1000));int j 0; for (int i 0; i len; i) { if (s[i] -) {//这个if是如果有“-”相应操作 if ((i 0 i len - 1) ((isupper(s[i - 1]) isupper(s[i 1]) )||(isdigit(s[i - 1]) isdigit(s[i 1]))||(islower(s[i-1])islower(s[i1])))) //条件判断1是否符合类型一致{ begin s[i - 1]; end s[i 1]; if ((isupper(begin) isupper(end) end begin) ||(isdigit(begin) isdigit(end) end begin)||(islower(s[i-1])islower(s[i1])))//条件判断2是否顺序正确{ for (char c begin1; c end; c) { newstr[j] c; //把缺失的补全} i; //原数组向前移一位进行下一位的判断continue; } } } newstr[j] s[i]; //正常的字符直接读入即可} newstr[j] \0;printf(%s\n, newstr); free(newstr);return 0;
}
