数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
1. 数据
所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。
2. 数据元素
数据（集合）中的一个“个体”，数据及结构中讨论的基本单位
3.数据项
数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
4. 数据类型
在一种程序设计语言中，变量所具有的数据种类。整型、浮点型、字符型等等
5. 逻辑结构
数据之间的相互关系：
5.1 集合
结构中的数据元素除了同属于一种类型外，别无其它关系。
数字集合
5.2 线性结构
数据元素之间一对一的关系
5.3 树形结构
数据元素之间一对多的关系
5.4 图状结构或网状结构
结构中的数据元素之间存在多对多的关系
6.物理结构/存储结构
是指数据的逻辑结构在计算机中的存储形式。
6.1 顺序存储结构
顺序存储中，相邻数据元素的存放地址也相邻，内存中存储单元的地址必须是连续的，存储密度 = 1。
优点：
不用为表示节点间的逻辑关系而增加额外的存储开销。
具有按元素序号随机访问的特点。
缺点：
在做插入/删除操作时，平均每次移动表中的一半元素，因此表中数据量越大效率越低。
需要预先分配足够大的存储空间。过大可能会导致存储空间闲置，过小会造成溢出。
使用：
线性表的长度变化不大，且其主要操作是查找。
6.2 链式存储结构
链式存储中，逻辑上相邻的数据元素，物理存储位置不一定相邻，使用指针实现元素之间的逻辑关系。链表的存储空间是动态分配的，存储密度 < 1。
优点：
插入/删除方便（只需要修改指针）。
缺点：
要占用额外的存储空间存储元素之间的关系，存储密度低。
不是随机存储结构，不能随机存取元素，只能顺序存取。
使用：
线性表的长度变化较大，且其主要操作是插入/删除。
ps：存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比
网友评论