L09-L10 算法分析与数据结构.ppt

《L09-L10 算法分析与数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络游戏算法设计第2章算法分析与数据结构第2章算法分析与数据结构栈的基本运算栈的存储结构迷宫问题的实现了解栈的基本运算了解栈的存储结构了解迷宫问题的实现第2章算法分析与数据结构栈的基本运算栈的存储结构迷宫问题的实现栈的基本运算栈的存储结构迷宫问题的实现第2章算法分析与数据结构2.4线性表2.4.3栈栈是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶，另一端称为栈底。栈的插入操作通常称为入栈或进栈，而栈的删除操作则称为出栈或退栈。当栈中没有数据元素时，称为空栈。第2章算法分析与数据结构2.4线性表栈通常用指针top指示栈顶的位置，用指针

2、bottom指向栈底。栈顶指针top动态反映栈的当前位置。入栈时，新加入的元素变成新的栈顶，栈顶指针top指向新加入的元素；出栈时，它指向出栈元素的下一个元素，即新的栈顶第2章算法分析与数据结构2.4线性表栈的基本运算栈的基本运算包括以下6种：1）StackFull判断是否栈满；2）Empty()栈的空判断：若栈为空，则返回TRUE；否则，返回FALSE；3）Push(x)入栈：在栈的顶部插入元素x，若栈满，则返回FALSE；否则，返回TRUE；4）Pop()出栈：若栈不空，则返回栈顶元素，并从栈顶中删除该元素；否则，返回空元素NULL；5）GetTop()取栈元素：若栈不空，则返回栈顶元素

3、；否则返回空元素NULL；6）SetEmpty()置栈空操作：置栈为空栈。第2章算法分析与数据结构2.4线性表栈的存储结构constunsignedSTACKSIZE=10;//定义栈的最大容量classStack{unsignedm_nTop;intm_StackData[STACKSIZE];public:Stack():m_nTop(0){}boolEmpty()const;//判断栈是否为空boolStackFull()const;//判断栈是否满voidPush(intdata);//将data数据压入栈中intPop();//将栈顶数据弹出intGetTop()const;//获

4、取栈顶数据voidSetEmpty();//将栈设为空};顺序栈第2章算法分析与数据结构2.4线性表1）Push(x)入栈voidGameCollege::Stack::Push(intdata){if(StackFull()){Exceptione("栈已经满，无法进行压入操作");throwe;}m_StackData[m_nTop++]=data;//将数据压入栈中}m_nTop用来表示栈顶位置，它对应m_StackData数组单元的位置，当有数据需要压入栈中，只要通过m_nTop找到m_StackData数组相对应的单元，然后将数据写入此单元第2章算法分析与数据结构2.4线性表2）Po

5、p()出栈intGameCollege::Stack::Pop(){if(Empty()){Exceptione("栈已空，无法进行出栈操作");throwe;}returnm_StackData[--m_nTop];}第2章算法分析与数据结构2.4线性表3）StackFull判断是否栈满boolGameCollege::Stack::StackFull()const{returnm_nTop==STACKSIZE;}4）Empty()空栈判断。boolGameCollege::Stack::Empty()const{returnm_nTop==0;}第2章算法分析与数据结构2.4线性表5）S

6、etEmpty()设置栈为空voidGameCollege::Stack::SetEmpty(){m_nTop=0;}6）GetTop()取栈顶元素intGameCollege::Stack::GetTop()const{if(Empty()){Exceptione("栈为空");throwe;}returnm_StackData[m_nTop-1];}第2章算法分析与数据结构2.4线性表链栈structNode{intnData;Node*pNextNode;};classStack{public:Stack();~Stack();voidPush(intdata);intPop();boo

7、lEmpty();voidSetEmpty();intGetTop()const;private:voidClearStack();Node*m_pTop;};第2章算法分析与数据结构2.4线性表voidGameCollege::Stack::Push(intdata){Node*pNewNode=newNode;if(!pNewNode){Exceptione("内存分配失败！");throwe