数据结构之-链式栈及其常见应用（进制转换、括号匹配、行编辑程
1、栈的概念栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。总的来说就是LIFO(Last In First Out)； 代码：#pragma once /* *Copyright? 中国地质大学（武汉） 信息工程学院 *All right reserved. * *文件名称：Stack.h *摘 要：编写栈算法 * *当前版本：1.0 *作 者：邵玉胜 *完成日期：2018-12-28 */ #ifndef STACK_H_ #define STACK_H_ #include //结点结构体,双向栈 template struct StackNode { T _tData; //数据域 StackNode StackNode StackNode(StackNode StackNode this->_pNext = nullptr; this->_pLast = nullptr; } StackNode(T data,StackNode StackNode this->_tData = data; this->_pNext = next; this->_pLast = last; } }; template class Stack { private: StackNode StackNode int _iConuntOfElement; //结点数量 public: Stack(); //构造函数 Stack(Stack ~Stack(); //析构函数 bool IsEmpty(); //判断栈是否为空 void MakeEmpty(); //将栈中的元素全部删除 void Put(const T data); //顶端插入数据 int Size() { return _iConuntOfElement; } //返回栈中的结点数 void GetTop(T& data); //获取顶端结点 void Pop(T& data); //顶端弹出结点，并将元素传至参数中 void Traverse(); //逆序栈中的结点 void DisPlay(bool forward = true); //输出函数,默认正向输出 }; //构造函数，为栈顶和栈底分配内存 template Stack _pTop = _pBottom = nullptr; this->_iConuntOfElement = 0; } //拷贝构造函数 //缺少此函数，在传参与析构的时候容易出问题 template Stack StackNode while (pCur) { //遍历本对象的结点 T data = pCur->_tData; //依此取出结点值 copy.Put(data); //插入到copy栈中 pCur = pCur->_pNext; } } //析构函数 template Stack MakeEmpty(); //释放结点内存 this->_pTop = this->_pBottom = nullptr; //将指针指向空，避免出现野指针 } //判断栈是否为空 template bool Stack if (!this->_pTop) //如果栈对象没有头节点，那么栈就为空 return true; return false; } //将栈中的元素全部删除 template void Stack StackNode while (_pTop) { //循环依此从顶端删除 pDel = this->_pTop; this->_pTop = _pTop->_pNext; delete pDel; } _iConuntOfElement = 0; //栈结点数量置零 } //顶端插入数据 template void Stack StackNode if (!newData) { //如果内存分配错误 std::cerr << "内存分配错误！" << std::endl; exit(-1); } if (this->IsEmpty()) { //如果插入的是第一个结点 newData->_pLast = nullptr; //将这个结点的指向上一下一结点的指针都赋空值 newData->_pNext = nullptr; this->_pTop = newData; //将栈顶和栈底指针都指向这个结点 this->_pBottom = newData; ++this->_iConuntOfElement; //节点数加1 return; } this->_pTop->_pLast = newData; //栈顶的上一结点指针指向新结点 newData->_pNext = this->_pTop; //将新结点的下一结点指针指向栈顶 this->_pTop = newData; //新结点作为栈顶 ++this->_iConuntOfElement; } //获取顶端结点 template void Stack if (this->IsEmpty()) //栈为空，直接返回 return; data = this->_pTop->_tData; //获取栈顶元素，赋值给返回参数 return; } //顶端弹出元素，并将元素传至参数中 template void Stack if (this->IsEmpty()) //栈为空，直接返回 return; data = this->_pTop->_tData; //先取出栈顶的值 StackNode if (this->_pTop->_pNext) { //如果有后继结点，就将后继结点的上一个指针指向空 this->_pTop->_pNext->_pLast = nullptr; this->_pTop = this->_pTop->_pNext; delete pDel; //释放原栈顶内存 --this->_iConuntOfElement; //栈结点数量递减 return; } delete pDel; //如果就只有一个结点，直接释放原栈顶的空间 this->_pTop = this->_pBottom = nullptr; //没有后继结点，释放栈顶空间，将指针指向空，避免出现野指针 --this->_iConuntOfElement; //栈结点数量递减 return; } //逆序栈中的结点 template void Stack StackNode StackNode while (pCur) { //循环将栈中结点的前驱与后继指针对调 pTmp = pCur->_pLast; pCur->_pLast = pCur->_pNext; pCur->_pNext = pTmp; pCur = pCur->_pLast; //这个是很值得细细品味的 } //将栈顶与栈顶指针对调 pTmp = this->_pTop; this->_pTop = this->_pBottom; this->_pBottom = pTmp; return; } //输出函数 template void Stack StackNode if(forward == true) pCur = this->_pTop; else pCur = this->_pBottom; while (pCur) { //如果当前指针不为空，就一直循环遍历 std::cout << pCur->_tData; //为了照顾 //if (iCount % 10 == 0) //每隔十个换一行，以免输出的太长 // std::cout << std::endl; if (forward == true) pCur = pCur->_pNext; else pCur = pCur->_pLast; } std::cout << std::endl; } #endif // !STACK_H_ 由于栈的后进先出的特性，使得栈有很多的应用，下面就一一举例： 2、栈的应用之-数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理： ? ? ? ? ? ? ? ? ? ? N = (N div d) * d + N mod d(其中：div为整除运算，mod为求余运算) 例如：将十进制的121转化为二进制的过程为： 代码：//进制转换函数 //十进制转换为其他低进制，如二进制，八进制,默认是二进制 //注意这个函数仅适用于整数 void DecConvert(Stack const int decimal,const int radix) { if (radix < 2 && radix > 10) { //先判断参数合不合理 std::cout << "进制转换函数参数不合理！" << std::endl; return; } result.MakeEmpty(); //先将用于结果返回的栈参数置空 int iQuotient = decimal; //商 int iRemainder; //余数 while (iQuotient) { //商为0的时候结束循环 iRemainder = iQuotient % radix; //求余 result.Put(iRemainder); //将余数装入结果的栈中 iQuotient /= radix; //求商 } } 3、栈的应用之-括号匹配假设表达式中包含三种括号：圆括号、方括号和花括号，并且它们可以任意嵌套。例如{[()]()[{}]}或[{()}([])]等为正确格式，而{[}()]或[({)]为不正确的格式。那么怎么检测表达式是否正确呢？ 这个问题可以用“期待的急迫程度”这个概念来描述。对表达式中的每一个左括号都期待一个相应的右括号与之匹配，表达式中越迟出现并且没有得到匹配的左括号期待匹配的程度越高。不是期待出现的右括号则是不正确的。它具有天然的后进先出的特点。 于是我们可以设计算法：算法需要一个栈，在读入字符的过程中，如果是左括号，则直接入栈，等待相匹配的同类右括号；如果是右括号，且与当前栈顶左括号匹配，则将栈顶左括号出栈，如果不匹配则属于不合法的情况。另外，如果碰到一个右括号，而堆栈为空，说明没有左括号与之匹配，则非法。那么，当字符读完的时候，如果是表达式合法，栈应该是空的，如果栈非空，那么则说明存在左括号没有相应的右括号与之匹配，也是非法的情况。 代码：//括号匹配函数 //注意此处的括号匹配使用的时英文括号 //检验括号是否匹配，该方法使用“期待的紧迫程度”这个概念来描述的 //可能出现不匹配的情况 //1、到来的有括弧非是所“期待”的 //2、到来的是不速之客（左括弧多了） //3、直到结束也没有到来所“期待”的 //设计思想：1、凡是出现左括弧就让他进栈 //2、若出现右括弧，则检查栈是否为空，若为空，就表明右括弧多了 //否则和栈顶元素匹配，匹配成果，则左括弧出栈，否则，匹配失败！ //3、表达式检验结束时，检查栈是否为空，不为空，说明左括号多了 void ParMatching(std::string str) { //先定义一些括号常量 const char LCURVES = '('; const char RCURVES = ')'; const char LBRAKET = '['; const char RBRAKET = ']'; const char LBRACE = '{'; const char RBRACE = '}'; Stack char chPop; //保存弹出的括号 for (int i = 0; i < str.length(); i++) { switch (str[i]) { case LCURVES: //凡是出现左括弧就让他进栈 case LBRAKET: case LBRACE: stackMatch.Put(str[i]); break; case RCURVES: //若出现右括弧 if (!stackMatch.IsEmpty()) { //则检查栈是否为空,否则和栈顶元素匹配 stackMatch.GetTop(chPop); if (chPop == LCURVES) { //匹配成果，则左括弧出栈 stackMatch.Pop(chPop); std::cout << "()匹配成功！n"; break; } } std::cout << ")匹配失败！n"; //否则，就表明右括弧多了 break; case RBRAKET: if (!stackMatch.IsEmpty()) { stackMatch.GetTop(chPop); if (chPop == LBRAKET) { stackMatch.Pop(chPop); //弹出 std::cout << "[]匹配成功！n"; break; } } std::cout << "]匹配失败！n"; break; case RBRACE: if (!stackMatch.IsEmpty()) { stackMatch.GetTop(chPop); if (chPop == LBRACE) { stackMatch.Pop(chPop); //弹出 std::cout << "{}匹配成功！n"; break; } } std::cout << "}匹配失败！n"; break; default: break; } } //将栈中没有匹配的左括号给弹出来 for (int i = 0; i < stackMatch.Size(); i++) { stackMatch.Pop(chPop); std::cout << chPop << "匹配失败！n"; } return; } 4、栈的应用之-行编辑程序一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，因此，若在行编辑程序中“每接受一个字符即存入用户区”的做法显然是不恰当的。 较好的做法是，设立一个输入缓冲区，用以接收用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错， 并在发现有误时及时改正。 例如：当用户发现刚刚建入的一个字符是错的时，可补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以输入一个退格符“@”，以表示当前行中的字符均无效。例如，假设从终端接受了这两行字符： whil##ilr#e(s#*s) ?? ?outcha@putchar(*s=#++) 则实际有效的是下列两行： while(*s) ??? putchar(*s++) 代码：//行编辑程序问题 //设立一个输入缓冲区，用以接受用户输入的一行字符， //然后逐行存入用户数据区。允许用户输入出差错，并在发现的时候可以及时改正。 //例如，当用户刚刚键入的一个字符是错误的时候，可以补进一个退格符“#”， //以表示前一个字符无效；如果发现当前键入的行内差错比较多或难以补救， //则可以键入一个退行符“@”,以表示当前行中的字符均无效。 void LineEditing() { Stack char chInput; //接收输入的字符 char chTmp; //临时字符变量，用于保存弹出的字符 chInput = getchar(); //获取输入的字符 while (chInput != EOF) { //EOF为全文结束符，遇到他则不在等待输入，ctrl+Z stackResult.MakeEmpty(); while (chInput != EOF && chInput != 'n') { //如果没有输入回车和全文结束符 switch (chInput) { case '#': //输错一个字符 stackResult.Pop(chTmp); //弹出这个字符 break; case '@': //输出一行字符 stackResult.MakeEmpty(); //情况栈 break; default: stackResult.Put(chInput); break; } chInput = getchar(); } stackResult.DisPlay(false); chInput = getchar(); } } 5、栈的应用之表达式求值表达式求值可以认为是栈的典型应用之一了，如果想弄明白表达式求值的方法这里一两句是介绍不清楚的，主要需要了解表达式三种表示方法（中缀、前缀、后缀）以及为什么要选后缀最为最后参与运算的表示方式（读者可以自行了解，这里不做介绍）。既然是用后缀作为周会残云运算的表示方式，而我们平时使用的右采用的中缀表达式，因此，欲求中缀表达式的值，需要将中缀表达式的值转换为后缀表达式，我将主要的参考代码放下下面，里面由较为详细的注释说明。 代码：//辅助函数：运算符优先级函数，返回符号的优先级（+-x/()六种） int OperatorPriority(char chOperator) { int result; switch (chOperator) { case '(': //左括号的优先级最大为6 result = 6; break; case ')': //右括号的优先级最小，为1 result = 1; break; case '+': //+-的优先级为2 case '-': result = 2; break; case '*': //乘除的优先级为3 case '/': result = 3; break; case '#': //栈底放一个‘#’方便运算，比所有运算符都笑 result = 0; break; default: result = -1; //如果是除了数字与上诉运算符的其他字符，就默认返回-1 break; } return result; } //1、先将原表达式变成后缀表达式 //2、在利用栈将后缀表达式求值 float ExpressionEvaluating(std::string strExpression) { Stack Stack Stack char chTopOfStack; //运算符栈的顶端操作符 float fReault; //保存结果 stkChOperator.Put('#'); //往栈底放入‘#’,其比任何运算符的优先级都小 for (int i = 0; i < strExpression.length(); i++) {//对字符串中的字符进行分析 char chRead = strExpression[i]; if (chRead >= '0' && chRead <= '9') //如果读出的是数字，直接放到后缀栈 stkChPostfix.Put(chRead); else //读出的是其他字符的话 { if (OperatorPriority(chRead) == -1) {//如果读出的不是数字，也不是操作符 std::cerr << "表达式有误！n"; exit(-1); } while (true) { stkChOperator.GetTop(chTopOfStack); if (OperatorPriority(chTopOfStack) >= OperatorPriority(chRead)) { stkChOperator.Pop(chTopOfStack); //弹出顶端操作符 if (chTopOfStack != '(') //'('是不入后缀表达式的栈的 stkChPostfix.Put(chTopOfStack); //向后缀表达式的栈读入运算符栈顶端操作符 } else break; } if (chRead != ')') //')'也是不吐后缀表达式的栈的 stkChOperator.Put(chRead); //向运算符栈中装入读取的操作符 } } while (stkChOperator.Size() > 1) { //将操作符栈中的剩余操作符弹出放入后缀表达式 stkChOperator.Pop(chTopOfStack); stkChPostfix.Put(chTopOfStack); } stkChPostfix.Traverse(); //将后缀表达式栈逆序 //开始由后缀表达式计算结果 while (stkChPostfix.Size() > 0) { //一直弹出后缀表达式栈顶值 stkChPostfix.Pop(chTopOfStack); if (chTopOfStack >= '0' && chTopOfStack <= '9') stkReult.Put(float(chTopOfStack) - 48.0); //0-9的ascii码是 48-58 else //如果弹出的是运算结果 { float fFirst; float fSencond; stkReult.Pop(fSencond); stkReult.Pop(fFirst); switch (chTopOfStack) { case '+': stkReult.Put(fFirst + fSencond); break; case '-': stkReult.Put(fFirst - fSencond); break; case '*': stkReult.Put(fFirst * fSencond); break; case '/': stkReult.Put(fFirst / fSencond); break; default: break; } } } stkReult.GetTop(fReault); //获取结果 return fReault; //返回结果 } 此外，本人还利用栈和MFC做了几个简易的计算器，可以实现加减乘除、指数、开方等运算，支持连续输入。有需要的可以自行下载，以供相互交流，计算机的界面如下： 计算器代码下载地址： MFC+栈实现简易计算器 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |