数据结构queue计算机导论 编辑母版

1、第三章 栈和队列北理计算机学院北理计算机学院通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表线性表。Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)1in+1Delete(L, i) Delete(S, n) Delete(Q, 1)1in线性表 栈 队列栈和队列是两种常用的数据类型3.1 3.1 栈的类型定义3.2 3.2 栈的应用举例3.3 3.3 栈类型的实现3.4 3.4 队列的类型定义3.5 3.5 队列类型的实现3.1 栈的类型定义ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1

2、,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作基本操作： ADT StackInitStack(&S) DestroyStack(&S)ClearStack(&S) StackEmpty(s)StackLength(S) GetTop(S, &e)Push(&S, e) Pop(&S, &e)StackTravers(S, visit() InitStack(&S)操作结果操作结果：构造一个空栈S。 DestroyStack(&S)初

3、始条件初始条件：栈S 已存在。操作结果操作结果：栈S 被销毁。 StackEmpty(S)初始条件初始条件：栈S 已存在。操作结果操作结果：若栈S 为空栈，则返回TRUE，否则FALE。 StackLength(S)初始条件初始条件：栈S 已存在。操作结果操作结果：返回S 的元素个数，即栈的长度。 GetTop(S, &e)初始条件初始条件：栈S 已存在且非空。操作结果操作结果：用e 返回S 的栈顶元素。 ClearStack(&S)初始条件初始条件：栈S 已存在。操作结果操作结果：将S 清为空栈。 Push(&S, e)初始条件初始条件：栈S 已存在。操作结果操作结果

4、：插入元素e 为新的栈顶元素。 Pop(&S, &e)初始条件初始条件：栈S 已存在且非空。操作结果操作结果：删除S 的栈顶元素，并用e 返回其值。3.2 栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归例一、数制转换算法基于原理：N = (N div d)d + N mod d例如：（1348)10 = (2504)8 ，其运算过程如下：void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!

5、StackEmpty(S) Pop(S,e); printf ( %d, e ); DestroyStack(S); / / conversion例二、括号匹配的检验假设在表达式中（）或（ ）等为正确的格式，（ ）或（ ）或（）)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8分析可能出现的不匹配不匹配的情况: 到来的右括弧并非是所“期待”的； 直到结束，也没有到来所“期待” 的括弧。算法的设计思想：1 1）凡出现左括弧左括弧，则进栈进栈；2 2）凡出现右括弧右括弧，首先检查栈是否空 若栈空栈空，则

6、表明该“右括弧”多余， 否则和栈顶元素和栈顶元素比较， 若相匹配相匹配，则“左括弧出栈左括弧出栈” ， 否则表明不匹配。不匹配。3 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确，匹配正确， 否则表明“左括弧”有余。例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器” ?并不恰当！ 在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正合理的作法是： 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符。假设从终端接受了这样两行字符：whli#ilr#e（s#*s) outchaputchar(*s=#+);

7、则实际有效的是下列两行：while (*s) putchar(*s+);while (ch != EOF) /EOF为全文结束符 while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符 将从栈底到栈顶的字符传送至调用过程的数据区；ClearStack(S); / 重置S为空栈if if (ch != EOF!= EOF)

8、 ch = getchar();例四、迷宫求解书上的方法复杂，可以用递归的方法实现例五、表达式求值限于二元运算符的表达式定义限于二元运算符的表达式定义:表达式:= (操作数) + (运算符) + (操作数)操作数:= 简单变量| 表达式简单变量: = 标识符| 无符号整数表达式的三种标识方法：设 Exp = S1 + OP + S2则称 OP + S1 + S2 为前缀表示法S1 + OP + S2 为中缀表示法S1 + S2 + OP 为后缀表示法中缀表达式的求值： 5+6(1+2)-45 + 6 (1 + 2) - 4=5+63- 4 = 5+18-4= 23-4=19利用栈进行表达式求值

9、A+B*C 1 D 2 算符优先关系表12 表达式求值从左向右扫描表达式： 5+65+6(1+2)-4(1+2)-4 遇操作数保存； 遇运算符号2与前面的运算符1比较 若12 则1可进行运算； 若1=2 需要消去括号；表达式求值示意图（算符优先算法）读入表达式：5+6 ( 1+ 2 )-4 #1+2=363=185+18=2323-4=19算符优先算法OperandType EvaluateExpression( )OperandType EvaluateExpression( ) /算术表达式求值的算符优先算法。设OPTROPTR和OPNDOPND分别为运算符栈和操作数栈，OPOP为运算符集

