第3章 栈
由于栈是运算受限线性表，因此线性表的存储结构对栈也适用，而线性表有顺序存储和链式存储两种，所以，栈也有顺序存储和链式存储两种。
（1）顺序栈：栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。 （2）顺序栈的描述
#define StackSize 100 //假定栈空间最多为100个元素 typedef char DataType;//假定栈元素的类型为字符类型 typedef struct{
DataType data[StackSize];//栈元素定义 int top;//栈指针定义 }SeqStack; SeqStack *S;// 定义栈S
设S是SeqStack类型的指针变量，则栈顶指针可表示为S-> top；若栈底位置在向量的低端，则S->data[0]是栈底元素，栈顶元素可表示为S->data[S-> top]。
注意：
①有元素x进栈时，需要先将S->top加1，然后再将元素进栈，即依次完成下列操作：++S->top;S->data[S-> top]=x;。
②当栈顶元素做退栈操作后，需要将S->top减1，即完成操作：S->top--;。 ③条件S->top==StackSize-1表示栈满；S->top==-1表示栈空。
④当栈满时，再做进栈运算所产生的空间溢出现象称为上溢。上溢是一种出错状态，应设法避免。
⑤当栈空时，做退栈运算所产生的溢出现象称为下溢。 3、顺序栈上基本运算的算法 ①置栈空
void InitStack（SeqStack *S）{//将顺序栈置空 S->top=-1; }
②判栈空
如果栈S为空，则S->top==-1，此时应该返回1，而关系表达式S->top==-1的值为1；如果栈S为非空，则S->top!=-1，此时应该返回0，而关系表达式S->top==-1的值为0，因此，无论怎样只需返回S->top==-1的值。
int StackEmpty（SeqStack *S）{
return S->top==-1; }
③判栈满
第3章 栈
与判栈空的道理相同，只需返回S->top==StackSize-1。
int StackFull（SeqStack *S）{
return S->top==StackSize-1; }
④进栈
进栈操作需要将栈和进栈元素的值作为函数参数，由于使用栈指针作为函数参数，对栈进行操作，所以进栈函数不需要有返回值；进栈操作时，需要判断是否栈满，当栈不满时，先将栈顶指针加1，再进栈。
int Push（SeqStack *S，DataType x）{
if (StackFull(S))
{puts(\栈满\
S->data[++S->top]=x;//栈顶指针加1后将x入栈 return 1; }
⑤退栈
退栈操作需要将栈指针作为函数参数，并返回栈顶元素的值，所以函数返回值的类型为DataType；退栈操作时，需要判断是否栈空，当栈不空时，先退栈，再将栈顶指针减1，可以先将栈顶元素的值记录下来，然后栈顶指针减1，最后返回记录下来的值，也可以像给出的退栈函数那样来操作。
DataType Pop（SeqStack * S）{
if(StackEmpty(S))
{puts(\栈空\
return S->data[S->top--];//返回栈顶元素并将栈顶指针减1 }
⑥取栈顶元素
取栈顶元素与退栈的区别在于，退栈需要改变栈的状态，而取栈顶元素不需要改变栈的状态。
DataType StackTop（SeqStack *S）{
if(StackEmpty(S))
{puts(\栈空\return S->data[S->top]; }
由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有
第3章 栈
摆脱。
例 元素a1，a2，a3，a4依次进入顺序栈，则下列不可能的出栈序列是 A．a4, a3, a2, a1 B．a3, a2, a4, a1 C．a3, a4, a2, a1 D．a3, a1, a4, a2
分析：对于A，由于元素a1，a2，a3，a4依次进栈，而a4先出栈，说明a1，a2，a3已经入栈，所以出栈顺序只能是a4，a3，a2，a1，因此A是正确的出栈序列；对于B，C，D，由于都是a3先出栈，说明a1，a2已经入栈，所以a1，a2的相对位置一定是不变的，这就是a2一定在a1之前出栈，比较上述三个答案，只有D中的a1出现在a2的前面，这显然是错误的。因此，答案为D。 2.链栈及基本操作的实现
若栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。
由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。链栈如图3.2。 top
? ^ 栈顶 栈底
图3.2 链栈
（1）链栈：栈的链式存储结构称为链栈，它是运算受限的单链表，其插入（2）链栈的描述
和删除操作仅限制在表头位置上进行，栈顶指针就是链表的头指针。
typedef char DataType;//假定栈元素的类型为字符类型 typedef struct stacknode{//结点的描述
DataType data; struct stacknode *next; }StackNode;
typedef struct{//栈的描述
StackNode *top; //栈顶指针 }LinkStack;
LinkStack *S; //定义指向链栈的指针S
设S是LinkStack类型的指针变量，则S是指向链栈的指针，链栈栈顶指针可表示为S-> top；链栈栈顶元素可表示为S-> top ->data。
设p是StackNode类型的指针变量，则p是指向链栈某结点的指针，该结点的数据域可表示为p ->data，该结点的指针域可表示为p -> next。
第3章 栈
注意：
①LinkStack结构类型的定义是为了方便在函数体中修改top指针本身。 ②若要记录栈中元素个数，可将元素个数属性作为LinkStack类型中的成员定义。
③条件S->top== NULL表示空栈，链栈没有栈满的情况。 3、链栈上基本运算的算法 ①置栈空
void InitStack（LinkStack *S）{//将链栈置空
S->top=NULL; }
②判栈空
int StackEmpty（LinkStack *S）{ return S->top==NULL; }
③进栈
void Push（LinkStack *S，DataType x ）{//将元素x插入链栈头部 StackNode *p=(StackNode *)malloc(sizeof(StackNode)); p->data=x;
p->next=S->top;//将新结点*p插入链栈头部 S->top=p; //栈顶指针指向新结点 }
④退栈
DataType Pop（LinkStack *S）{ DataType x;
StackNode *p=S->top;//保存栈顶指针 if(StackEmpty(S))
{puts(“栈空”); return 0;}//下溢，退出运行 x=p->data; //保存栈顶结点数据
S->top=p->next; //将栈顶结点从链上摘下 free(p); return x; }
⑤取栈顶元素
DataType StackTop（LinkStack *S）{
第3章 栈
if(StackEmpty(S)) {puts(“栈空”); return 0;} return S->top->data; }
注：由于链栈中的结点是动态分配的，可以不考虑上溢，所以无须定义StackFull运算。
3.3 栈的应用
1.数值转换
十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。
转换法则：该转换法则对应于一个简单算法原理:n=(n div d)*d+n mod d 其中：div为整除运算,mod为求余运算
例如 (1348)10= (2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 采用静态顺序栈方式实现
void conversion(int n , int d) { /*将十进制整数N转换为d(2或8)进制数*/
SqStack S ; int k, *e ; S=Init_Stack();
while (n>0) { k=n%d ; push(S , k) ; n=n/d ; } /* 求出所有的余数，进栈 */
while (S.top!=0) { /* 栈不空时出栈，输出 */ pop(S, e) ; printf(“ ” , *e) ; }
2.表达式的求值
问题:能否设计算法，编制一个程序，让计算机扫描如下表达式，并将其值打印出来。
# 3 * ( 4 + 8 ) / 2 -5 #
注：给表达式设置#，标志扫描的开始和结束。
这个表达式的计算顺序是：3*（4+8）/2-5=3*12/2-5=36/2-5=18-5=13 任何一个表达式都是由操作数、运算符和界位符组成的，操作数可以使一些常数也可以使一些变量或是常量的标示符，运算符则分为算数运算符、关系运算符和逻辑运算符；基本界位符有左右括号和表达式结束。一般将运算符和界位符看做是界符。
}
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库NOIP高中信息技术竞赛资料 - -数据结构(4)在线全文阅读。
相关推荐：