数据结构

一 .基本概念

1.数据结构
数据结构：存储具有一种或或多种特定关系的数据的集合（如何组织和存储数据）

程序设计 = 数据结构 + 算法

2.数据与数据之间的关系

逻辑结构：数据元素与元素之间的关系
集合 ：数据元素与元素之间关系平等
线性结构 ：数据元素与元素之间一对一的关系（顺序表（数组）、链表、队列、栈）
树形结构 ：数据元素与元素之间一对多的关系（二叉树）
图形结构 ：数据元素与元素之间多对多的关系（网状结构）

物理结构：数据元素在计算机内存中的存储方式

顺序存储：选取内存中连续空间进行存储
代表：顺序表（数组）

1. 内存空间必须连续
2. 数据元素的插入和删除需要移动后续大量数据，不方便
3. 访问元素效率高
4. 需要预分配把内存空间，分配不合适，可能造成内存空间浪费或者数组越界

链式存储 ：可以选取非连续内存空间进行存储
代表：链式表

1. 内存空间可以不连续
2. 插入和删除数据元素方便
3. 访问数据元素必须要遍历
4. 不需要预分配内存空间，可以根据数据动态存储

索引存储：将要存储的元素关键字和存储位置构建索引表，数据查找是通过查询索引表获取数
据的真正存储位置。

散列存储（哈希存储）：将要存储的元素的关键字和存储位置之间建立起对应关系，这个关系
称为哈希函数，数据存储时，按照哈希函数的映射进行存储；数据查找时也按照哈希函数的映射进行查找。