【字符串處理算法】回文判斷的算法設計及C代碼實現
作者：周兆熊
今天主要講講回文判斷的算法設計及C代碼實現。
一、需求描述
輸入一個字符串，編寫程序判斷這個字符串是否是回文串。
為了便于說明，設定輸入的字符串分為中文字符串和非中文字符串兩種。其中，中文字符串中僅包含中文字符，非中文字符串中不包含中文字符。
所謂回文串，是指正讀和反讀都一樣的字符串。下面舉幾個例子予以說明：
1.“level”是一個非中文字符的回文串，因為正讀和反讀都是“level”。
2.“Good”不是一個非中文字符的回文串。
3.“我愛我”是一個中文字符的回文串，因為正讀和反讀都是“我愛我”。
4.“我愛你”不是一個中文字符的回文串。
二、算法設計
對于非中文字符的回文串的判斷比較簡單，我們只要以字符串的中間為原點，比較前后對應的字符是否相等就可以了;但對于中文字符的回文串的判斷要復雜一點，因為一個中文字符占兩個字節，我們不能采用非中文字符的回文串的判斷方法，而是應該先單獨獲取每個中文字符，然后再比較一前一后兩個字符是否相等。
程序的總體流程如圖1所示。
圖1 程序的總體流程
三、特殊流程考慮
在編寫程序的過程中，我們要對輸入的字符串的長度及格式多做考慮，如：
1.如果輸入的字符串中只有一個字符，那么程序直接返回，不執行后續流程，因為回文串中至少有兩個及以上的字符。
2.如果輸入的中文串中含有非中文字符，或者是輸入的非中文串中含有中文字符，那么程序直接返回，不執行后續流程。
四、程序代碼
- /**********************************************************************
- * 版權所有 (C)2016, Zhou Zhaoxiong。
- *
- * 文件名稱： PalindromicString.c
- * 文件標識： 無
- * 內容摘要： 回文判斷
- * 其它說明： 形如madam, php, 2992, 1234321這樣的串就是回文串
- * 當前版本： V1.0
- * 作 者： Zhou Zhaoxiong
- * 完成日期： 20160222
- *
- **********************************************************************/
- #include <stdio.h>
- // 重新定義數據類型
- typedef signed char INT8;
- typedef int INT32;
- typedef unsigned int UINT32;
- // 全局變量聲明, 用于存放漢字, ***支持100個漢字
- INT8 gszStrCharArray[101][5] = {0};
- UINT32 giCharNum = 0;
- // 函數聲明
- void JudgePalindromicString(INT8 *pszInputStr, UINT32 iInputStrLen, UINT32 iStrType);
- void GetChineseChars(INT8 *pszInputStr);
- INT32 JudgeStrFormat(INT8 *pszInputStr, UINT32 iStrType);
- /**********************************************************************
- * 功能描述： 主函數
- * 輸入參數： 無
- * 輸出參數： 無
- * 返 回 值： 0-執行成功 其它-執行失敗
- * 其它說明： 無
- * 修改日期 版本號 修改人 修改內容
- * ---------------------------------------------------------------------
- * 20160222 V1.0 Zhou Zhaoxiong 創建
- ***********************************************************************/
- INT32 main()
- {
- UINT32 iStrType = 0;
- INT32 iRetVal = 0;
- INT8 szInputStr[100] = {0};
- printf("Please input the string type(1:中文字符串,2:非中文字符串): \n");
- scanf("%d", &iStrType);
- printf("Please input the string: \n");
- scanf("%s", szInputStr);
- // 判斷輸入的字符串是中文字符串或者是非中文字符串
- iRetVal = JudgeStrFormat(szInputStr, iStrType);
- if (iRetVal != 0)
- {
- return -1;
- }
- if (iStrType == 1) // 如果輸入的是中文串, 則先獲取各個中文字符
- {
- GetChineseChars(szInputStr);
- if (giCharNum <= 1) // 只輸入了一個字符, 直接返回
- {
- printf("%s has only one character, please check!\n", szInputStr);
- return -1;
- }
- }
- else if (iStrType == 2)
- {
- if (strlen(szInputStr) <= 1) // 只輸入了一個字符, 直接返回
- {
- printf("%s has only one character, please check!\n", szInputStr);
- return -1;
- }
- }
- // 判斷輸入的字符串是否為回文串
- JudgePalindromicString(szInputStr, strlen(szInputStr), iStrType);
- return 0;
- }
- /**********************************************************************
- * 功能描述：判斷輸入的字符串是否為回文串
- * 輸入參數：pszInputStr-輸入的字符串
- iInputStrLen-輸入的字符串的長度
- iStrType-輸入的字符串的類型
- * 輸出參數：無
- * 返 回 值：無
- * 其它說明：無
- * 修改日期 版本號 修改人 修改內容
- * -------------------------------------------------------------------
- * 20160222 V1.0 Zhou Zhaoxiong 創建
- ***********************************************************************/
- void JudgePalindromicString(INT8 *pszInputStr, UINT32 iInputStrLen, UINT32 iStrType)
- {
- UINT32 iPosFlag = 0;
- if (NULL == pszInputStr)
- {
- return;
- }
- if (iStrType == 1) // 中文字符串
- {
- for (iPosFlag = 0; iPosFlag < giCharNum/2; iPosFlag ++)
- {
- if (strcmp(gszStrCharArray[iPosFlag], gszStrCharArray[giCharNum-1-iPosFlag]) != 0) // 有對應字符不相等
- {
- printf("%s is not a palindromic string!\n", pszInputStr);
- return;
- }
- }
- }
- if (iStrType == 2) // 非中文字符串
- {
- // 從中間分開, 一前一后兩個字符互相比較, 如果全部對應相等, 則是回文串
- for (iPosFlag = 0; iPosFlag < iInputStrLen/2; iPosFlag ++)
- {
- if (pszInputStr[iPosFlag] != pszInputStr[iInputStrLen-1-iPosFlag]) // 有對應字符不相等
- {
- printf("%s is not a palindromic string!\n", pszInputStr);
- return;
- }
- }
- }
- printf("%s is a palindromic string!\n", pszInputStr);
- return;
- }
- /**********************************************************************
- * 功能描述：獲取輸入的字符串中的每個中文字符
- * 輸入參數：pszInputStr-輸入的字符串
- iInputStrLen-輸入的字符串的長度
- * 輸出參數：無
- * 返 回 值：無
- * 其它說明：無
- * 修改日期 版本號 修改人 修改內容
- * -------------------------------------------------------------------
- * 20160222 V1.0 Zhou Zhaoxiong 創建
- ***********************************************************************/
- void GetChineseChars(INT8 *pszInputStr)
- {
- UINT32 iPosFlag = 0;
- if (NULL == pszInputStr)
- {
- return;
- }
- memset(gszStrCharArray, 0x00, sizeof(gszStrCharArray));
- giCharNum = 0;
- while (iPosFlag < strlen(pszInputStr))
- {
- snprintf(gszStrCharArray[giCharNum], sizeof(gszStrCharArray[giCharNum])-1, "%c%c", pszInputStr[iPosFlag], pszInputStr[iPosFlag+1]);
- iPosFlagiPosFlag = iPosFlag + 2; // 每個中文字符占兩個字節
- giCharNum ++;
- }
- }
- /**********************************************************************
- * 功能描述：判斷輸入的字符串的格式是否正確
- * 輸入參數：pszInputStr-輸入的字符串
- iStrType-輸入的字符串的類型
- * 輸出參數：無
- * 返 回 值：0-格式正確 其它-格式不正確
- * 其它說明：無
- * 修改日期 版本號 修改人 修改內容
- * -------------------------------------------------------------------
- * 20160222 V1.0 Zhou Zhaoxiong 創建
- ***********************************************************************/
- INT32 JudgeStrFormat(INT8 *pszInputStr, UINT32 iStrType)
- {
- UINT32 iPosFlag = 0;
- if (NULL == pszInputStr)
- {
- return -1;
- }
- if (iStrType == 1) // 先判斷中文字符串
- {
- for (iPosFlag = 0; iPosFlag < strlen(pszInputStr); iPosFlag ++)
- {
- if (pszInputStr[iPosFlag] >= 0) // 不小于0則表示含有非中文字符
- {
- printf("%s has non-Chinese character, please check!\n", pszInputStr);
- return -2;
- }
- }
- }
- else if (iStrType == 2) // 再判斷非中文字符串
- {
- for (iPosFlag = 0; iPosFlag < strlen(pszInputStr); iPosFlag ++)
- {
- if (pszInputStr[iPosFlag] < 0) // 小于0則表示含有中文字符
- {
- printf("%s has Chinese character, please check!\n", pszInputStr);
- return -3;
- }
- }
- }
- else
- {
- printf("Please input the right string type!\n");
- return -4;
- }
- return 0;
- }
五、程序測試
我們將編寫好的程序“PalindromicString.c”上傳到Linux機器，并使用“gcc -g -o PalindromicStringPalindromicString.c”命令對該程序進行編譯，生成“PalindromicString”文件。下面對程序進行詳細的測試。
1.輸入中文字符串為“人上人”時，程序運行情況如下：
- Please input the string type(1:中文字符串,2:非中文字符串):
- 1
- Please input the string:
- 人上人
- 人上人 is a palindromic string!
2.輸入中文字符串為“我是誰”時，程序運行情況如下：
- Please input the string type(1:中文字符串,2:非中文字符串):
- 1
- Please input the string:
- 我是誰
- 我是誰 is not a palindromic string!
3.輸入非中文字符串為“level”時，程序運行情況如下：
- Please input the string type(1:中文字符串,2:非中文字符串):
- 2
- Please input the string:
- level
- level is a palindromic string!
4.輸入非中文字符串為“good”時，程序運行情況如下：
- Please input the string type(1:中文字符串,2:非中文字符串):
- 2
- Please input the string:
- good
- good is not a palindromic string!
5.輸入字符串為“你好good”時，程序運行情況如下：
- Please input the string type(1:中文字符串,2:非中文字符串):
- 1
- Please input the string:
- 你好good
- 你好good has non-Chinese character, pleasecheck!
6.輸入字符串為“good好”時，程序運行情況如下：
- Please input the string type(1:中文字符串,2:非中文字符串):
- 2
- Please input the string:
- good好
- good好 has Chinese character, pleasecheck!
7.輸入字符串類型非1或2時，程序運行情況如下：
- Please input the string type(1:中文字符串,2:非中文字符串):
- 3
- Please input the string:
- goog
- Please input the right string type!
可見，對于上面考慮到的幾種特殊情況，程序均能做出正確的處理。
六、需求擴展
基于本文中的需求和程序，我們可考慮對需求進行以下擴展：
1.不限制輸入的字符串中只能是中文串或者非中文串，可以是中文字符和非中文字符的混合串。
2.當輸入的字符串中是非中文串時，要求該字符串的字符個數為偶數。即要求形如“goog”這樣的字符串為回文串，而像“level” 這樣的字符串不為回文串。
【本文是51CTO專欄作者周兆熊的原創文章，作者微信公眾號：周氏邏輯(logiczhou)】
責任編輯：趙寧寧
來源：
51CTO專欄
