数据结构（一）

什么是数据结构

• 数据结构是数据对象、存在于该对象的实例以及组成实例的数据元素之间的关系，并且这种关系可以通过定义相关的函数来给出
• 数据结构是抽象数据类型ADT的物理实现
• 一个数据结构是由数据元素依据某种逻辑联系起来的，对数据元素之间逻辑关系的描述称为数据的逻辑结构。由于数据必须在计算机内存储，数据的存储结构是其在计算机内的表示，既数据的实现形式

基本概念

• 数据（Data）：数据是信息的载体，其能够被计算机识别、存储和加工处理，是计算机程序加工的“原材料”。
• 数据元素：数据元素是数据的基本单位，其也称之为元素，结点、顶点、记录等。
• 数据项：一个元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。数据项也可称之为字段、域、属性
• 数据结构：是指数据间的相互关系，也就是数据的组织形式。

####数据结构的内容

• 数据的逻辑结构
• 数据的存储结构
• 数据的运算（检索、插入、删除、更新、排序等）

数据结构分类

• 按逻辑结构分类
  1. 线性结构
     • 线性结构是非空集
     • 线性结构有且仅有一个开始结点和一个终端结点
     • 线性结构所有结点最多只有一个直接前驱结点和一个直接后继结点
     • 线性表、栈、队列和串等
  2. 非线性结构
     • 非线性结构是非空集
     • 非线性结构的一个结点可能有多个直接前驱结点和多个直接后继结点
     • 数组、广义表、树结构和图结构等
• 按存储结构分类
  1. 顺序存储结构
     • 在一块连续的存储区域一个接着一个的存放数据
     • 线性存储方式主要用于线性逻辑结构的数据存放
  2. 链式存储结构
     • 不要求逻辑上相邻的结点物理位置上相邻，结点间的逻辑关系由附加的引用字段表示。一个结点的引用字段往往指向下一个结点的存放位置。
     • 也称链式存储结构
  3. 索引存储结构
     • 采用附加的索引表的方式来存储结点信息
  4. 散列存储方式
     • 根据结点的关键字 直接计算出该结点的存储地址的一种存储方式

常用数据结构

1. 数组
   数组是一种聚合数据类型，是将具有相同类型的若干变量有序的组织在一起的计集合。
2. 栈
   栈是一种特殊的线性表，其只能在一个表的固定端进行数据节点的插入和删除操作。
3. 队列
   队列和栈类似也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，在表的另一端进行删除操作。
4. 链表
   链表是一种数据元素按照链式存储结构进行存储的数据结构。
5. 树
   树是典型的非线性结构，其中包括了n个结点的有穷集合。
6. 图
   图是另一种非线性结构
7. 堆
   堆是一种特殊的树形结构，我们一般讨论的是堆都是二叉树。
8. 散列表
   散列表源自于散列函数，结构中存在关键字和T相等的记录。