10、合InitStack(OPTR); Push (OPTR, #);InitStack(OPTR); Push (OPTR, #);InitStack(OPND); c=getchar( );InitStack(OPND); c=getchar( );while(c!=while(c!= # # | GetTop(OPTR)!= | GetTop(OPTR)!=# #)if (!In (c, OP) if (!In (c, OP) /操作数进栈OPNDOPND Push(OPND, c); c=getchar( ) Push(OPND, c); c=getchar( )elseelse swit

11、ch (Precede(GetTop(OPTR), c) case : Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /if/whilereturn GetTop(OPND); /EvaluateExpression例六、实现递归当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务： 将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。从被调用函数返回调用

12、函数之前，应该完成下列三项任务： 保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。多个函数嵌套调用的规则是： 后调用先返回！后调用先返回！此时的内存管理实行“栈式管理”例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区 递归函数执行的过程可视为同一函数进行嵌套调用void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，

13、y可用作辅助塔座。1 if (n=1)2 move(x, 1, z); / 将编号为的圆盘从x移到z3 else 4 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔5 move(x, n, z); / 将编号为n的圆盘从x移到z6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔7 8 3.3 栈类型的实现顺序栈链栈 类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。/- 栈的顺序存储表示-#define STACK_INIT_SIZE 100#define STACKINCREMENT

14、 10typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; basetop basetop Abasetop大家请注意：大家请注意：toptop指针的位置指针的位置 B Abasetop B AbasetopStatus InitStack (SqStack &S) / 构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE* sizeof(SElemType); if (!S.base) exit (OVERFLOW); /存储分配失败S.top =

15、S.base;S.stacksize = STACK_INIT_SIZE;return OK;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.st

16、acksize += STACKINCREMENT; *S.top+ = e; return OK;Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;链栈DCBAtop3.4 队列的类型定义ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i

17、=2,.,n 约定其中a1 端为队列头， an 端为队列尾 基本操作：基本操作： ADT Queue队列的基本操作：队列的基本操作：InitQueue(&Q) DestroyQueue(&Q)QueueEmpty(Q) QueueLength(Q)GetHead(Q, &e) ClearQueue(&Q)DeQueue(&Q, &e) EnQueue(&Q, e)QueueTravers(Q, visit()InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结

18、果：队列Q被销毁， 不再存在。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSEQueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q, &e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。EnQueue(&Q, e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q, &e)初始条件：Q为非空队列。操作结果：删除Q的队

19、头元素，并用e返回其值。3.5 队列类型的实现链队列链式映象循环队列顺序映象链队列链队列链式映象链式映象typedef struct QNode / 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;链队列链队列链式映象链式映象Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr

20、)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK;Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素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;Statu

21、s DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用e 返回其值;并返回OK;否则返回ERROR 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;队列队列顺序映象顺序映象#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType

22、*base; / 动态分配存储空间 int front; / 头指针，若队列不空， /指向队列头元素队列头元素 int rear; / 尾指针，若队列不空，指向 /队列尾元素的下一个位置下一个位置 SqQueue;Status Status InitQueue (SqQueue & &Q) / 构造一个空队列Q Q.base = (ElemType * *) mallocmalloc (MAXQSIZE *sizeof sizeof (ElemType); if if (! !Q.base) exit exit (OVERFLOW); / 存储分配失败 Q.front = Q.

23、rear = 0; return return OK; Q.rear=(Q.rear+1)%MAXQSIZEQ.front=(Q.front+1)% MAXQSIZE循环队列判空、判满的方法及条件循环队列判空、判满的方法及条件 另设标志 少用一个存储单元判满条件(Q.rear+1)%MAXQSIZE = =Q.front判空条件Q.rear = =Q.frontStatus EnQueue (SqQueue &Q, ElemType e) / 插入元素e为Q的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /队列满 Q.

24、baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;Status DeQueue (SqQueue &Q,ElemType &e) / 若队列不空，则删除Q的队头元素， /用e返回其值,并返回OK;否则返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;本章学习要点 1. 1. 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。2. 2. 熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。 3. 3. 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法 4. 4. 理解递归算法执行过程中栈的状态变化过程。1、已知一堆栈的进栈序列为：、已知一堆栈的进栈序列为：1234，则下列哪个序，则下列哪个序列为不可能的出栈序列：列为不可能的出栈序