数据结构-从概念到C++实现（第4版）课件 第三章 栈和队列

3-1引言v第三章栈和队列括号匹配问题在实际问题的处理过程中，有些数据具有后到先处理的特点【问题】判断给定表达式中所含括号是否正确配对。【想法】配对原则：右括号与其前面最近的尚未配对的左括号相配对。顺序扫描表达式，将右括号与已经扫描过的最后一个尚未配对的左括号进行配对。如何保存已经扫描过的尚未配对的左括号，并对其实施配对操作？5+((3+2)×8–7)÷35+((3+2)×8–7))÷3用栈保存，扫描到左括号进栈，扫描到右括号出栈进制转换问题【问题】将十进制数转换为二进制数。【想法】转换规则：除基取余，逆序排列。如何保存得到的余数，使之能够逆序输出？232111215222120101(23)10=用栈保存，从最后进栈的元素开始输出在实际问题的处理过程中，有些数据具有后到先处理的特点(10111)2

函数嵌套调用【问题】嵌套调用：在函数的执行过程中调用其他函数，返回到哪里？【想法】为保证函数嵌套调用的正确执行，返回到调用位置。如何保存调用位置？用栈保存，返回最后进栈的位置主函数mainABCED在实际问题的处理过程中，有些数据具有后到先处理的特点Office的撤销机制人生无法后悔，所以且行且珍惜！计算机后悔很容易，所以大胆往前走！随处可见的栈结构关于栈结构什么是栈？在逻辑上有什么特点？在操作上有什么特性？如何存储栈结构？在不同的存储结构上，如何实现插入、删除、查找等基本操作？在不同的存储结构上，基本操作的时空性能如何？银行排队问题在实际问题的处理过程中，有些数据具有先到先处理的特点【问题】银行个人储户的储蓄业务。【想法】先来先服务原则，模拟排队，储户叫号后排在队尾，窗口顺次叫号。如何保存正在等待的储户顺序？用队列保存等待队列打印缓冲区【问题】多个用户共享打印机，保证打印功能。【想法】先来先服务原则，设置打印缓冲区，先送到缓冲区的先打印。如何保存等待打印的文件？用队列保存即将打印的文档在实际问题的处理过程中，有些数据具有先到先处理的特点随处可见的队列随处可见的队列关于队列什么是队列？在逻辑上有什么特点？在操作上有什么特性？如何存储队列？在不同的存储结构上，如何实现插入、删除、查找等基本操作？在不同的存储结构上，基本操作的时空性能如何？八皇后问题很多问题的表现形式是矩阵，很多科学问题的数据模型是矩阵【问题】八皇后问题是数学家高斯于1850年提出的。问题是：在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。。【想法——数据表示】如何表示棋盘？如何获得每个皇后的位置信息进而判断是否互相攻击？用二维数组保存QQQQQQQQ解不唯一，N皇后可能无解！骑士巡游问题【骑士巡游问题】在n×n

方格的国际象棋棋盘上，马（也称为骑士）从任意指定的方格出发，以跳马规则（横一步竖两步或横两步竖一步）周游棋盘的每一个格子，要求每个格子只能跳一次。【想法——数据表示】如何表示棋盘？如何表示走位信息（位移量）？科学计算中的矩阵计算机中的矩阵关于数组多维数组：逻辑结构、存储结构及寻址矩阵的压缩存储：特殊矩阵、稀疏矩阵3-2栈v第三章栈和队列栈的逻辑结构栈的顺序存储结构及实现栈的链式存储结构及实现学什么？顺序栈和链栈的比较3-2-1栈的逻辑结构v第三章栈和队列栈的定义栈：限定仅在一端进行插入和删除操作的线性表（a1,…,an-1,an）栈顶（top）：允许插入和删除的一端称为栈顶栈底（bottom）：另一端称为栈底插入位置：1~n+1删除位置：1~n线性表插入位置：n+1删除位置：n栈栈底栈顶栈的操作特性插入：入栈、进栈、压栈删除：出栈、弹栈a插入删除bc此时执行出栈操作，哪个元素可以出栈呢？栈的操作特性：后进先出（LastInFirstOut，LIFO）空栈：不含任何数据元素的栈

