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

数据结构课件、代码第3章栈和队列-81-3_图文

第3章 栈和队列
张成文 北京邮电大学计算机学院

概述
? 两种特殊的线性表。 ? 逻辑结构和线性表相同。 ? 比起线性表其运算受限制,故又称它们为 运算受限的线性表。 ? 栈和队列应用在各种程序设计中 ? 尤其栈的应用更广

1. 栈
1.1 栈的定义 1.2 顺序栈 1.3 链栈

1.1 栈的定义
栈(Stack)是限制仅在表的一端进行插入 和删除运算的线性表。 (1)通常称插入、删除的这一端为栈顶(Top), 另一端称为栈底(Bottom)。 (2)当表中没有元素时称为空栈。 (3)栈的插入操作被形象地称为进栈或入栈,删 除操作称为出栈或退栈。

栈的示意图
每次进栈的元素都被放在原栈顶元素之上而成为新 的栈顶,而每次出栈的总是当前栈中“最新”的元素, 即最后进栈的元素。因此,栈又称为后进先出的线性 表。简称为LIFO表。
入栈 pus h 出栈 pop

top

an

栈顶(表尾)

bottom

a2 a1

栈底

栈的存储方式
栈在计算机中主要有两种基本的存储 结构:顺序存储结构和链式存储结构。 ? 顺序存储的栈为顺序栈

? 链式存储的栈为链栈

1.2 顺序栈
栈的顺序存储结构简称为顺序栈,它是运 算受限的顺序表。

顺序栈利用一组地址连续的存储单元依 次存放自栈底到栈顶的数据元素。

顺序栈的类型定义
#define TRUE 1 #define FALSE 0 #define Stack_Size 50 typedef struct { StackElementType elem[Stack_Size]; /* 一维数组*/ int top; /*用来存放栈顶元素的下标*/ }SeqStack;

top top

top
空栈 e d c b a e 进栈

a a 进栈
e d c b a f 进栈溢出

top

b a b 进栈

top

top

e d c b a e 退栈

d top c b a d 退栈

top

c b a c 退栈

top

b a

b 退栈

a
top a 退栈 top 空栈

注意
①顺序栈中元素用向量存放 ②栈底位置是固定不变的,可设置在向量两 端的任意一个端点 ③栈顶位置是随着进栈和退栈操作而变化的, 用一个整型量top(通常称top为栈顶指针) 来指示当前栈顶位置

顺序栈的基本运算
(1) 置栈空(初始化) (2) 判栈空 (3) 判栈满 (4) 进栈操作 (5) 退栈操作 (6) 取栈顶元素

