1.2　基本概念和术语

视频二维码（扫码观看）

一、基本概念和术语

数据（Data）：是对客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素（Data Element）：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。

一个数据元素可由若干个数据项（Data Item）组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。

数据对象（Data Object）：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C＝{‘A’，‘B’，…，‘Z’}。

数据结构（Data Structure）：是指相互之间存在一种或多种特定关系的数据元素的集合。

结构：元素之间的相互联系（关系）。四种基本类型：

①集合：结构中的数据元素除了“同属于一个集合”的关系外，没有其他关系；

②线性结构：结构中的数据元素之间存在一对一的关系；

③树形结构：结构中的数据元素之间存在一对多的关系；

④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

二、数据结构的形式定义

数据结构的形式定义是一个二元组：Data_Structure＝（D，S），其中，D是数据元素的有限集，S是D上关系的有限集。

数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

三、数据结构的存储方式

存储结构：数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系的表示。

元素的关系的表示方法：

①顺序映像的特点，用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构（关系）。

②非顺序映像的特点，借助指示元素存储地址的的指针（pointer）来表示数据元素之间的逻辑结构（关系）。

对应两种存储结构：

①顺序存储结构，数据元素存放的地址是连续的；

②链式存储结构，数据元素存放的地址是否连续没有要求。

数据结构的三个组成部分：

①逻辑结构，数据元素之间逻辑关系的描述D_S＝（D，S）。

②存储结构，数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。

③数据操作，对数据要进行的运算。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

四、数据类型

数据类型（Data Type）：指的是一个值的集合和定义在该值集上的一组操作的总称。

数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型、指针类型、空类型和构造类型。

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

五、数据结构的运算

数据结构的主要运算包括：

（1）建立（Create）一个数据结构；

（2）消除（Destroy）一个数据结构；

（3）从一个数据结构中删除（Delete）一个数据元素；

（4）把一个数据元素插入（Insert）到一个数据结构中；

（5）对一个数据结构进行访问（Access）；

（6）对一个数据结构（中的数据元素）进行修改（Modify）；

（7）对一个数据结构进行排序（Sort）；

（8）对一个数据结构进行查找（Search）。