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

题目展示

【问题描述】

从键盘输入包含扩展符'-'的字符串，将其扩展为等价的完整字符，例如将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;  
}

到此这篇关于C语言数据结构之扩展字符详解的文章就介绍到这了,更多相关C语言数据结构扩展字符内容请搜索程序员之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持程序员之家！

最新评论