スタックを使ったC言語での回文判定アルゴリズム

1年 ago
海斗, 葵
1 minute

パлиндローム判定アルゴリズムをスタックで実装する手順：

  1. まず、文字を入れるスタック構造体を定義します。
  2. 判断対象の文字列を順次スタックに格納し、文字列の終端まで続ける。
  3. 文字の先頭から順に文字を取り除き、元の文字列に対応する位置の文字と比較する
  4. ポップされた文字が文字列中の対応する位置の文字と等しくない場合、その文字列は回文ではないので、すぐに結果を返してよい
  5. スタックから取り出した文字が、文字列の対応する位置の文字と等しければ、次の比較に進み、スタックが空になるかまたは文字列全体の比較が終わるまで続ける。
  6. スタックが空で文字列全体を比較し終わったら、その文字列は回文である、真を返す。そうでなければ、偽を返す。

スタックを利用した回文判定の実装例を以下に示します。

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 100

// 定义栈结构
typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 入栈
void push(Stack *s, char c) {
    s->data[++(s->top)] = c;
}

// 出栈
char pop(Stack *s) {
    return s->data[(s->top)--];
}

// 判断字符串是否为回文
int isPalindrome(char *str) {
    Stack s;
    initStack(&s);
    int len = strlen(str);
    int i;

    // 将字符串依次入栈
    for (i = 0; i < len; i++) {
        push(&s, str[i]);
    }

    // 逐个字符出栈并比较
    for (i = 0; i < len; i++) {
        if (pop(&s) != str[i]) {
            return 0; // 不是回文
        }
    }

    return 1; // 是回文
}

int main() {
    char str[MAX_SIZE];

    printf("请输入一个字符串：");
    scanf("%s", str);

    if (isPalindrome(str)) {
        printf("%s 是回文\n", str);
    } else {
        printf("%s 不是回文\n", str);
    }

    return 0;
}

このプログラムを実行すると、文字列を入力するよう求められ、その文字列が回文かどうかが判定されます。回文の場合、「回文です」と出力され、そうでない場合は「回文ではありません」と出力されます。

bannerAds