注册 登录
编程论坛 数据结构与算法

设计一个算法,使用顺序栈,实现键盘输入字符序列逆置输出的算法设计。请问为什么字符串中有空格,就输出不正确?

Queenlight 发布于 2017-10-17 15:47, 3410 次点击
#include <iostream>
#include <cstdlib>
using namespace std;

const int MAXLISTSIZE = 100;
const int STACKINCREMENT = 10;

template<class ElemType>
class SqStack
{
private:
    ElemType *base;   //栈尾指针
    ElemType *top;   // 栈顶指针
    int maxSize;        // 允许的最大存储容量(以sizeof(ElemType)为单位
public:
    SqStack(int ms = 0);
    ~SqStack()
    {
        StackDestroy();
    }
    bool StackDestroy();
    bool StackClear( );
    int StackLength() const
    {
        return top - base;
    }
    bool SetListLength(int len);
    bool StackisEmpty() const
    {
        return top == base;
    }
    bool StackFull() const;
    bool GetTop(ElemType &e) const;
    bool push(ElemType &e);
    bool pop(ElemType &e);
    void StackTraverse() const;
    bool DoubleSpace();
};
//初始化
template<class ElemType>
SqStack<ElemType>::SqStack(int ms)
{
    if(ms == 0) maxSize = MAXLISTSIZE;
    base = new ElemType[maxSize];
    if(!base) exit(1);
    maxSize = ms;
    top = base;
}
//销毁
template<class ElemType>
bool SqStack<ElemType>::StackDestroy()
{
    if(!base) return false;
    free(base);
    base = top = NULL;
    maxSize = 0;
    return true;
}
//空表
template<class ElemType>
bool SqStack<ElemType>::StackClear( )
{
    if(!base) return false;
    top = base;
    return true;
}
//设置长度
template<class ElemType>
bool SqStack<ElemType>::SetListLength(int len)
{
    if(len < 0||len > MAXLISTSIZE) return false;
    maxSize = len;
    return true;
}
//满栈
template<class ElemType>
bool SqStack<ElemType>::StackFull() const
{
    if(maxSize < MAXLISTSIZE) return false;
    return true;
}
//返回栈顶元素
template<class ElemType>
bool SqStack<ElemType>::GetTop(ElemType &e) const
{
    if(base == top) return false;
    e = *(top-1);
    return true;
}
//入栈
template<class ElemType>
bool SqStack<ElemType>::push(ElemType &e)
{
    if(top - base >= maxSize)
    {
        base = new ElemType[maxSize+STACKINCREMENT];
        if(!base) exit(1);
        top = base + maxSize;
        maxSize += STACKINCREMENT;
    }
    *(top++) = e;
    return true;
}
//出栈
template<class ElemType>
bool SqStack<ElemType>::pop(ElemType &e)
{
    if(base == top) return false;
    e = *(--top);
    return true;
}
//遍历
template<class ElemType>
void SqStack<ElemType>::StackTraverse() const
{
    ElemType *p = top;
    while(p > base)
    {
        cout << *(--p);
    }
    cout << endl;
}
//空间加倍
template<class ElemType>
bool SqStack<ElemType>::DoubleSpace()
{
    if(base == top) return false;
    base = new ElemType[2*maxSize];
    maxSize *= 2;
    return true;
}

template<class ElemType>
void Invert_Input( SqStack<ElemType> &S )
{
    string str;
    getline(cin, str);
    int n = str.length();
    for(int i = 0; i < n; i++)
    {
        S.push(str[i]);
    }
    S.SetListLength(n);
    S.StackTraverse();
}

int main()
{
    SqStack<char> S;
    Invert_Input(S);
    return 0;
}
1 回复
#2
xzlxzlxzl2017-10-19 21:09
调试时没有看到“getline”,显示error C3861: “getline”: 找不到标识符。
使用替代调试法,经运行,没发现字符串中有空格就不正确的bug,我反正不管怎么加空格都能正常逆序,将“const int STACKINCREMENT = 10;”修改为“const int STACKINCREMENT = 30;”,可以操作较长的字符串。
1