chapter 3.ppt

第三章 栈和队列 主要内容 1、栈的类型定义 栈 例题： 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是哪个？（ ） （1）A，B，C，D （2）B，D，C，A （3）A，C，D，B （4）D，A，B，C 栈抽象数据类型的定义 2、栈类型的实现 2.1 顺序栈 2.2 链栈 2.1 顺序栈的表示和实现 栈的顺序存储结构—顺序栈 特点：用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设指针top指示栈顶元素在顺序栈中的位置。 缺点：操作不便，且栈使用过程中所需空间难以估计。 解决办法：在应用中，附设栈底指针，空间不足时逐段扩大 顺序栈的C语言描述： #define STACK_INIT_SIZE 100//为栈分配一个基本容量 #define STACKINCREMENT 10//存储空间分配增量 typedef struct{ SElemType *base;//栈底指针，始终指向栈底； SElemType *top;//栈顶指针始终指向栈顶元素的下一个位置 int stacksize;//当前已分配的存储空间 }SqStack; 顺序栈栈顶、栈底指针和栈中元素的关系 基本操作（1） 基本操作（2） Status GetTop(SqStack S, SElemType e) { //用e返回栈顶元素 if(S.top==S.base) return ERROR;//栈空 e=*(S.top-1);//取栈顶元素 return OK; }//GetTop 基本操作（3） 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; } 基本操作（4） Status Pop (SqStack S, SElemType e) { // 若栈不空，则删除S的栈顶元素， // 用e返回其值，并返回OK； // 否则返回ERROR if (S.top == S.base) return ERROR; e = *--S.top; return OK; } 3、栈的应用举例—字符序列逆置 例1:将从键盘输入的字符序列逆置输出 例2： 栈的应用—数制转换 十进制数和其它进制数的转换是计算机实现计算的基本问题 算法策略:N=(N div d)*d+N mod d 例： (1348)10=( )8，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 例3：栈的应用—迷宫求解 从入口出发，沿某一方向向前探索，若能走通，将当前位置纳入“当前路径”，继续向前走，即切换“下一位置”为“当前位置”；如此重复直至到达出口；否则（当前位置“不可通”），则顺着“来向”退回到“前一通道块”（沿原路返回），换个方向再向前探索，若该通道块的四周四个方块均不可通，则应从“当前路径”上删除该通道块，直到所有可能的通路都探索为止。 为了保证在任何位置上都能沿原路退回，需要一个后进先出的结构来保存从入口到当前位置的路径。 所求路径应该是简单路径（无环） 设定当前位置的初值为入口位置 do{若当前位置可通 //是通道块且不在当前路径上 则｛将当前位置插入栈顶； // 纳入路径