【文字列処理アルゴリズム】回文判定のアルゴリズム設計とCコード実装

1. 要件の説明

文字列を入力し、その文字列が回文であるかどうかを判断するプログラムを作成します。

便宜上、入力文字列は中国語文字列と非中国語文字列の 2 種類に分かれていると仮定します。中国語文字列には中国語の文字のみが含まれ、中国語以外の文字列には中国語の文字が含まれません。

回文とは、前から読んでも後ろから読んでも同じ文字列のことです。以下にいくつかの例を挙げて説明します。

1. 「level」は非中国語文字の回文です。正読も逆読も「level」だからです。

2. 「Good」は非中国語の文字の回文ではありません。

3. 「我愛我」は漢字の回文です。正読も逆読も「我愛我」となるからです。

4. 「愛しています」は漢字の回文ではありません。

2. アルゴリズム設計

非中国語文字の回文文字列の判定は比較的簡単です。文字列の中央を起点として、前後の対応する文字が等しいかどうかを比較するだけです。ただし、中国語文字の回文文字列の判定は、中国語文字が 2 バイトを占めるため、少し複雑です。非中国語文字の回文文字列の判定方法は使用できません。代わりに、最初に各中国語文字を個別に取得し、次に前後の 2 つの文字が等しいかどうかを比較する必要があります。

プログラムの全体的な流れを図 1 に示します。

図1 プログラムの全体的なプロセス

3. 特別なプロセスに関する考慮事項

プログラムを作成する過程では、次のような入力文字列の長さと形式を考慮する必要があります。

1. 入力文字列に 1 文字しか含まれていない場合、回文文字列には少なくとも 2 文字以上が含まれているため、プログラムは後続の処理を実行せずに直接戻ります。

2. 入力された中国語文字列に中国語以外の文字が含まれている場合、または入力された中国語以外の文字列に中国語の文字が含まれている場合、プログラムは後続の処理を実行せずに直接戻ります。

4. プログラムコード

 /******************************************************************************************
 * 著作権 (C) 2016、Zhou Zhaoxiong。
 *
 * ファイル名: PalindromicString.c
 * ファイルID: なし
* 内容概要: 回文判定
* その他の注意: madam、php、2992、1234321 などの文字列は回文です。
 * 現在のバージョン: V1.0
 * 著者: 周昭雄
* 完成日: 20160222
 *
 ******************************************************************************/
 #include < stdio.h >   
 
 
 // データ型を再定義する
typedef signed char INT8;
型定義 int INT32;
 typedef 符号なし int UINT32; 
 
 // グローバル変数宣言。中国語の文字を格納するために使用します。*** 100 文字の中国語をサポートします
INT8 gszStrCharArray[101][5] = {0};
 UINT32 giCharNum = 0 ; 
 
 
 // 関数宣言
