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

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

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

3、删除该元素；否则，返回空元素NULL； 5）GetTop() 取栈元素：若栈不空，则返回栈顶元素；否则返回空元素NULL； 6）SetEmpty() 置栈空操作：置栈为空栈。,第2章 算法分析与数据结构,2.4 线性表, 栈的存储结构,const unsigned STACKSIZE = 10; / 定义栈的最大容量 class Stack unsigned m_nTop; int m_StackDataSTACKSIZE; public: Stack() : m_nTop(0) bool Empty()const; / 判断栈是否为空 bool StackFull() const; / 判断

4、栈是否满 void Push(int data); / 将data数据压入栈中 int Pop(); / 将栈顶数据弹出 int GetTop() const; / 获取栈顶数据 void SetEmpty(); / 将栈设为空 ;,顺序栈,第2章 算法分析与数据结构,2.4 线性表,1）Push(x)入栈,void GameCollege:Stack:Push(int data) if (StackFull() Exception e(栈已经满，无法进行压入操作); throw e; m_StackDatam_nTop+ = data; / 将数据压入栈中 ,m_nTop用来表示栈顶位置，它

5、对应m_StackData数组单元的位置，当有数据需要压入栈中，只要通过m_nTop找到m_StackData数组相对应的单元，然后将数据写入此单元,第2章 算法分析与数据结构,2.4 线性表,2）Pop()出栈,int GameCollege:Stack:Pop() if (Empty() Exception e(栈已空，无法进行出栈操作); throw e; return m_StackData-m_nTop; ,第2章 算法分析与数据结构,2.4 线性表,3）StackFull判断是否栈满,bool GameCollege:Stack:StackFull()const return m_

6、nTop = STACKSIZE; ,4）Empty()空栈判断。,bool GameCollege:Stack:Empty() const return m_nTop = 0; ,第2章 算法分析与数据结构,2.4 线性表,5）SetEmpty()设置栈为空,void GameCollege:Stack:SetEmpty() m_nTop = 0; ,6）GetTop()取栈顶元素,int GameCollege:Stack:GetTop() const if (Empty() Exception e(栈为空); throw e; return m_StackDatam_nTop-1; ,第

7、2章 算法分析与数据结构,2.4 线性表,链栈,struct Nodeint nData;Node *pNextNode; class Stack public: Stack(); Stack(); void Push(int data); int Pop(); bool Empty(); void SetEmpty(); int GetTop() const; private: void ClearStack(); Node* m_pTop; ;,第2章 算法分析与数据结构,2.4 线性表,void GameCollege:Stack:Push(int data) Node *pNewNod

8、e = new Node; if (!pNewNode) Exception e(内存分配失败！); throw e; pNewNode-nData = data; pNewNode-pNextNode = NULL; if (!m_pTop)m_pTop = pNewNode; else pNewNode-pNextNode = m_pTop; m_pTop = pNewNode; ,1）Push(x)入栈。,第2章 算法分析与数据结构,2.4 线性表,2）Pop()出栈,int GameCollege:Stack:Pop() if (!m_pTop) Exception e(栈为空，无法完

9、成弹出操作！); throw e; Node *tempNode = m_pTop; m_pTop = m_pTop-pNextNode; int data = tempNode-nData; delete tempNode; return data; ,第2章 算法分析与数据结构,2.4 线性表,3）Empty()空栈判断,bool GameCollege:Stack:Empty() if (!m_pTop) return true; else return false; ,第2章 算法分析与数据结构,2.4 线性表,4） SetEmpty()设置栈为空,void GameCollege:S

10、tack:SetEmpty()ClearStack(); void GameCollege:Stack:ClearStack() if (m_pTop) Node *tempNode = m_pTop; while (m_pTop) m_pTop = m_pTop-pNextNode; delete tempNode; tempNode = m_pTop; m_pTop = NULL; ,第2章 算法分析与数据结构,2.4 线性表,5）GetTop()取栈顶元素,int GameCollege:Stack:GetTop() const if (!m_pTop) Exception e(栈为空，

11、无法获取栈顶数据！); throw e; return m_pTop-nData; ,第2章 算法分析与数据结构,2.4 线性表,迷宫问题的实现,在迷宫中行进时必须遵守以下3个原则： 1）一次只能走一格； 2）遇到墙无法往前走时则退回一步，看一下是否有其他的路可以走； 3）走过的路不会再走第二次。,走迷宫是堆栈在实际应用上的一个很好的例子。在迷宫出口路径的搜索过程中，程序必须判断下一步该往哪一个方向移动，此外还必须记录走过的迷宫路径，如此才可以在走迷宫中死路时回头来搜索其他的路径。,第2章 算法分析与数据结构,2.4 线性表,用二维数组MAZErowcol来表现一个模拟迷宫,1）MAZEij=

12、1表示ij处有墙，无法通过； 2）MAZEij=0表示ij处无墙，可以通过； 3）MAZE11是入口，MAZEmn是出口。,第2章 算法分析与数据结构,2.4 线性表,老鼠可以选择的方向有4个，分别为东、西、南、北。但并非每个位置都有4个方向可以选择，必须视情况来决定,可以利用链表来记录走过的位置，并且将走过位置的队列元素均标记为2，然后将这个位置放入堆栈再进行下一次的选择。如果走进死巷子并且还没有抵达终点，那么就必须退回到上一个位置，并一直退到上一个叉口再选择其他路径。 由于每次新加入的位置必定在堆栈的最末端，因此堆栈末端所指的方格编号便是目前老鼠所在的位置。,小结,第2章 算法分析与数据结构,本章还描述基本数据结构-堆栈。栈是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而是最后出栈。,小测验,第2章 算法分析与数据结构,判断试题,入栈时，新加入的元素变成新的栈顶，栈顶指针top指向新加入的元素；出栈时，它指向出栈元素的下一个元素。 （ ）,选择题（单选题）,关于堆栈的说法正确的是（ ）。 A. 堆栈的访问顺序是FIFO B. 堆栈的插入和删除是分别在两端进行 C. 堆栈的插入操作称为入栈，删除操作称为出栈 D. 堆栈只能用顺序结构存储,小测验答案,第2章 算法分析与数