題目展示

【問題描述】

從鍵盤輸入包含擴展符'-'的字符串，將其擴展為等價的完整字符，例如將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.如何進行替換，選擇什么樣的數據結構來進行實現？是否只需要對原來的字符串進行操作？還是需要額外再申請空間？

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

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

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

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

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

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

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

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

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

小小的延申

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

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

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';
}
 

代碼實現：

#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語言數據結構擴展字符內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論