课件：数据结构讲解

第三章

汽车智能设计05汽车智能设计基础3

CAD中常用的数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(Structure)。数据结构是一堆数据元素和这些数据元素之间的关系的总和。4

按数据元素之间关系的不同特性，通常有4类基本结构（1）集合结构中的数据元素除了“同属于一个集合”外，别无其它关系。（2）线性结构结构中的数据元素之间存在一对一的关系。（3）树型结构结构中的数据元素之间存在一对多的关系。（4）图状结构或网状结构结构中的数据元素之间存在多对多的关系。5问题：为什么要学习数据结构？计算机的主要用途：

早期：主要用于数值计算。

后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。62.1基本概念1.数据（data）：

数据是信息的载体，是描述客观事物的数字、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合,是计算机程序加工的”原料”。2.数据元素（dataelement）数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。数据可以是简单的，也可能是复杂的，只是相对独立的单元。产品——部件；部件——零件；零件——基本形体数据元素又称为元素、结点、记录。73、数据的逻辑结构和物理结构数据的逻辑结构从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数据模型，与数据的存储无关，也与数据元素本身的形式、内容、相对位置无关；线性表、栈、队列、串、树8数据的物理结构数据结构在计算机中的表示(或称映象）称为数据的物理结构，又称为存储结构。它包括数据元素的表示和关系的表示。（1）数据元素的表示：

计算机处理数据的最小单位叫做位(Bit)，一个位表示一个二进制的数，若干位组合起来形成一个位串。用一个位串表示一个数据元素，称这个位串为一个结点。结点是数据元素在计算机中的映象。（2）关系的表示两种基本的存储结构：①顺序映像（顺序存储结构）②非顺序映像（链式存储结构）9顺序存储结构:

所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内仍然相邻。链式存储结构：

在每一个数据元素中增加一个存放地址的指针，借助该指针来表示数据元素之间的逻辑关系。

所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址（指针）确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。10数据类型是程序设计语言确定变量所具有的种类。每种程序设计语言都提供一组基本的数据类型。C语言提供字符型、整型、浮点型和双精度型4种基本数据类型；程序设计语言还可以将不同类型的数据组合成一个有机的整体，构造出新的数据类型用来实现各种复杂的数据结构的运算。4.数据类型11线性表：是n(n＞o)个数据元素的有限序列。逻辑结构如下：(a1,a2,a3,…,ai-1,ai,ai+1,…,an-1,an)

其中ai可以是一个数、是一个符号，还可以是一个线性表，甚至是更复杂的数据结构。当n＞o时，除第一个及最后一个元素外，线性表中每个元素有且只有一个直接前趋，有且只有一个直接后继。线性表中数据元素的数量定义为线性表的长度。2.2线性表2.2.1线性表的逻辑结构122.3栈和队列1、栈栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。表的一端是封闭的，另一端是开口的。

对表只能在开口的一端进行删除（出栈）和插入（进栈）运算，这一端称为栈顶，另一端称为栈底。an…a3a2a1进栈出栈栈底栈顶132．队(或称队列)

队列是一个两端均开口的线性表，元素只能从表的一端插入，在表的另一端删除。表中允许插入的一端称为“队尾”，允许删除的一端称为“队头”。入队列时，队尾指针加1；出队列时，对头指针减1。入队出队队头指针队尾指针14树是一类重要的非线性数据结构，元素之间存在明显的层次关系。

几何形体的分解2．4树和二叉树15树的定义：树是由一个或多个结点组成的有限集T，其中有一个特定的称为根的结点，其余结点可分为n(n＞o)