数据结构教程：基本定义

数据定义

数据：所有可能被输入到计算机中，且能被计算机处理的符号的集合。一个班中所有的学生。

数据元素：数据的基本单位。学生

数据项：具有独立含义的数据最小单位。学生的学号，性别等

数据对象：性质相同数据元素的集合，是数据的一个子集。男学生

数据结构：所有数据元素以及数据元素之间的关系，可以看做相互之间存在着某种特定关系的数据元素的集合。一个班所有学生+学生之间的关系(集合)

数据结构三个方面

数据的逻辑结构

数据的存储结构

数据的运算

1.数据的逻辑结构

是从数据元素的逻辑关系上描述数据的，是指数据元素之间逻辑关系的整体，通常是从求解问题中提炼出来的

数据逻辑结构的常用表示：

图表表示：采用表格或者图形直接描述数据之间的逻辑关系。

二元组表示：B=(D,R),D数据的集合，R数据关系(r1,r2)的集合,r1数据元素间的关系r1={,,}

前驱元素与后继元素：a,b,c是前驱元素，b,c,d是后继元素

开始元素与终端元素：a是开始元素，d是终端元素

逻辑结构的类型：

集合：数据元素之间同属于一个集合，无其他关系，(并列)

线性结构：一对一的关系，开始与终端元素唯一，其他元素有且仅有一个前驱元素+后去元素。

树形结构：一堆多的关系，开始元素外，一个元素仅有一个前驱元素

图形结构：多对多的关系。

2.数据的存储结构

数据逻辑结构在计算机中的存储实现称为数据的存储结构，存储结构需要存储数据元素和数据元素之间的关系。

4种常见的存储结构：

顺序存储结构：连续的存储单元存放所有数据元素，逻辑相邻，存储也相邻(元素之间的关系)。优点是存取效率高，分配给数据元素的存储单元全部用来存储数据元素，元素之间的关 系没有占用额外的存储空间。每个元素对应一个逻辑序号，可直接获取元素。缺点是不便于数据修改，插入删除数据可能需要移动一系列数据。

链式存储结构：每个元素用一个内存节点存储，内存节点是单独分配的，不一定是连续的，无须占用一整块存储空间，每个内存节点包含一个指向相邻节点的指针，通过指针链接所有节点。优点是便于数据修改，数据插入删除只需要修改指针域，不必移动节点。缺点是存储内存利用率低，需要存储指针域，逻辑相邻，存储不一定相邻，不能随机存取，需要从头结点开始查找。

索引存储结构：存储数据元素信息的同时还建立附加的索引表，存储所有数据元素的表称为主数据表，每个元素有一个 关键字和对应的存储地址。索引表每一项成为索引项，一般是“关键字,地址”，索引表是按关键字有序排列的。优点是查找效率高，缺点是需要建立索引表，从而增加了空间开销。

哈希(散列)存储结构：根据元素的关键字通过hash函数计算出一个值，作为元素的存储地址。优点是查找速度快，给出元素可直接根据元素的关键字找到元素的存储地址，与前三种不同，哈希存储方法只存储数据结构的数据元素，不存储元素之间的逻辑关系，只适合快速查找和插入的场景。

3.数据的运算

对数据实施的运算。常用的运算有检索，插入，删除，更新，排序等，根据逻辑结构和存储结构分为运算定义和运算实现

运算定义：是运算功能的描述，抽象的，基于逻辑结构

运算实现：运算的实现算法，具体的，基于存储结构。

对于一种数据结构，其逻辑结构总是唯一的，但它可能对应多种存储结构，不同存储结构的同一实现过程可能不同。

数据类型和抽象数据类型

数据类型：一组性质相同的值得集合和定义在此集合上的一组操作的总称，是某种程序设计语言已经实现的数据结构。C、C++常用的数据类型(原子类型，与结构类型)：基本类型，指针类型，数组类型，结构体类型，共生体类型，自定义类型。

抽象数据类型(ADT)：用户进行软件系统设计时从问题等待数学模型中抽象出来的逻辑数据结构和逻辑结构上的运算，不考虑具体的存储类型和运算实现。

ADT 抽象数据类型名

{ 数据类型：数据对象的声明(D)

数据关系：数据关系的声明(R)

基本运算：基本运算的声明(运算定义)

}

算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列

1.算法的五种特性：

有穷性

确定性

可行性

有输入

有输出

2.算法的设计目标

正确性

可使用性

可读性

健壮性

高效率与低存储量需求

以上就是星辉小编介绍的"数据结构教程：基本定义"，希望对大家有帮助，如有疑问，请在线咨询，有专业老师随时为您服务。