java数据结构第9章综合应用设计.ppt

《数据结构（Java版）》 叶核亚 《数据结构（Java版）》 第1章 绪论 第2章 线性表 第3章 排序 第4章 栈与队列 第5章 数组和广义表 第6章 树和二叉树 第7章 查找 第8章 图 第9章 综合应用设计 第9章 综合应用设计 9.1 用“预见算法”解骑士游历问题 9.2 综合应用实习 9.1 用“预见算法”解骑士游历问题 题意 在国际象棋的棋盘（8行×8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0, y0），编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格，这就是“骑士游历”问题。 2．棋盘的存储结构 设二维数组mat表示棋盘，每个元素表示棋盘的一格，其值定义为： 3．常规的“回溯算法” （1）设计思想 （2）辅助结构——栈 （3）性能评价 4．“预见算法” （1）设计思想 如果在每步选择方向时，不是任意选择一个方向，而是经过一定的测试和计算，“预见”每条路的“宽窄”，再选择一条最“窄”的路先走，成功的可能性较大。 （2）实现手段 算法描述 例9.1用“预见算法”解骑士游历问题 5．进一步研究方向 程序运行时，随意设置棋盘的大小，最小为5×5。 设置栈，在无路可通时，选择另一条路径。 设置队列，对于同一个初始位置，求得多条路径。 用图形描绘马在棋盘上的移动情况。 使用栈或队列时，跟踪程序运行，观察并描绘栈或队列的动态变化情况。 9.2 综合应用实习 1．求解骑士游历、迷宫等问题的多种算法 2．计算表达式值的多种算法 3．利用线程比较多种查找、排序算法的运行时间 4．管理信息系统中的算法设计 5．经典问题求解 6．数据结构的算法设计与动态描述 1．求解骑士游历、迷宫等问题的多种算法 （1）实习目的 掌握栈、队列的基本概念，熟练运用。掌握递归算法的设计思想。 （2）题意 骑士游历、迷宫的题意参见第4章实习4。 汉诺塔问题和八皇后问题 2．计算表达式值的多种算法 （1）实习目的 掌握栈、递归算法、二叉树的设计技术。 （2）题意 计算表达式的值。 （3）实习要求 同时使用两个栈求值。 递归算法。 采用二叉树结构。 3．利用线程比较多种查找、排序算法的运行时间 （1）实习目的 利用线程技术，比较不同查找、排序算法的性能。 （2）题意 将顺序、折半查找算法设计成线程，启动二个不同线程同时运行，并计算不同查找算法的运行时间。 将冒泡、快速等多个排序算法设计成线程，启动二个以上不同线程同时运行，并计算不同排序算法的运行时间。 4．管理信息系统中的算法设计 （1）实习目的 以Java中的流技术，练习管理信息系统中常用的算法设计。 （2）题意 以学生管理信息系统为例： 设计Student类的增加、删除、修改、查询、统计、自动编号等功能。 设计系统管理员、班主任、任课教师、学生、普通用户等多级用户管理权限。 设计系别、专业、班级等字典库，并进行维护。 5．经典问题求解 （1）实习目的 综合运用所学知识，设计新算法并实现。 （2）题意 对于以下的经典问题，设计相应的算法： 电梯调度算法。 自动排课算法。 电话号码簿的设计与查找算法。 数据字典的设计与查找算法。 城市道路交通网络的构架设计。 6．数据结构的算法设计与动态描述 （1）实习目的 对常用数据结构和经典算法进行动态描述。将数据结构用图形方式显示在屏幕上，并对插入、删除等操作的每一步状态（当前结点等）进行动态演示。 （2）题意 线性表：单向链表、双向链表的插入与删除操作，约瑟夫环问题，多项式相加。 排序：单向链表的简单选择排序（不新建链表）、归并排序，顺序表的希尔排序、快速排序、堆排序、归并排序的排序过程动态演示，九宫排序的排序过程动态演示，各种排序算法的比较演示。 栈与队列：计算表达式值时的栈、解素数环问题时的队列的动态演示。 稀疏矩阵与广义表：稀疏矩阵三元组的顺序存储结构、链式存储结构。广义表的存储结构。 树和二叉树：二叉树的建立与3种遍历算法（先根、中根、后根），表达式二叉树的建立与计算，广义表描述的二叉树的建立与遍历，线索二叉树的建立与遍历。二叉树中求两个结点最近的共同祖先。树与二叉树的转换。 查找：顺序表的链表的顺序查找算法，有序顺序表的折半查找算法，动态查找表的插入、删除操作及查找算法，二叉排序树的建立与查找算法，哈希表的插入、删除操作及查找算法，各种查找算法的比较。 图：图的2种存储结构与2种遍历算法（深度优先、广度优先），最小代价生成树，最短路径。 * 《数据结构（Java版）》叶核亚 * * 图9.1 马下一步可走的8个方向 图9.2 从（1, 1）开始的一次成功的遍历 图9.3 “回溯算法”流程图 表9.1 （5, 4）位置的可通路数情况