(1)置栈空(初始化)
void InitStack(SeqStack *S) {//将顺序栈置空 S->top=-1; }

(2) 判栈空
int StackEmpty(SeqStack *S) { /*判栈S为空栈时返回值为真,反之为假*/ return S->top==-1; }

(3)判栈满
int StackFull(SeqStack *S) { /*判栈S为满时返回真,否则返回假*/ return S->top==StackSize-1; }

(4)进栈
进栈时,需要将S->top加1 注意: ①S->top==StackSize-1表示栈满 ②"上溢"现象-当栈满时,再做进栈运算产生 空间溢出的现象。 上溢是一种出错状态,应设法避免。 void Push(SeqStack *S,DataType x) { if (StackFull(S)) Error(“Stack overflow”); //上溢,退出运行 S->data[++S->top]=x;//栈顶指针加1后将x入栈 }

(5)退栈
退栈时,需将S->top减1 注意: ①S->top<0表示空栈 ②"下溢"现象——当栈空时,做退栈运算产 生的溢出现象。 下溢是正常现象,常用作程序控制转移的条件。 DataType Pop(S) { if(StackEmpty(S)) Error(“Stack underflow”); //下溢,退出运行 return S->data[S->top--];//栈顶元素返回后将栈 顶指针减1 }

(6)取栈顶元素
DataType StackTop(S) { if(StackEmpty(S)) Error("Stack is empty"); return S->data[S->top]; }

1.4 链栈
链栈是采用链表作为存储结构实现的栈,是线性链 表的特例。因为栈的插入和删除操作仅限制在表头位 置进行,所以链表的表头指针就作为栈顶指针。

栈顶指针 top

an

an-1

a1



注意: 链栈中指针的方向是从栈顶指向栈底方向

top为栈顶指针,始终指向当前栈顶元素结点。 若top=NULL,则代表空栈。 注意:链栈在使用完毕时,应该释放其空间。

typedef struct stacknode{ DataType data struct stacknode *next }StackNode;
StackNode *head=NULL; typedef struct{ StackNode *top; //栈顶指针 }LinkStack;

链栈的基本运算
(1) 置栈空 (2) 判栈空 (3) 进栈 (4) 退栈 (5) 取栈顶元素

(1) 置栈空
void InitStack(LinkStack *S) { S->top=NULL; }

(2) 判栈空
int StackEmpty(LinkStack *S) { return S->top==NULL; }

(3) 进栈
void Push(LinkStack *S,DataType x) {//将元素x插入链栈头部 StackNode *p= (StackNode *)malloc(sizeof(StackNode)); if(p==NULL) { printf(“内存空间不够分配”); exit(0);//return } //健壮(Robust) p->data=x; p->next=S->top;//将新结点*p插入链栈头部 S->top=p; }

(4) 退栈
DataType Pop(LinkStack *S) { DataType x; StackNode *p=S->top;//保存栈顶指针 if(StackEmpty(S)) Error("Stack underflow."); //下溢 x=p->data; //保存栈顶结点数据 S->top=p->next; //将栈顶结点从链上摘下 free(p); return x; }

链栈的入栈操作和出栈操作
将x入栈,修改栈顶 指针:top=p

an出栈,修改栈顶指 针:top=top->next

(5) 取栈顶元素
DataType StackTop(LinkStack *S) { if(StackEmpty(S)) Error("Stack is empty.") return S->top->data; }

注意
链栈中的结点是动态分配的,所以可 以不考虑上溢,无须定义StackFull运算。

2. 队列
2.1 队列的定义 2.2 顺序队列 2.3 链队列

2.1 队列的定义和基本运算
队列是一种特殊的线性表,限定插入和 删除操作分别在表的两端进行。

出队

a1
队头 f

a2 … ai … an
队尾 r

入队

队列的性质
(1)允许删除的一端称为队头(Front)。
(2)允许插入的一端称为队尾(Rear)。 (3)当队列中没有元素时称为空队列。 (4)队列亦称作先进先出(First In First Out)的 线性表,简称为FIFO表

队列的进队和出队
A
front rear 空队列 front rear A进队

A B
front rear B进队

A B C D
front rear C, D进队

B C D
front rear A退队

C D
front rear B退队

C D E F G
front rear E,F,G进队

C D E F G
front rear

H进队,溢出

队列的进队和出队原则
进队时队尾指针先进一 rear = rear + 1, 再将新元素按 rear 指示位置加入。 ? 出队时队头指针先进一 front = front + 1, 再将下标为 front 的元素取出。 ? 队满时再进队将溢出出错; ? 队空时再出队将队空处理。 ? 解决办法之一:将队列元素存放数组首尾 相接,形成循环(环形)队列。
?

队列的存储方式
队列在计算机中主要有两种基本的存储结构: 顺序存储结构和链式存储结构。 ?顺序存储的队列为顺序队列 ?链式存储的队列为链队列

队列的基本运算
(1)初始化队列 (2)判队空 (3)判队满 (4)入队 (5)出队 (6)取队首元素

2.2 顺序队列
2.2.1 顺序队列的定义 2.2.2 顺序队列的基本运算 2.2.3 循环队列

2.2.1 顺序队列的定义
队列的顺序存储结构称为顺序队列, 顺序队列实际上是运算受限的顺序表

front front rear

rear rear

a b c d e f

顺序队列的表示
①和顺序表一样,顺序队列用一个向量 空间来存放当前队列中的元素。 ②由于队列的队头和队尾的位置是变化 的,设置两个“指针”front和rear分别指 示队头元素和队尾元素在向量空间中的 位置,它们的初值在队列初始化时均应 置为0。

2.2.2 顺序队列的基本运算
①入队时:将新元素插入rear所指的位置,然后将 rear加1。 ②出队时:删去front所指的元素,然后将front加1并 返回被删元素。
注意: ①当头尾指针相等时,队列为空。 ②在非空队列里,队头指针始终指向队头元素,尾 指针始终指向队尾元素的下一位置。

假上溢
当Q->front= Q->rear 时,队列空。 当Q->rear+1>MaxSize 时,队列满(即上溢出),但此 时头指针指示的元素之前可能还有空单元,此现象称为 假溢出;若把这样的顺序结构设想为一个循环表, 插入 时就可以利用这些空单元, 这样就构成循环队列。

2.2.3 循环队列
为充分利用向量空间,克服“假上溢” 现象的方法: 将向量空间想象为一个首尾相接的圆 环,并称这种向量为循环向量。

循环队列示意图

循环队列的几种状态

入队操作时的尾指针运算: rear=(rear+1)%Maxsize 出队操作时的头指针运算: front=(front+1)%Maxaize 问题:在循环队列中,由于队空时有front==rear;队满时也有front==rear;因 此我们无法通过front==rear来判断队列是“空”还是“满”。

循环队列队满和队空的描述方法
front rear

队空 : rear=front front

front

rear

队满: rear=front(?)
front rear

rear

循环队列边界条件处理
如何判断是“空”还是“满”。 解决这个问题的方法至少有三种:
① 另设一布尔变量以区别队列的空和满; ② 少用一个元素的空间。约定入队前,测试尾指针 在循环意义下加1后是否等于头指针,若相等则认 为队满(注意:rear所指的单元始终为空); ③使用一个计数器记录队列中元素的总数(即队列 长度)。

顺序循环队列的类型定义
#define QueueSize 100 //应根据具体情况定义该值 typedef char DataType; //DataType的类型依赖于具体的
应用

typedef struct{ int front; //头指针,队非空时指向队头元素 int rear; //尾指针,队非空时指向队尾元素的下一位置 int count; //计数器,记录队中元素总数 DataType data[QueueSize] }CirQueue;

顺序循环队列的基本运算
1.置队空 2.判队空 3.判队满 4.入队 5.出队 6.取队头元素

① 置队空
void InitQueue(CirQueue *Q) { Q->front=Q->rear=0; Q->count=0; //计数器置0 }

② 判队空
int QueueEmpty(CirQueue *Q) { //队列无元素为空,属第三种方法 return Q->count==0; } int QueueEmpty(CirQueue *Q) { //属第二种方法 return Q->rear==Q->front; }

③ 判队满
int QueueFull(CirQueue *Q) { return Q->count==QueueSize;
//队中元素个数等于QueueSize时队满,属第三种方法

}

int QueueFull(CirQueue *Q) { return (Q->rear+1)%QueueSize==Q->front ;
//队中元素个数等于QueueSize时队满,属第二种方法

}

④ 入队
void EnQueue(CirQueue *Q,DataType x) { if(QueueFull((Q)) Error("Queue overflow"); //队满上溢 Q->count ++; //队列元素个数加1 Q->data[Q->rear]=x; //新元素插入队尾 Q->rear=(Q->rear+1)%QueueSize;
//循环意义下将尾指针加1 }

⑤ 出队
DataType DeQueue(CirQueue *Q) { DataType temp; if(QueueEmpty((Q)) Error("Queue underflow"); //队空下溢 temp=Q->data[Q->front]; Q->count--; //队列元素个数减1 Q->front=(Q->front+1)%QueueSize; /*循环意义下的头指针加1*/ return temp; }

⑥取队头元素
DataType QueueFront(CirQueue *Q) { if(QueueEmpty(Q)) Error("Queue if empty."); return Q->data[Q->front]; }

2.3链队列
2.3.1 链队列的定义 2.3.2 链队列的基本运算

2.3.1 链队列的定义
队列的链式存储结构简称为链队列。它是限制 仅在表头删除和表尾插入的单链表。

队头在链头,队尾在链尾。 q.front q.rear

a1
q.front q.rear




an ∧

空队列

链队列的几种状态示意图
此时,front==rear 修改rear指针

修改rear指针

修改头结点的 指针域

①链队列为空的特征:front==rear
一般不会,因为删除时有free动作,除非内存不足! ② 链队列会满吗?

注意
增加指向链表上的最后一个结点的尾 指针,便于在表尾做插入操作
①和链栈类似,无须考虑判队满的运算及上溢。 ②在出队算法中,一般只需修改队头指针。但当原 队中只有一个结点时,该结点既是队头也是队尾, 故删去此结点时亦需修改尾指针,且删去此结点后 队列变空。 ③以上讨论的是无头结点链队列的基本运算。和单 链表类似,为了简化边界条件的处理,在队头结点 前也可附加一个头结点,增加头结点的链队列的基 本运算

定义链队列的存储结构
typedef char DataType; typedef struct queuenode { DataType data; struct queuenode *next;

}QueueNode; typedef struct {
QueueNode * front; QueueNode *rear; } LinkQueue;

2.3.2 链队列的基本运算
1.置空队 2.判队空 3.入队 4.出队 5.取队头元素

(1) 置空队
int InitQueue( LinkQueue *Q ) { //构造一个空队列 *Q Q->front = (LQnode *)malloc(sizeof(LQnode)); if( Q->front == NULL ) return FALSE; //申请内存失败返回 Q->rear = Q->front; Q->front-> next = NULL; return TRUE; //申请内存成功返回 }

(2) 判队空
int QueueEmpty(LinkQueue *Q) { return Q-> front-> next ==NULL&&Q->rear>next==NULL;
/*实际上只须判断队头指针是否为空即可*/

}

(3) 入队
void EnQueue(LinkQueue *Q,DataType x) {//将元素x插入链队列尾部
QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode)); //申请新结点 p->data=x; p->next=NULL; if(QueueEmpty(Q)) { Q->front->next=p; Q->rear=p; } //将x插入空队列 else { //x插入非空队列的尾 Q->rear->next=p; //*p链到原队尾结点后 Q->rear=p; //队尾指针指向新的尾 } }

(4) 出队
DataType DeQueue (LinkQueue *Q) { DataType x; QueueNode *p; if(QueueEmpty(Q)) Error(“Queue underflow”);//下溢 p=Q->front->next; //指向队头结点 x=p->data; //保存队头结点的数据 Q->front->next=p->next; //将队头结点从链上摘下 if(Q->rear==p)//原队中只有一个结点,删去后队列变空,
此时队头指针已为空

{ Q->rear= Q->front;} free(p); //释放被删队头结点 return x; //返回原队头数据

}

(5) 取队头元素
DataType QueueFront(LinkQueue *Q) { if(QueueEmpty(Q)) Error("Queue if empty."); return Q->front->next->data; }

3. 栈的应用
3.1 函数调用 3.2 递归、非递归

3.1 函数调用
当在一个函数的运行期间调用另一个函数时, 在运行该被调用函数之前, 需先完成三项任务:

① 保存现场, 保存本函数参数、返回地址等信息;
② 为被调用函数的局部变量分配存储区传递参数;

③ 将控制转移到被调用函数的入口。

从被调用函数返回调用函数之前, 应该完成下列 三项任务: ① 保存返回的计算结果(用函数名,引用参数) ;

② 释放被调函数的数据区, 恢复调用函数现场 ;
③ 依照被保存的返回地址将控制转移到调用函数。

多个函数嵌套调用的规则 后调用先返回 !

此时的内存管理实行“栈式管理”
例如:
main( ) { … a( ); … }//main void a( ) { … b( ); void b( ) { … 函数b的数据区 }// b 函数a的数据区 main的数据区


}// a

栈在函数调用中的作用
过程一 过程二 过程三 过程四

断点三
断 点 一
断 点 二

断点二
断 点 三

断点一 stack
程序执行 调用子程序 返回断点

3.2 递归、非递归
[递归的含义] 函数、过程或者数据结构的内部又直接或者间接 地由自身定义。 [适合于应用递归的场合] 规模较大的问题可以化解为规模较小的问题,且二者 处理(或定义)的方式一致; 当问题规模降低到一定程度时是可以直接求解的(终止 条件) 例1. 阶乘 n!= 1 n=0 n×(n-1)! n>0
数据结构---第3章 栈和队列 70

[写递归算法应注意的问题] – 递归算法本身不可以作为独立的程序运行,需在其 它的程序中设置调用初值,进行调用; – 递归算法应有出口(终止条件) 例1. 求n! int Factorial(int n) { if (n==0) return(1); return n*Factorial(n-1); }//Factorial

数据结构---第3章 栈和队列

71

[递归算法的实现原理] s
3 1 2

3

2
1

- 利用栈,栈中每个元素称为工作记录,分成三个部分: 返回地址 实际参数表(变参和值参) 局部变量 - 发生调用时,保护现场,即当前的工作记录入栈,然后

转入被调用的过程
- 一个调用结束时,恢复现场,即若栈不空,则退栈,从 退出的返回地址处继续执行下去
数据结构---第3章 栈和队列 72

[递归时系统工作原理示例]
int Factorial( int n) { L1: if ( n==0 ) L2: return 1; L3: else return n*Factorial(n-1); L4: } //Factorial L3 void main(void) L3 { …… L3 L0: N=Factorial(3); L0 …… } //main 返回地址 n 1 2 3 3 1 / 1 / 2 / 6 / /

Factorial N
73

[递归算法的用途] – 求解递归定义的数学函数 – 在以递归方式定义的数据结构上的运算/操作 – 可用递归方式描述的解决过程

[递归算法的特点] – 递归算法简单明了,直观易懂 – 时间效率低,空间开销大,算法不易优化

数据结构---第3章 栈和队列

74

[递归转换为非递归的方法]

1)采用迭代算法

递归—从顶到底

迭代—从底到顶

例:求n! int fact(int n) { m=1; for ( i=1; i<= n; i++) return m; }//fact

m=m*i;

数据结构---第3章 栈和队列

75

2)消除尾递归 例:顺序输出单链表中的结点数据
void linklist_output(LNode *p); 使用跳转语句: { if (p) void linklist_output1(LNode *p) { printf(p->data); { 使用循环语句: 1: if ( p ) linklist_output(p->next) { linklist_output2 printf(p->data);(LNode *p) void } p=p->next; { while ( p ) goto 1 }//linklist_output { printf(p->data); } p=p->next; }//linklist_output1 } }//linklist_output2 a1 a2 an ^
数据结构---第3章 栈和队列 76

p

3)对递归算法改写—通用方法(利用栈模拟递归) 如果是递归函数,需改写为递归过程 例:求n! void fact(int n, int &f) InitStack(S); Push( S, (2, n, f )); {0: if (n==0) f=1; n=n-1; goto 0; else [ 1: fact(n-1,f); 2: f=n*f if ( !StackEmpty(S) ) { (S.top-1)->f=f; //还原本层变参值 Pop(S, (rd, n, f) ); goto rd ; }
77

]
} //fact

数据结构---第3章 栈和队列

自设栈模拟系统工作栈 top
例:typedef

S

struct { int rd; int n; int f; }SElemType;

rd

n

f

改写算法 – 在程序开头增加栈的初始化语句 – 改写递归调用语句 入栈处理; 确定调用的参数值; 转至调用的开始语句 – 改写所有递归出口 退栈还原参数; 转至返回地址处

78

void fact(int n; int &f) { InitStack(S); 0: if (n==0) f=1; else { 1: Push( S, (2, n, f )); n=n-1; goto 0; 2: f:=n*f; } if ( !StackEmpty(S) ) { (S.top-1)->f=f; Pop(S, (rd, n, f) ); goto rd ; } }//fact

void fact(int n; int &f ) { InitStack(S); while (n!=0) { Push (S, n); n=n-1; }
f=1; while ( !StackEmpty(S) ) { Pop (S, n); f=n*f; } }//fact
注:此时可确定栈中只 存放n值即可。

typedef int SElemType;


相关文章:
数据结构课件、代码第3章栈和队列-81-3_图文.ppt
数据结构课件代码第3章栈和队列-81-3_数学_高中教育_教育专区。文档均来自
《数据结构课件、代码》第3章 栈和队列-81-3._图文.ppt
数据结构课件代码第3章 栈和队列-81-3. - 第3章 栈和队列 张成文
数据结构课件_第3章 栈和队列_图文.ppt
数据结构课件_第3章 栈和队列 - 例如:ListInsert_Sq(L, 5,
数据结构课件 第3章 栈和队列资料_图文.ppt
数据结构课件 第3章 栈和队列资料 - 第三章 栈和队列 【课前思考】 1. 什
第3章 栈与队列 数据结构ppt_图文.ppt
第3章 栈与队列 数据结构ppt - 计算机必修科目数据结构,很好的ppt,值得
数据结构第3章栈和队列栈ppt课件-精选文档_图文.ppt
数据结构第3章栈和队列栈ppt课件-精选文档 - 武汉科技大学 Wuhan Un
[课件]数据结构Java版第三章栈和队列PPT_图文.ppt
[课件]数据结构Java版第三章栈和队列PPT - 数据结构 Java版第三 章_栈和队列 3.1 栈 2. 3.2 队列 ? 目的:使用栈或队列求解应用问题。 ? 要求:掌握栈和...
数据结构Java版第三章_栈和队列ppt课件_图文.ppt
数据结构Java版第三章_栈和队列ppt课件 - 数据结构Java 版第三章_栈和 队列 3.1 栈 2. 3.2 队列 ? 目的:使用栈或队列求解应用问题。 ? 要求:掌握栈和...
数据结构-PPT第三章-栈和队列_图文.ppt
数据结构-PPT第三章-栈和队列 - 通常称,栈和队列是限定插入和删除只 能在表
数据结构第三章 栈和队列_图文.ppt
数据结构第三章 栈和队列 - 中国石油大学,宋会英主讲,严蔚敏、吴伟民,数据结构(c语言版)清华大学出版社,1997.4(第一版), 2001.1(第2版), 严蔚敏,吴伟民,...
数据结构第3章栈和队列2队列ppt课件32页PPT_图文.ppt
数据结构第3章栈和队列2队列ppt课件32页PPT - 武汉科技大学 Wuhan
数据结构课件(C语言版)--第3章 栈和队列_图文.ppt
数据结构课件(C语言版)--第3章 栈和队列 - 第3章 栈和队列 栈和队列是两
数据结构 第3章栈和队列_图文.ppt
数据结构 第3章栈和队列 - 第3章 教学内容: 栈和队列 栈和队列的逻辑结构、
严蔚敏数据结构课件第三章栈和队列_图文.ppt
严蔚敏数据结构课件第三章栈和队列 - 第3章 栈和队列 孙甲霞 ? 教学目标:掌
数据结构Java版第三章_栈和队列_图文.ppt
数据结构Java版第三章_栈和队列 - 数据结构与算法设计(Java版) ? ? ? ? ? ? ? ? 第1章 绪论 第2章 线性表 第3章 栈与队列 第4 章串第5章 数组 ...
数据结构课件第3章栈和队列B_图文.pdf
数据结构课件第3章栈和队列B - 数据结构课程的内容 1 第三章 栈和队列 3.
数据结构-王红梅-第3章-栈和队列_图文.ppt
数据结构-王红梅-第3章-栈和队列 - 清华大学出版社 数据结构(C++版)第2版 第 3 章 栈和队列 本章的基本内容是: 两种特殊的线性表栈和队列 ?从数据...
数据结构(第3章栈和队列)_图文.ppt
数据结构(第3章栈和队列) - 第3章 栈和队列 3.1 栈和队列是两种特殊的线
数据结构第3章栈和队列_图文.ppt
数据结构第3章栈和队列 - 第章 3.1 栈 3.1.1 3.1.2 3.1.3 3.1.4 3.1.5 栈的定义 栈的实例 顺序栈 栈的插入和删除 链栈 栈和队列 3.2 3.3 栈...
数据结构--第三章栈和队列_图文.ppt
数据结构--第三章栈和队列 - 第 3章 限定性线性表栈和队列 3.1 栈 3