基础名词解释
-
数据：程序的操作对象，用于描述客观事物，有以下两个特点可以
输入到计算机可以
被计算机处理
数据元素：组成数据对象的基本单元数据项：一个数据元素由若干数据项组成数据对象：性质相同的数据元素的集合，类似于数组
以上4种名词之间的关系如下图所示：
结构：数据元素之间不是独立的，存在特定的关系，这些关系即是结构数据结构：指的是相互之间存在一种或多种特定关系的数据元素的集合算法：对特定问题求解步骤的一种描述程序设计= 数据结构 + 算法
基本概念
逻辑结构 & 物理结构
一般从两个视角对数据进行描述，一个是逻辑结构，一个是物理结构
-
逻辑结构：描述的是数据与数据之间的逻辑关系 -
物理结构：描述的是数据在内存中存储的形式
逻辑结构
逻辑结构主要有以下4种：
-
集合结构：集合中的所有元素除了同属于一个集合外，他们之间没有其他关系，如下图所示
逻辑结构之集合结构
-
线性结构：数据之间的关系是一对一的，所有符合一对一的都是线性结构，如下图所示
逻辑结构之线性结构数组、链表是线性结构-
队列、栈是特殊线性结构，区别在于读取方式队列是先进先出，即FIFO栈是先进后出，即FILO
字符串是特殊线性结构，存储内容只能是字符串
-
树形结构：数据之间的存在一对多的层次关系，如下所示
逻辑结构之树形结构-
二叉树、B+、B-、红黑树、哈西曼树都是属于树形结构
-
-
图形结构：数据之间存在多对多的关系，如下图所示
逻辑结构之图形结构
物理结构
数据的物理结构就是数据存储在磁盘中的方式，这里的磁盘指的是计算机的内存，主要研究的是数据结构在计算机中的实现方式，包括数据结构中的元素的表示及元素间关系的表示，有以下两种
-
顺序存储结构：逻辑上相邻的数据元素，物理存储位置也相邻，顺序表的存储空间需要预先分配，且存储空间是一段的连续的内存，顺序存储结构如下图所示
顺序存储结构- 优点
方法简单，易实现，因为在各种高级语言中都有数组顺序存储结构具有
随机访问的特点
- 缺点
顺序表中做
插入/删除操作时，需要进行大量的数据移动，因此对n较大的顺序表效率低需要
预先分配空间，如果空间预估过大，会导致顺序表后面的大部分空间闲置，浪费内存，如果预估过小，又会造成溢出
- 优点
-
链式存储结构：逻辑上相邻的数据元素，其物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系，且链表的存储空间是动态分布的，链式存储结构如下图所示
链式存储结构- 优点：
不需要提前开辟一段连续的空间，其空间是动态分配的插入、删除操作方便，只需要改变指针的指向，不需要移动数据元素
- 缺点
- 链表
不能随机存取元素，如果在链式存储中遍历，需要遍历所有的元素
- 链表
- 优点：
