数据结构的基本概念和三要素
数据结构的基本概念和三要素
数据结构的基本概念
什么是数据
与画家或音乐家相同，程序员也在用自己独特的方式来描绘这个世界。他们可以被称作数据艺术家，用数据来描绘这个世界。
数据定义：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机识别和处理的符号的集合。数据是计算机程序加工的原料。
计算机的演变
早期计算机
世界公认的第一台通用电子计算机，是1946年美国制造的ENIAC（埃尼阿克），它是“电子数字积分计算机”英文首字母的缩写。ENIAC(电子数字积分计算机) 是第一台电子通用计算机。它是图灵完全和数字化的，能够通过重新编程解决“一大类数值问题”。ENIAC于1945年完工，并于1945年12月10日首次投入实用。
军方使用，只用于处理纯数值型问题。
现代计算机
常用来处理非数值型问题。
如处理富豪榜人物关系等。
对于非数值型问题
1.我们关心每个个体的具体信息
2.我们还关心个体之间的信息
数据元素
数据元素：是数据的基本单位，通常作为一个整体进行考虑和处理。
一个数据结构可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。
例如一波顾客的数据元素里面可能有号码、取号人数、就餐人数等数据项。而一个账号的数据元素里面可能有昵称、生日、性别等数据项。
数据对象
数据对象：是具有相同性质的数据元素的集合，是数据的一个子集。
数据结构
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
如富豪榜的线性数据结构和网状数据结构。
数据结构的三要素
逻辑结构
集合结构
各个元素同属一个集合，别无其他关系。
线性结构
数据结构是一对一的关系。
除了第一个元素，所有的元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。
树形结构
数据元素之间是一对多的关系
网状结构
数据元素之间是多对多的关系。
数据的运算
针对某种逻辑结构，结合实际需求，定义基本运算。
基本运算：
1.查找第i个数据元素
2.在第i个位置插入新的数据元素
3.删除第i个位置的数据元素
数据的物理结构（存储结构）
顺序存储
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
链式存储
逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
索引存储
在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。
散列存储
根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。
物理结构的注意事项
1.若采用顺序结构，则各个数据结构在物理上必须是连续的；若采用非顺序存储结构，则各个数据元素在物理上是可以离散的。
2.数据的存储结构会影响存储空间分配的方便程度。
3.数据的存储结构会影响对数据运算的速度。
数据类型和抽象数据类型
数据类型
数据类型：是一个值的集合和定义在此集合上的一组操作的总称。
原子类型
其值不可再分的数据类型
结构类型
其值可以再分解为若干成分（分量）的数据类型。
抽象数据类型
抽象数据类型(AbstractDataType，ADT)是抽象数据组织及与之相关的操作。
定义了ADT相当于定义了一种数据结构。