西交《数据结构》faq（三）
西交《数据结构》FAQ（三）第三章 栈和队列
1、栈的定义和相关基本概念？
限定运算在线性表尾进行的线性表
允许插入、删除的返一端称为栈顶另一个固定端称为栈底。当表中没有元素时称为空栈定义仅是在线性表上规定了操作点,操作受限的、线性的后进先出线性表LIFO
2、对于栈，常做的基本运算有哪些？
1）栈初始化InitStack(s)栈S不存在，构造一个空栈
2）销毁栈 DstoryStack(&s)栈S存在，将S销毁
3）清为空栈 ClearStack(&s) 栈S存在，将S清空
4）判栈空 StackEmpty(s) 栈S己存在，若S为空栈返回TRUE，否则返回FALSE
5）清空栈 Stacklength(s) 栈S存在，返回S的元素个数
6）读栈顶元素 GeTStack(s，&e)栈S存在且非窄，返回栈顶元素e
7）入栈 Push(&s，e) 栈S己存在，在S顶部插入新栈元X
8）出栈 Pop(&s，&e) 栈S存在且非空，删除栈S顶元，用e返回其值
9）遍历栈 StackTraverse(s，visit())依次对栈调用visit()
3、栈的顺序存储结构的定义。
#defineSTACK_INIT_SIZE 100
#defineSTACKINCREMENT10
typedef struct {
SElemType *base;
SElemType *top ;
} sqstack;
说明
top指向栈顶元素的下一个位置，即待接收数据的位置
top= base 空栈
top=base+stacksize栈满补添存储
由于栈是运算受限的线性表，因此线性表的存储体结构对栈也是适用的，只是操作点不同而己。顺序栈的置空首先建立栈空间，然后初始化栈顶指针。
顺序栈
约定与类型定义：top的含义
#defineSTACK_INIT_SIZE100// 存储空间的初始分配量
typedefstruct{
ElemType base; // 栈底指针
int top; // 栈顶指针(栈顶元素的下一个位置)
}SqStack;
4、栈的顺序存储结构及其基本操作的实现。
约定：top指向栈顶元素的下一个位置
顺序栈的初始化 首先建立栈空间，然后初始化栈顶指针。
status InitStack(SqStack &s ){
s.base=(SElemtype*)malloc(STACK_INIT_SIZE*
sizeof(SElemtype));
if(!s.base) exit (OVERFLOW) ；
s.top=s.base ;
s.stacksize=STACK-INIT-SIZE ;
returnOk;
} // InitStack
顺序栈的取栈顶元
status GetTop(SqStack s,SElemType &e ){
if(s.top==s.base) returnERROR;
e=*(S.top-1);
returnOk;
} // GetTop
出栈和取栈顶元，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件
顺序栈入栈
status Push (SqStack &s, SElemType e){
if (s.top-s.base >= s.stacksize) {
s.base=(SElemType*)realloc(s.base,(s.stacksize
+STACKINCREMENT)*sizeof(SElemType));
if (!s.base) exit (OVERFLOW) ；
s.top=s.base+ s.stacksize;
s.stacksize+= STACKINCREMENT ;
}
*s.top++=e ;
return OK;
} //Push}
对于顺序栈，入栈时先判栈是否满了，栈满时不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。
顺序栈出栈
status Pop (SqStack &s, SElemType e){
if (s.top==s.base) return ERROR ;
e=*--s.top ;
return OK ;
} //Pop
顺序栈判空
status StackEmpty(SqStack s ){
if (s.top= =s.base)return1;
elsereturn0;
}
5、栈与单链表的关系？
单链表：仅在一端操作。用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，其结点结构与单链表的结构相同
typedef structNode {
datatype data ;
structNode *next ;
} StackNode, *LinkStack ;
因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986
页:
[1]