资源预览内容
第1页 / 共20页
第2页 / 共20页
第3页 / 共20页
第4页 / 共20页
第5页 / 共20页
第6页 / 共20页
第7页 / 共20页
第8页 / 共20页
第9页 / 共20页
第10页 / 共20页
亲,该文档总共20页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构(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种遍历算法(深度优先、广度优先),最小代价生成树,最短路径。,
收藏 下载该资源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号