題目展示

【問題描述】

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

要求：只處理[a-z]、[A-Z]、[0-9]范圍內(nèi)的字符擴(kuò)展，即只有當(dāng)擴(kuò)展符前后的字符同時(shí)是小寫字母、大寫字母或數(shù)字，并且擴(kuò)展符后的字符大于擴(kuò)展符前的字符時(shí)才進(jìn)行擴(kuò)展，其它情況不進(jìn)行擴(kuò)展，原樣輸出。例如：a-R、D-e、0-b、4-B等字符串都不進(jìn)行擴(kuò)展。

【輸入形式】

從鍵盤輸入包含擴(kuò)展符的字符串
【輸出形式】
輸出擴(kuò)展后的字符串

【輸入樣例1】
ADEa-g-m02
【輸出樣例1】
ADEabcdefghijklm02

【輸入樣例2】
cdeT-bcd
【輸出樣例2】
cdeT-bcd

【樣例說明】
將樣例1的輸入ADEa-g-m02擴(kuò)展為：ADEabcdefghijklm02；樣例2的輸入cdeT-bcd中，擴(kuò)展符前的字符為大寫字母，擴(kuò)展符后的字符為小寫字母，不在同一范圍內(nèi)，所以不進(jìn)行擴(kuò)展。 

思路分析

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

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

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

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

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

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

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

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

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

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

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

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

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

小小的延申

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

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

void squeez(char s[],char c)
{
 int i,j;
 for(i=j=0;s[i]!='\0';i++)//i是正常移動(dòng)的
  if(s[i]!=c)
   s[j++]=s[i];//如果等于c時(shí)，則不執(zhí)行j++操作，意味著慢指針不移動(dòng)
 s[j]='\0';
}
 

代碼實(shí)現(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] == '-') {//這個(gè)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;  //把缺失的補(bǔ)全
                    }  
                    i++; //原數(shù)組向前移一位，進(jìn)行下一位的判斷
                    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)擴(kuò)展字符內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論