数据结构第10章--综合应用设计课件

1、数据结构（C+版）第1章 绪论第2章 线性表第3章 排序第4章 串第5章 栈与队列第6章 数组和广义表第7章 树和二叉树第8章 查找第9章 图第10章 综合应用设计第10章 综合应用设计10.1 用“预见算法”解骑士游历问题10.2 综合应用实习数据结构（C+版）叶核亚10.1 用“预见算法”解骑士游历问题题意在国际象棋的棋盘（8行8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0, y0），编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格，这就是“骑士游历”问题。图10-1 马下一步可走的8个方向数据结构（C+版

2、）叶核亚2棋盘的存储结构设二维数组mat表示棋盘，每个元素表示棋盘的一格，其值定义为：图10-2 从（1, 1）开始的一次成功的遍历数据结构（C+版）叶核亚3常规的“回溯算法”（1）设计思想（2）辅助结构栈（3）性能评价图10-3 “回溯算法”流程图数据结构（C+版）叶核亚4“预见算法”（1）设计思想如果在每步选择方向时，不是任意选择一个方向，而是经过一定的测试和计算，“预见”每条路的“宽窄”，再选择一条最“窄”的路先走，成功的可能性较大。数据结构（C+版）叶核亚（2）实现手段表10-1 （5, 4）位置的可通路数情况方向下一位置可通路数1(3,5)72(4,6)73(6,6)74(7,5)5

3、5(7,3)56(6,2)57(4,2)58(3,3)7数据结构（C+版）叶核亚例10-1 用“预见算法”解骑士游历问题 数据结构（C+版）叶核亚算法描述图10-4 play()方法实现游历的算法流程数据结构（C+版）叶核亚5进一步研究方向程序运行时，随意设置棋盘的大小，最小为55。设置栈，在无路可通时，选择另一条路径。设置队列，对于同一个初始位置，求得多条路径。用图形描绘马在棋盘上的移动情况。使用栈或队列时，跟踪程序运行，观察并描绘栈或队列的动态变化情况。数据结构（C+版）叶核亚10.2 综合应用实习1求解骑士游历、迷宫等问题的多种算法2计算表达式值的多种算法3利用线程比较多种查找、排序算法

4、的运行时间4管理信息系统中的算法设计5经典问题求解6数据结构的算法设计与动态描述数据结构（C+版）叶核亚1求解骑士游历、迷宫等问题的多种算法（1）实习目的掌握栈、队列的基本概念，熟练运用。掌握递归算法的设计思想。（2）题意骑士游历、迷宫的题意参见第5章实习5。数据结构（C+版）叶核亚汉诺塔问题和八皇后问题图10-5 汉诺塔问题的解答图10-6 八皇后问题数据结构（C+版）叶核亚2计算表达式值的多种算法（1）实习目的掌握栈、递归算法、二叉树的设计技术。（2）题意计算表达式的值。（3）实习要求同时使用两个栈求值。递归算法。采用二叉树结构。图10-7 表达式二叉树数据结构（C+版）叶核亚3利用线程比

5、较多种查找、排序算法的运行时间（1）实习目的利用线程技术，比较不同查找、排序算法的性能。（2）题意将顺序、折半查找算法设计成线程，启动二个不同线程同时运行，并计算不同查找算法的运行时间。将冒泡、快速等多个排序算法设计成线程，启动二个以上不同线程同时运行，并计算不同排序算法的运行时间。数据结构（C+版）叶核亚4管理信息系统中的算法设计（1）实习目的以Java中的流技术，练习管理信息系统中常用的算法设计。（2）题意以学生管理信息系统为例：设计Student类的增加、删除、修改、查询、统计、自动编号等功能。设计系统管理员、班主任、任课教师、学生、普通用户等多级用户管理权限。设计系别、专业、班级等字典库，并进行维护。数据结构（C+版）叶核亚5经典问题求解（1）实习目的综合运用所学知识，设计新算法并实现。（2）题意对于以下的经典问题，设计相应的算法：电梯调度算法。自动排课算法。电话号码簿的设计与查找算法。数据字典的设计与查找算法。城市道路交通网络的构架设计。数据结构（C+版）叶核亚6数据结构的算法设计与动态描述（1）实习目的对常用数据结构和经典算法进行动态描述。将数据结构用图形方式显示在屏幕上，并对插入、删除等操作的每一步状态（当前结点等）进行动态演示。（2）题意线性表：单向链表、双向链表的插入与删除操作，约瑟夫环问题，多项式相加。排序：单