资源描述
.,第三章栈和队列,数据结构,.,一、栈,2,第一节栈,栈是限定仅在表尾(top)进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top，表尾)，另一端称为栈底(bottom，表头)特点：后进先出 (LIFO),.,二、栈的实现,3,第一节栈,栈的存储结构主要有两种：1. 顺序栈2. 链式栈,.,一、顺序栈,4,第二节顺序栈,顺序栈是栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。,.,二、顺序栈的定义,5,第二节顺表栈,采用C语言中动态分配的一维数组表示顺序表,#define STACK_INIT_SIZE 100 /栈存储空间的初始分配量#define STACKINCREMENT 10 /栈存储空间的分配增量typedef struct SElemType*base /存储空间基址SElemType*top; /栈顶指针int stacksize; /当前分配的存储容量(元素数) SqStack;,.,三、顺序栈的特性,6,第二节顺序栈,top=0 或top=base 表示空栈base=NULL表示栈不存在当插入新的栈顶元素时,指针top+1删除栈顶元素时，指针top-1当topstacksize时，栈满，溢出,.,四、顺序栈的主要操作,7,第二节顺序栈,ADT Stack 数据对象：D = ai | aiElemSet, i=1,2,3,n 数据关系：R = | ai-1,aiD 基本操作： Status InitStack(SqStack &S) / 构造空栈 Status Push(SqStack &S, e) / 进栈 Status Pop(SqStack &S, &e) / 出栈 Status GetTop(SqStack S, &e)/ 取栈顶元素值 Status StackEmpty(SqStack S) / 栈是否为空 ADT Stack,.,五、创建顺序栈,8,第二节顺序栈,Status InitStack(SqStack / InitStack,.,六、进栈（插入新元素）,9,第二节顺序栈,Status Push(SqStack / Push,.,七、出栈（删除元素）,10,第二节顺序栈,Status Pop(SqStack / Pop,.,八、取栈顶元素,11,第二节顺序栈,Status GetTop(SqStack S, SElemType / GetTop,.,1.创建堆栈节点类template class LinStack;/前视定义,否则友元无法定义template /模板类型为Tclass StackNode friend class LinStack; /定义类LinStack为友元private: T data; /数据元素 StackNode *next; /指针public: StackNode(StackNode *ptrNext = NULL) /构造头结点 next = ptrNext; StackNode(const T,第三节链栈,.,第三节链栈,2.创建链式堆栈类 template class LinStackprivate:StackNode *head;/头指针int size;/数据元素个数public:LinStack(void);/构造函数LinStack(void);/析构函数void Push(const T,.,第三节链栈,3.链式堆栈的实现 template LinStack:LinStack()/构造函数 head = new StackNode;/头指针指向头结点 size = 0; /size的初值为0template LinStack:LinStack(void)/析构函数 StackNode *p, *q; /释放所有动态申请的结点空间 p = head;/p指向头结点 while(p != NULL) /循环释放结点空间 q = p; p = p-next; delete q; template int LinStack:NotEmpty(void) const/堆栈非空否if(size != 0) return 1;else return 0;,.,第三节链栈,template void LinStack:Push(const T/元素个数加1,.,第三节链栈,template T LinStack:Pop(void)/出栈 if(size = 0) cout *p = head-next;/p指向栈顶元素结点 T data = p-data;head-next = head-next-next;/原栈顶元素结点脱链delete p;/释放原栈顶结点空间size-;/结点个数减1return data;/返回原栈顶结点的data域值,.,第三节链栈,template T LinStack:GetTop(void)const /取栈顶元素return head-next-data;,.,一、数值转换,18,第四节栈的应用举例,将十进制转换为其它进制(d)，其原理为： N = (N/d)*d + N mod d例1：（1348)10=(2504)8 ，其运算过程如下： N N /8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,.,一、数值转换,19,第四节栈的应用举例,void conversion () InitStack(S); / 创建新栈S scanf (“%d”,N); / 输入一个十进制数N while (N) Push(S, N % 8); / 将余数送入栈中 N = N/8; / 求整除数 while (!StackEmpty(S) / 如果栈不空 Pop(S,e); / 将栈中数出栈 printf ( %d, e ); / conversion,.,二、行编辑程序,20,第四节栈的应用举例,用户输入一行字符允许用户输入出差错，并在发现有误时，可以用退格符“#”及时更正假设从终端接受两行字符： whli#ilr#e（s#*s) 实际有效行为： while (*s),.,二、行编辑程序,21,第四节栈的应用举例,例2:对用户输入的一行字符进行处理,直到行结束(“n”)void LineEdit() InitStack(s); ch = getchar(); /从终端接受一个字符 while (ch != n) switch(ch) case # : Pop(S, c);break; / 仅当栈非空时退栈 case : ClearStack(S); break; default: Push(S, ch); break; / 有效字符进栈 ch = getchar(); / 从终端接受一个字符 /将从栈底到栈顶的栈内字符传送到调用过程的数据区; ,.,第四节栈的应用举例,三.括号匹配 假设一个算术表达式中包括( )、 和 三种形式的括号，设计一个判别表达式中括号是否正确匹对的程序。1.算法思想： 算术表达式中右括号和左括号匹配的次序:后到括号要最先被匹配的“后进先出”堆栈操作特点，因此可用一个堆栈来进行判断。顺序扫描算术表达式（表现为一个字符串）；当遇到三种类型的左括号时，该括号进栈；当遇到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配则退栈，继续进行判断；若不匹配，则左右括号配对次序不正确，结束。若字符串当前为某一类型的右括号而堆栈为空，则右括号多于左括号，结束。若字符串扫描结束而堆栈非空，则左括号多于右括号，结束。若字符串扫描结束而堆栈为空，则左右括号匹配正确，结束。,.,第四节栈的应用举例,#include #include #include using namespace std;bool brackMatch(string str) /括号匹配 int i = 0;stack stk; / 使用C+的stack类while(istr.size() if(stri=(|stri=|stri=) /出现三种左括号之一压栈；否则进行匹配判断 stk.push(stri); else if(stri=)|stri=|stri=) /遇到右括号,判断栈顶元素是否为左括号，如不为匹配的左括号，括号不匹配；否则出栈 if(stri=) / 左括号多于右括号,.,四、迷宫求解,24,第四节栈的应用举例,迷宫求解一般采用“穷举法”逐一沿顺时针方向查找相邻块（一共四块东(右)、南(下)，西(左)、北(上)）是否可通，即该相邻块既是通道块，且不在当前路径上用一个栈来记录已走过的路径,.,四、迷宫求解,25,第四节栈的应用举例,.,四、迷宫求解（算法）,第四节栈的应用举例,设定当前位置为入口位置do 若当前位置可通，则 将该位置插入栈顶(Push)； 若该位置是出口，则结束 否则切换当前位置的相邻方块为当前位置； 否则 若栈不空则 如栈顶位置四周均不可通,则删除栈顶位置(Pop),并重 新测试新的栈顶位置 如找到栈顶位置的下一方向未经探索，则将该方向方 块设为当前位置 while(栈不空)；找不到路径；,.,第四节栈的应用举例,四、迷宫求解(举例） 入口int mgm+1n+1= 1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1; 出口,.,第四节栈的应用举例,求解结果：迷宫路径： (1,1) (1,2) (2,2) (3,2) (3,1) (4,1)(5,1) (5,2) (5,3) (6,3) (6,4) (6,5) (5,5) (4,5) (4,6) (4,7) (3,7) (3,8)(4,8) (5,8) (6,8) (7,8) (8,8),.,五、表达式求值,29,第四节栈的应用举例,表达式由操作数、运算符和界限符组成，它们皆称为单词操作数：常数或变量运算符：+, -, *, / 等界限符：(, ), #(表达式开始及结束符),.,五、表达式求值,30,第四节栈的应用举例,设置两个栈：操作数栈（OPND）运算符栈（OPTR）,.,五、表达式求值,31,第四节栈的应用举例,运算符的优先级关系,新运算符,运算符栈顶元素,.,五、表达式求值（算法）,第四节栈的应用举例,置运算符栈(OPTR)和操作数栈(OPND)为空#插入OPTR栈；取表达式第一个单词；while(单词 或 OPTR栈顶元素不为#) 若单词是操作数，则插入OPND栈顶，取下一个单词否则 OPTR栈顶元素优先级与新运算符优先级关系为：小于,则插入OPTR栈顶，取下一单词等于,则删除OPTR栈顶元素，取下一单词大于,则从OPND栈顶依次取出两个操作数，用从OPTR栈顶取出的元素进行计算，结果插入OPND栈顶 ,从栈顶取出元素，包括取值及删除栈顶元素两个过程,.,第四节栈的应用举例,举例1:求算术表达式1+2*3-4/2的值 计算顺序（1）2*3 （2）1+6 （3）4/2 （4）7-2,.,第四节栈的应用举例,步骤 OPTR OPND 输入字符 栈操作 # 1+2*3-4/2# PUSH（OPND,1 ） # 1 +2*3-4/2# PUSH（OPTR,+ ） #+ 1 2*3-4/2# PUSH（OPND,2 ） #+ 1 2 *3-4/2# PUSH（OPTR,*） #+* 1 2 3-4/2# PUSH（OPND,3 ） #+* 1 2 3 -4/2# operate（2,*,3） #+ 1 6 -4/2# operate（1,+,6） # 7 -4/2# PUSH（OPTR,- ） # - 7 4/2# PUSH（OPND,4 ） #- 7 4 /2# PUSH（OPTR,/ ） #-/ 7 4 2# PUSH（OPND,2 ） #-/ 7 4 2 # operate（4,/,2） #- 7 2 # operate（7,-,2） # 5 # return(TOP(OPND),.,举例2:写出表达式5+(6-4/2)*3的计算过程,最后的结果T4,置于OPRD的栈顶。,.,第四节栈的应用举例,表达式求值算法： coutinput an expression (Ending with #)”next; /p指向新的队头结点T data = front-data;/保存原队头结点的data域值delete front;/释放原队头结点空间front = p;/front指向新的队头结点count-;/计数器减1return data;/返回原队头结点的data域值,.,队列应用举例,实例: 编写判断一个字符序列是否回文的函数. 回文:一个字符序列以中间字符为基准且两边字符 完全相同。 算法描述:字符数组中存放要判断的字符串。 把字符数组中字符逐个分别存入一个队列和一个堆栈 逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。,.,队列应用举例,const int MaxQueueSize = 10;const int MaxStackSize = 10;typedef char DataType; /构造一个顺序循环队列,一个顺序栈void HuiWen(char str) /判断字符串str是否是回文SeqStack myStack;SeqQueue myQueue;int n = strlen(str); /求字符串长度for(int i = 0; i n; i+)myQueue. EnQueue(stri);myStack.Push(stri); while(myQueue.NotEmpty() ,.,队列应用举例,void main(void)char str1 = ABCDEDCBA;char str2 = ABCDEDBAC;cout 字符串ABCDEDCBA;HuiWen(str1);cout next=s. Bs-next=top-next;top-next=s.Ctop-next=s;top=s. Ds-next=top; top=top-next.8. 从栈顶指针为top的链栈中删除一个结点,并将被删结点的值保存到x中,其操作步骤为（）。Ax=top-data; top=top-next; Btop=top-next; x=top-data;Cx=top; top=top-next; Dx=top-data.,.,练 习,9. 链栈和顺序栈相比，有一个较明显的优点是（）。A通常不会出现栈满的情况 B通常不会出现栈空的情况C插入操作更加方便 D删除操作更加方便10. 设数组Am作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作操作修改指针的是（）Asq.front=(sq.front+1)%m Bsq.front=(sq.front+1)%(m+1)Csq.rear=(sq.rear+1)%m Dsq.rear=(sq.rear+1)%(m+1)11、在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为（）。Af-next=c;f=s; Br-next=s;r=s;Cs-next=r;r= s Ds-next=f;f=s;,.,队列应用举例,课堂练习:报数问题有10个人站一排队,从左向右编号:1-10号现从左向右报数”1,2,1,2,1,2,1,2,1,2”,要求报数1的人出列,报数2的人立即站到队尾,直到所有的人都出列,给出人们的出列顺序算法.,
展开阅读全文