void JudgePalindromicString(INT8 *pszInputStr、UINT32 iInputStrLen、UINT32 iStrType);
 void GetChineseChars(INT8 *pszInputStr);
 INT32 判定Strフォーマット(INT8 *pszInputStr、UINT32 iStrType); 
 
 
 /******************************************************************************************
 * 機能説明: 主な機能
* 入力パラメータ: なし
* 出力パラメータ: なし
* 戻り値: 0 - 実行成功 その他 - 実行失敗
* その他の指示: なし
* 変更日 バージョン番号 修正者 変更内容
* ---------------------------------------------------------------------
 * 20160222 V1.0 作成者: Zhou Zhaoxiong
 ******************************************************************************/
 INT32 メイン()
 {
    UINT32 iStrType = 0 ;
    INT32 iRetVal = 0 ;
    INT8 szInputStr[100] = {0}; 
 
    printf("文字列タイプを入力してください(1: 中国語文字列、2: 中国語以外の文字列): \n");
    scanf("%d", &iStrType); 
     
    printf("文字列を入力してください: \n");
    scanf("%s", szInputStr); 
 
    // 入力文字列が中国語文字列か非中国語文字列かを判定する
iRetVal = JudgeStrFormat (szInputStr、iStrType);
    (iRetVal != 0) の場合
    {
        -1 を返します。
    } 
 
    if ( iStrType == 1) // 入力が中国語の文字列の場合、まず各中国語の文字を取得します
    {
        中国語文字を取得します(szInputStr); 
 
        if (giCharNum < = 1) // 1文字だけ入力された場合は直接戻ります
        {
            printf("%s には文字が 1 つしかありません。確認してください!\n", szInputStr);
            -1 を返します。
        }
    }
    そうでない場合 ( iStrType == 2)
    {
        if (strlen(szInputStr) < = 1) // 1文字だけ入力されたので、直接戻ります
        {
            printf("%s には文字が 1 つしかありません。確認してください!\n", szInputStr);
            -1 を返します。
        }
    } 
  
    // 入力文字列が回文かどうかを判定する
    回文文字列を判断します(szInputStr、strlen(szInputStr)、iStrType); 
 
    0を返します。
 } 
 
 
 /******************************************************************************************
 * 関数の説明: 入力文字列が回文であるかどうかを判定する
* 入力パラメータ: pszInputStr-入力文字列
            iInputStrLen - 入力文字列の長さ
            iStrType - 入力文字列の型
* 出力パラメータ: なし
* 戻り値: なし
* その他の指示: なし
* 変更日 バージョン番号 修正者 変更内容
* -------------------------------------------------------------------
 * 20160222 V1.0 作成者: Zhou Zhaoxiong
 ******************************************************************************/
 void 判定回文文字列(INT8 *pszInputStr、UINT32 iInputStrLen、UINT32 iStrType)
 {
    UINT32 iPosFlag = 0 ; 
 
    if ( NULL == pszInputStr)
    {
        戻る;
    } 
 
    if ( iStrType == 1) // 中国語文字列
    {
        ( iPosFlag = 0 ; iPosFlag <   giCharNum /2; iPosFlag ++)
        {
            if (strcmp(gszStrCharArray[iPosFlag], gszStrCharArray[giCharNum-1-iPosFlag]) != 0) // 対応する文字が等しくありません
            {
                printf("%s は回文文字列ではありません!\n", pszInputStr);
                戻る;
            }
        }
    } 
 
    if ( iStrType == 2) // 中国語以外の文字列
    {
        // 真ん中から分割し、前後の 2 つの文字を比較します。すべての対応が等しい場合は回文です。
        ( iPosFlag = 0 ; iPosFlag <   iInputStrLen /2; iPosFlag++)
        {
            if (pszInputStr[iPosFlag] != pszInputStr[iInputStrLen-1-iPosFlag]) // 対応する文字が等しくありません
            {
                printf("%s は回文文字列ではありません!\n", pszInputStr);
                戻る;
            }
        }
    } 
 
    printf("%s は回文文字列です!\n", pszInputStr); 
 
    戻る;
 } 
 
 
 /******************************************************************************************
 * 関数の説明: 入力文字列内の各中国語文字を取得します
* 入力パラメータ: pszInputStr-入力文字列
            iInputStrLen - 入力文字列の長さ
* 出力パラメータ: なし
* 戻り値: なし
* その他の指示: なし
* 変更日 バージョン番号 修正者 変更内容
* -------------------------------------------------------------------
 * 20160222 V1.0 作成者: Zhou Zhaoxiong
 ******************************************************************************/
 void GetChineseChars(INT8 *pszInputStr)
 {
    UINT32 iPosFlag = 0 ; 
     
    if ( NULL == pszInputStr)
    {
        戻る;
    } 
 
    memset(gszStrCharArray, 0x00, sizeof(gszStrCharArray));
 giCharNum = 0 ; 
     
    (iPosFlag <   strlen (pszInputStr))
    {
        snprintf(gszStrCharArray[giCharNum], sizeof(gszStrCharArray[giCharNum])-1, "%c%c", pszInputStr[iPosFlag], pszInputStr[iPosFlag+1]); 
 
 iPosFlag iPosFlag = iPosFlag + 2; // 各漢字は2バイトを占めます
         
        giCharNum++;
    }
 } 
 
 
 /******************************************************************************************
 * 関数の説明: 入力文字列の形式が正しいかどうかを判定する
* 入力パラメータ: pszInputStr-入力文字列
            iStrType - 入力文字列の型
* 出力パラメータ: なし
* 戻り値: 0 - 正しい形式 その他 - 不正な形式
* その他の指示: なし
* 変更日 バージョン番号 修正者 変更内容
* -------------------------------------------------------------------
 * 20160222 V1.0 作成者: Zhou Zhaoxiong
 ******************************************************************************/
 INT32 判定Strフォーマット(INT8 *pszInputStr、UINT32 iStrType)
 {
    UINT32 iPosFlag = 0 ; 
     
    if ( NULL == pszInputStr)
    {
        -1 を返します。
    } 
 
    if ( iStrType == 1) // まず中国語の文字列を決定する
    {
        ( iPosFlag = 0 ; iPosFlag <   strlen (pszInputStr); iPosFlag++)
        {
            if (pszInputStr[iPosFlag] > = 0) // 0未満でない場合は、中国語以外の文字が含まれていることを意味します
            {
                printf("%s には中国語以外の文字が含まれています。確認してください!\n", pszInputStr);
                -2 を返します。
            }
        }
    }
    else if ( iStrType == 2) // 中国語以外の文字列かどうかをチェックする
    {
        ( iPosFlag = 0 ; iPosFlag <   strlen (pszInputStr); iPosFlag++)
        {
            if (pszInputStr[iPosFlag] <   0 ) // 0未満は中国語の文字が含まれていることを意味します
            {
                printf("%s には中国語の文字が含まれています。確認してください!\n", pszInputStr);
                -3 を返します。
            }
        }
    }
    それ以外
    {
        printf("正しい文字列タイプを入力してください!\n");
        -4 を返します。
    } 
 
    0を返します。
 }

