2-基本数据结构1.ppt

1、ACM/ICPC程序设计,基本数据结构 及其在程序设计中的应用,程序=数据结构+算法,数据结构(Data Structure)是数据的计算机表示和相应的一组操作。 算法(Algorithm)就是解决问题的方法或过程。,基本数据结构,线性结构 非线性结构 集合,树结构 图结构,线性表 栈 队列 串,线性结构,线性表: 由n个元素组成的有限序列。每个元素有确定的前驱和后继。,元素之间的关系仅限于前趋、后继关系 表、栈、队列、串,元素的存储方式 数组 链表,线性结构,由n个元素组成的有限序列。每个元素有确定的前驱和后继。,表：不限制元素的插入和删除位置。有n+1个位置可供插入，n个元素可供删除 栈：

2、插入和删除操作只允许在表尾进行 队列：在表尾插入、在表头删除 串：元素为字符的线性表，有求子串、子串定位、子串替换等操作,(a1，a2，ai，an),数组,用一组连续的存储单元依次存储数据元素. 表中任一元素可以随机存取. 插入或删除一个元素需要移动其他元素.,由下标确定数组元素ai： Loc(ai)=Loc(a1)+(i-1)*d (1in),例如：由n个元素构成的一维数组a,链表,链式存储:任意存储单元存储元素 链表结点包括数据域和指针域 插入或删除一个元素,只需修改结点指针域 访问任一元素必须从链表头指针开始,链表结点,链式存储:任意存储单元存储元素 链表结点包括数据域和指针域 插入或删

3、除一个元素,只需修改结点指针域 访问任一元素必须从链表头指针开始,struct Node ElemType data； /数据元素 struct Node *next； /指向后继结点的指针 ;,单向链表,线性表： (a1，a2，ai-1，ai，ai+1，an),(a) 单向链表,双向链表和循环链表,线性表： (a1，a2，ai-1，ai，ai+1，an),单链表的插入和删除,链式存储:任意存储单元存储元素 链表结点包括数据域和指针域 插入或删除一个元素，只需修改结点指针域 访问任一元素必须从链表头指针开始,头结点,带头结点的单向链表,单链表中插入元素,将元素ai所在结点的地址赋给元素e结点的

4、指针域： S-next = P-next;,修改元素ai-1所在结点指针域的值： P-next = S;,单链表中删除元素ai,修改元素ai-1所在结点指针域的值： P-next = P-next -next;,例1:Ugly Numbers,Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, . shows the first 11 ugly numbers. By convention, 1 is included.

5、 Write a program to find and print the 1500th ugly number.,算法思路: 一个正整数m可表示如下： m = (p1)j1 * (p2)j2 * *(pn)jn Ugly number = 2j1 * 3j2 * 5j3 (j1,j2,j3=0) 在已知序列中,找一个最小的数,使得它乘以2比已知序列最后一个元素大;找一个最小的数,使得它乘以3比最后一个元素大;找一个最小的数,使得它乘以5比最后一个元素大. 在这三个乘积中找最小的添加到表尾,反复按此规则构造递增序列,直到表中有1500个元素。 可以用数组预先分配1500个单元,也可以用链表动

6、态分配.,例2：The Blocks Problem,编号为0n-1的n个木块，放在编号为0n-1的n个格子里, 可对它们进行四种有效的操作。,0,1,2,3,4,n-1,.,Initial Block World,move a onto b ：先将a和b上的其他木块移回到它们的初始位置，然后将木块a摞在木块b上.,move a over b ：先将木块a上的其他木块移到它们的初始位置后，然后将木块a摞到包含了木块b的那一堆木块上面,pile a onto b ：先将木块b上的所有木块移回到它们的初始位置，然后将木块a及其上的木块移到木块b上.,pile a over b ：将包含木块a的那一

7、摞木块移到包含了木块b的那一堆木块上面.,move a onto b 先将a和b上的其他木块移回到它们的初始位置，然后将木块a摞在木块b上.,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,Example: move 3 onto 6,3,move a over b 先将木块a上的其他木块移到它们的初始位置后，然后将木块a摞到包含了木块b的那一堆木块上面.,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,Example: move 3 over 6,3,pile a onto b 先将木块b上的所有木块移回到它们的初始位置，然后将