条件判断

abc栈只是对插入和删除操作的位置进行了限制并没有限定插入和删除操作进行的时间例1有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况一出栈：cbaabc情况二出栈：bca栈的操作特性abc能否得到如下出栈序列？出栈：cab例1有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的操作特性栈的抽象数据类型定义ADTStackDataModelOperationendADT栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系InitStack：栈的初始化DestroyStack：栈的销毁Push：入栈Pop：出栈GetTop：取栈顶元素Empty：判空相对于其他数据结构，栈的基本操作是确定的InitStack输入：无功能：栈的初始化，初始化一个空栈输出：无

DestroyStack输入：无功能：销毁栈，释放栈所占用的存储空间输出：无Push

输入：元素值x

功能：在栈顶插入一个元素x

输出：如果插入成功，栈顶增加了一个元素，否则返回失败信息入栈出栈Push操作需要指明插入位置吗？栈的抽象数据类型定义

Pop输入：无功能：删除栈顶元素输出：如果删除成功，返回被删元素值；否则返回失败信息GetTop输入：无功能：读取当前的栈顶元素输出：若栈不空，返回当前的栈顶元素值；否则返回失败信息Empty输入：无功能：判断栈是否为空输出：如果栈为空，返回1；否则，返回0入栈出栈栈的抽象数据类型定义3-2-2栈的顺序存储结构及实现v第三章栈和队列顺序栈的存储结构定义顺序栈：栈的顺序存储结构

012345678如何表示栈顶：设变量top存储栈顶元素所在的下标如何表示栈底：用数组的一端作为栈底如何改造数组实现栈的顺序存储呢？topabc什么是顺序存储？constintStackSize=10;template<typenameDataType>classSeqStack{public:SeqStack();~SeqStack();voidPush(DataTypex);DataTypePop();DataTypeGetTop();intEmpty();private:DataTypedata[StackSize];inttop;};

顺序栈的类定义InitStack：栈的初始化DestroyStack：栈的销毁Push：入栈Pop：出栈GetTop：取栈顶元素Empty：判空栈的抽象数据类型定义？栈满：top=StackSize-1template<typenameDataType>voidSeqStack<DataType>::Push(DataTypex){

if(top==StackSize-1)throw"上溢";

data[++top]=x;}时间复杂度？什么情况下无法入栈？顺序栈的实现——入栈

012…

StackSize-1topabcx栈空：top=-1template<typenameDataType>DataTypeSeqStack<DataType>::Pop(){

DataTypex;

if(top==-1)throw"下溢";

x=data[top--];

returnx;}如何取栈顶元素？什么情况下无法出栈？

012…

StackSize-1abctop顺序栈的实现——出栈判空的函数原型是什么？Empty

输入：无功能：判断栈是否为空输出：如果栈为空，返回1；否则，返回0

012…

