C语言数据结构之扩展字符详解

来自:网络
时间:2024-06-09
阅读:

题目展示

【问题描述】

从键盘输入包含扩展符'-'的字符串,将其扩展为等价的完整字符,例如将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(i=j=0;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)*(len+1000));
   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[i+1])))) //条件判断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[i+1])))//条件判断2,是否顺序正确
                {  
                    for (char c = begin+1; c <= end; c++) 
                    {  
                        newstr[j++] = c;  //把缺失的补全
                    }  
                    i++; //原数组向前移一位,进行下一位的判断
                    continue;  
                }  
            }  
        } 
        newstr[j++] = s[i]; //正常的字符直接读入即可
    }  
    newstr[j] = '\0';
    printf("%s\n", newstr);  
    free(newstr);
    return 0;  
}
返回顶部
顶部