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