栈和队列的应用之回文数判断-蒲公英云

栈和队列的应用之回文数判断

题目：

采用栈和队列的方法检测并输出一个单词是否为回文。

代码：

#include<stdio.h>
#include<malloc.h>
#define SIZE 20  
using namespace std;
//1.定义顺序栈
typedef struct{
    char c[SIZE];//记录字符
    int top;//栈指针
}Stack;
//初始化栈
void initStack(Stack &S){
    S.top=-1;//初始化指针
}
//入栈
void push(Stack &S,char c){
    S.top++;//指针上移
    S.c[S.top]=c;//存储数据
} 
//出栈
void pop(Stack &S,char &c){
    c=S.c[S.top];
    S.top--;//指针下移 
} 
//2.定义循环队列
typedef struct{
    char *base;
    int front;
    int rear; 
} Queue;
//初始化队列
void initQueue(Queue &Q){
    Q.base=(char *)malloc(SIZE*sizeof(char));//动态分配队列存储空间 
    Q.front=Q.rear=0;//空队列
}
//入队列
void inQueue(Queue &Q,char c){
    Q.base[Q.rear]=c;//存储数据
    Q.rear=(Q.rear+1)%SIZE;//队尾指针后移
}
//出队列
void outQueue(Queue &Q,char &c){
    c=Q.base[Q.front];
    Q.front=(Q.front+1)%SIZE;//队头指针后移
}
//3.偶数个字符比较 
bool evenNumbers(Stack &S,Queue &Q,char &c){
    while(emptyStack(S)&&emptyQueue(Q)){
        if(S.c[S.top]!=Q.base[Q.front]){
            printf("不是回文！\n");
            return false;//返回false，结束循环 
        }else{
            pop(S,c);//出栈
            outQueue(Q,c);//出队列
        }
    }
    return true;
}
//主函数
int main(){
    Stack S;
    initStack(S);
    //定义、初始化循环队列 
    Queue Q; 
    initQueue(Q);
    char c;
    int count=0;
    printf("请输入单词,长度小于20: ");
    while((c=getchar())!='\n') { //循环读取字符并判断类型，以末尾换行符’\n’结束
        push(S,c);//入顺序栈
        inQueue(Q,c);//入队列 
        count++;
    }
    if(count>2) { 
        bool yes;  
        if(count%2==0){ 
            yes=evenNumbers(S,Q,c);
        }else{  
            yes=oddNumber(S,Q,c,count);
        }
        if(yes){printf("是回文单词！\n");}
    }else{
        printf("***单词字符个数少于3个无法判断是否为 回文***\n");
    }
    return 0;
}

效果图：

思考：

中文回文如何判断呢？废话不多说，直接上代码：

代码：

#include <iostream>
#include <string.h>
using namespace std;
struct Stack{
    char data[100];
    int top;
};
int Test(Stack L,int lens,string a){
    int n;
    int x = lens/2;
    if(x%2 == 1){
        for(int i=0;i<lens/2-1;i++){
            L.data[L.top] = a[i];
            L.top++;
        }
    }else{
        for(int i=0;i<lens/2;i++){
            L.data[L.top] = a[i];
            L.top++;
        }
    }
    return 1;
}
int main(int argc, char **argv) {
    printf("请输入中文语句：\n");
    char str[100];
    gets(str);
    int lens = strlen(str);
    Stack L;
    L.top = 0;
    if(Test(L,lens,str)){
        printf("%s 是回文",str);
    }else{
        printf("%s 不是回文",str);
    }
    return 0;
}

效果图：

提高篇：

采用栈和队列方法编程实现统计一篇文档中的所有出现的回文单词。（这里小编建议采用文件的形式读入）

代码：

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
//队列
typedef char QElemType;
typedef struct {
    QElemType *base;    //指向动态分配的数组中的元素
    int front;
    int rear;
}SqQueue;
//栈
#define MaxSize 200
typedef struct {
    char data[MaxSize];
    int top;
}Stack;
//队列
void InitQueue(SqQueue &Q){
    //构造一个空队列Q
    Q.base = (QElemType *)malloc(sizeof(QElemType)*MaxSize); 
    if(!Q.base) exit(1);   //验证，Q不为空，返回1
    Q.front = Q.rear = 0;
}
void EnQueue(SqQueue &Q, QElemType e){
    //插入的元素e为Q的新的队尾元素
    if((Q.rear+1) % MaxSize == Q.front) exit(1);
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MaxSize;
}
int DeQueue(SqQueue &Q, char &i) {
    //若队列不空，则删除Q的队头元素,并用i接收队头元素
    if(Q.front == Q.rear)
        exit(1);
    i = Q.base[Q.front];
    Q.front = (Q.front+1) % MaxSize;
}
//栈
void InitStack(Stack &stack){
    stack.top = -1;
}
int push(Stack &S, char x) /*将x置入S栈新栈顶*/
{
    if(S.top == MaxSize -1)
        return false;
    else{
        S.top++;
        S.data[S.top]=x;
        return true;
    }
}
int pop(Stack &S, char &x)  /*将栈S的栈顶元素弹出，放到x中*/
{
    if(S.top==-1)
        return false;
    else{
        x = S.data[S.top];
        S.top--;
        return true;
    }
}
int compare(char a, char b){
    if (a == b) return 0;
    else return 1;
}