程序设计初步1

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

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];//顺序堆栈数组inttop;//栈顶位置指示器public:SeqStack(void){top=0;}//构造函数~SeqStack(void){}//析构函数void

3、Push(constDataTypeitem);//入栈DataTypePop(void);//出栈DataTypeGetTop(void)const;//取栈顶数据元素intNotEmpty(void)const;//堆栈非空否{return(top!=0);};};(3)顺序栈类的操作实现一、voidSeqStack::Push(constDataTypeitem)//入栈//把元素item入栈;堆栈满时出错退出{if(top==MaxStackSize){cout<<"堆栈已满!"<

4、后top加1}二、DataTypeSeqStack::Pop()//出栈//出栈并返回栈顶元素;堆栈空时出错退出{if(top==0){cout<<"堆栈已空!"<#

5、includeconstintMaxStackSize=100;//定义问题要求的元素数目的最大值typedefintDataType;//定义具体问题元素的数据类型voidmain(voie){SeqStackmyStack;//构造函数无参数时，定义的对象后不带括号DataTypetest[]={1,3,5,7,9};intn=5;for(inti=0;i

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

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