8、木块a及其上的木块移到木块b上.,Example: pile 3 onto 6,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,pile a over b 将包含木块a的那一摞木块移到包含了木块b的那一堆木块上面.,Example: pile 3 over 6,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over

9、9 quit,输入数据样本,0: 0 1: 1 9 2 4 2: 3: 3 4: 5: 5 8 7 6 6: 7: 8: 9:,input：,output：,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,处理过程：,Initial Block World,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,格子 编号,10 move 9 onto 1 move 8 over

10、1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,处理过程(续)：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,处理过程(续) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,

11、5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,处理过程(续) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,

12、处理过程(续) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,处理过程(续) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,Any command in which a = b or in which a and b are in the same stack of blocks i

13、s an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,处理过程(续) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 o

14、nto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,处理过程(续) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,处理过程(续) ：,0,1,2,3,4,5

15、,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit,处理过程(续) ：,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,output：,10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2

16、 over 1 move 4 over 9 quit,处理结果,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0: 0 1: 1 9 2 4 2: 3: 3 4: 5: 5 8 7 6 6: 7: 8: 9:,input：,分析,设计的操作: f(i): 把叠在木块i上的其他木块放回初始位置. m(i,j): 把i及其以上的木块全叠到包含j的上方.,move a onto b = f(a),f(b),m(a,b) move a over b = f(a),m(a,b) pile a onto b = f(b),m(a,b) pile a over b = m(

17、a,b),按以上规则，用链表的操作直接模拟即可.,数据结构设计,设计的数据结构:,struct Node int No； /木块编号 struct Node *next； /指向后继结点的指针 ;,struct Node *Station25; int Bplace25;,示例 ：,pile 9 over 6,示例(续)：,0,Station0,1,Station1,2,Station2,3,Station3,4,Station4,5,Station5,6,Station6,7,Station7,8,Station8,9,Station9,pile 9 over 6,q-next = p,示例

18、(续) ：,0,Station0,1,Station1,2,Station2,3,Station3,4,Station4,5,Station5,6,Station6,7,Station7,8,Station8,9,Station9,pile 9 over 6,6,6,示例(续) ：,pile 9 over 6,示例结束,例3: Roman Roulette,N个人排成一圈，按顺时针从1到N编号。从1开始顺时针数到第k个人，让其出圈，接着数到第k个人，让他站在出圈者的位置上。然后从出圈者的后继位置开始数，重复上述过程直到环中只剩1个人。当N=5,k=2时，出环者的顺序为：2，5，3，1；最后留下

19、4。 输入：N，k 输出：I，使得从第I个人开始数，最后能留下第1人。,模拟过程,N5，k2,1,2,3,4,5,1,出圈序列：,2,2出去,接着从1开始数,模拟过程(续1),N5，k2,1,4,5,2,3,出圈序列：2,3,4,4占据2的位置,模拟过程(续2),N5，k2,1,3,5,4,出圈序列：2,3,接着从1 开始数,5,5出去,模拟过程(续3),N5，k2,3,5,4,出圈序列：2，5,接着数,1,1,4,4占据5的位置,模拟过程(续4),N5，k2,1,3,出圈序列：2，5,4,接着数,1,3,3出去,模拟过程(续5),N5，k2,1,3,4,出圈序列：2，5，3,接着数,4,1,

20、1占据3的位置,模拟过程(续6),N5，k2,1,4,接着数,出圈序列：2，5，3,4,1,1出去，环内仅剩1人，结束,1,模拟过程(续7),N5，k2,1,4,出圈序列：2，5，3，1,计数时需要避免计算已出圈的元素,分析,当N5，k2时 从1开始数，留下4； 从2开始数，留下5； 从3开始数，留下1； 因此，输入5、2时，按照要求，应输出3,一般的情况： 从1开始数，留下i； 从2开始数，留下i1； 从n-i+1开始数，留下i+ (n-i+1) -1 = n； 从n-i+2开始数，留下i+ (n-i+2) -1 = 1； 即对任意输入，设程序均从1开始数，则最后第i人留下，若希望第1人留下

