• 1. 第三章 栈和队列栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性DS 3.1 栈(stack) 3.2 栈的应用举例 3.3 队列 3.4 队列应用举例
  • 2. 3.1.1栈的定义 定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈特点:先进后出(FILO)或后进先出(LIFO)ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)3.1 栈(stack)栈顶(top):允许插入和删除的一端;栈底(bottom):不允许插入和删除的一端。
  • 3. 3.1.2 栈的实际应用 生活中的例子: a. 刷洗盘子。把洗净的盘子一个接一个地往上放 (相当于把元素入栈);取用盘子的时候,则从最上 面一个接一个地往下拿(相当于把元素出栈)。 b. 枪械上子弹时,把子弹一个接一个地往弹匣里 放(相当于把元素入栈);发射子弹时,则从最上一 个接一个往外发射(相当于把元素出栈)。
  • 4. 2. 在计算机系统中的应用: a. 括号匹配 括号匹配问题是计算机程序设计中常见的问题。为简化问题,假设表达式中只允许有两种括号:圆括号和方括号。嵌套的顺序是任意的,([]())或[()[()][]]等都为正确的格式,而[(])或(([)])等都是不正确的格式。 b. 游戏中的迷宫问题求解 从入口出发,沿某一方向进行探索,若能走通,则继续 向前走;否则沿原路返回,换一方向再进行搜索,直到所 有可能的通路都探索到为止。即所谓的回溯法(用一个栈 保存探索的路径 )。
  • 5. c. 函数调用 在程序中运行到某一行时,需要调用另一个函数,这个函数可能又要嵌套调用另外一个函数,当执行完函数后,要正常回到程序的下一句继续执行。例:有这样的函数嵌套关系 Main→TestA →TestB →TestC →TestD 在Main中执行到要调用TestA函数时,需要记录下(入栈)当前函数名字Main以及程序的行号(例如11行),在TestA函数中调用到TestB时,又入栈TestA函数名及行号,依次类推..... ,当执行完TestD函数后,出栈依次返回调用它的函数TestC及运行的行号,TestC结束后,又返回TestB函数及行号,依次类推...,最后返回Main函数及运行到的行号
  • 6. 1.顺序栈top=-1123450栈空栈顶指针top,指向实际栈顶 位置,初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为M top=-1,栈空,此时出栈,则下溢(underflow) top=M-1,栈满,此时入栈,则上溢(overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空3.1.2栈的存储实现和运算实现
  • 7. 存储结构的实现#define MAXSIZE 1000 typedef struct {ElemType data[MAXSIZE]; int top; }SeqStack;运算实现(1)置空栈 (2)判栈空 (3)入栈 (4)出栈 (5)取栈顶元素S->top=-1123450栈空S->top123450进栈xS->topS->data[s->top]SeqStack *SSInit() {SeqStack *s; s=(SeqStack *)malloc(sizeof(SeqStack)); s->top= -1; return s; } int SSIsFull(SeqStack *s) { return s->top= = -1; } void SSpush(SeqStack *s, ElemType x) { if (s->top= =MAXSIZE-1) {printf(“\nStack Overflow!\n”); return;} s->top++; s->data[s->top]=x; } void SSpop(SeqStack *s, ElemType *x) { if (s->top==-1 ) {printf(“\nStack Underflow!\n”); return; } *x=s->data[s->top]; s->top--; } int SSGetTop(SeqStack *s,ElemType *x) { if ( s->top==-1 ) {printf(“\nStack Is Empty!\n”); return 0; } *x=s->data[s->top]; return 1; }
  • 8. 课堂演示:表达式括号配对检测查看表达式中的括号是否配对 例如: (1+2)*3 – (4*(5-2))
  • 9. 课堂练习:括号配对同时支持() {} []三种括号的配对
  • 10. d .表达式求值   要把一个表达式翻译成正确求值的一个机器指令序列,或者直接对表达式求值,首先要能够正确解释表达式,这需要了解算术四则运算的规则。算术四则运算的规则如下: 先乘除后加减; 先括号内后括号外;  同级别时先左后右。
  • 11. 表3-1 算符之间的优先级关系  θ2+ -*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=θ1
  • 12. 算符优先级设置 栈内:   * / :4  + - :2 ( :0 ):5 # :-1 栈外:   * / :3  + - :1 ( :5 ):0 # :-1
  • 13. d .表达式求值设计两个栈   OPTR栈(存放运算符)   OPND栈(存放操作数和结果) 栈的初始化:
  • 14. d .表达式求值表达式后面加结束符’#’ 规则: 从左向右扫描每个字符 (1)数字,入栈OPND; (2)运算符(设为θ2),则需与OPTR的栈顶(设为θ1)相比较优先关系 θ1>θ2,OPND出栈一次得到数a,再出栈一次得到b,OPTR出栈,得到运算符θ1,bθ1 a得到结果c后,将结果c入栈OPND; θ1<θ2,θ2入栈OPTR,取下一字符; θ1=θ2,OPTR出栈,取下一字符 (3) 当OPTR栈中仅剩’#’且读入的字符也为‘#’ 结束,取    OPND栈栈顶元素得结果
  • 15. [例3-10]表达式求值 中缀表达式 a*b+c a+b*c a+(b*c+d)/e (1)中缀表达式求值:对象栈和运算符栈例 计算 2+(4-3)*6#++1左括号在栈外优先级最高右括号遇到左括号,左括号直接出栈左括号在栈内优先级比-低对象栈算符栈2+#对象栈243算符栈+(-#对象栈算符栈2+(#对象栈算符栈2+1#对象栈算符栈2+(#对象栈216算符栈*#+对象栈算符栈26#+对象栈算符栈8#1
  • 16. 课后完成-表达式求值(项目2)1、能进行+、-、*、/四则运算 2、能正确计算带有圆括号的表达式 3、能对整型数据进行计算 4、能判断用户输入的表达式括号是否匹配 5、能判断用户输入的表达式是否为正确的表达式 6、对代码添加详细的注释
  • 17. 3.1.3 栈的链式存储 若是栈中元素的数目变化范围较大或不清楚栈元素的数目,就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。 由于栈的插入删除操作只能在一端进行,而对于单链表来说,在首端插入删除结点要比尾端相对地容易一些,所以,我们将单链表的首端作为栈顶端。
  • 18. 栈顶 ^…...ls栈底结点定义: typedef struct _node { ELEMTYPE data; struct _node * pNext; }Node; 链栈定义: typedef struct _linkedStack { Node * pHead; }LinkedStack; 2.链栈
  • 19. 2.1 链栈的操作判断栈空 int IsStackEmpty(LinkedStack * pStack); 入栈 void Push(LinkedStack * pStack, ElemType data); 出栈 int Pop(LinkedStack * pStack, ElemType* data); 取栈顶元素 int Top(LinkedStack * pStack, ElemType* data);
  • 20. 2.2 链栈的应用数制转换问题:将十进制N转换为r进制的数。例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732算法思想: while(N>0) {将N%r结果进栈; N=N/r;} while(栈非空) 出栈并输出原栈顶元素;
  • 21. 3.3 队列 3.3.1 队列的定义 队列特殊性在于限定插入在线性表的一端进行,删除在线性表的另外一端进行。如图3-5所示: a1 a2 a3 a4 a5 a6 a7 a8 a9 删除端 (头) 插入端(尾)
  • 22. 插入端和删除端都是浮动的。通常我们将插入端称为队尾,用一个“队尾指针”指示(rear );而删除端被称为队头,用一个“队头指针”指示(front) 。 结论:先进先出(First In First Out),简称为FIFO线性表。 a1 a2 a3…………………….an 入队出队frontrear队列Q=(a1,a2,……,an)
  • 23. 3.3.2 队列的实际应用 生活中的例子: a. 排队上车 后面的人一个个排到队伍后面,成为入队,排在前面的 人一个个上车,成为出队。 计算机应用中的例子: a. 模拟打印机缓冲区: 在主机将数据输出到打印机时,会出现主机速度与打印 机的打印速度不匹配的问题。这时主机就要停下来等待打 印机。显然,这样会降低主机的使用效率。为此人们设想 了一种办法:为打印机设置一个打印数据缓冲区,当主机
  • 24. 需要打印数据时,先将数据依次写入这个缓冲区,写满 后主机转去做其他的事情,而打印机就从缓冲区中按照先 进先出的原则依次读取数据并打印,这样做即保证了打印 数据的正确性,又提高了主机的使用效率。由此可见,打 印机缓冲区实际上就是一个队列结构。 b. CPU分时系统 在一个带有多个终端的计算机系统中,同时有多个用户 需要使用CPU运行各自的应用程序,它们分别通过各自的 终端向操作系统提出使用CPU的请求,操作系统通常按照 每个请求在时间上的先后顺序,将它们排成一个队列,每 次把CPU分配给当前队首的请求用户,即将该用户的应用 程序投入运行,当该程序运行完毕或用完
  • 25. 规定的时间片后,操作系统再将CPU分配给新的队首请求 用户,这样即可以满足每个用户的请求,又可以使CPU正 常工作。
  • 26. 3.3.2 队列的顺序存储 队列的顺序存储结构如下图3-6所示:图 3-6012n-2n-1a1a2a3...an-1anfrontrear
  • 27. 顺序队的类型定义如下: define MAXSIZE 100 /*队列的最大容量*/ typedef struct {ElemType data[MAXSIZE]; /*队员的存储空间*/ int rear,front; /*队头队尾指针*/ }SeQueue; 定义一个指向队的指针变量: SeQueue *sq;
  • 28. front=0 rear=0123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定: rear指示队尾元素下一位置; front指示队头元素 初值front=rear=0空队列条件:front==rearrearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront队满条件:rear=MAXSIZE
  • 29. 问题1: 设数组维数为M,则: 当front=0,rear=M时,再有元素入队发生溢出——真溢出 当front0,rear=M时,再有元素入队发生溢出——假溢出 解决方案 循环队列 基本思想:把队列设想成环形,让sq->data[0]接在sq->data[M-1]之后,若rear==M,则令rear=0;0M-11frontrear…...…...实现:利用“模”运算 入队: sq->data[sq->rear]=x; sq->rear=(sq->rear+1)%M; 出队: *x=sq->data[sq->front]; sq->front=(sq->front+1)%M;
  • 30. 012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空:front==rear 队满:front==rear问题2:队满、队空判定条件解决方案: 另外设一个标志(num)以区别队空、队满
  • 31. 解决方法:浪费一个元素空间, 队满的条件:(rear+1)%MAXSIZE==front 队空的条件:front==rear 循环队列的类型定义: typedef struct { ElemType data[MAXSIZE]; /*数据的存储区*/ int front,rear; /*队头队尾指针*/ }CirQueue; /*循环队*/
  • 32. 各项基本操作算法。 ⑴ 置空队 CirQueue *InitCQueue() { CirQueue *q; q=(CirQueue *)malloc(sizeof(CirQueue)); q->front=q->rear=0; return q; }
  • 33. ⑵ 入队 int EnCQueue ( CirQueue *q , ElemType x) { if ((q->rear+1)%MAXSIZE==q->front) { printf("队满"); return 0; /*队满不能入队*/ } q->data[q->rear]=x; q->rear=(q->rear+1) % MAXSIZE; return 1; /*入队完成*/ }
  • 34. ⑶ 出队 int DeCQueue (CirQueue *q , ElemType *x) { if (q->front==q->rear) { printf("队空"); return 0; /*队空不能出队*/ } *x=q->data[q->front]; /*读出队头元素*/ q->front=(q->front+1) % MAXSIZE; return 1; /*出队完成*/ }
  • 35. 课堂练习1、完成循环队列的基本操作实现: 置空队:CirQueue *InitCQueue() 入队:int EnCQueue ( CirQueue *q , ElemType x) 出对:int DeCQueue (CirQueue *q , ElemType *x) 2、报数问题。设有n个人站成一排,从左至右的编号为1-n,现在从左往右“1 2 1 2 …”报数,数到1的人出列,数到2的人立即站到队伍的最右端。报数过程反复进行,直到n个人都出列为止。要求给出他们的出列顺序。如:n=8,初始序列为1 2 3 4 5 6 7 8 出列序列为1 3 5 7 2 6 4 8 。
  • 36. 3.3.3 队列的链式存储 在用链式存储结构表示队列时,需要设置队头指针和队尾指针,以便指示队头结点和队尾结点。
  • 37. 链队列 结点定义3.3.3队列 的存储实现及运算实现 typedef struct _node { ELEMTYPE data; struct _node * pNext; }Node; typedef struct _LinkedQueue { Node * pHead; Node *pRear; }LinkedQueue;头结点 ^…...q->front队头队尾q->rear头结点q->frontq->rear^
  • 38. 创建链式队列Node * CreateNode(ELEMTYPE data); LinkedQueue * CreateLinkedQueue();
  • 39. 链式队列的基本操作判空 int IsEmpty(LinkedQueue* pQueue); 入队 void EnQueue(LinkedQueue* pQueue, ElemType data); 出队 int DeQueue(LinkedQueue* pQueue, ElemType *data);
  • 40. 链队列基本运算实现(1)创建一个带头结点的空队头结点q->frontq->rear^(2)判队空(3)入队q->frontq->rearx入队^xq->frontq->reary入队x^y
  • 41. frontrearx出队x^yfrontreary出队^(4)出队
  • 42. 课堂练习1、完成链队列的基本操作实现: 置空队:LQueue *LQInit() 入队:int EnLQueue(LinkQueue *q , int x) 出队:int DelLQueue(LinkQueue *q , int *x) 2、编写队列管理的模拟算法,队列管理的模拟算法采用如下管理模式: (1)队列初始化为空队列 (2)当键盘输入奇数时,奇数入队列 (3)当键盘输入偶数时,队头出队列 (4)当键盘输入0时,退出算法 (5)每当键盘输入一个整数时,显示操作后队列中的值 3、写一算法,判断一个表达式中括号匹配问题。判断有n个字符的表达式exp括号是否匹配,正确返回1,错误返回0. 函数原型:int ExpIsCorrect(char exp[],int n)