数据结构实验：回文判断_数据结构回文判断编程

一、实验目的

通过该实验，掌握栈的相关基本概念，认识栈是插入和删除集中在一端进行的线性结构，掌握栈的“先入后出”操作特点。

栈在进行各类操作时，栈底指针固定不动，掌握栈空、栈满的判断条件。

二、实验题目

（一）二选一

①建立一个顺序栈，实现进栈、出栈操作。

②建立一个链队列，实现入队、出队操作。

（二）回文判断

回文，指正读和反读都相同的字符序列，称为“回文”序列。

从键盘以此读入一个以@为结束符的字符序列，判断此序列是否为形如“序列1 & 序列2”模式的字符序列。其中序列1和序列2中都不含字符“&”，而且序列2是序列1的逆序列。例如，字符序列“a+b&b+a”是属于该模式的序列，而“1+3&3-1”则不是回文。

要求设计一个程序，利用栈或者队列模拟此过程，判断输入的字符序列是否为回文，并将判断结果输出。

三、问题分析

1.数据分析

定义栈Stack用作存放输入的字符

定义存放输入字符栈的栈s

定义输入的字符为ch

当字符从栈中弹出时，使用temp暂存

2.运算分析

预处理指令：初始化栈、入栈、出栈、判断栈是否为空

InitStack(&s)-初始化栈s

getchar单个输入字符

当ch不为字符&时，压入栈s，循环输入字符

3.主要算法分析

当ch不为字符@并且栈s不为空时，将&后输入的字符与之前压入栈中的字符依次循环判断是否对应相等

如果&后新输入的字符与栈s弹出的字符不依次对应相等，输出序列1与序列2不相同，返回FALSE*

栈为空时并且输入的下一个字符为@时，说明序列1与序列2相同，反之不同

4.测试数据分析

字符序列“a+b&b+a”是属于该模式的序列，而“1+3&3-1”则不是回文

四、源程序

#include <stdio.h>
 
#define TRUE 1
 
#define FALSE 0
 
 
 
typedef struct {
 
    char elem[100];
 
    int top;
 
}Stack;
 
 
 
void InitStack(Stack* s);
 
int Push(Stack* s, char e);
 
int Pop(Stack* s, char* x);
 
int IsEmpty(Stack* s);
 
 
 
int main() {
 
    Stack s;
 
    char ch;
 
    char temp;
 
    InitStack(&s);
 
    printf("\n请输入以@为结尾的字符序列：");
 
    ch = getchar();
 
    while (ch != '&') {
 
        Push(&s, ch);
 
        ch = getchar();
 
    }
 
    do {
 
        ch = getchar();
 
        Pop(&s, &temp); 
 
        if (ch != temp) {
 
            printf("\n序列1与序列2不相同");
 
             return(FALSE);
 
        }
 
    } while (ch != '@' && !IsEmpty(&s));
 
    ch = getchar();
 
    if (ch == '@' && IsEmpty(&s)) {
 
        printf("\n序列1与序列2相同");
 
        return(TRUE);
 
    }
 
    else {
 
        printf("\n序列1与序列2不相同");
 
        return(FALSE);
 
    }
 
}
 
 
 
void InitStack(Stack* s) {
 
    s->top = -1;
 
}
 
 
 
int Push(Stack* s, char e) {
 
    if (s->top != 99) {
 
        (s->top)++;
 
        s->elem[s->top] = e;
 
    }
 
    else
 
        return (FALSE);
 
}
 
 
 
int Pop(Stack* s, char* x) {
 
    if (s->top != -1) {
 
        *x = s->elem[s->top];
 
        s->top--;
 
        return(TRUE);
 
    }
 
    else
 
        return(FALSE);
 
}
 
 
 
int IsEmpty(Stack* s) {
 
    if (s->top == -1)
 
        return(TRUE);
 
    return(FALSE);
 
}

五、运行结果及分析

字符序列“a+b&b+a”形如“序列1 & 序列2，而“1+3&3-1”则不是回文