《程序设计初步》PPT课件.ppt

《《程序设计初步》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章堆栈和队列主要知识点堆栈堆栈应用队列优先级队列3.1堆栈1、堆栈的基本概念(1)定义:限定只能在固定一端进行插入和删除操作的线性表。特点：后进先出。(2)允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。2、堆栈抽象数据类型数据集合:{a0,a1,…,an-1}ai的数据类型为DataType。操作集合：(1)Initiate(S)初始化堆栈S(2)Push(S,x)入栈(3)Pop(S,d)出栈(4)GetTop(S)取栈顶数据元素(5)NotEmpty(S)堆栈S非空否3、顺序堆栈类(1

2、)顺序堆栈顺序存储结构的堆栈。(2)顺序栈的存储结构它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，其结构如图所示：a0a1a2a3a4stack栈底栈顶MaxStackSize-1012345=top其中，a0,a1,a2,a3,a4表示顺序堆栈中已存储的数据元素，stack表示存放数据元素的数组，MaxStackSize-1表示最大存储单元个数，top表示当前栈顶存储下标。类的定义：classSeqStack{private:DataTypedata[MaxStackSize];//

3、顺序堆栈数组inttop;//栈顶位置指示器public:SeqStack(void){top=0;}//构造函数~SeqStack(void){}//析构函数voidPush(constDataTypeitem);//入栈DataTypePop(void);//出栈DataTypeGetTop(void)const;//取栈顶数据元素intNotEmpty(void)const;//堆栈非空否{return(top!=0);};};(3)顺序栈类的操作实现一、voidSeqStack::Push(c

4、onstDataTypeitem)//入栈//把元素item入栈;堆栈满时出错退出{if(top==MaxStackSize){cout<<"堆栈已满!"<

5、//然后取元素返回}三、DataTypeSeqStack::GetTop(void)const//取栈顶数据元素//取当前栈顶数据元素并返回{if(top==0){cout<<"堆栈空!"<#includeconstintMaxStackSize=100;//定义问题要求的元素数目的最大值typedefintDataType;//定义具体问

6、题元素的数据类型voidmain(voie){SeqStackmyStack;//构造函数无参数时，定义的对象后不带括号DataTypetest[]={1,3,5,7,9};intn=5;for(inti=0;i

7、链式栈的存储结构它是以头指针为栈顶，在头指针处插入或删除，其结构如图所示：头结点an-1an-2a0∧…h栈底栈顶链栈中每个结点由两个域构成：data域和next域，其结点类和类定义分别如下：templateclassLinStack;//前视定义，否则友元无法定义//结点类template//模板类型为TclassStackNode{friendclassLinStack;//定义类LinStack为友元private:Tdata;//数据元素StackN

8、ode*next;//指针public://构造函数1，用语构造头结点StackNode(StackNode*ptrNext=NULL){next=ptrNext;}//构造函数2，用于构造其他结点StackNode(constT&item,StackNode*ptrNext=NULL){data=item;next=ptrNext;}~StackNode(){};};//链式堆栈类的定义templateclassLin