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

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