【字符串處理算法】字符串包含的算法設(shè)計(jì)及C代碼實(shí)現(xiàn)
一、需求描述
給定一個(gè)長(zhǎng)字符串和一個(gè)短字符串，編寫(xiě)程序判斷短字符串中的所有字符是否都在長(zhǎng)字符串中。如果是，則長(zhǎng)字符串包含短字符串;反之，不包含。
為了盡量包含大多數(shù)情況，字符串中可以包含大小寫(xiě)英文字母、數(shù)字和各種標(biāo)點(diǎn)符號(hào)，并且區(qū)分大小寫(xiě)字母。
下面舉幾個(gè)例子予以說(shuō)明：
1.如果長(zhǎng)字符串是“ABCDE”，短字符串是“ADC”，那么短字符串中的所有字符都在長(zhǎng)字符串中，即長(zhǎng)字符串包含了短字符串。
2.如果長(zhǎng)字符串是“ABCDE”，短字符串是“ADCF”，那么短字符串中不是所有字符都在長(zhǎng)字符串中，即長(zhǎng)字符串不包含了短字符串。
3.如果長(zhǎng)字符串是“ABCDE”，短字符串是“AAB”，那么短字符串中的所有字符都在長(zhǎng)字符串中，即長(zhǎng)字符串包含了短字符串。
二、算法設(shè)計(jì)
我們都知道，就像人體是由一個(gè)個(gè)的細(xì)胞組成一樣，一個(gè)字符串是由一個(gè)個(gè)的字符組成。如果組成某個(gè)字符串的所有字符都在另一個(gè)字符串中，那么這個(gè)字符串就被另一個(gè)字符串包含。
因此，我們可以考慮先將兩個(gè)字符串中的所有字符都找出來(lái)，再判斷較短的字符串中的所有字符是否都出現(xiàn)在了較長(zhǎng)的字符串中。如果是，那么兩個(gè)字符串是包含與被包含的關(guān)系;如果不是，那么兩個(gè)字符串則“形同陌路”。
程序的總體流程如圖1所示。
圖1 程序的總體流程
三、特殊流程考慮
在編寫(xiě)程序的過(guò)程中，我們要對(duì)輸入的兩個(gè)字符串的長(zhǎng)度及格式多做考慮，如：
1.如果輸入失誤，導(dǎo)致短字符串的長(zhǎng)度大于了長(zhǎng)字符串，那么程序直接返回，不進(jìn)行后續(xù)處理。
2.不允許在輸入字符串的中間出現(xiàn)空格，如果出現(xiàn)了，只能把空格前面的內(nèi)容作為輸入的字符串。
3.輸入字符串可以包含字母(區(qū)分大小寫(xiě))、數(shù)字、標(biāo)點(diǎn)符號(hào)等字符。
4.為了方便程序處理，設(shè)定較長(zhǎng)的字符串最長(zhǎng)為500個(gè)字節(jié)，較短的字符串最長(zhǎng)為100個(gè)字節(jié)。
四、程序代碼
- /**********************************************************************
- * 版權(quán)所有 (C)2016, Zhou Zhaoxiong。
- *
- * 文件名稱： StringContains.c
- * 文件標(biāo)識(shí)： 無(wú)
- * 內(nèi)容摘要： 測(cè)試一個(gè)字符串是否是另一個(gè)字符串的子串
- * 其它說(shuō)明： 例如, "ABC"是"ABCD"的子串
- * 當(dāng)前版本： V1.0
- * 作 者： Zhou Zhaoxiong
- * 完成日期： 20160216
- *
- **********************************************************************/
- #include <stdio.h>
- #include <stdlib.h>
- // 重新定義數(shù)據(jù)類型
- typedef signed char INT8;
- typedef unsigned short int UINT16;
- typedef int INT32;
- typedef unsigned int UINT32;
- // 存放字符串中的字符和格式的結(jié)構(gòu)體
- typedef struct
- {
- INT8 szStrCharArray[101][2]; // 字符串中不相同的字符的存放數(shù)組，***支持100個(gè)
- INT32 iStrCharCount; // 字符串中不相同的字符的個(gè)數(shù)
- } StrInfo_T;
- StrInfo_T gtLongerStrInfo = {0};
- StrInfo_T gtShorterStrInfo = {0};
- // 函數(shù)聲明
- void GetStrChar(INT8 *pszInputStr, INT32 iProcessFlag);
- INT32 JudgeIfContainsStr();
- /**********************************************************************
- * 功能描述： 主函數(shù)
- * 輸入?yún)?shù)： 無(wú)
- * 輸出參數(shù)： 無(wú)
- * 返 回 值： 0-執(zhí)行成功 其它-執(zhí)行失敗
- * 其它說(shuō)明： 無(wú)
- * 修改日期 版本號(hào) 修改人 修改內(nèi)容
- * -----------------------------------------------------------------
- * 20160216 V1.0 Zhou Zhaoxiong 創(chuàng)建
- ***********************************************************************/
- INT32 main()
- {
- INT8 szLongerStr[500] = {0};
- INT8 szShorterStr[100] = {0};
- UINT32 iContainFlag = 1; // 包含標(biāo)志, 1-包含, 0-不包含
- printf("Please input the longer string: \n");
- scanf("%s", szLongerStr);
- printf("LongerStr=%s\n", szLongerStr);
- printf("Please input the shorter string: \n");
- scanf("%s", szShorterStr);
- printf("ShorterStr=%s\n", szShorterStr);
- // 如果ShorterStr的長(zhǎng)度大于LongerStr, 則直接返回
- if (strlen(szShorterStr) > strlen(szLongerStr))
- {
- printf("%s is longer than %s, please check!\n", szShorterStr, szLongerStr);
- return -1;
- }
- // 獲取較長(zhǎng)的字符串中的不同的字符
- GetStrChar(szLongerStr, 1);
- // 獲取較短的字符串中的不同的字符
- GetStrChar(szShorterStr, 2);
- iContainFlag = JudgeIfContainsStr();
- if (iContainFlag == 0)
- {
- printf("%s doesn't contain %s!\n", szLongerStr, szShorterStr);
- }
- else
- {
- printf("%s contains %s!\n", szLongerStr, szShorterStr);
- }
- return 0;
- }
- /**********************************************************************
- * 功能描述： 獲取字符串中不相同的字符及其個(gè)數(shù)
- * 輸入?yún)?shù)： pszInputStr-輸入字符串
- iProcessFlag-處理標(biāo)志(1:處理長(zhǎng)字符串, 2:處理短字符串)
- * 輸出參數(shù)： 無(wú)
- * 返 回 值： 無(wú)
- * 其它說(shuō)明： 無(wú)
- * 修改日期 版本號(hào) 修改人 修改內(nèi)容
- * ---------------------------------------------------------------
- * 20160216 V1.0 Zhou Zhaoxiong 創(chuàng)建
- ***********************************************************************/
- void GetStrChar(INT8 *pszInputStr, INT32 iProcessFlag)
- {
- INT32 iCharCount = 0; // 字符個(gè)數(shù)
- INT8 szInputStr[501] = {0};
- INT8 szCharBuf[2] = {0}; // 存放單個(gè)字符的緩存
- INT32 iRepeatFlag = 0;
- UINT32 iStrPosFlag = 0;
- UINT32 iLoopFlag = 0;
- UINT32 iInputStrLen = 0;
- if (pszInputStr == NULL)
- {
- return;
- }
- iInputStrLen = strlen(pszInputStr);
- if (iInputStrLen >= 500) // ***支持100個(gè)字母
- {
- return;
- }
- memcpy(szInputStr, pszInputStr, iInputStrLen);
- iCharCount = 0;
- for (iStrPosFlag = 0; iStrPosFlag < iInputStrLen; iStrPosFlag ++)
- {
- iRepeatFlag = 0;
- // 判斷正要獲取的字符是否已經(jīng)存在了
- memset(szCharBuf, 0x00, sizeof(szCharBuf));
- memcpy(szCharBuf, szInputStr+iStrPosFlag, 1);
- // 若與之前已經(jīng)加入的字符重復(fù), 則忽略
- for (iLoopFlag = 0; iLoopFlag < iCharCount; iLoopFlag ++)
- {
- if (iProcessFlag == 1) // 處理長(zhǎng)字符串
- {
- if (0 == strncmp(gtLongerStrInfo.szStrCharArray[iLoopFlag], szCharBuf, 1))
- {
- iRepeatFlag = 1; // 有重復(fù)的, 直接忽略
- break;
- }
- }
- else // 處理短字符串
- {
- if (0 == strncmp(gtShorterStrInfo.szStrCharArray[iLoopFlag], szCharBuf, 1))
- {
- iRepeatFlag = 1; // 有重復(fù)的, 直接忽略
- break;
- }
- }
- }
- if (1 == iRepeatFlag)
- {
- continue;
- }
- if (iProcessFlag == 1) // 處理長(zhǎng)字符串
- {
- strncpy(gtLongerStrInfo.szStrCharArray[iCharCount], szCharBuf, 1);
- }
- else // 處理短字符串
- {
- strncpy(gtShorterStrInfo.szStrCharArray[iCharCount], szCharBuf, 1);
- }
- iCharCountiCharCount = iCharCount + 1;
- }
- if (iProcessFlag == 1) // 處理長(zhǎng)字符串
- {
- gtLongerStrInfo.iStrCharCount = iCharCount;
- }
- else // 處理短字符串
- {
- gtShorterStrInfo.iStrCharCount = iCharCount;
- }
- return;
- }
- /**********************************************************************
- * 功能描述： 判斷長(zhǎng)字符串是否包含了短字符串
- * 輸入?yún)?shù)： 無(wú)
- * 輸出參數(shù)： 無(wú)
- * 返 回 值： 1-包含了 0-沒(méi)有包含
- * 其它說(shuō)明： 無(wú)
- * 修改日期 版本號(hào) 修改人 修改內(nèi)容
- * ---------------------------------------------------------------
- * 20160216 V1.0 Zhou Zhaoxiong 創(chuàng)建
- ***********************************************************************/
- INT32 JudgeIfContainsStr()
- {
- UINT32 iLongerLoopFlag = 0;
- UINT32 iShorterLoopFlag = 0;
- UINT32 iCharIdenticalFlag = 0;
- // 判斷較短的字符串中的字符是否全部都在較長(zhǎng)的字符串中的字符中
- for (iShorterLoopFlag = 0; iShorterLoopFlag < gtShorterStrInfo.iStrCharCount; iShorterLoopFlag ++)
- {
- iCharIdenticalFlag = 0;
- for (iLongerLoopFlag = 0; iLongerLoopFlag < gtLongerStrInfo.iStrCharCount; iLongerLoopFlag ++)
- {
- if (strcmp(gtShorterStrInfo.szStrCharArray[iShorterLoopFlag], gtLongerStrInfo.szStrCharArray[iLongerLoopFlag]) == 0)
- {
- iCharIdenticalFlag = 1; // 字符相同
- break;
- }
- }
- if (iCharIdenticalFlag == 0) // 表示兩個(gè)字符串中有不相同的字符
- {
- return 0;
- }
- }
- return 1;
- }
五、程序測(cè)試
我們將編寫(xiě)好的程序“StringContains.c”上傳到Linux機(jī)器，并使用“gcc -g -o StringContainsStringContains.c”命令對(duì)該程序進(jìn)行編譯，生成“StringContains”文件。下面對(duì)程序進(jìn)行詳細(xì)的測(cè)試。
1.輸入較長(zhǎng)字符串為“ABCDF”、較短字符串為“AF”時(shí)，程序運(yùn)行情況如下：
- Please input the longer string:
- ABCDF
- LongerStr=ABCDF
- Please input the shorter string:
- AF
- ShorterStr=AF
- ABCDF contains AF!
2.輸入較長(zhǎng)字符串為“AB”、較短字符串為“ABC”時(shí)，程序運(yùn)行情況如下：
- Please input the longer string:
- AB
- LongerStr=AB
- Please input the shorter string:
- ABC
- ShorterStr=ABC
- ABC is longer than AB, please check!
3.輸入較長(zhǎng)字符串為“awe”、較短字符串為“rf”時(shí)，程序運(yùn)行情況如下：
- Please input the longer string:
- awe
- LongerStr=awe
- Please input the shorter string:
- rf
- ShorterStr=rf
- awe doesn't contain rf!
4.輸入較長(zhǎng)字符串為“`11245”、較短字符串為“45”時(shí)，程序運(yùn)行情況如下：
- Please input the longer string:
- `11245
- LongerStr=`11245
- Please input the shorter string:
- 45
- ShorterStr=45
- `11245 contains 45!
5.輸入較長(zhǎng)字符串為“123”、較短字符串為“123 45”時(shí)，程序運(yùn)行情況如下：
- Please input the longer string:
- 123
- LongerStr=123
- Please input the shorter string:
- 123 45
- ShorterStr=123
- 123 contains 123!
可見(jiàn)，對(duì)于上面考慮到的幾種特殊情況，程序均能做出正確的處理。
六、需求擴(kuò)展
基于本文中的需求和程序，我們可考慮對(duì)需求進(jìn)行以下擴(kuò)展：
1.限制輸入的字符串中只能包含字母，如果包含了其它字符，則直接退出而不進(jìn)行處理。
2.如果較短的字符串中的所有字符雖然都在較長(zhǎng)的字符串中，但某個(gè)字符在較短的字符串中出現(xiàn)的次數(shù)大于了在較長(zhǎng)的字符串中出現(xiàn)的次數(shù)，那么就認(rèn)為較長(zhǎng)的字符串不包含較短的字符串。
【本文是51CTO專欄作者周兆熊的原創(chuàng)文章，作者微信公眾號(hào)：周氏邏輯(logiczhou)】
