西交《数据结构》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、栈的顺序存储结构的定义。
#define  STACK_INIT_SIZE   100
#define  STACKINCREMENT  10
typedef   struct {                                          
    SElemType   *base;
    SElemType   *top ;
} sqstack;


说明
top指向栈顶元素的下一个位置，即待接收数据的位置
top= base 空栈
top=base+stacksize  栈满  补添存储
由于栈是运算受限的线性表，因此线性表的存储体结构对栈也是适用的，只是操作点不同而己。顺序栈的置空首先建立栈空间，然后初始化栈顶指针。
顺序栈
约定与类型定义：top的含义
#define  STACK_INIT_SIZE  100// 存储空间的初始分配量
typedef  struct{
        ElemType        base[100];                // 栈底指针               
        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 ;
  return  Ok;
   } // InitStack
顺序栈的取栈顶元
status GetTop(SqStack s,SElemType &e )  {
   if  (s.top==s.base) return  ERROR;
   e=*(S.top-1);
   return  Ok;
} // 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)  return  1;
   else  return  0;
}
5、栈与单链表的关系？
单链表：仅在一端操作。用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，其结点结构与单链表的结构相同
typedef   struct  Node {
    datatype         data ;
    struct  Node   *next ;
} StackNode, *LinkStack ;
因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986