5. プログラムのテスト

記述したプログラム「PalindromicString.c」を Linux マシンにアップロードし、「gcc -g -o PalindromicStringPalindromicString.c」コマンドを使用してプログラムをコンパイルし、「PalindromicString」ファイルを生成します。以下はプログラムの詳細なテストです。

1. 中国語の文字列「人上人」を入力すると、プログラムは次のように実行されます。

文字列の種類を入力してください (1: 中国語文字列、2: 中国語以外の文字列):
 1
文字列を入力してください:
最高の
最高なのは回文文字列です！

2. 中国語の文字列「Who am I」が入力されると、プログラムは次のように実行されます。

文字列の種類を入力してください (1: 中国語文字列、2: 中国語以外の文字列):
 1
文字列を入力してください:
私という人間
「私は誰ですか?」は回文文字列ではありません。

3. 中国語以外の文字列「level」を入力すると、プログラムは次のように実行されます。

文字列の種類を入力してください (1: 中国語文字列、2: 中国語以外の文字列):
 2
文字列を入力してください:
レベル
レベルは回文文字列です!

4. 中国語以外の文字列「good」が入力されると、プログラムは次のように実行されます。

文字列の種類を入力してください (1: 中国語文字列、2: 中国語以外の文字列):
 2
文字列を入力してください:
良い
good は回文文字列ではありません。

5. 入力文字列が「你好good」の場合、プログラムは次のように実行されます。

文字列の種類を入力してください (1: 中国語文字列、2: 中国語以外の文字列):
 1
文字列を入力してください:
こんにちは
Hellogoodには中国語以外の文字がありますので、ご確認ください。

6. 入力文字列が「good」の場合、プログラムは次のように実行されます。

文字列の種類を入力してください (1: 中国語文字列、2: 中国語以外の文字列):
 2
文字列を入力してください:
良い
「good好」には漢字がありますので、確認してください。

7. 入力文字列の型が 1 または 2 でない場合、プログラムは次のように実行されます。

文字列の種類を入力してください (1: 中国語文字列、2: 中国語以外の文字列):
 3
文字列を入力してください:
グーグ
正しい文字列タイプを入力してください。

プログラムは、上で検討したいくつかの特殊なケースを正しく処理できることがわかります。

6. 需要拡大

この記事の要件と手順に基づいて、要件の次の拡張を検討できます。

1. 入力文字列は、中国語文字列または非中国語文字列のみに限定されず、中国語文字と非中国語文字の混合文字列にすることもできます。

2. 入力文字列が中国語以外の文字列の場合、文字列内の文字数は偶数でなければなりません。つまり、「goog」のような文字列は回文ですが、「level」のような文字列は回文ではありません。

[この記事は51CTOコラムニストの周兆雄氏によるオリジナル記事です。著者のWeChat公開アカウント：周の論理（logiczhou）]

この著者の他の記事を読むにはここをクリックしてください