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

严蔚敏数据结构课件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


赞助商链接
相关文章:
清华大学严蔚敏数据结构课后习题答案 第三章(栈与队列)
清华大学严蔚敏数据结构课后习题答案 第三章(栈与队列)_理学_高等教育_教育专区。严蔚敏数据结构课后习题答案清华大学严蔚敏数据结构课后习题答案 第三章(栈与队列) ...
数据结构栈和队列C语言实现
数据结构栈和队列C语言实现 - 数学与信息技术学院 2016~2017(下)学年 计科专业 2015 级《数据结构》实验报告 4 学号:2015201018 实验名称 栈的应用 姓名:汪...
数据结构栈和队列
数据结构栈和队列_计算机软件及应用_IT/计算机_专业...数据结构03章_栈和队列... 暂无评价 107页 2...数据结构-清华大学严蔚敏... 814页 5下载券 数据...
数据结构-实验3 栈和队列
所属课程名称 项目类型 实验(实训)日期 实验 3 栈和队列 数据结构验证性 2013...(1) 在日常生活中,除课件中提到的例子(超市存放购物车的轨道、折反型的火车...
数据结构第三章栈和队列习题及答案
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 IT/计算机 ...数据结构第三章栈和队列习题及答案_计算机软件及应用_IT/计算机_专业资料。数据...
数据结构__栈与队列
数据结构__栈与队列_计算机软件及应用_IT/计算机_专业资料。仲恺农业工程学院实验报告纸(院、系) 学号 姓名 专业 实验日期 班组 教师评定 课 实验一 栈和队列的...
数据结构习题3-栈和队列
数据结构习题3-栈和队列 - 3 栈和队列 选择题 1. 一个栈的入栈序列 a,b,c,d,e,则栈的不可能的输出序列是__C__。 A. edcba B. decba C. dceab...
数据结构(C语言版)例题(第三章:栈和队列)
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 ...栈和队列 严蔚敏 数据结... 9页 2下载券 数据结构C语言版第三章 ... 暂无...
数据结构作业-栈和队列
(S)){ pop(S,d); if(d!=e) Push(T,d); } while(!StackEmpty(T)){ Pop(T,d); Push(S,d); } } 4 简述队列和栈这两种数据类型的相同点和...
《数据结构》习题集:第3章 栈和队列
搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 理学...4页 免费 严蔚敏数据结构(c语言版... 4页 免费 数据结构第3章栈和队列 ...
更多相关标签: