《数据结构》课件-第三章 栈和队列

数据结构

(DATASTRUCTURE)第三章栈和队列栈(Stack)栈的应用递归队列(Queue)23.1

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

Stack{

数据对象:D＝{ai

|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

InitStack(&S):栈的初始化

DestoryStack(&S):销毁栈S

Push(&S,e):进栈

Pop(&S):出栈

GetTop(S):取栈顶元素

IsEmpty(S):判栈空否

……}2)栈的抽象数据类型41)存储特点：

利用一组地址连续的存储单元依次存放栈元素附设指针top指示栈顶元素在顺序栈中的位置2)顺序栈的表示#defineStackInitSize100;//存储空间初始分配量typedef

int

StackElementType；

typedef

struct{

StackElementType

data[StackInitSize]；/*栈存储空间用一个预设的长度的一维数组来实现 */

inttop； /*栈顶指针*/}SeqStack；3.1.1

栈的顺序存储—顺序栈5①进栈（入栈）

分析

首先判断栈满？（栈满:s->top==StackInitSize)

若栈满，则不能进栈操作栈顶指针加1s->top++;

数据元素入栈

s->data[s->top]=x;

3)基本操作的实现6算法voidPush(SeqStack*s,StackElementTypex){if(s->top==StackInitSize){printf("栈满!栈发生上溢，程序运行终止!\n"); exit(0);}else{s->top++; /*栈顶指针加1，指向新的栈顶*/ s->data[s->top]=x; /*将数据元素x压入栈*/}return;}7

分析

首先判断栈空？（栈空:(s->top==-1

)

数据元素出栈temp=s->data[s->top]

栈顶指针减1s->top--

算法StackElementType

Pop(SeqStack*s){StackElementTypetemp;

if(IsEmpty(s)){printf("栈空！栈发生下溢，程序运行终止!\n");exit(0); }else{temp=s->data[s->top];s->top--;returntemp; }}②出栈（退栈）8顺序栈演示：9多栈处理栈浮动技术n

个栈共享一个数组空间V[m]设立栈顶指针数组t[n+1]

和栈底指针数组b[n+1]，t[i]和b[i]分别指示第i个栈的栈顶与栈底各栈初始分配空间s=

m/n

指针初始值t[0]=b[0]=-1b[n]=m-1

t[i]=b[i]=b[i-1]+s,i=1,2,…,n-110113.1.2

栈的链式存储—链式栈1）存储特点是一种特殊形式的单链表（无表头结点；插入、删除操作限定在表头端进行）链式栈无栈满问题，空间可扩充122）链式栈的表示：同单链表

typedef

structnode{SElemtypedata;

structnode*next;}linkstack;13①进栈（入栈）

分析

首先申请一个结点空间(用p指向该结点)

若链栈不为空，将*p插入链表的第一个结点之前：

p->next=top;top=p;否则：p->next=NULL;top=p;3）基本运算的实现14

分析首先判断栈空？（栈空:top=NULL)

若不空，判断*top是否为栈中最后一个元素如不是，则将*top从链表中删除：

top=top->next

否则，令top=NULL

释放栈顶元素空间;

②出栈（退栈）153.1.3

栈的应用举例例1：简单应用：数制转换问题问题：将十进制数N转换为r进制的数，其转换方法利用辗转相除法。分析：所转换的r进制数按低位到高位的顺序产生，而通常的输出是从高位到低位的，恰好与计算过程相反16例2中缀表达式求值

问题：根据算符优先法对表达式求值,所讨论的算术运算符包括：+、-、*、/、%、^(乘方)和括号()。运算规则为：运算符的优先级为:()→^→＊、/、%→+、-；有括号时先算括号内的，后算括号外的，多层括号由内向外进行；乘方连续出现时先算最右面的；17分析：表达式作为一个串，如表达式“3+2*4-5”,其求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因后面可能有更高的运算需要两个栈：对象栈OPND和算符栈OPTR;自左至右扫描表达式,若当前字符是运算对象，入OPND栈;对运算符，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从OPND栈出栈两个数，从OPTR栈出栈一运算符进行运算，并将其运算结果入OPND栈，继续处理当前字符，直到遇到结束符。18例3栈与递归

问题：栈的一个重要应用是在程序设计语言中实现递归过程。

n!=分析：根据定义可以很自然的写出相应的递归函数

intfact(intn){if(n==0)return1;elsereturn(n*fact(n-1));}1

n=0/*递归终止条件*/n*(n-1)!n>0/*递归步骤*/19递归的概念递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况常常用到递归方法。

定义是递归的数据结构是递归的问题的解法是递归的20定义是递归的求解阶乘函数的递归算法long

Factorial(

long

n)

{if(n==0)

return1;

elsereturn

n*Factorial(n-1);}例如，阶乘函数21数据结构是递归的搜索链表最后一个结点并打印其数值void

Find(

LinkListL){if(L→next==NULL)

printf(L→data);elseFind

(

L→next

);}

例如，单链表结构22

问题的解法是递归的

例如，汉诺塔(TowerofHanoi)问题23递归过程与递归工作栈递归过程在实现时，需要自己调用自己。每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。层层向下递归，退出时的次序正好相反：

递归次序

n!(n-1)!(n-2)!1!0!=1

返回次序因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。

243.2

队列(Queue)1)定义队列是只允许在一端删除，在另一端插入的线性表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)25ADTQueue

{

数据对象:D＝{ai

|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

InitQueue

(&Q):初始化队列

DestoryQueue(&Q):销毁队列

EnQueue(&Q,e):进队列

DeQueue(Q,&e):出队列

GetHead(Q,&e):取队头元素值

QueueEmpty(S):判队列空否

……}2）队列的抽象数据类型263.2.1

队列的链接存储—链式队列1)存储特点：队头在链头，队尾在链尾。设置队头、队尾指针分别保存队头、队尾地址272)链队列表示：结点类型：

typedef

struct

Qnode{QElemtypedata;

struct

QNode*next;定义一链队列

}Qnode,*Queueptr;LinkQueueQ;

链队列类型队头结点：

typedef

struct

Q.front->next{Queueptrfront;队尾结点：Q.rear

Queueptrrear;队尾结点数据：

}LinkQueue;Q.rear->next283)基本操作的实现①入队Queueptr

EnQueue(LinkQueueQ,Qelemtypex){p=(Queueptr)malloc(sizeof(QNode));/*申请结点空间*/

if(!p)exit(overflow);p->data=x;p->next=NULL;

Q.rear->next=p;Q.rear=p;returnQ;}29②出队Queueptr

DeQueue(LinkQueueQ,Qelemtype&e){if(Q.front==Q.rear)returnERROR;/*空队列*/p=Q.fornt->next;e=p->data;/*p指向队头结点*/

Q.front->next=p->next;/*删除队头结点*/if(Q.rear==p)Q.rear=Q.front;/*p是队中最后一个结点*/free(p);returnQ;}30

存储特点：利用地址连续的存储单元依次存放队列各元素。设置两个指示器front,rear

分别指示队头、队尾元素的下标3.2.2

队列的顺序存储—循环队列31

存在问题:“假溢出”解决方法:把队列存储空间看作首尾相连的环012345CDEFfrontrear32存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从MaxSize

-1直接进到0，可用C语言的取模(余数)运算实现。1）循环队列(CircularQueue)出队:队头指针进1

front=(front+1)%MaxSize;入队:队尾指针进1

rear=(rear+1)%MaxSize;队列初始化：front=rear=0;012345CDEFfrontrear33队空条件：队满条件：(rear+1)%MaxSize==front;front==rear;342）循环队列数据类型描述typedef

struct{

QElemtyope*base;//data[MAXSIZE]数据的存储区

intfront;//队头指针,指向对头元素

intrear;//队尾指针,指向对尾元素的下一个位置}SqQueue;/*循环队列*/353）基本操作的实现①初始化（置空队）36SqQueue

Init_SqQueue(){SqQueueQ;Q.base=(QElemtype*)malloc(Maxsize*

sizeof(QElemtype));//申请存储空间

if(!Q.base)exit(overflow);Q.front=Q.rear=0;//队列置空

returnQ;}

算法37②入队（插入）38SqQueue

EnSqQueue(SqQueueQ