良好格式序列的判断-Read.PPT

McGraw-Hill/Irwin ? 2001 by the McGraw-Hill Companies, Inc. All rights reserved. USING INFORMATION TECHNOLOGY 第二次上机实验 课时目标：熟练掌握堆栈和队列的数据结构描述形式，会在堆栈和队列上进行基本的操作（包括入栈、出栈和入队列、出队列等操作）。能基于栈和队列结构进行一些简单的算法设计。 第二次上机题（1） 1．良好格式序列的判断。写一个程序，它读入若干括号字符（有方括号、大括号、圆括号、尖括号、等）的一个序列，并确定该序列是否为良好格式序列。比如{ [ ( ) ( ) ] ( ( ) ( ) ) }是良好格式序列；而{ ( ( ) ( ) ) [ ( ) } }不是良好格式序列。（利用栈结构来实现判断） 算法分析 对括号序列自左至右地进行扫描，用一个栈存放所扫描到的括号，若扫描到开括号‘{’, ‘[’, ‘’, ‘(’时，则让其进栈；若扫描到开括号‘}’, ‘]’, ‘’, ‘)’时，则检查栈顶元素是否与它匹配，若匹配，则退出栈顶元素；若不匹配，则输出不匹配的信息。若到扫描完毕时，栈已退空，则括号序列是良好的格式序列。 第二次上机题（2） 2．走迷宫问题：迷宫是一个如下图所示的m行n列的0-1矩阵，其中0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元，编程给出一条通过迷宫的路径或报告一个“无法通过”的信息。 第二次上机题（2） 算法分析 要寻找一条通过迷宫的路径，就必须进行试探性有哪些信誉好的足球投注网站，只要有路可走就前进一步，无路可走时，退回一步，重新选择未走过的可走的路，如此继续，直至到达出口或返回入口（无法通过迷宫）。我们可使用如下的数据结构：mg[1..m, 1..n]表示迷宫，为了算法方便，在四周加上一圈“哨兵”即变为数组mg[0..m+1, 0..n+1]表示迷宫，用数组zx，zy分别表示X，Y方向的移动增量，其值如下表所示： 算法分析 在探索前进路径时，需要将有哪些信誉好的足球投注网站的踪迹记下来，记录的踪迹应包含当前位置以及前驱位置。在有哪些信誉好的足球投注网站函数中，将所有需要有哪些信誉好的足球投注网站的位置形成一个队列，将队列中每一个元素可能到达的位置加入到队列中，当队列中某元素所有可能到达的位置全部加入到队列之后，即从队列中将该元素去掉。用变量front和rear分别表示队列的首与尾，当rear指示的元素已到达出口(m, n)时，根据rear所指示的前趋序号可回溯得到走迷宫的最短路径。 Is the computer just a convenient new gadget that makes things easier? Or is it a truly revolutionary tool whose long range result will be to change all rules? How does the computer compare to the evolution of the electric motor which changed the country’s economic dynamics? Learning Objectives Learning Objectives Learning Objectives Learning Objectives * * * * Is the computer just a convenient new gadget that makes things easier? Or is it a truly revolutionary tool whose long range result will be to change all rules? How does the computer compare to the evolution of the electric motor which changed the country’s economic dynamics?