文档介绍：第二章计算机辅助工程基础?数据结构和算法?计算机图形学?工程数据库?软件工程?新技术趋势数据结构和算法数据结构实际问题数学模型求解算法抽象设计编程解答求解实际问题的一般步骤: 信号相位是指在一个交叉口某个方向的交通流(或几个交通流的组合) 同时得到的通行权及被分配得到这些通行权的时间带。在多叉路口需设几个相位才能既使车辆相互之间不冲突而又达到最大的流通呢? 交叉口信号相位的设置问题 A B CDE 假设有如图所示的五叉路,其中 C和E为单行道,在路口有 13条可行的通路,其中有的可以同时通行而不发生冲突,如 A→B和E→C,而有的在同时通行时一定会冲突,如 E→B和A→D,那末,在该交叉口应如何设置相位?这个问题可以转换成一个图的染色问题。?在图上以一个圆圈表示一条通路,在不能同时通行的两个圆圈之间画一连线,对图中的圆圈上色,要求同一连线上的两个圆圈不同色且颜色种类最少; ?一种解决方案,图中 13个圆圈表示 13条通路,四种颜色分别表示四个相位。交叉口信号相位的设置问题——图的染色问题 A B CDE AB AC AD BA BC BD DA DB DC EA EB EC ED DC AB AC AD BA ED BC BD EA DA DB EB EC 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中,数据元素都不是孤立存在的,而是在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构。数据结构就是一门研究非数值性程序设计中计算机操作的对象以及它们之间的关系和运算等的学科基本概念基本概念?数据:对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称?数据元素:数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理?数据对象:性质相同的数据元素的集合,是数据的一个子集?数据结构:相互之间存在一种或多种特定关系的数据元素的集合四类基本结构?集合?线性结构?树形结构?网状结构数据元素 1数据元素 2 ……数据元素 1数据元素 2 ……数据元素 1 数据元素 2数据元素 3 ……数据元素 1 数据元素 2数据元素 3 ……线性表?线性表是最常用且最简单的一种数据结构,它是属同一数据对象的 n个数据元素的有限序列?若将线性表记为,称 a i -1是a i的直接前趋元素,a i +1是a i的直接后继元素?线性表中元素的个数 n(n >=0) 定义为线性表的长度,n =0时称为空表。?在非空表中的每个数据元素都有一个确定的位置,比如 a i 是第 i个数据元素,称 i为a i在线性表中的位序 1 1 1 ( , , , , , , ) i i i n a a a a a ? ?? ?线性表 1—顺序表顺序表以一组地址连续的存储单元依次存储线性表的数据元素,由此在逻辑上相邻的两个元素在物理位置上也是相邻的。只要给定了存储线性表的起始位置,表中任一数据元素都可以随机存取,因此顺序表是一种随机存取的存储结构。 -1 … 21 a i的地址计算函数为: addr(a i)=addr(a 1)+(i-1) *d