当前位置:首页 >> 工学 >>

严蔚敏数据结构课件03:栈和队列


第3章 栈和队列
3.1 3.2 3.3 3.4 栈 栈的应用举例 栈与递归的实现 队列

2011-3-12

第3章

1

3.1 栈 ( Stack )
1.定义:限定只在表的一端(表尾) 1.定义:限定只在表的一端(表尾)进行 定义 插入和删除操作的线性表 特点:后进先出(LIFO) 特点:后进先出(LIFO) 允许插入和删除 的一端称为栈顶 的一端称为栈顶 (top),另一端称 top) 栈底(bottom) 为栈底(bottom)

表尾

表头

2. 栈的表示和实现
1)顺序栈——栈的顺序存储结构

2)链栈——栈的链式存储结构

3)静态分配整型指针

1)顺序栈——栈的顺序存储结构
限定在表尾进行插入和删除操作的顺序表 类型定义: p46 typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; SqStack s;

说明:
base称为栈底指针,始终指向栈底; 当base = NULL时,表明栈结构不存在。 top为栈顶指针 a. top的初始值指向栈底,即top=base b. 空栈:当top=base时为栈空的标记 c. 当栈非空时,top的位置:指向当前栈 顶元素的下一个位置 stacksize ——当前栈可使用的最大容量

进栈示例
stacksize

base

base

base

base

base

退栈示例

base

base

base

base

base

几点说明:
栈空条件:s. top =s. base 此时不能出栈 栈满条件:s.top-s.base>=s.stacksize 进栈操作:*s.top++=e; 或*s.top=e; s.top++; 退栈操作:e=*--s.top; 或s.top--; e=*s.top; e=*--s.top s.top-- e=*s.top 当栈满时再做进栈运算必定产生空间溢出, 简称“上溢”; 当栈空时再做退栈运算也将产生溢出,简 称“下溢”。

栈练习:
若借助栈由输入序列1、2、…n得到的输出序列 为p1、p2、p3、…pn(它是输出序列的一个排 列),则在输出序列中不可能出现这样的情形: 存在着i<j<k使pj<pk<pi。(练习册p23) 讲解:举例(a、b、c)不可能-》c、a、b 某栈的输入序列为1、2、3…n,输出序列的第 一个元素为n,则第i个元素为( ) A i B N-i C N-i+1 D 哪个元素无所谓 (北航2002 -四分)

基本操作的实现(详见stack.c)
栈的初始化操作 p47 Status InitStack(SqStack &S) 取栈顶元素 p47 Status GetTop(SqStack S, SElemType &e) 进栈操作 p47 Status Push(SqStack &S, SElemType e) 退栈操作 p47 Status Pop(SqStack &S, SElemType &e)

栈的初始化操作 p47
Status InitStack (SqStack &S) {
S.base = (SElemType )malloc(STACK_INIT_SIZE * sizeof(ElemType));

if (!S.base) return (OVERFLOW); S.top=S.base; S.stacksize = STACK_INIT_SIZE; return OK; }

取栈顶元素

p47

Status GetTop(SqStack S, SElemType &e) { if (S.top == S.base) return ERROR; e = *(S.top-1); 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(ElemType));

p47

