数据结构与算法(C++) 讲栈ppt课件.ppt

《数据结构与算法(C++) 讲栈ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、EssentialofLectureFive：一、栈的定义二、栈的存储结构三、顺序栈和链栈的实现四、栈的应用第五讲栈难点1课前实战：程序填空题以下程序功能是实现带附加头结点的单链表数据结点逆序连接。voidreverse(pointerh){/*h为附加头结点指针*/pointerp,q;p=h->next;h->next=NULL;while((1)){q=p;p=p->next;q->next=h->next;h->next=(2);}}2一、栈的定义（stack）只允许在一端插入和删除的线性表。允许插入和删除的一端称为栈顶(to

2、p)，另一端称为栈底(bottom)。特点：后进先出(LIFO)退栈进栈a1anan-1topbottom3一、栈的定义（stack）1．intLength()const初始条件：栈已存在。操作结果：返回栈元素个数。2．boolEmpty()const初始条件：栈已存在。操作结果：如栈为空，则返回true，否则返回false3．voidClear()初始条件：栈已存在。操作结果：清空栈。栈的基本操作4一、栈的定义（stack）4．voidTraverse(void(*Visit)(constElemType&))const初始条件：

3、栈已存在。操作结果：从栈底到栈顶依次对栈的每个元素调用函数(*visit)5．StatusCodePush(constElemType&e)初始条件：栈已存在。操作结果：插入元素e为新的栈顶元素。栈的基本操作a1a2anx……5一、栈的定义（stack）6．StatusCodeTop(ElemType&e)const初始条件：栈已存在且非空。操作结果：用e返回栈顶元素。栈的基本操作a1a2an……6a1a2anan-1……7．StatusCodePop(ElemType&e)初始条件：栈已存在且非空。操作结果：删除栈顶元素，并用e

4、返回栈顶元素。一、栈的定义（stack）栈的基本操作7templateclassSqStack{protected://顺序栈的数据成员:intcount;//元素个数intmaxSize;//栈最大元素个数ElemType*elems;//元素存储空间//辅助函数boolFull()const;//判断栈是否已满voidInit(intsize);//初始化栈二、栈的存储结构1、顺序栈类的实现8public://抽象数据类型方法声明及重载编译系统默认方法声明:SqStack(intsize=DEFAUL

5、T_SIZE);//构造函数virtual~SqStack();//析构函数intLength()const;//求栈长度boolEmpty()const;//判断栈是否为空voidClear();//将栈清空voidTraverse(void(*Visit)(constElemType&))const;//遍历栈二、栈的存储结构1、顺序栈类的实现9StatusCodePush(constElemType&e);//入栈StatusCodeTop(ElemType&e)const;//返回栈顶元素StatusCodePop(ElemT

6、ype&e);//出栈SqStack(constSqStack©);//复制构造函数SqStack&operator=(constSqStack©);//赋值语句重载};二、栈的存储结构1、顺序栈10templateSqStack::SqStack(constSqStack©){elems=NULL;//未分配存储空间前,elems为空Init(copy.maxSize);//初始化

7、新栈count=copy.count;//栈元素个数for(intcurPosition=1;curPosition<=Length();curPosition++){//从栈底到栈顶对栈copy的每个元素进行复制elems[curPosition-1]=copy.elems[curPosition-1];}}二、栈的存储结构复制构造函数11templateSqStack&SqStack::operator=(constSqStack©)

8、{if(©!=this){Init(copy.maxSize);//初始化当前栈count=copy.count;//复制栈元素个数for(intcurPosition=1;curPosition<=Length