计算机辅助工程基础

《计算机辅助工程基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章计算机辅助工程基础数据结构和算法计算机图形学工程数据库软件工程新技术趋势12.1数据结构和算法2数据结构实际问题数学模型求解算法抽象设计编程解答求解实际问题的一般步骤：3信号相位是指在一个交叉口某个方向的交通流（或几个交通流的组合）同时得到的通行权及被分配得到这些通行权的时间带。在多叉路口需设几个相位才能既使车辆相互之间不冲突而又达到最大的流通呢？交叉口信号相位的设置问题ABCDE假设有如图所示的五叉路，其中C和E为单行道，在路口有13条可行的通路，其中有的可以同时通行而不发生冲突，如A→B和E→C，而有的在同时通行时一定会

2、冲突，如E→B和A→D，那末，在该交叉口应如何设置相位？这个问题可以转换成一个图的染色问题。4在图上以一个圆圈表示一条通路，在不能同时通行的两个圆圈之间画一连线，对图中的圆圈上色，要求同一连线上的两个圆圈不同色且颜色种类最少；一种解决方案，图中13个圆圈表示13条通路，四种颜色分别表示四个相位。交叉口信号相位的设置问题——图的染色问题ABCDEABACADBABCBDDADBDCEAEBECEDDCABACADBAEDBCBDEADADBEBEC5数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不

3、是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。数据结构就是一门研究非数值性程序设计中计算机操作的对象以及它们之间的关系和运算等的学科基本概念6基本概念数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理数据对象：性质相同的数据元素的集合，是数据的一个子集数据结构：相互之间存在一种或多种特定关系的数据元素的集合7四类基本结构集合线性结构树形结构网状结构数据元素1数据元素2……数据元素1数

4、据元素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—顺序表顺序表以一组地址连续的存储单元依次存储线性表的数据元素，由此在逻辑上相邻的两个元素在物理位置上也是相邻的。只

5、要给定了存储线性表的起始位置，表中任一数据元素都可以随机存取，因此顺序表是一种随机存取的存储结构。顺序表通常用数组类型来实现.12…n-1nai的地址计算函数为：addr(ai)=addr(a1)+(i-1)*d10线性表2—链表链表使用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的，即逻辑上相邻的两个元素在物理位置不一定相邻）。数据元素ai的存储映象（称为结点）包括两个域：①存储数据元素信息的数据域；②存储直接后继位置信息的指针域，n个结点链接成一个链表。链表在高级程序语言中可用指针来实现11

6、线性表2—链表数据指针数据指针数据指针……数据指针数据指针数据指针删除元素数据指针数据指针数据指针添加元素数据指针12栈栈是限定在表尾进行插入或删除操作的特殊线性表。先进后出的线性表.a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,…,an的次序进栈，出栈的第一个元素应为栈顶元素an。13栈基本运算有：建立一个栈检查栈中剩余容量从栈顶推入一个元素从栈顶取出一个元素删除一个栈应用举例：常用软件中的撤销与恢复操作14队列队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在表的另一端进行删除。在队列中，允许插入的一端叫做队

7、尾，允许删除的一端则称为队首。假设队列为，则称a1为队首元素，an为队尾元素。队中元素按a1,a2,…,an的次序进入退出队列也只能按这个次序依次进行。15队列基本运算有：建立一个队列检查队列状态从队尾插入一个元素从队首删除一个元素删除一个队列应用举例：生活中的排队16例—交叉口仿真系统控制结构当采用仿真方法分析一系列交叉口所发生的交通状态时，需要采用分时处理技术分别逐个改变每一个交叉口的状态，同时系统整体环境也在发生着一些具有时间先后次序的情况。17树ABCDEFGH结点A为树的根，根的每个分支称为子树，子树也是一棵树结点子树的

8、根为结点的孩子，如B、C、D为结点A的孩子，而A为B、C、D的双亲同一个双亲的孩子之间为兄弟关系，如B、C、D没有孩子的结点为树的叶子，H、F、G、D为树的叶子18树的基本运算初始化一棵树得到树的根得到一个结点的双亲得到一个结点的兄弟得到一个结点的