678-算法与数据结构.ppt

算法与数据结构 主讲人：谭定英 “算法＋数据结构＝程序” 程序就是在数据的某些特定的结构和表示的基础上对于算法的描述。 算法与数据结构是程序设计中相辅相成、不可分割的两个方面。 抽象数据类型 有一定行为（操作）的抽象（数学）类型。 抽象出数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏起来。 支持数据类型的实现与使用分离的原则，是一种十分有效的对问题进行抽象与分解的思维工具。 是面向对象技术与方法的主要理论基础。 数据结构 “数据结构是抽象数据类型的物理实现”。 解决： 1）如何具体表示抽象数据类型中的数学模型； 2）如何具体实现抽象数据类型中操作。 学习目的 理解数据结构和算法的概念； 掌握设计数据结构与算法的主要原理和方法； 比较不同数据结构和算法的特点。 提高学生使用计算机解决问题的能力。 第一章 绪 论 本章重点： 理解从问题到程序的主要过程； 体会抽象数据类型、数据结构和算法在问题求解过程中的作用； 了解数据结构的主要概念和分类； 了解算法的概念和主要设计、分析方法。 1.1 从问题到程序 用计算机解决（一种）实际问题，就是在计算机中建立一个解决问题的模型。 程序是使用程序设计语言精确描述的实现模型，它是问题求解的一个可以在计算机上运行的模型。 程序中描述的数据用来表示问题中涉及的对象，程序中描述的过程表示了对于数据的处理算法；通过接受（具体）实际问题的输入，经过程序的运行，便可以得到实际问题的一个解。 问题求解（1） 分析阶段。 弄清用户的需求是什么，设计者根据它进行深入分析，使用规范说明语言（或数学语言等工具）给出系统的需求模型（或数学模型）。  问题求解（2） 设计阶段（本课讨论的重点） 。 建立求解系统的实现模型，重点是算法的设计和数据结构的设计。对于大型的复杂的系统，还包括抽象数据类型或者模块的设计。 一般而言，设计过程需要从粗到细，经过多次精化才能完成。 问题求解（3） 编码阶段。 根据设计的要求，采用适当的程序设计语言（C语言、C++语言或Java语言），编写出可执行的程序。 问题求解（4） 测试和维护。 发现和排除在前几个阶段中产生的错误，经测试通过的程序便可投入运行，在运行过程中还可能发现隐含的错误和问题，因此还必须在使用中不断维护和完善。  1.1.1 问题分析与抽象 为了能正确地解决问题，必须首先深刻地理解需要解决的问题。只有在深刻地认识了这个问题以后，才能着手确定这个问题的解决方法。 信号灯问题：为这个路口设计一个安全有效的交通信号灯的管理系统。 信号灯问题－分析 分析所有车辆的行驶路线的冲突问题。 这个问题可以归结为对车辆的可能行驶方向作某种分组， 对分组的要求：使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。 信号灯问题－分析 可以确定13个可能通行方向： A→B，A→C，A→D， B→A，B→C，B→D， D→A，D→B，D→C， E→A，E→B，E→C，E→D。 信号灯问题 －抽象 要求将图1.2中的结点分组，使有线相连(互相冲突)的结点不在同一个组里。 这个问题的解有许多“可行解”。 我们希望能够设计一个最佳（分组数最少）的方案。称作“最优解”。  着色问题－经典问题 把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界， 上述问题就变成著名的“着色问题”：即求出（最少）要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。 1.1.2 程序的设计与实现 一个问题的解决可以有许多办法，由于使用的工具是计算机，所以在选择方法时必须充分考虑到计算机的特点和条件，才能找到比较巧妙的办法，比较快而且准确地计算出需要的结果。 选择算法－穷举法 具体做法：从分为1、2、3…组开始考察，逐个列举出所有可能的着色方案，检查这样的分组方案是否满足要求。首先满足要求的分组，自然是问题的最优解。 穷举法的分析 这类穷举法对结点少的问题(称为“规模小的”问题)还可以用；对规模大的问题，由于求解时间会随着实际问题规模的增长而指数性上升，使计算机无法承受。 贪心法 先用一种颜色给尽可能多的结点上色；然后用另一种颜色在未着色结点中给尽可能多的结点上色；如此反复直到所有结点都着色为止。 贪心法的一个解 (1) 红色：AB AC AD BA DC ED(2) 蓝色：BC BD EA(3) 绿色：DA DB(4) 白色：EB EC 抽象数据类型的选择 为了便于给出上述算法的实现，可以按照抽象数据类型的观点，先把被处理的对象加以抽象。 在着色问题中具体解决：使用什么抽象数据类型来表示地图，以及使用什么样的抽象数据类型表示一组国家等。