21、，则应从第ni2人开始数，因此输出：ni2。,存储结构,用循环链表作为存储结构进行模拟，除了考虑计数问题外，还特别需要注意指针的运算,用数组作为存储结构，重点在于计数的处理,#include #include int surviver(int n,int k); int main() ifstream fin(E.in); ofstream fout(E.out); int n,k; for(;finnk ,Roman Roulette程序实现 (uva 130),surviver(n,k) 从第1人开始数，返回值为留下的人的编号i。 输出：ni2，使第1人留下,int surviver(in

22、t n,int k) std:vector people; int i,p=-1,p2; for(i=0;i1) p = (p+k) % people.size(); for(i=0,p2=p;ip2) p-; return people0; ,Roman Roulette程序实现 (uva 130),用线性表保存,n个人放进环里,数到第k个人,继续往后数k个人,前者出去，后者 取代他的位置,栈和队列,栈：仅在表尾进行插入删除的线性表,后进先出。 栈常用于模拟和深度优先搜索。 队列：在表尾插入，在表头删除，先进先出。 队列常用于模拟和广度优先搜索。,(a1，a2，ai，an),栈的示意,栈的修

23、改是按照后进先出的原则进行的，所以栈称为后进先出的线性表（LIFO）,栈底,入栈,出栈,栈顶,栈运算示例,例如，有A、B、C、D、E五个元素依次进入一个栈，若得到的输出序列是CBDAE ，那么栈中的运算是如何进行的？,空栈,栈运算示例(续),设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。,A,元素A入栈,栈运算示例(续),A,元素A入栈,B,元素B入栈,设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。,break,栈运算示例(续),A,元素A入栈 元素B入栈,B,C,元素C入栈,设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列

24、CBDAE的过程。,break,栈运算示例(续),A,元素A入栈 元素B入栈 元素C入栈,C,B,元素C出栈,C,设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。,break,栈运算示例(续),A,元素A入栈 元素B入栈 元素C入栈 元素C出栈,C,元素B出栈,B,B,设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。,break,栈运算示例(续),A,元素A入栈 元素B入栈 元素C入栈 元素C出栈 元素B出栈,C，B,D,元素D入栈,设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。,break,C，B,栈运算示

25、例(续),A,元素A入栈 元素B入栈 元素C入栈 元素C出栈 元素B出栈 元素D入栈,C，B，D,D,元素D出栈,设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。,break,C，B，D,栈运算示例(续),空栈,元素A入栈 元素B入栈 元素C入栈 元素C出栈 元素B出栈 元素D入栈 元素D出栈,C，B，D，A,元素A出栈,A,设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。,break,栈运算示例(续),元素A入栈 元素B入栈 元素C入栈 元素C出栈 元素B出栈 元素D入栈 元素D出栈 元素A出栈,C，B，D，A,E,元素E入栈,设有A、

26、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。,break,C，B，D，A,栈运算示例(续),空栈,元素A入栈 元素B入栈 元素C入栈 元素C出栈 元素B出栈 元素D入栈 元素D出栈 元素A出栈 元素E入栈,C，B，D，A，E,元素E出栈,E,设有A、B、C、D、E五个元素依次进入一个栈，得到输出序列CBDAE的过程。,break,栈运算示例(续),Push(A) Push(B) Push(C) pop() pop() Push(D) pop() pop() Push(E) pop(),C，B，D，A，E,A，B，C，D，E,设有A、B、C、D、E五个元素依次进入一个栈，

