3.2 栈的应用举例
3.2.5 表达式求值
? 算符优先法,
? 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8
? 操作数 (operand),进 OPND栈
? 操作符 (operator),进 OPTR栈
? 界限符 (delimiter):
算符间的优先关系,
? θ 1 θ 2 + - * / ( ) #
? + > > < < < > >
? - > > < < < > >
? * > > > > < > >
? / > > > > < > >
? ( < < < < < ≒
? ) > > > > > >
? # < < < < < =
Precede,判定运算符栈的栈顶运算符 θ 1与读入的运算符 θ 2之间
的优先关系的函数,
Operate,进行二元运算 aθ b的函数,
算术表达式求值过程 (算法 3.4)
OperandType EvaluateExpression()
? {InitStack(OPTR); Push(OPTR,?#?);
? InitStack(OPND); c = getchar();
? While(c!=?#?|| GetTop(OPTR)!=?#?){
? If(!In(c,OP)){ Push(OPND,c); c = getchar();} // 不是运算符则进栈
? else
? switch(Precede(GetTop(OPTR),c)){
? case?<?,// 栈顶元素优先权低
? Push(OPTR,c); c = getchar(); break;
? case?≒ ?,// 脱括号并接受下一个字符
? Pop(OPTR,x); c = getchar(); break;
? case?>?,// 退栈并将运算结果入栈
? Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a);
? Push(OPND,Operate(a,theta,b)); break;
? default:printf(“Expressionerror!”); return(ERROR);
? } // switch
? } // while
? return GetTop(OPND);
? } // EvaluateExpression
对算术表达式 3*(7-2) 求值,
? 步骤 OPTR栈 OPND栈 输入字符 主要操作
? 1 # 3 * ( 7 - 2 ) # Push(OPND,?3?)
? 2 # 3 * ( 7 - 2 ) # Push(OPTR,?*?)
? 3 # * 3 ( 7 - 2 ) # Push(OPTR,?(?)
? 4 # * ( 3 7 - 2 ) # Push(OPND,?7?)
? 5 # * ( 3 7 - 2 ) # Push(OPTR,?-?)
? 6 # * ( - 3 7 2 ) # Push(OPND,?2?)
? 7 # * ( - 3 7 2 ) # Operate(?7?,?-?,?2?)
? 8 # * ( 3 5 ) # POP(OPTR)
? 9 # * 3 5 # Operate(?3?,?*?,?5?)
? 10 # 15 # Return(GetTop(OPND))
例：汉诺塔问题：
将 a柱子上的盘移到 c柱，用 b柱放临时盘
要求：一次只能移动一个盘，大盘不可放于小盘上 。
a b c
hanoi塔问题
? 定义函数,movetower(n,a,c,b) n个盘 a－ >c,b放临时盘
? 分三步：
? movetower(n-1,a,b,c) 将 n-1个盘从 a->b,c放临时盘
? movedisk(a,n,c) 将第 n个盘从 a->c
? movetower(n-1,b,c,a) 将 n-1个盘从 b->c,a放临时盘
? void hanoi(int n,char a,char b,char c)
? {if (n==1) move(a,1,c);
? else{ hanoi(n-1,a,c,b);
? move(a,n,c);
? hanoi(n-1,b,a,c);
? }
? }
hanoi塔的递归算法
3.4 队列
3.4.1抽象数据类型队列的定义
? 队列 （ Queue）, 先进先出 (First In First Out)
? (缩写为 FIFO）的线性表。
? 仅在 队尾 进行插入和 队头 进行删除操作的线性表 。
?队头 （ front）, 线性表的表头端, 即可删除端 。
?队尾 （ rear）, 线性表的表尾端, 即可插入端 。
队头 对尾
......a1 a2 a3 an-1 an
入队列 (Enqueue)出队列 (Dequeque)
队列的抽象数据类型
?ADT Queue {
? 数 据 对 象, D = {ai | ai 属于 Elemset,
(i=1,2,…,n,n≥ 0)}
? 数据关系, R1 = { ＜ ai-1,ai ＞ |ai-1,ai 属于
D,(i=2,3,…,n)} 约定 an为队尾,a1为队头 。
? 基本操作,
? InitQueue(&Q); DestroyQueue (& Q);
? ClearQueue (& Q); QueueEmpty(Q);
? QueueLength(Q) ; GetHead(Q,&e);
? EnQueue (& Q,e); DeQueue (& Q,&e);
? QueueTraverse(Q,visit ())
?}ADT Queue
队列的 基本操作 (之一 )
?InitQueue (&Q)
? 操作结果,构造一个空的队列 Q。
?DestroyQueue (&Q)
? 初始条件, 队列 Q已经存在。
? 操作结果, 销毁队列 Q。
?ClearQueue (&Q)
? 初始条件, 队列 Q已经存在。
? 操作结果, 将队列 Q重置为空队列。
队列的 基本操作 (之二 )
?QueueEmpty(Q)
? 初始条件, 队列 Q已经存在。
? 操作结果, 若队列 Q为空队列，则返回 TURE;
否则返回 FALSE。
?QueueLength(Q)
? 初始条件, 队列 Q已经存在。
? 操作结果, 返回队列 Q中的数据元素个数,即队列 Q的长度。
?GetHead(Q,&e)
? 初始条件, 队列 Q已经存在且非空。
? 操作结果, 用 e返回队列 Q中队头元素的值。
队列的 基本操作 (之三 )
?EnQueue (&Q,e)
? 初始条件, 队列 Q已经存在 。
? 操作结果, 插入元素 e为新的队尾元素 。
?DeQueue (&Q,&e)
? 初始条件, 队列 Q已经存在且非空 。
? 操作结果, 删除队列 Q 的队头元素并用 e返回其值 。
?QueueTraverse(Q,visit ())
? 初始条件, 队列 Q已经存在且非空 。
? 操作结果, 从队头到队尾依次对队列 Q的每个元素调用函数 visit ()。 一旦 visit ()失败, 则操作失
败 。
3.4.2 链队列 --
队列的链式表示与实现
? typedef struct QNode{
? QElemType data;
? struct QNode *next;
? }Qnode,*QueuePtr;
? typedef struct {
? QueuePtr front; // 队头指针
? QueuePtr rear; // 队尾指针
? }LinkQueue;
? #define OK 1
? #define OVERFLOW -1
? #define ERROR 0
data *next
front
rear
链队列 示意图
front
rear
front
rear
赵
front
rear
钱赵
front
rear
钱赵
(a)空队列 (b)元素“赵”入队列
(c)元素“钱”入队列
(d)元素“赵”出队列
链队列 的操作实现举例
/* InitQueue 构造一个空的队列 Q*/
?Status InitQueue(LinkQueue &Q)
? { Q.rear=(QueuePtr)malloc(sizeof(QNode) );
? Q.front = Q.rear;
? if(!Q.front) return(OVERFLOW);
? Q.front -> next = NULL;
? return OK;
? } // InitQueue
链队列 的操作实现 (DestroyQueue)
// 销毁队列 Q
?Status DestroyQueue(LinkQueue &Q)
?{ while(Q.front ){
? Q.rear = Q.front -> next;
? free(Q.front);
? Q.front = Q.rear;
? }
? return OK;
?} // DestroyQueue
链 队 列 的 操 作 实 现 (EnQueue)
// 插入元素 e为新的队尾元素
?Status EnQueue(LinkQueue &Q,QelemType e)
? { p = ( QueuePtr )malloc(sizeof(QNode));
? if(!p) return(OVERFLOW);
? p->data = e;
? p -> next = NULL;
? Q.rear ->next = p;
? Q.rear = p;
? return OK;
? } // EnQueue
链 队 列 的 操 作 实 现 (DeQueue)
// 若队列不空,删除队列 Q 的队头元素并用 e返回
其值,同时返回 OK; 否则返回 ERROR 。
?Status DeQueue(LinkQueue &Q,QelemType &e)
? { if(Q.front == Q.rear) retrun 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;
? } // DeQueue
3.4.3 循环队列 --
队列的顺序表示与实现
? 采用顺序存储结构
? 约定,1)初始空队列,front = rear=0 ;
? 2)插入新的元素时,rear++;
? 3)删除队头元素时,front++;
J1
J2
J3
Q.front
Q.rear
J3Q.front
Q.rear
J5
J6
Q.front
Q.rear
Q.rear
Q.front
1
0
2
3
5
4
循环列表 ----
解决 数组越界但未占满空间 的办法
1
0
maxsize-1
...
Q.frontQ.rear
...
队列
当 Q.rear > Q.front时, Q.rear – Q.front = 队列中元素个数
当 Q.rear < Q.front时, Q.rear – Q.front +maxsize = 队列中元素个数
当 Q.rear = Q.front时, 队列是’空’或’满’
循环队列的头尾指针
0
123
4 5
J3
J4
J5 Q.rear
Q.front
(a)一般队列
0
123
4 5
Q.rear
Q.front
(c)空队列
J6
J3
J4
J5
0
123
4 5
J7
J8
Q.rear
Q.front
(b)满队列
循环队列 --
队列的顺序存储结构实现 (1)
? typedef struct {
? QElemType *base; // 存储空间基地址
? int front; // 队头指针
? int rear; // 队尾指针
? }SqQueue;
? #define MAXSIZE 100
? Status InitQueue(SqQueue &Q)
? {Q.base=(QElemType*)malloc(sizeof(QElemType)
? *MAXSIZE );
? if(!Q.base) return(OVERFLOW);
? Q.front = Q.rear = 0;
? return OK;
? } // InitQueue
循环队列 --
队列的顺序存储结构实现 (2)
?Status EnQueue(SqQueue &Q,QelemType e)
? {
? if((Q.rear+1)% MAXSIZE == Q.front)
return(ERROR);
? Q.base[Q.rear] = e;
? Q.rear = (Q.rear+1) % MAXSIZE;
? return OK;
? } // EnQueue
循环队列 --
队列的顺序存储结构实现 (3)
?Status DeQueue(SqQueue &Q,QelemType &e)
? {
? if(Q.front == Q.rear) retrun ERROR;
? e = Q.base[Q.front];
? Q.front = (Q.front+1) % MAXSIZE;
? return OK;
? } // DeQueue
实验与习题
?理论习题 3.7,3.11,3.13,3.18
?实验题,
? ① 写一个主程序来 上机验证顺序存储结构 --
循环队列的基本操作 ；
? ② 3.18
3.2.5 表达式求值
? 算符优先法,
? 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8
? 操作数 (operand),进 OPND栈
? 操作符 (operator),进 OPTR栈
? 界限符 (delimiter):
算符间的优先关系,
? θ 1 θ 2 + - * / ( ) #
? + > > < < < > >
? - > > < < < > >
? * > > > > < > >
? / > > > > < > >
? ( < < < < < ≒
? ) > > > > > >
? # < < < < < =
Precede,判定运算符栈的栈顶运算符 θ 1与读入的运算符 θ 2之间
的优先关系的函数,
Operate,进行二元运算 aθ b的函数,
算术表达式求值过程 (算法 3.4)
OperandType EvaluateExpression()
? {InitStack(OPTR); Push(OPTR,?#?);
? InitStack(OPND); c = getchar();
? While(c!=?#?|| GetTop(OPTR)!=?#?){
? If(!In(c,OP)){ Push(OPND,c); c = getchar();} // 不是运算符则进栈
? else
? switch(Precede(GetTop(OPTR),c)){
? case?<?,// 栈顶元素优先权低
? Push(OPTR,c); c = getchar(); break;
? case?≒ ?,// 脱括号并接受下一个字符
? Pop(OPTR,x); c = getchar(); break;
? case?>?,// 退栈并将运算结果入栈
? Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a);
? Push(OPND,Operate(a,theta,b)); break;
? default:printf(“Expressionerror!”); return(ERROR);
? } // switch
? } // while
? return GetTop(OPND);
? } // EvaluateExpression
对算术表达式 3*(7-2) 求值,
? 步骤 OPTR栈 OPND栈 输入字符 主要操作
? 1 # 3 * ( 7 - 2 ) # Push(OPND,?3?)
? 2 # 3 * ( 7 - 2 ) # Push(OPTR,?*?)
? 3 # * 3 ( 7 - 2 ) # Push(OPTR,?(?)
? 4 # * ( 3 7 - 2 ) # Push(OPND,?7?)
? 5 # * ( 3 7 - 2 ) # Push(OPTR,?-?)
? 6 # * ( - 3 7 2 ) # Push(OPND,?2?)
? 7 # * ( - 3 7 2 ) # Operate(?7?,?-?,?2?)
? 8 # * ( 3 5 ) # POP(OPTR)
? 9 # * 3 5 # Operate(?3?,?*?,?5?)
? 10 # 15 # Return(GetTop(OPND))
例：汉诺塔问题：
将 a柱子上的盘移到 c柱，用 b柱放临时盘
要求：一次只能移动一个盘，大盘不可放于小盘上 。
a b c
hanoi塔问题
? 定义函数,movetower(n,a,c,b) n个盘 a－ >c,b放临时盘
? 分三步：
? movetower(n-1,a,b,c) 将 n-1个盘从 a->b,c放临时盘
? movedisk(a,n,c) 将第 n个盘从 a->c
? movetower(n-1,b,c,a) 将 n-1个盘从 b->c,a放临时盘
? void hanoi(int n,char a,char b,char c)
? {if (n==1) move(a,1,c);
? else{ hanoi(n-1,a,c,b);
? move(a,n,c);
? hanoi(n-1,b,a,c);
? }
? }
hanoi塔的递归算法
3.4 队列
3.4.1抽象数据类型队列的定义
? 队列 （ Queue）, 先进先出 (First In First Out)
? (缩写为 FIFO）的线性表。
? 仅在 队尾 进行插入和 队头 进行删除操作的线性表 。
?队头 （ front）, 线性表的表头端, 即可删除端 。
?队尾 （ rear）, 线性表的表尾端, 即可插入端 。
队头 对尾
......a1 a2 a3 an-1 an
入队列 (Enqueue)出队列 (Dequeque)
队列的抽象数据类型
?ADT Queue {
? 数 据 对 象, D = {ai | ai 属于 Elemset,
(i=1,2,…,n,n≥ 0)}
? 数据关系, R1 = { ＜ ai-1,ai ＞ |ai-1,ai 属于
D,(i=2,3,…,n)} 约定 an为队尾,a1为队头 。
? 基本操作,
? InitQueue(&Q); DestroyQueue (& Q);
? ClearQueue (& Q); QueueEmpty(Q);
? QueueLength(Q) ; GetHead(Q,&e);
? EnQueue (& Q,e); DeQueue (& Q,&e);
? QueueTraverse(Q,visit ())
?}ADT Queue
队列的 基本操作 (之一 )
?InitQueue (&Q)
? 操作结果,构造一个空的队列 Q。
?DestroyQueue (&Q)
? 初始条件, 队列 Q已经存在。
? 操作结果, 销毁队列 Q。
?ClearQueue (&Q)
? 初始条件, 队列 Q已经存在。
? 操作结果, 将队列 Q重置为空队列。
队列的 基本操作 (之二 )
?QueueEmpty(Q)
? 初始条件, 队列 Q已经存在。
? 操作结果, 若队列 Q为空队列，则返回 TURE;
否则返回 FALSE。
?QueueLength(Q)
? 初始条件, 队列 Q已经存在。
? 操作结果, 返回队列 Q中的数据元素个数,即队列 Q的长度。
?GetHead(Q,&e)
? 初始条件, 队列 Q已经存在且非空。
? 操作结果, 用 e返回队列 Q中队头元素的值。
队列的 基本操作 (之三 )
?EnQueue (&Q,e)
? 初始条件, 队列 Q已经存在 。
? 操作结果, 插入元素 e为新的队尾元素 。
?DeQueue (&Q,&e)
? 初始条件, 队列 Q已经存在且非空 。
? 操作结果, 删除队列 Q 的队头元素并用 e返回其值 。
?QueueTraverse(Q,visit ())
? 初始条件, 队列 Q已经存在且非空 。
? 操作结果, 从队头到队尾依次对队列 Q的每个元素调用函数 visit ()。 一旦 visit ()失败, 则操作失
败 。
3.4.2 链队列 --
队列的链式表示与实现
? typedef struct QNode{
? QElemType data;
? struct QNode *next;
? }Qnode,*QueuePtr;
? typedef struct {
? QueuePtr front; // 队头指针
? QueuePtr rear; // 队尾指针
? }LinkQueue;
? #define OK 1
? #define OVERFLOW -1
? #define ERROR 0
data *next
front
rear
链队列 示意图
front
rear
front
rear
赵
front
rear
钱赵
front
rear
钱赵
(a)空队列 (b)元素“赵”入队列
(c)元素“钱”入队列
(d)元素“赵”出队列
链队列 的操作实现举例
/* InitQueue 构造一个空的队列 Q*/
?Status InitQueue(LinkQueue &Q)
? { Q.rear=(QueuePtr)malloc(sizeof(QNode) );
? Q.front = Q.rear;
? if(!Q.front) return(OVERFLOW);
? Q.front -> next = NULL;
? return OK;
? } // InitQueue
链队列 的操作实现 (DestroyQueue)
// 销毁队列 Q
?Status DestroyQueue(LinkQueue &Q)
?{ while(Q.front ){
? Q.rear = Q.front -> next;
? free(Q.front);
? Q.front = Q.rear;
? }
? return OK;
?} // DestroyQueue
链 队 列 的 操 作 实 现 (EnQueue)
// 插入元素 e为新的队尾元素
?Status EnQueue(LinkQueue &Q,QelemType e)
? { p = ( QueuePtr )malloc(sizeof(QNode));
? if(!p) return(OVERFLOW);
? p->data = e;
? p -> next = NULL;
? Q.rear ->next = p;
? Q.rear = p;
? return OK;
? } // EnQueue
链 队 列 的 操 作 实 现 (DeQueue)
// 若队列不空,删除队列 Q 的队头元素并用 e返回
其值,同时返回 OK; 否则返回 ERROR 。
?Status DeQueue(LinkQueue &Q,QelemType &e)
? { if(Q.front == Q.rear) retrun 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;
? } // DeQueue
3.4.3 循环队列 --
队列的顺序表示与实现
? 采用顺序存储结构
? 约定,1)初始空队列,front = rear=0 ;
? 2)插入新的元素时,rear++;
? 3)删除队头元素时,front++;
J1
J2
J3
Q.front
Q.rear
J3Q.front
Q.rear
J5
J6
Q.front
Q.rear
Q.rear
Q.front
1
0
2
3
5
4
循环列表 ----
解决 数组越界但未占满空间 的办法
1
0
maxsize-1
...
Q.frontQ.rear
...
队列
当 Q.rear > Q.front时, Q.rear – Q.front = 队列中元素个数
当 Q.rear < Q.front时, Q.rear – Q.front +maxsize = 队列中元素个数
当 Q.rear = Q.front时, 队列是’空’或’满’
循环队列的头尾指针
0
123
4 5
J3
J4
J5 Q.rear
Q.front
(a)一般队列
0
123
4 5
Q.rear
Q.front
(c)空队列
J6
J3
J4
J5
0
123
4 5
J7
J8
Q.rear
Q.front
(b)满队列
循环队列 --
队列的顺序存储结构实现 (1)
? typedef struct {
? QElemType *base; // 存储空间基地址
? int front; // 队头指针
? int rear; // 队尾指针
? }SqQueue;
? #define MAXSIZE 100
? Status InitQueue(SqQueue &Q)
? {Q.base=(QElemType*)malloc(sizeof(QElemType)
? *MAXSIZE );
? if(!Q.base) return(OVERFLOW);
? Q.front = Q.rear = 0;
? return OK;
? } // InitQueue
循环队列 --
队列的顺序存储结构实现 (2)
?Status EnQueue(SqQueue &Q,QelemType e)
? {
? if((Q.rear+1)% MAXSIZE == Q.front)
return(ERROR);
? Q.base[Q.rear] = e;
? Q.rear = (Q.rear+1) % MAXSIZE;
? return OK;
? } // EnQueue
循环队列 --
队列的顺序存储结构实现 (3)
?Status DeQueue(SqQueue &Q,QelemType &e)
? {
? if(Q.front == Q.rear) retrun ERROR;
? e = Q.base[Q.front];
? Q.front = (Q.front+1) % MAXSIZE;
? return OK;
? } // DeQueue
实验与习题
?理论习题 3.7,3.11,3.13,3.18
?实验题,
? ① 写一个主程序来 上机验证顺序存储结构 --
循环队列的基本操作 ；
? ② 3.18
