数据结构概述

1.1：什么是数据结构

• 数据结构是数据的组织形式，可以用来表示特定的对象数据。计算机程序所操作的对象是各式各样的数据，通常拥有不同的数据解耦股，对此采用的处理方法不同，计算的复杂程度也不一样，因此算法往往依赖于某种数据结构，即数据结构是算法实现的基础。

1.2：数据结构的内容

• 数据结构包括三方面内容
  • 数据的逻辑结构
    • 数据元素之间的逻辑关系，与数据在计算机中如何存储无关，是独立于计算机的抽象概念。
  • 数据的存储结构
    • 数据元素及其逻辑关系在计算机存储器上的表示形式。存储结构依赖于计算机语言，是逻辑结构在计算机语言的实现。
  • 数据的运算
    • 对数据施加的操作，数据运算的基础为数据的逻辑结构。
• 数据的逻辑结构、存储结构和数据的运算是一个整体，不可以孤立地去理解这三个中的任何一个。
  • 同一个逻辑结构可以有不同的存储结构。例如，线性表是最简单的一种逻辑结构，采用顺序方式存储就是顺序表；采用链式方式存储就是链表；采用散列方式存储就是散列表。
  • 同一种逻辑结构可以有不同的数据运算集合。一个相同的数据逻辑结构和存储结构采用不同的运算集合及运算性能，将产生全新的数据结构。如果将线程表的插入运算限制在表的一端，将删除操作限制在表的另一端，那么这种数据结构就是队列；如果将线性表的插入和删除操作都限制在表的同一端，那么这种数据结构就是栈。

1.3：数据结构的分类

• 一般来说可以根据逻辑结构进行分类，线性结构和非线性结构
• 线性结构（线性表、栈、堆、串等）
  • 非空集
  • 有且仅有一个开始结点和终端结点
  • 所有结点至多只有一个直接前趋和一个直接后继结点
• 非线性结构（数组、广义表、树、图）
  • 非空集
  • 一个结点可能有多个直接前趋结点和直接后继结点

1.5：数据结构几种存储方式

• 顺序存储方式
  • 在一块地址连续的存储区域一个接一个存储数据。逻辑上相邻的节点存储在物理位置上相邻的存储单元中。
• 链式存储方式
  • 灵活，不要求逻辑上相邻的结点在物理上相邻，结点间的逻辑关系由附加的引用字段表示。
• 索引存储方式
  • 采用附加的索引表的方式来存储结点信息的方式。
  • 索引表由若干索引项组成，索引项的一般形式为（关键字、地址），其中关键字是能够唯一标识一个结点的数据项。
  • 细分两类
    • 稠密索引
      • 每个结点在索引表中都有一个索引项，索引项的地址指向对应结点的存储位置。
    • 稀疏索引
      • 一组结点在索引表中只对应一个索引项，索引项的地址对应一组结点的其实存储位置。
• 散列存储方式
  • 根据结点的关键字直接计算出该结点的存储位置的存储方式

1.6：数据类型

• 数据类型就是一个值的集合以及在这些值上定义的一系列操作的总称。

1.7：常用数据结构

• 数组（Array）
  • 聚合数据类型，具有相同类型的若干变量有序组织在一起的集合。
• 栈（Stack）
  • 特殊的线性表，只能在一个表的固定端进行数据结点的插入和删除操作，后进先出存储数据。
• 队列（Queue）
  • 特殊的线性表，允许表的一段进行插入–队尾，另一端进行删除–队头。
• 链表（LinkedList）
  • 数据元素按照链式存储结构存储的数据结构。每个数据节点包括数据域和引用域组成。
• 树（Tree）
  • 非线性结构，包括n个结点的有穷结合K。树结构中有且仅有一个根结点，根结点没有前驱节点。其他结点有且仅有一个前驱节点，可以有m个后继结点，m>=0
• 图（Graph）
  • 非线性数据结构。数据结点一般称为顶点，而边是顶点的有序偶对。如果两个顶点直接存在一条边，就表示两个顶点具有相邻关系。
• 堆（Heap）
  • 一种特殊的树形结构，一般都是讨论二叉堆。堆的特点是其根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构。
• 散列表（Hash）
  • 源自于散列函数，思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用比较而直接取得所查记录。