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