回文

回文是指正讀反讀均相同的字符序列,如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個(gè)算法判定給定的字符序列是否為回文。（提示：將一半字符入棧。）

所需的知識(shí)前提：棧

以下是順序棧的基本算法
結(jié)構(gòu)表示，初始化，銷毀棧，入棧，出棧，得到棧頂元素，判斷棧是否為空等算法。

#include<stdio.h> #include<bits/stdc++.h> using namespace std; #include<malloc.h> #include<string>typedef int Status; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0// ------棧的順序存儲(chǔ)結(jié)構(gòu)表示---------- #define STACK_INIT_SIZE 100 // 存儲(chǔ)空間初始分配量 #define STACK_INCREMENT 10 // 存儲(chǔ)空間分配增量 typedef char ElemType; typedef struct {ElemType *base; // 棧底指針ElemType *top; // 棧頂指針int stacksize; // 棧空間大小 } SqStack;void InitStack(SqStack &S) {// 構(gòu)造一個(gè)空棧Sif(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType))))exit(OVERFLOW); // 存儲(chǔ)分配失敗S.top = S.base;S.stacksize = STACK_INIT_SIZE; }void DestroyStack(SqStack &S) {// 銷毀棧S，S不再存在free(S.base);S.base = NULL;S.top = NULL;S.stacksize = 0; }void Push(SqStack &S, ElemType e) {if(S.top - S.base >= S.stacksize) { // 棧滿，追加存儲(chǔ)空間S.base = (ElemType *)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(ElemType));if(!S.base)exit(OVERFLOW); // 存儲(chǔ)分配失敗S.top = S.base + S.stacksize;S.stacksize += STACK_INCREMENT;}*(S.top)++ = e; }Status Pop(SqStack &S, ElemType &e) {// 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；// 否則返回ERRORif(S.top == S.base)return ERROR;e = *--S.top;return OK; }Status GetTop(SqStack S, ElemType &e) {// 若棧不空，則用e返回S的棧頂元素，并返回OK；// 否則返回ERRORif(S.top > S.base) {e = *(S.top - 1);return OK;}elsereturn ERROR; }Status StackEmpty(SqStack S) {// 若棧S為空棧，則返回TRUE，否則返回FALSEif(S.top == S.base)return TRUE;elsereturn FALSE; }

接下來(lái)是判斷回文的關(guān)鍵算法
參數(shù)：傳入函數(shù)的字符串的首地址和字符串的長(zhǎng)度
//思路
將字符串的每個(gè)字符一一入st棧
因?yàn)闂５奶攸c(diǎn)：后進(jìn)先出 LIFO（last in first out）
所以字符串的字符全部入棧后，與原來(lái)的字符串逆序
因此僅需要將棧中的數(shù)據(jù)一一出棧與原來(lái)次序字符串的字符一一對(duì)比：
若出現(xiàn)不相同的狀況，即返回不是回文。
若字符串的比較過(guò)半（或全部進(jìn)行完）時(shí)，返回是回文。

int Palindrome(char str[], int n) { SqStack st; //定義一個(gè)順序棧stInitStack(st); //棧初始化int i;char ch; for (i=0;i<n;i++) //所有字符依次進(jìn)棧Push(st,str[i]); i=0; //從頭開(kāi)始遍歷str while (!StackEmpty(st)) //棧不空循環(huán) { Pop(st,ch); //出棧元素chif (ch!=str[i++]) //兩字符不相同時(shí)返回0return 0; }return 1; //所有相應(yīng)字符都相同時(shí)返回1 }

下面是關(guān)于回文問(wèn)題的全部代碼（可直接運(yùn)行）

#include<stdio.h> #include<bits/stdc++.h> using namespace std; #include<malloc.h> #include<string>typedef int Status; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0// ------棧的順序存儲(chǔ)結(jié)構(gòu)表示---------- #define STACK_INIT_SIZE 100 // 存儲(chǔ)空間初始分配量 #define STACK_INCREMENT 10 // 存儲(chǔ)空間分配增量 typedef char ElemType; typedef struct {ElemType *base; // 棧底指針ElemType *top; // 棧頂指針int stacksize; // 棧空間大小 } SqStack;void InitStack(SqStack &S) {// 構(gòu)造一個(gè)空棧Sif(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType))))exit(OVERFLOW); // 存儲(chǔ)分配失敗S.top = S.base;S.stacksize = STACK_INIT_SIZE; }void DestroyStack(SqStack &S) {// 銷毀棧S，S不再存在free(S.base);S.base = NULL;S.top = NULL;S.stacksize = 0; }void Push(SqStack &S, ElemType e) {if(S.top - S.base >= S.stacksize) { // 棧滿，追加存儲(chǔ)空間S.base = (ElemType *)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(ElemType));if(!S.base)exit(OVERFLOW); // 存儲(chǔ)分配失敗S.top = S.base + S.stacksize;S.stacksize += STACK_INCREMENT;}*(S.top)++ = e; }Status Pop(SqStack &S, ElemType &e) {// 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；// 否則返回ERRORif(S.top == S.base)return ERROR;e = *--S.top;return OK; }Status GetTop(SqStack S, ElemType &e) {// 若棧不空，則用e返回S的棧頂元素，并返回OK；// 否則返回ERRORif(S.top > S.base) {e = *(S.top - 1);return OK;}elsereturn ERROR; }Status StackEmpty(SqStack S) {// 若棧S為空棧，則返回TRUE，否則返回FALSEif(S.top == S.base)return TRUE;elsereturn FALSE; }int Palindrome(char str[], int n) { SqStack st; //定義一個(gè)順序棧stInitStack(st); //棧初始化int i;char ch; for (i=0;i<n;i++) //所有字符依次進(jìn)棧Push(st,str[i]); i=0; //從頭開(kāi)始遍歷str while (!StackEmpty(st)) //棧不空循環(huán) { Pop(st,ch); //出棧元素chif (ch!=str[i++]) //兩字符不相同時(shí)返回0return 0; }return 1; //所有相應(yīng)字符都相同時(shí)返回1 }int main() {char str[100];printf("輸入一個(gè)字符串:"); gets(str);int len=strlen(str);;if(Palindrome(str, len)==1) printf("是回文\n");else printf("不是回文\n");return 0; }

運(yùn)行的例子

總結(jié)

以上是生活随笔為你收集整理的数据结构——用栈解决回文字符问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。