算法与数据结构— C语言描述张乃孝 主编高等教育出版社.ppt

张乃孝 算法与数据结构——C语言描述 张乃孝：算法与数据结构——C语言描述 ? ADT circle is data float r ; operations void constructor( ) 处理： 构造一个圆 float area ( ) { return(3.14*r*r);} float circumference( ) { return(2*3.14*r); }end ADT circle; * * 算法与数据结构 —— C语言描述 张乃孝 主编 高等教育出版社 第一章 绪 论 学习数据结构的必要性 1.1 问题求解 1.2 数据结构 1.3 算法 1.4 算法分析 1.5 抽象数据类型 计算机 信息表示A 信息表示B 1.1 问题求解 建立求解问题的模型，把描述实际对象的数据及其相互关系映射到计算机的存储器上，编程序模拟对象领域中的求解过程。 为一个实际问题开发一个程序 系统通常可以分成以下四个阶段 3。编码阶段 2。设计阶段 1。分析阶段 4。测试和维护 （与本课程关系最密切） 问题分析示例 对于一个多叉路口， 设计一个交通信号灯 的管理系统。首先需 要分析一下所有车辆 的行驶路线的冲突问 题。这个问题可以归 结为对车辆的可能行 驶方向作某种分组， 对分组的要求是使任 一个组中各个方向行 驶的车辆可以同时安 全行驶而不发生碰撞。 1.1.1 问题分析 可通行方向 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 有些通行方向显然不能同时进行，相应的结点间画一条连线。 AB AC AD BA BC BD DA D B DC EA EB EC ED 图1.2 交叉路口的图示模型 把图1.2中的结点进行分组，使得有边相连的结点不在同一个组里。 地图着色问题 如果把上图中的一个结点理解为一个国家， 结点之间的连线看作两国有共同边界，上述问题 就变成著名的“着色问题”：即求出最少要几种颜 色可将图中所有国家着色，使得任意两个相邻的 国家颜色都不相同。 通过上面的分析，我们就获得了该交通管系统的数学模型。下面就可以着手进行算法的设计。 1.1.2 程序设计 算法设计 方法2. “贪心法” while 有结点未着色； { 选择一种新颜色； 在未着色的结点中,给尽可能多的彼此结 点之间没有边连接的点着色； } 方法1. 对n个结点，逐个测试其所有组合； 有些通行方向显然不能同时进行，相应的结点间画一条连线。 AB AC AD BA BC BD DA D B DC EA EB EC ED 图1.2 交叉路口的图示模型 把上面方法应用于图1.2，得到下面的分组： 绿色：AB, AC, AD, BA, DC, ED 蓝色：BC, BD, EA 红色：DA, DB 白色：EB, EC 假设需要着色的图是G，集合V1包括图中所有未被着色的结点，着色开始时V1是G所有结点集合。NEW表示已确定可以用新颜色着色的结点集合。 从V1中找出可用新颜色着色的结点集的程序框架描述为： NEW={ }; 　 for 每个v ? V1 do 　　 if v与NEW中所有结点间都没有边 　　　 { 从V1中去掉v ; NEW=NEW?{v} ; } 对集合和图的操作: 判断一个集合是否为空:isSetEmpty(V1); 置一个集合为空: emptySet(NEW); 从集合中去掉一个元素:removeFromSet(V1,v); 向集合里增加一个元素:addToSet(NEW,v); 检查结点v与结点集合中各结点之间在图G中是 否有边连接: notAdjacentWithSet(NEW,v,G); 有了图、集合这样的结构和基于其上的操作，程序的实现非常简单。 算法： int colorUp( Graph G) { int color=0; V1=G.V; while(!isSetEmpty(V1)) { emp