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

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

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

3、 （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数据结构（C+版）叶核亚例10-1 用“预见算法”解骑士游历问题#include const N=8;/定义棋盘大小const MaxSize=N+2*2;/表示棋盘的二维数组的维数 /数组比实际棋盘多顶边、底边各二行，左边、右边各两列class Position /表示棋盘上一格的位置 public:int x,y;Position(int x=1,int y=1)this-x=x;this-y=y;class Horse 数据结构

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

5、解骑士游历、迷宫等问题的多种算法（1）实习目的掌握栈、队列的基本概念，熟练运用。掌握递归算法的设计思想。（2）题意骑士游历、迷宫的题意参见第5章实习5。数据结构（C+版）叶核亚汉诺塔问题和八皇后问题图10-5 汉诺塔问题的解答图10-6 八皇后问题数据结构（C+版）叶核亚2计算表达式值的多种算法（1）实习目的掌握栈、递归算法、二叉树的设计技术。（2）题意计算表达式的值。（3）实习要求l同时使用两个栈求值。l递归算法。l采用二叉树结构。图10-7 表达式二叉树数据结构（C+版）叶核亚3利用线程比较多种查找、排序算法的运行时间（1）实习目的利用线程技术，比较不同查找、排序算法的性能。（2）题意将顺

6、序、折半查找算法设计成线程，启动二个不同线程同时运行，并计算不同查找算法的运行时间。将冒泡、快速等多个排序算法设计成线程，启动二个以上不同线程同时运行，并计算不同排序算法的运行时间。数据结构（C+版）叶核亚4管理信息系统中的算法设计（1）实习目的以Java中的流技术，练习管理信息系统中常用的算法设计。（2）题意以学生管理信息系统为例：设计Student类的增加、删除、修改、查询、统计、自动编号等功能。设计系统管理员、班主任、任课教师、学生、普通用户等多级用户管理权限。设计系别、专业、班级等字典库，并进行维护。数据结构（C+版）叶核亚5经典问题求解（1）实习目的综合运用所学知识，设计新算法并实现

7、。（2）题意对于以下的经典问题，设计相应的算法：电梯调度算法。自动排课算法。电话号码簿的设计与查找算法。数据字典的设计与查找算法。城市道路交通网络的构架设计。数据结构（C+版）叶核亚6数据结构的算法设计与动态描述（1）实习目的对常用数据结构和经典算法进行动态描述。将数据结构用图形方式显示在屏幕上，并对插入、删除等操作的每一步状态（当前结点等）进行动态演示。（2）题意线性表：单向链表、双向链表的插入与删除操作，约瑟夫环问题，多项式相加。排序：单向链表的简单选择排序（不新建链表）、归并排序，顺序表的希尔排序、快速排序、堆排序、归并排序的排序过程动态演示，九宫排序的排序过程动态演示，各种排序算法的比较演示。数据结构（C+版）叶核亚