顺序栈ADT模板简单应用算法设计：回文判断_顺序栈adt模板简单应用算法设计:回文判断 时间限制: 1s 类别: ds:栈->栈定义及应

问题描述 :

• 目的：使用C++模板设计顺序栈的抽象数据类型（ADT）。并在此基础上，使用顺序栈ADT的基本操作，设计并实现简单应用的算法设计。

• 内容：

  • （1）请参照顺序表的ADT模板，设计顺序栈的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件，以及网盘中的顺序表ADT原型文件，自行设计顺序栈的ADT。）

  • （2）ADT的简单应用：使用该ADT设计并实现若干应用顺序栈的算法设计。

• 应用：正读与反读都相同的字符序列称为“回文”序列。请使用顺序栈，设计并实现一个算法，判断依次读入的一个以@为结束符的字符序列是否为形如’序列1&序列2’模式的字符序列。其中序列1和序列2中都不含有字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属于该模式的字符序列，而‘1+3&3-1’则不是。

参考函数原型：

template<class ElemType>

bool parlindrome_judge( SqStack<ElemType> &S );
1
2
3

输入说明 :

第一行：以@为结束符的字符序列

输出说明 :

第一行：true（回文）

false（不是回文）

输入范例 :

a+b&b+a@
1

输出范例 :

true

Don
1
2
3

题目分析

• 以“&”为两个字符的连接符
• 以@结束符
• 直接遍历字符串，将所有的字符都入栈，直到遇到&，然后在出栈，和&之后的字符在一个一个比较

实现源码

bool parlindrome_judge( SqStack<ElemType> &S )
{
	//去除结束符号@
    S.pop(middle);
	
	//转移栈内一半的数据
    while(S.GetTop(top) && top != '&')
    {
        S.pop(middle);
        temp.push(middle);
    }
    //去掉中间的连接符&
    S.pop(middle); 

	//开始比较
    while(!S.StackisEmpty())
    {
        S.pop(middle);
        temp.pop(top);
        if(middle != top)
        {
            cout<<"false"<<endl;
            return false;
        }
    }

	//一个为空，一个不为空
    if(!temp.StackisEmpty())
    {
        cout<<"false"<<endl;
        return false;
    }
    else
    {
    	//两个同时为空
        cout<<"true"<<endl;
        return true;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

事故现场

第一次提交

• 应该是一个正确的样例，一个错误的样例，这里应该室错误的样例没检测出来，自己拟一个。
• 1+1&1-1@

• 测试之下，发现了一个小问题

• 调用栈的时候应该是引用传递，否则仅仅只是值的复制，并不会影响到外面的数字

第二次提交

分析与总结

• 问题很简单，但是小问题不断，总是在一些细节出问题，当栈为函数的参数，要用引用传递，不然没有任何变化

希望多多分享，若有不妥之处，可加鄙人的扣扣651378276，一同商量解决