27、得到输出序列CBDAE的过程。,例4：Rail,zoj 1259 火车有n节车厢，顺序编号为1,2,3,.,n，从A驶入，从B驶出，车站里能停放任意多节车厢。一旦进入车站就不再回到A方向的铁轨上，一旦进入B方向铁轨，不再回车站。判断一个指定车厢顺序能否从B方向驶出。,例5: Anagrams by Stack(zoj 1004),问题：有一个字母序列，对它每个元素进行入栈、出栈操作。判断是否能得到指定输出序列，如果可以，则输出相应的栈操作。,input：,madam adamm,output：, i i i i o o o i o o i i i i o o o o i o i i o i o

28、 i o i o o i i o i o i o o i o ,例6：迷宫问题,寻找一条从入口到出口的通路,东,南,迷宫问题(续),北(上),西(左),前进方向：上(北)、下(南)、左(西)、右(东),首先从下方开始，按照逆时针方向搜索下一步可能前进的位置,迷宫问题(续),入口,出口,在迷宫周围加墙，避免判断是否出界,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,迷宫问题(续),9,0,9,0,在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出栈,i,8,1,2,3,4,5,6,

29、7,8,1,2,3,4,5,6,7,迷宫问题(续),9,0,9,0,栈,(1,1),(2,1),向下方前进一步,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),i,(3,1),向下方前进一步,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(4,1),(3,1),i,向下方前进一步,break,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),

30、(5,1),(3,1),(4,1),向下方前进一步,break,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(6,1),(3,1),(4,1),(5,1),向下方前进一步,break,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),向下方前进一步,break,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,

31、2,3,4,5,6,7,9,0,9,0,向下方 、右方、左方均不能前进，上方是来路，则后退,栈,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),break,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),向右方、左方均不能前进，下方路不通，上方是来路，则后退,break,i,i,i,i,i,8,1,2,3,4,5,6,7,迷宫问题(续),0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,

32、9,0,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(5,2),向右方前进一步,break,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(5,3),(5,2),break,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,迷宫问题(续),0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1

33、),(6,1),(5,2),(5,3),break,i,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,4),(5,2),(5,3),(6,3),i,break,i,i,i,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,5),(5,2),(5,3),(6,3

34、),(6,4),break,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,迷宫问题(续),0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(7,5),(5,2),(5,3),(6,3),(6,4),(6,5),break,i,i,i,i,i,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,5),

35、(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),break,i,i,i,i,i,i,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,6),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),break,i,i,i,i,i,i,i,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一

36、步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,7),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),break,i,i,i,i,i,i,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一步，到达出口,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),i,i,(8,7),break,i,i,i,i,i,i,i

37、,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,迷宫问题(续),9,0,用栈保存了路径,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),(8,7),迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7

38、,9,0,9,0,1,1,2,2,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,2,2,3,3,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,2,2,3,4,3,4,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,2,2,3,4,

39、5,3,4,5,5,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,1,2,6,2,3,4,5,3,4,5,6,5,6,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,7,1,2,6,7,2,3,4,5,3,4,5,6,5,7,6,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4

40、,5,6,7,9,0,9,0,1,7,8,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,6,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,1,7,8,9,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,9,6,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,1,7,8,9,1,2,6,7,8,2,3,4,5,10,3,10,4,5

41、,6,10,5,7,8,9,6,10,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,1,7,8,9,1,2,6,7,8,2,3,4,5,10,11,3,11,10,11,4,5,6,10,11,5,7,8,9,6,10,11,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,1,7,8,9,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,1

42、1,12,4,5,6,10,11,12,5,7,8,9,6,10,12,11,12,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,

43、9,0,9,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,迷宫问题(最短路径),入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,栈与递归,递归是描述或解决一类问题的简单方法 递归定义的函数运行时需要控制栈的支持,long f(int n) if (n1) return n*f(n-1); else return 1; ,递归函数的执行,STL中的栈,#

44、include #include #include using namespace std; int main() stack s; s.push(1); s.pop(); s.push(10); s.push(11); cout s.top() endl; cout s.size() endl; cout s.empty() endl; return 0; ,The C+ Stack is a container adapter that gives the programmer the functionality of a stack - specifically, a FILO (first-in, last-out) data structure Stack constructors:construct a new stack empty:true if the stack has no elements pop:removes the top element of a stack push:adds an element to the top of