StackSize-1abctop栈空：top=-1template<typenameDataType>intSeqStack<DataType>::Empty(){if(top==-1)return1elsereturn0;}顺序栈的实现——判空3-2-3栈的链式存储结构及实现v第三章栈和队列存储结构定义链栈：栈的链式存储结构单链表是如何存储线性表的？firsta1a2an∧ai栈顶topanan-1a1∧firsta1a2an∧aiP：用链表的哪一端作为栈顶？A：为方便操作，用链头作为栈顶P：链栈需要加头结点吗？P：单链表为什么加头结点？A：链栈无须加头结点，也可以为了一致加上头结点链栈的类定义template<typenameDataType>classLinkedStack{public:LinkedStack();~LinkedStack();voidPush(DataTypex);DataTypePop();DataTypeGetTop();intEmpty();private:

Node<DataType>*top;};InitStack：栈的初始化DestroyStack：栈的销毁Push：入栈Pop：出栈GetTop：取栈顶元素Empty：判空栈的抽象数据类型定义？链栈的实现——入栈topanan-1a1∧xstoptemplate<typenameDataType>voidLinkedStack<DataType>::Push(DataTypex){Node<DataType>*s=nullptr;s=newNode<DataType>;s->data=x;//申请结点s数据域为x

s->next=top;top=s;//将结点s插在栈顶}链栈的入栈操作为什么不用判断是否栈满？template<typenameDataType>DataTypeLinkedStack<DataType>::Pop(){Node<DataType>*p=nullptr;DataTypex;if(top==nullptr)throw"下溢";x=top->data;p=top;//暂存栈顶元素

top=top->next;//将栈顶结点摘链deletep;returnx;}topanan-1a1∧topp

什么情况下无法删除？top=nullptr空栈如何取栈顶元素？链栈的实现——出栈顺序栈和链栈的比较作为一般规律，当栈的使用过程中元素个数变化较大时，应该采用链栈，反之，应该采用顺序栈。基本操作的时间复杂度均为O(1)。比较空间性能：顺序栈：初始时必须确定一个固定的长度，有存储元素个数的限制和浪费空间的问题。链栈：没有栈满的问题，但是每个元素都需要一个指针域，从而产生了结构性开销。3-3队列v第三章栈和队列队列的逻辑结构队列的顺序存储结构及实现队列的链式存储结构及实现学什么？循环队列和链队列的比较3-3-1队列的逻辑结构v第三章栈和队列队列的定义队列：只允许在表的一端进行插入操作，在另一端进行删除操作（a1,a2,…,an-1,an）队尾：允许插入的一端，相应地，位于队尾的元素称为队尾元素a1

a2

…

an栈a1

a2

…

an队列队头队尾队头：允许删除的一端，相应地，位于队头的元素称为队头元素队列的操作特性插入：入队、进队任何时候执行出队操作，一定是哪个元素呢？队列的操作特性：先进先出（FirstInFirstOut，FIFO）a入队出队bc例：有三个元素按a、b、c的次序依次入队，且每个元素只允许进一次队，则出队序列是什么？答：出队序列只有一种情况：abc删除：出队空队列：不含任何数据元素的队列

队列的抽象数据类型定义ADTStackDataModelOperationendADT队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系InitQueue：队列的初始化DestroyQueue：队列的销毁EnQueue：入队DeQueue：出队GetQueue：取队头元素Empty：判空与栈类似，队列的基本操作是确定的InitQueue

输入：无功能：初始化队列，创建一个空队列输出：无DestroyQueue

输入：无功能：销毁队列，释放队列所占用的存储空间输出：无EnQueue

输入：元素值x

功能：在队尾插入一个元素输出：如果插入成功，队尾增加了一个元素；否则返回失败信息a1

a2

…an入队出队Enqueue操作需要指明插入位置吗？队列的抽象数据类型定义DeQueue

输入：无功能：删除队头元素输出：如果删除成功，返回被删元素值；否则给出失败信息GetQueue

输入：无功能：读取队头元素输出：若队列不空，返回队头元素；否则给出失败信息Empty

输入：无功能：判断队列是否为空输出：如果队列为空，返回1，否则，返回0a1

a2

…an入队出队队列的抽象数据类型定义3-3-2队列的顺序存储结构及实现v第三章栈和队列顺序队列顺序队列：队列的顺序存储结构如何表示队尾：设变量rear存储队尾元素所在的下标如何表示队头：用数组的一端作为队头，从下标0处开始存放如何改造数组实现队列的顺序存储？01234a1a2a3a4rear例：a1a2a3a4依次入队入队操作的时间性能？01234a1a2a3a4rear例：a1a2依次出队顺序队列顺序队列：队列的顺序存储结构出队操作的时间性能？如何表示队尾：设变量rear存储队尾元素所在的下标如何表示队头：用数组的一端作为队头，从下标0处开始存放如何改造数组实现队列的顺序存储？如何改进出队操作的时间性能？01234a2a3a4rear设置队头、队尾两个位置指针约定：队头front指向队头元素的前一个位置，队尾rear指向队尾元素fronta1例：a1a2依次出队入队、出队时间性能均是O(1)顺序队列队列的移动有什么特点？01234a2a3a4front例：a1a2依次出队整个队列向数组下标较大方向移动单向移动性队列的单向移动性会产生什么问题？a5假溢出：数组空间发生上溢，但数组的低端还有空闲空间rear顺序队列如何解决假溢出呢？01234a3a4rearfront如何使数组下标循环呢？a5a6if(rear+1>4)rear=0;elserear++;循环队列：队列采用顺序存储，并且数组是头尾相接的循环结构程序技巧：求模（正余数）使得数组下标循环rear=(rear+1)%5循环队列循环队列的类定义InitQueue：队列的初始化DestroyQueue：队列的销毁EnQueue：入队DeQueue：出队GetQueue：取队头元素Empty：判空队列的抽象数据类型定义？constintQueueSize=100;template<typenameDataType>classCirQueue{public:CirQueue();~CirQueue();voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();intEmpty();private:

DataTypedata[QueueSize];intfront,rear;};CirQueue<DataType>::CirQueue(){front=rear=QueueSize-1;}循环队列的实现——初始化01234rearfrontCirQueue<DataType>::CirQueue(){front=rear=-1;}rearfront循环队列：队列采用顺序存储，并且数组是头尾相接的循环结构设置队头、队尾两个位置指针会出现Bug？01234a3rearfront如何判断循环队列的队空？队空的判定条件：front=rearintCirQueue<DataType>::Empty(){if(rear==front)return1;elsereturn0;}循环队列的实现——判空a6a2a4a5rearfront如何判断循环队列队满？队空的判定条件：front=rear队满的判定条件：front=rearx队空和队满0123401234a6a2a4a5rearfront如何确定不同的队空、队满的判定条件？队空的判定条件：front=rear队满的判定条件：front=rear数组中有一个空闲单元01234a1a2a4a5rearfront(rear+1)%QueueSize=front队空和队满template<typenameDataType>voidCirQueue<DataType>::EnQueue(DataTypex){

if((rear+1)%QueueSize==front)throw"上溢";

rear=(rear+1)%QueueSize;//队尾指针在循环意义下加1data[rear]=x;//在队尾处插入元素}

01234a3a4rearfront时间复杂度是多少？循环队列的实现——入队xPage07template<typenameDataType>DataTypeCirQueue<DataType>::DeQueue(){if(rear==front)throw"下溢";

front=(front+1)%QueueSize;//队头指针在循环意义下加1returndata[front];//读取并返回出队前的队头元素}取队头元素的实现？01234a2a3a4rearfront循环队列的实现——出队3-3-3队列的链式存储结构及实现v第三章栈和队列链队列的存储结构定义链队列：队列的链接存储结构firsta1a2an∧aiP：用链表的哪一端作为队头？哪一端作为队尾？A：链头作为队头，出队时间为O(1)

链尾作为队尾，入队时间为O(n)P：链队列需要加头结点吗？rearfront设置队尾指针rear链队列的类定义InitQueue：队列的初始化DestroyQueue：队列的销毁EnQueue：入队DeQueue：出队GetQueue：取队头元素Empty：判空队列的抽象数据类型定义？template<typenameDataType>classLinkedQueue{public:

LinkedQueue();~LinkedQueue();voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();intEmpty();private:

Node<DataType>*front,*rear;};xs∧front∧rear没有头结点会怎样？xs∧rearfrontrear=s;front=s;链队列的实现——入队voidLinkedQueue<DataType>::EnQueue(DataTypex){

Node<DataType>*s=nullptr;

s=newNode<DataType>;//申请结点s

s->data=x;s->next=nullptr;

rear->next=s;rear=s;}时间复杂度是多少？a1a2an∧airearfrontxs∧考虑边界情况？p∧考虑边界情况？如何判断边界情况？a1a2an∧airearfrontprear∧a1frontp->next=nullptr链队列的实现——出队DataTypeLinkedQueue<DataType>::DeQueue(){DataTypex;Node<DataType>*p=nullptr;

if(rear==front)throw"下溢";p=front->next;x=p->data;

front->next=p->next;if(p->next==nullptr)rear=front;deletep;returnx;}如何取队头元素？循环队列与链队列的比较作为一般规律，当队列中元素个数变化较大时，应该采用链队列，反之，应该采用循环队列，如果确定不会发生假溢出，也可以采用顺序队列。基本操作的时间复杂度均为O(1)。比较空间性能：循环队列：初始时必须确定一个固定的长度，所以有存储元素个数的限制和浪费空间的问题。链队列：没有溢出的问题，但是每个元素都需要一个指针域，从而产生了结构性开销。3-4多维数组v第三章栈、队列和数组数组的逻辑结构数组的存储结构及寻址学什么？3-4-1数组的逻辑结构v第三章栈、队列和数组数组的定义（多维）数组：由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标，并称该数组为

n维数组。

a11…a1n

…………

am1…amnA=a21

a22…a2na12am2数组有什么特点呢？（1）元素本身可以具有某种结构，属于同一数据类型；

A=(A1，A2，…，An)其中：Aj=(a1j，a2i，…，amj)(1≤j≤n)

A=(A1，A2，…，Am)其中：Ai=(ai1，ai2，…，ain)(1≤i≤m)（2）数组是一个具有固定格式和数量的数据集合。x数组的抽象数据类型定义数组有什么基本操作呢？（1）存取：给定一组下标，读出对应的数组元素（2）修改：给定一组下标，存储或修改与其相对应的数组元素寻址ADTMDArrayDataModel

相同类型的数据元素的有序集合，每个元素受n（n≥1）个线性关系的约束Operation

InitArray：数组的初始化

DestroyArray：数组的销毁Get：读操作，读取这组下标对应的数组元素Set：写操作，存储或修改这组下标对应的数组元素endADT3-4-2数组的存储结构及寻址v第三章栈、队列和数组数组的存储结构如何存储（多维）数组呢？数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储二维数组内存二维结构一维结构按行优先：先存储行号较小的元素，行号相同者先存储列号较小的元素按列优先：先存储列号较小的元素，列号相同者先存储行号较小的元素按行优先：先存储行号较小的元素，行号相同者先存储列号较小的元素l2h2

l1h1aij第l1行第l1+1行如何得到元素aij的存储地址？数组的存储结构l2h2

l1h1aijaij前面的元素个数=整行数×每行元素个数+本行中aij前面的元素个数=(i

-l1)×(h2

-l2＋1)＋(j

-l2)Loc(aij)Loc(al1l2)(i

-l1)×(h2

-l2+1)＋(j

-l2)个元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按列优先与此类似，请自行给出数组元素的寻址3-5矩阵的压缩存储v第三章栈、队列和数组对称矩阵的压缩存储三角矩阵的压缩存储对角矩阵的压缩存储学什么？稀疏矩阵的压缩存储特殊矩阵的压缩存储3-5-1特殊矩阵的压缩存储v第三章栈、队列和数组特殊矩阵什么是特殊矩阵？

特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律特殊矩阵如何压缩存储？为值相同的元素分配一个存储空间特殊矩阵压缩存储后有什么要求吗？保证随机存取，即在O(1)时间内寻址3647862842481697460582957A＝对称矩阵特点：aij=aji如何压缩存储对称矩阵呢？只存储下三角部分的元素对称矩阵aij在一维数组中的序号=

i×(i-1)/2+j∵一维数组下标从0开始∴aij在一维数组中的下标k=i×(i-1)/2+j-1

1…

i

n1…j…n

aij第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2-1对称矩阵下三角中的元素aij（i≥j）：k＝i×(i-1)/2＋j-1压缩存储后的寻址方法上三角中的元素aij（i＜j），k＝j×(j-1)/2＋i

-1如何压缩存储三角矩阵呢？3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩阵34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩阵相同的常数只存储一个下（上）三角部分的元素三角矩阵下三角矩阵的压缩存储第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2c下三角中的元素aij（i≥j）：k＝i×(i

-1)/2+j-1上三角中的元素aij（i＜j）：k＝n×(n+1)/2下三角矩阵压缩存储后的寻址方法上三角矩阵的压缩存储请仿此给出三角矩阵对角矩阵对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，所有其他元素都为零。

a11a120

00a21a22

a23000a32

a33a34000

a43

a44

a45000a54

a55A=如何压缩存储对角矩阵呢？只存储非零元素

元素aij在一维数组中的序号=2+3(i-2)+(j-i+2)=2i+j-2∵一维数组下标从0开始∴元素aij在一维数组中的下标=

2i+j-3a11a12000a21a22

a23000a32a33

a34000

a43a44

a45

000a54a55A=

a11a12a21a22a23a32a33a34a43a44a45a54a55012345678