内蒙古大学《算法与数据结构》课件第3章栈、队列与广义表
98页1、1第三章第三章 栈、队列与广义表栈、队列与广义表 3.1 栈栈 3.2 队列队列 3.3 栈与队列的应用栈与队列的应用 3.4 广义表广义表23.1 栈栈 ( Stack ) 3栈的抽象数据类型栈的抽象数据类型ADT Stack Data 数据元素表数据元素表 top: 栈顶位置栈顶位置 Operations Constructor Process: 创建一个空栈创建一个空栈 IsEmpty Process: 判断栈是否为空判断栈是否为空 Output: 如果栈为空,则返回如果栈为空,则返回true,否则返回,否则返回false GetTop Process: 取栈顶元素取栈顶元素 Output: 返回栈顶元素返回栈顶元素 3.1.1 ADT栈栈4栈的抽象数据类型栈的抽象数据类型 Length Process: 求栈中元素个数求栈中元素个数 Output: 返回栈中元素的个数返回栈中元素的个数 Push / 入栈入栈 Input: 要添加的数据元素要添加的数据元素 Process: 向栈中添加元素向栈中添加元素x Pop / 出栈出栈 Process: 删除栈顶元素删除栈顶元素 Out
2、put: 返回栈顶元素返回栈顶元素 Clear Process: 删除栈中所有元素并置新的栈顶删除栈中所有元素并置新的栈顶 /Stack5一、顺序栈一、顺序栈const int MaxStackSize=50; /栈中能容纳最大元素个数栈中能容纳最大元素个数class SeqStack DataType StackListMaxStackSize; int top; public: SeqStack(); /构造函数,初始化构造函数,初始化top bool IsEmpty(); /判断栈的状态是否为空判断栈的状态是否为空 bool IsFull(); DataType GetTop(); /取栈顶元素取栈顶元素 void Push(const DataType x); /入栈入栈 DataType Pop(); /出栈出栈 void Clear(); /栈清空栈清空;/ SeqStack3.1.2 栈的实现栈的实现6顺序栈的基本操作的实现顺序栈的基本操作的实现: SeqStack( ) /构造函数,初始化一个空栈构造函数,初始化一个空栈 StackList = new DataType
3、MaxStackSize; top=-1; / SeqStack bool SeqStack : IsEmpty ( ) /判断栈是否为空判断栈是否为空 if(top=-1) return true; else return false;/ IsEmpty7bool SeqStack :IsFull( ) /判断栈是否已满判断栈是否已满 if(top=MaxStackSize-1) return true; else return false;/ IsFull8DataType SeqStack : GetTop( ) /取栈顶元素取栈顶元素 i f (IsEmpty( ) cout”栈空!栈空!”endl; return nulldata; return StackListtop;9栈顶指针栈顶指针top,指向栈底指向栈底位置位置top入栈入栈Atop出栈出栈栈满栈满BCDEFtop=-1,栈空,此时出栈,则下溢(栈空,此时出栈,则下溢(underflow)top= MaxStackSize-1,栈满,此时入栈,则上溢栈满,此时入栈,则上溢(overflow)toptoptoptop
4、toptoptoptoptoptoptop栈空栈空top123450栈空栈空123450ABCDEF123450顺序栈的入栈与出栈顺序栈的入栈与出栈10void SeqStack : Push(DataType x) /入栈入栈 if (IsFull( ) cout”栈满!栈满!”endl; else StackList+top = x;/ Push11DataType SeqStack : Pop( ) /出栈出栈 if (IsEmpty( ) cout”栈空!栈空!”next=NULL; /创建头结点创建头结点 void Push (DataType data); /入栈入栈 DataType Pop ( ); /出栈出栈 DataType GetTop ( ); / 读栈顶元素读栈顶元素 void Clear ( ) top-next=NULL; /清栈空清栈空,实现错实现错 bool IsEmpty ( ) return top -next= = NULL; /判栈空判栈空;/ LinkStack链式栈链式栈 (LinkedStack)类的定义类的定义17类中操作算法描述如下:
5、类中操作算法描述如下:void LinkStack : Push (DataType item ) /入栈操作入栈操作 p=new StackNode ( item); p-next=top-next; top-next=p;/Push18DataType LinkStack :pop ( ) /出栈操作出栈操作 if ( top-next!=NULL ) p = top-next; retvalue = p-data; /暂存栈顶数据暂存栈顶数据 top -next= p-next; /修改栈顶指针修改栈顶指针 delete p; return retvalue; /释放释放,返回数据返回数据 else /栈空的情况栈空的情况 cout”the stack is empty!”next!=NULL) return top-next-data; else /栈空的情况栈空的情况 cout”the stack is empty!”0Fact(n)=1 若n=0Fib(n)=0 (n=0)1 (n=1)Fib(n-1)+Fib(n-2) (n1)3.1.3 栈与递归栈与递归243递归算法的
《内蒙古大学《算法与数据结构》课件第3章栈、队列与广义表》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》课件第3章栈、队列与广义表》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页