題目展示

【問題描述】

從鍵盤輸入包含擴展符'-'的字符串，將其擴展為等價的完整字符，例如將a-d擴展為abcd，并輸出擴展后的字符串。

要求：只處理[a-z]、[A-Z]、[0-9]范圍內(nèi)的字符擴展，即只有當(dāng)擴展符前后的字符同時是小寫字母、大寫字母或數(shù)字，并且擴展符后的字符大于擴展符前的字符時才進行擴展，其它情況不進行擴展，原樣輸出。例如：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中，擴展符前的字符為大寫字母，擴展符后的字符為小寫字母，不在同一范圍內(nèi)，所以不進行擴展。 

思路分析

首先我們明確一下這道題的目的，即：如果出現(xiàn)“-”且前后均為同類型的字符（整數(shù)，大寫小寫字母），并且滿足擴展的順序（前面的小于后面的），則對其進行擴展，將“-”替換為前后兩個字符中間的字符。

所以我們要處理以下的問題：

1.如何判斷前后字符是否符合條件

2.如何進行替換，選擇什么樣的數(shù)據(jù)結(jié)構(gòu)來進行實現(xiàn)？是否只需要對原來的字符串進行操作？還是需要額外再申請空間？

切入點是：把“-”替換成為中間的字符，那么，首先想到的是讀到“-”的時候就去把相應(yīng)的位置替換。但是原來的字符串沒有辦法擴展空間（當(dāng)然如果是使用的動態(tài)內(nèi)存申請另說），而且就算使用的是動態(tài)內(nèi)存申請，那么每添加一個字符就會需要把后面所有的字符全部向后移動一位，因此耗費時間很大，并不劃算。（這里沒有使用鏈表，當(dāng)然，如果使用鏈表的話會非常簡單）

在不使用鏈表的情況下，我們只能選擇數(shù)組來進行數(shù)據(jù)的存儲。這里我來談?wù)劦谝粋€很重要的思想：刪除/替換，不一定非要盯著原來的結(jié)構(gòu)不放，不妨換個思路，使用另外一個數(shù)組來把符合條件的元素留下，再把需要進行操作的元素進行相應(yīng)的操作后再放進新的數(shù)組里面，這樣就會節(jié)省很多的時間。

因此，我們使用新數(shù)組newstr來存儲改變后的字符串。具體的操作如下：

1.從頭開始遍歷，當(dāng)元素不是要被替換的元素時，直接把他存儲到新數(shù)組中。

2.當(dāng)遇到“-”的時候，把前面一個字符記為begin，后面一個字符記為end，然后對這兩個字符進行是否符合條件的判斷，如果符合，那么進行一個while循環(huán)，把從begin到end的所有字符放入新數(shù)組中，然后原數(shù)組繼續(xù)前進；如果不符合條件，直接原數(shù)組前進，跳過“-”。

3.最后在新數(shù)組后面加上“\0”，代表他是一個字符串。

其實整個過程還是十分清晰的，關(guān)鍵點有幾個：

1.使用新數(shù)組進行存儲，讓時間復(fù)雜度為O(n).

2.最后要給新的字符串加上‘\0’讓輸出能夠正常輸出。

小小的延申

針對這道題，其實還有一個很相像的操作，即刪除字符串中的指定字符，這個由于我們一種思路是可以使用新數(shù)組來存儲，但是需要花費額外的空間；還有一種的可行思路是：只針對字符串的本身進行操作，使用類似雙指針的方法，設(shè)置快慢指針（即快慢下標(biāo)），如果是正常的字符，快慢下標(biāo)同時向前移動，快指針給滿指針賦值；當(dāng)遇到要被刪除的指針時，快指針還是正常向前，但是慢指針則停在原處，此時快指針已經(jīng)跳過了待刪除的字符，直接將下一位字符賦值給仍然處在待刪除位置的慢指針，將原來的內(nèi)容覆蓋掉了，巧妙地實現(xiàn)了覆蓋。

那么如何實現(xiàn)快與慢呢？快指針由于是全過程都需要遍歷的，因此我們可以把它放在循環(huán)的條件中，不受條件的約束；而慢指針則需要用if條件來判斷，他的向前是依靠于是否有條件出現(xiàn)的。在條件中賦值時把慢指針的前移用j++放在數(shù)組下標(biāo)中實現(xiàn)，i++則在循環(huán)的條件中，當(dāng)遇到指定字符時，不執(zhí)行慢指針向前并賦值的操作，實現(xiàn)跳過。

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時，則不執(zhí)行j++操作，意味著慢指針不移動
 s[j]='\0';
}
 

代碼實現(xiàn)：

#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是如果有“-”相應(yīng)操作 
            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++; //原數(shù)組向前移一位，進行下一位的判斷
                    continue;  
                }  
            }  
        } 
        newstr[j++] = s[i]; //正常的字符直接讀入即可
    }  
    newstr[j] = '\0';
    printf("%s\n", newstr);  
    free(newstr);
    return 0;  
}

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)之?dāng)U展字符詳解的文章就介紹到這了,更多相關(guān)C語言數(shù)據(jù)結(jié)構(gòu)擴展字符內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論