数据结构（第2版）（C语言实现）课件：栈和队列.pptx

栈和队列;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;3.1栈的表示与实现;（5）取栈顶元素。

intGetTop(LinkStacktop,DataType*e)

/*取栈顶元素。取栈顶元素成功返回1，否则返回0*/

{

LStackNode*p;

p=top-next; /*指针p指向栈顶结点*/

if(!p)/*如果栈为空*/

{

printf(“栈已空”);

return0;

}

*e=p-data; /*将p指向的结点元素赋值给e*/

return1;

};3.1栈的表示与实现;3.1栈的表示与实现;3.1.1数制转换

【例3.1】利用栈的基本操作实现将十进制数1568转换为对应的八进制数。

【分析】进制转换是计算机实现计算的基本问题。根据我们掌握的C语言知识，我们可以采用辗转相除法实现将十进制数转换为八进制数。将1568转换为八进制数的过程如图所示。;转换后的八进制数为(1568)8。每次不断利用被除数除以8得到商数后，记下余数，又将商数作为新的被除数继续除以8，直到商数为0为止，把得到的余数排列起来就是转换后的八进制数。依据此原理，得到十进制数N转换为八进制的算法如下：

（1）将N除以8，记下其余数；

（2）判断商是否为零，如果为零，结束程序；否则，将商送N，转到（1）继续执行。

得到的位序正好与八进制数的位序相反，这恰好可利用栈的“后进先出”特性，先把得到的余数序列放入栈保存，最后依次出栈得到八进制数。;;3.2.2行编辑程序

试利用栈的“后进先出”思想，编写一个行编辑程序，前一个字符输入有误时，输入’#’消除???当输入的一行有误时，输入’@’消除当前行的字符序列。

voidLineEdit()

{

SeqStackS;charch;

DataTypee;DataTypea[50];

inti,j=0;

InitStack(S);

printf(输入字符序列(‘#’使前一个字符无效，’@’使当前行的字符无效).\n);

ch=getchar();

while(ch!=\n)

{

;3.2栈的应用;3.2.3求算术表达式的值

表达式求值是程序设计编译中的基本问题，它的实现是栈应用的一个典型例子。本节给大家介绍一种简单并广为使用的算法，被称之为算符优先法。计算机编译系统利用栈的“后进先出”特性把人们便于理解的表达式翻译成计算机能够正确理解的表示序列。

一个算术表达式是由操作数、运算符和分界符组成。为了简化问题，我们假设算术运算符仅由加、减、乘、除四种运算符和左、右圆括号组成。;例如，一个算术表达式为

a-(b+c*d)/e

这种算术表达式中的运算符总是出现在两个操作数之间，这种算术表达式被称为中缀表达式。计算机编译系统在计算一个算术表达式之前，要将中缀表达式转换为后缀表达式，然后对后缀表达式进行计算。后缀表达式就是算术运算符出现在操作数之后，并且不含括号。

计算机在求算术表达式的值时分为两个步骤：

（1）将中缀表达式转换为后缀表达式；

（2）依据后缀表达式计算表达式的值。;1．将中缀表达式转换为后缀表达式

要将一个算术表达式的中缀形式转化为相应的后缀形式，首先了解下算术四则运算的规则。算术