5. 堆栈和队列

5.1 栈的概念与实现
5.2 栈的应用
5.3 队的概念与实现
5.4 递归与回溯

对应的教材章节

5.1栈的概念与实现

教学目的： 栈的数据类型定义、栈的顺序存储表示与实现
教学重点： 栈的顺序存储表示与实现方法
教学难点： 栈的定义
授课内容：
一、栈的定义
栈是限定仅在 表尾进行插入或删除操作的线性表。
栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。
栈的抽象数据类型定义：
ADT Stack{
数据对象:D={ai|ai(- ElemSet,i=1,2,...,n,n>=0}
数据关系:R1={<ai-1,ai>|ai-1,ai(- D,i=2,...,n}
基本操作:
InitStack(&S) 构造一个空栈S
DestroyStack(&S) 栈S存在则栈S被销毁
ClearStack(&S) 栈S存在则清为空栈
StackEmpty(S) 栈S存在则返回TRUE,否则FALSE
StackLength(S) 栈S存在则返回S的元素个数,即栈的长度
GetTop(S,&e) 栈S存在且非空则返回S的栈顶元素
Push(&S,e) 栈S存在则插入元素e为新的栈顶元素
Pop(&S,&e) 栈S存在且非空则删除S的栈顶元素并用e返回其值
StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,则操作失败
}ADT Stack
二、栈的表示和实现
栈的存储方式：
1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置
2、链栈:利用链表实现
顺序栈的类C语言定义:
typedef struct{
SElemType *base;
SElemType *top; //设栈顶栈底两指针的目的是便于判断栈是否为空
int StackSize; //栈的当前可使用的最大容量.
}SqStack;
顺序栈的的模块说明:
struct STACK {
SElemType *base;
SElemType *top;
int stacksize;
};
typedef struct STACK Sqstack;
Status InitStack(SqStack &S);
Status DestroyStack(SqStack &S);
Status ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,SElemType &e);
Status Push(SqStack &S,SElemType e);
Status Pop(SqStack &S,SElemType &e);
Status StackTraverse(SqStack S,Status (*visit)());
 
Status InitStack(SqStack &S) {
S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INI_SIZE;
return OK;
}//IniStack
Status DestroyStack(SqStack &S); {
}//DestroyStack
Status ClearStack(SqStack &S); {
S.top=S.base;
} //ClearStack
Status StackEmpty(SqStack S); {
if(S.top==S.base) return TRUE;
else return FALSE;
} //StackEmpty
int StackLength(SqStack S); {
int i; SElemType *p;
i=0;
p=S.top;
while(p!=S.base) {p++; i++; }
} //stackLength
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=(ElemType *) realloc(S.base,
(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
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 StackTraverse(SqStack S,Status (*visit)()); {
}//StackTraverse

三、总结
栈的定义
栈的顺序存储实现

5.2 栈的应用

教学目的： 掌握栈的应用方法,理解栈的重要作用
教学重点： 利用栈实现行编辑,利用栈实现表达式求值
教学难点： 利用栈实现表达式求值
授课内容：
一、栈应用之一：数制转换
将十进制数转换成其它进制的数有一种简单的方法：
例：十进制转换成八进制：(66)10=(102)8
66/8=8 余 2
8/8=1 余 0
1/8=0 余 1
结果为余数的逆序:102 。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换：

二、栈应用之二：行编辑
一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定＃为退格符，以表示前一个字符无效，@为退行符，表示当前行所有字符均无效。
例：在终端上用户输入为
whli##ilr#e(s#*s) 应为
while(*s)

三、栈应用之三：表达式求值
一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例：1+2*3有+,*两个运算符，*的优先级高,1,2,3是操作数。 界定符有括号和表达式结束符等。
算法基本思想：
１首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素；
２依次讲稿表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。

四、总结
栈的先进后出、后进先出的特性。

5.3 队的概念与实现

教学目的： 掌握队列的类型定义,掌握链队列的表示与实现方法
教学重点： 链队列的表示与实现
教学难点： 链队列的表示与实现
授课内容：
一、队列的定义:
队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。象日常生活中的排队，最早入队的最早离开。
在队列中，允许插入的的一端叫队尾，允许删除的一端则称为队头。
抽象数据类型队列:
ADT Queue{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai> | ai-1,ai(- D,i=2,...,n}
基本操作：
InitQueue(&Q) 构造一个空队列Q
Destroyqueue(&Q) 队列Q存在则销毁Q
ClearQueue(&Q) 队列Q存在则将Q清为空队列
QueueEmpty(Q) 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
QueueLenght(Q) 队列Q存在,返回Q的元素个数,即队列的长度
GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素
EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素
DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值
QueueTraverse(Q,vivsit()) Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
}ADT Queue
二、链队列－队列的链式表示和实现
用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针。

链队列表示和实现：
//存储表示
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//操作说明
Status InitQueue(LinkQueue &Q)
//构造一个空队列Q
Status Destroyqueue(LinkQueue &Q)
//队列Q存在则销毁Q
Status ClearQueue(LinkQueue &Q)
//队列Q存在则将Q清为空队列
Status QueueEmpty(LinkQueue Q)
// 队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE
Status QueueLenght(LinkQueue Q)
// 队列Q存在,返回Q的元素个数,即队列的长度
Status GetHead(LinkQueue Q,QElemType &e)
//Q为非空队列,用e返回Q的队头元素
Status EnQueue(LinkQueue &Q,QElemType e)
//队列Q存在,插入元素e为Q的队尾元素
Status DeQueue(LinkQueue &Q,QElemType &e)
//Q为非空队列,删除Q的队头元素,并用e返回其值
Status QueueTraverse(LinkQueue Q,QElemType vivsit())
//Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
//操作的实现
Status InitQueue(LinkQueue &Q) {
//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front->next=NULL;
return OK;}
Status Destroyqueue(LinkQueue &Q) {
//队列Q存在则销毁Q
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;}
Status EnQueue(LinkQueue &Q,QElemType e) {
//队列Q存在,插入元素e为Q的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;}
Status DeQueue(LinkQueue &Q,QElemType &e) {
//Q为非空队列,删除Q的队头元素,并用e返回其值
if(Q.front==Q.rear)return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;}
三、总结
链队列的存储表示
链队列的操作及实现

5.4 递归与回溯

    为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这
种用自已来定义自己的方法，称为递归定义。递归是利用堆栈实现的。

例如：定义函数f(n)为：
        /n*f(n－1) (n>0)
f(n)= |
        \ 1(n=0)
    则当0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。
    由上例我们可看出，递归定义有两个要素：
    （1）递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。
         如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。
    （2）递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。
         如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。

    递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构
复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步
没其结果仍维持原问题的关系, 则采用递归算法编程比较合适.

    递归按其调用方式分为: 1. 直接递归, 递归过程P直接自己调用自己; 2. 间接递归, 即P包含另一过程
D, 而D又调用P.

    递归算法适用的一般场合为:
    1. 数据的定义形式按递归定义.
       如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.
       对应的递归程序为:
         int fib(int n )
         {
            if (n == 0) fib = 1; //    递归边界
            else if (n == 1) fib = 2;
            else fib = fib(n-2) + fib(n-1);  // 递归
         }
       这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.
    2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.
    3. 问题解法按递归算法实现. 例如回溯法等.

    从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "
的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法, 称作
" 回溯法 ".

[参考程序]
    下面给出用回溯法求所有路径的算法框架. 注释已经写得非常清楚, 请读者仔细理解.
Const maxdepth = ????;
Type statetype = ??????; { 状态类型定义 }
     operatertype = ??????; { 算符类型定义 }
     node = Record { 结点类型 }
               state : statetype; { 状态域 }
       operater :operatertype { 算符域 }
    End;
{ 注: 结点的数据类型可以根据试题需要简化 }
Var
   stack : Array [1..maxdepth] of node; { 存当前路径 }
   total : integer; { 路径数 }
Procedure make(l : integer);
Var i : integer;
Begin
   if stack[L-1]是目标结点 then
   Begin
      total := total+1; { 路径数+1 }
      打印当前路径[1..L-1];
      Exit
   End;
   for i := 1 to 解答树次数 do
   Begin
      生成 stack[l].operater;
      stack[l].operater 作用于 stack[l-1].state, 产生新状态 stack[l].state;
      if stack[l].state 满足约束条件 then make(k+1);
      { 若不满足约束条件, 则通过for循环换一个算符扩展 }
      { 递归返回该处时, 系统自动恢复调用前的栈指针和算符, 再通过for循环换一个算符扩展 }
      { 注: 若在扩展stack[l].state时曾使用过全局变量, 则应插入若干语句, 恢复全局变量在
                        stack[l-1].state时的值. }
   End;
   { 再无算符可用, 回溯 }
End;
Begin
   total := 0; { 路径数初始化为0 }
   初始化处理;
   make(l);
   打印路径数total
End.

[例子]    求N个数的全排列。
    ［分析］求N个数的全排列，可以看成把N个不同的球放入N个不同的盒子中，每个盒子中只能有一
个球。解法与八皇后问题相似。
    ［参考过程］
       void try(int I);
       {
             int j;
             for (j=1;j<=n;j++)
                 if (a[j]==0)
                 {
                      x[I]=j;
                      a[j]=1;
                      if (I<n) try(I+1);
                      else print;
                      a[j]=0;
                 }
        }