if (!S.base) return (OVERFLOW); S.top = S.base +S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; /* *S.top = e; S.top = S.top+1; return OK; }

退栈操作

p47

Status Pop(SqStack &S, SElemType &e) { if (S.top == S.base) return ERROR; e=*--S.top; /* S.top= S.top;-1; e=*S.top; return OK; }

2)链栈——栈的链式存储结构
不带头结点的单链表,其插入和删除操 作仅限制在表头位置上进行。链表的头 指针即栈顶指针。 类型定义: typedef struct SNode{ SElemType data; struct SNode *next; }SNode, *LinkStack; LinkStack s;

链栈示意图 p47 图3.3

栈空条件: s=NULL 栈满条件: 无 / 无Free Memory可申请

进栈操作:
Status Push_L (LinkStack &s,SElemType e) { p=(LinkStack)malloc(sizeof(SNode)); if (!p) exit(Overflow); p->data = e; p->next = s; s=p; return OK; }

退栈操作
Status Pop_L (LinkStack &s, SElemType &e) { if (!s) return ERROR; e=s->data; p=s; s=s->next; free(p); return OK; }

3)静态分配整型指针
定义 #define MAXSIZE 100 typedef struct { SElemType base[MAXSIZE]; int top; }SqStack; SqStack s;

初始化
status InitStack(SqStack &s) { s.top = 0; return OK; }

进栈
Status Push(SqStack &s,SElemType e) { if (s.top == MAXSIZE) return ERROR; s.base[s.top] = e; s.top++; return OK; }

退栈
Status Pop(SqStack &s,SElemType &e) { if (s.top ==0) return ERROR; s.top--; e=s.base[s.top]; return OK; }

取栈顶元素
Status GetTop(SqStack s, SElemType &e) { if (s.top == 0) return ERROR; e=s.base[s.top-1]; return OK; }

3.2 栈的应用
1. 数制转换 p48 算法3.1 2. 行编辑程序 p50 算法3.2 3. 表达式求值 p52 ~ p54 4. 把求n!的递归算法转化为非递归算法

1. 数制转换

p48

十进制N和其它进制数的转换是计算机实现计 的基本问题,基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8,其运算过程如下: n n div 8 n mod 8 低位 1348 168 4 168 21 0 21 2 5 高位 2 0 2

算法3.1
要求:输入一个非负十进制整数,输出任意进制数 void Conversion() { InitStack(s); scanf("%d,%d",&N,&base); N1=N; while (N1) { Push(s,N1%base); N1 = N1/base; } while (!(StackEmpty(s)) { Pop(s,e); printf("%c",e+48); } printf("\n"); }

void lineedit( ) { initstack(s); ch=getchar( ); while(ch!=eof) { while(ch!=eof && ch!=‘\n’) { switch(ch) { case ‘#’ : pop(s,c); case ‘@’ : clearstack(s); default : push(s,ch); } ch=getchar( ); } 将栈内字符送到调用过程的数据区; clearstack(s); if(ch!=eof) ch=gethar( ); } destroystack(s); }

2. 行编辑程序 p50 算法3.2 (自学)

3. 表达式求值 p52 ~ p54(自学)
算符间的优先级关系 p52 ~ p53 先括弧内后括弧外 左括号:比括号内的算符的优先级低 比括号外的算符的优先级高 右括号:比括号内的算符的优先级低 比括号外的算符的优先级高 #:优先级总是最低 为实现算符优先算法,可使用两个工作栈: OPND栈:存数据或运算结果 OPTR栈:存运算符

1.初态: 置OPND栈为空;将“#”作为OPTR栈的栈底元素 2.依次读入表达式中的每个字符 1)若是操作数,则进入OPND栈; 2)若是运算符,则与OPTR栈的栈顶运算符进行优先权(级) 的比较:

算法思想:

若读入运算符的优先权高,则进入OPTR栈; 若读入运算符的优先权低,则OPTR退栈(退出 原有的栈顶元素),OPND栈退出两个元素 (先退出b,再退出a),中间结果再进入OPND栈; 若读入“)”,OPTR栈的原有栈的栈顶元素若为 “(”,则OPTR退出“(”; 若读入“#”,OPTR栈栈顶元素也为“#”,则OPTR 栈退出“#”,结束。
例:3*(7-2)详见动画演示(pascal语言)

把求n!的递归算法转化为非递归算法
递归算法: int recursion(selemtype n){ if(n==0||n==1)return 1; else return n*recursion(n-1); } 非递归算法: (详见ky-p47-n!.c)

3.4 队列
1. 定义 2. 链队列----队列的链式存储结构 3. 循环队列----队列的顺序存储结构

1. 定义
是限定在表的一端进行删除,在表的另一端进行插 是限定在表的一端进行删除, 入操作的线性表。 入操作的线性表。 允许删除的一端叫做队头(front),允许插入的一端 , 允许删除的一端叫做队头 叫做队尾(rear)。 叫做队尾 。 特性:FIFO(First In First Out) 特性: 图示 p59
表头 表尾

2. 链队列——队列的链式存储结构
实质是带头结点的线性链表; 两个指针:
队头指针Q.front指向头结点 队尾指针Q.rear指向尾结点 Q.rear

初始态:队空条件
头指针和尾指针均指向头结点 Q.front = Q.rear

typedef struct QNode { //元素结点 QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct{ //特殊结点 QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue; LinkQueue Q; Q.front——指向头结点 Q.rear ——指向链尾结点

1)链队列的类型定义 p61

2)链队列示意图 p61图3.10

队列运算指针变化状况
空队列

3)基本操作与实现
初始化 p62 Status InitQueue (LinkQueue &Q) 销毁队列 p62 Status DestroyQueue (LinkQueue &Q) 入队 p62 Status EnQueue(LinkQueue &Q, QElemType e) 出队 p62 Status DeQueue(LinkQueue &Q, QElemType &e) 判队空 Status QueueEmpty(LinkQueue Q) 取队头元素 Status GetHead(LinkQueue Q,QElemType &e)

链队列初始化
Status InitQueue (LinkQueue &Q) {
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit(OVERFLOW); Q.front->next=NULL; return OK;

}

链队列的销毁
Status DestroyQueue (LinkQueue &Q) { while (Q.front) { Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } return OK; }

链队列的插入(入队)
Status EnQueue (LinkQueue &Q, QElemType e) { p=(QueuePtr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; }

链队列的删除(出队)
Status DeQueue (LinkQueue &Q, ElemType &e) { 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; }

判断链队列是否为空
Status QueueEmpty(LinkQueue Q) { if (Q.front==Q.rear) return TRUE; return FALSE; }

取链队列的第一个元素结点
Status GetHead(LinkQueue Q,QElemType &e) { if (QueueEmpty(Q)) return ERROR; e=Q.front->next->data; return OK; }

3. 循环队列——队列的顺序存储结构
顺序队列:
? 用一组地址连续的存储单元依次存放从队列 头到队列尾的元素

设两个指针:
? Q.front 指向队列头元素; ? Q.rear 指向队列尾元素的下一个位置

初始状态(空队列):
? Q.front = Q.rear=0

队列的真满与假满

类型定义 p64 #define MAXSIZE 100 typedef struct { QElemType *base; int front; int rear; }SqQueue; SqQueue Q;

队列的进队和出队

进队时,将新元素按Q.rear 指示位置加入, 进队时,将新元素按Q.rear 指示位置加入,再 将队尾指针增1 Q.rear 将队尾指针增1, Q.rear = Q.rear + 1 。 出队时,将下标为Q.front 的元素取出, 出队时,将下标为Q.front 的元素取出,再将队 头指针增1 Q.front 头指针增1, Q.front = Q.front + 1 。 队满时再进队将溢出出错; 队满时再进队将溢出出错;队空时再出队作队 空处理。上图为“假满” 空处理。上图为“假满”

循环队列 (Circular Queue)
存储队列的数组被当作首尾相接的表处理。 存储队列的数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize 直接进到0 队头、队尾指针加1时从maxSize -1直接进到0,可用 语言的取模(余数)运算实现。 语言的取模(余数)运算实现。 队头指针进1 Q.front (Q.front 队头指针进1: Q.front = (Q.front + 1)% MAXSIZE 队尾指针进1: Q.rear (Q.rear MAXSIZE; 队尾指针进1: Q.rear = (Q.rear + 1)% MAXSIZE; 队列初始化:Q.front Q.rear 队列初始化:Q.front = Q.rear = 0; 队空条件:Q.front Q.rear; 队空条件:Q.front == Q.rear; 队满条件:(Q.rear 队满条件:(Q.rear + 1) % MAXSIZE == Q.front 少用了一个空间,以区别队空的状态 队列长度:(Q.rear-Q.front+MAXSIZE)%MAXSIZE

循环队列的进队和出队

说明
不能用动态分配的一维数组来实现循环队列, 初始化时必须设定一个最大队列长度。 循环队列中要有一个元素空间浪费掉 ----p63 约定队列头指针在队列尾指针的下一位置上为 “满”的标志 解决 Q.front=Q.rear不能判别队列“空”还是 “满”的其他办法:
? 使用一个计数器记录队列中元素的总数(即队列长 度) ? 设一个标志变量以区别队列是空或满

基本操作
初始化 p64 Status InitQueue (SqQueue &Q) 求队列的长度 p64 int QueueLength(SqQueue Q) 入队 p65 Status EnQueue (SqQueue &Q, QElemType e) 出队 p65 Status DeQueue(SqQueue &Q, QElemType &e) 判队空 Status QueueEmpty(SqQueue Q) 取队头元素 Status GetHead(SqQueue Q,QElemType &e)

Status InitQueue (SqQueue &Q)
{ Q.base=(QElemTye *)malloc(MAXQSIZE*sizeof(QElemType)); if (!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK; }

int QueueLength(SqQueue Q)
{ return (Q.rearQ.front+MAXQSIZE)%MAXQSIZE; }

Status EnQueue (SqQueue &Q, QElemType e)
{ if ((Q.rear+1) % MAXQSIZE ==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear = (Q.rear+1)%MAXQSIZE; return OK; }

Status DeQueue(SqQueue &Q, QElemType &e)
{ if (Q.rear==Q.front) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK; }

Status QueueEmpty(SqQueue Q)
{ if (Q.front==Q.rear) return TRUE; return FALSE; }

Status GetHead(SqQueue Q,QElemType &e) { if QueueEmpty(Q) return ERROR; e=Q.base[Q.front]; return OK; }

非循环队列
类型定义:与循环队列完全一样 关键:修改队尾/队头指针 Q.rear = Q.rear + 1; Q.front = Q.front+1; 在判断时,有%MAXQSIZE为循环队列, 否则为非循环队列 队空条件: Q.front = Q.rear 队满条件: Q.rear>= MAXQSIZE 注意“假上溢”的处理 长度: Q.rear - Q.front


相关文章:
严蔚敏数据结构课件03栈和队列._图文.ppt
严蔚敏数据结构课件03栈和队列. - 第3章 栈和队列 3.1 3.2 3.3
3-数据结构-清华大学严蔚敏PPT-栈和队列_图文.ppt
3-数据结构-清华大学严蔚敏PPT-栈和队列_工学_高等教育_教育专区。数据结构第3章PPT,严蔚敏编著,清华大学出版社出版 第3章 栈和队列栈和队列是两种应用非常广泛...
严蔚敏数据结构课件第三章栈和队列_图文.ppt
严蔚敏数据结构课件第三章栈和队列 - 第3章 栈和队列 孙甲霞 ? 教学目标:掌握栈和队列的结构特性,熟练掌握栈和 队列的基本操作在两种存储结构上的实现方法。 ?...
严蔚敏数据结构课件03:栈和队列_图文.ppt
严蔚敏数据结构课件03:栈和队列 - 第3章 栈和队列 3.1 3.2 3.3
严蔚敏《数据结构》教学笔记第三章 栈和队列.pdf
严蔚敏《数据结构》教学笔记第三章 栈和队列_IT/计算机_专业资料。严蔚敏《数据结构》教学笔记 来在www.freekaoyan.com 转载请注明 严蔚敏数据结构教学笔记 第三章...
严蔚敏数据结构讲义(第03章 栈和队列).doc
严蔚敏数据结构讲义(第03栈和队列)_工学_高等教育_教育专区。严蔚敏数据结构讲义 第03栈和队列 03章栈的基本概念 3.1 栈的基本概念一、 一般线性表、栈...
数据结构,严蔚敏版 第三章 栈和队列_图文.ppt
数据结构,严蔚敏版 第三章 栈和队列 - 通常称,栈和队列是限定插入和删除只 能
PPT第三章_栈和队列(数据结构ppt-严蔚敏)_图文.ppt
PPT第三章_栈和队列(数据结构ppt-严蔚敏) - 数据结构 第三章栈和队列 信息科学与工程学院 信息管理与信息系统 进入知识海洋 ? 两种操作受限的线性表 ? 两种...
严蔚敏数据结构(栈和队列)_图文.ppt
严蔚敏数据结构(栈和队列) - 第三章 栈和队列 栈和队列是两种特殊的线性表,是
严蔚敏《数据结构(c语言版)习题集》答案第三章 栈与队列.doc
严蔚敏数据结构(c语言版)习题集》答案第三章 栈与队列 - 第三章 栈与队列 3.15 typedef struct{ Elemtype *base[2]; Elemtype *top[2];...
数据结构-2004-02-03栈和队列.ppt
数据结构-2004-02-03栈和队列_计算机软件及应用_IT/计算机_专业资料。数据结构...严蔚敏数据结构课件03:... 57页 免费 数据结构-03 栈和队列 155页 免费 数据...
数据结构(c语言版)课件_第三章_栈和队列_(严蔚敏、吴伟....ppt
数据结构(c语言版)课件_第三章_栈和队列_(严蔚敏、吴伟民编_清华大学出版社)_理学_高等教育_教育专区。数据结构(c语言版)课件_第三章_栈和队列_(严蔚敏、...
数据结构严蔚敏PPT(完整版)_图文.ppt
数据结构严蔚敏PPT(完整版)_工学_高等教育_教育专区。算法与数据结构教材:《...栈和队列 串 图1-5 数据逻辑结构层次关系图 1.1.5 数据类型数据类型(Data ...
数据结构(c语言版)课件_第三章_栈和队列_(严蔚敏、吴伟....ppt
数据结构(c语言版)课件_第三章_栈和队列_(严蔚敏、吴伟民编_清华大学出版社)_工学_高等教育_教育专区。第三章 栈和队列栈和队列是两种特殊的线性表,是操作...
数据结构(C语言版)严蔚敏吴伟民第三章栈和队列_图文.ppt
数据结构(C语言版)严蔚敏吴伟民第三章栈和队列 - 1 栈和队列是两种特殊的线性表,是操 作受限的线性表,简称限定性DS 。 栈和队列是两种常用的数据类型 2 通常...
数据结构(严蔚敏)课件第3章_图文.ppt
数据结构(严蔚敏)课件第3章 - 第三章 栈和队列 【课前思考】 1. 什么是线
数据结构_03_栈和队列_图文.ppt
数据结构_03_栈和队列 - 第3章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列 3.5 离散事件模拟 1 第3章 栈和队列 ? 栈和队列...
数据结构 栈和队列_图文.ppt
数据结构 栈和队列 - 第3章 栈和队列 3.1 栈 3.2 队列 本章小结 3
数据结构_03_栈与队列_图文.ppt
数据结构_03_栈与队列 - 第三章 栈与队列 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件 本章主要内容 ? ? ? ?...
数据结构课件第3章栈和队列B_图文.ppt
数据结构课件第3章栈和队列B - 数据结构课程的内容 1 第三章 栈和队列 3.
更多相关标签: