数据结构

数据结构是计算机 存储 / 组织 数据的方式。

数据结构是指 相互之间存在一种或多种特定关系的 数据元素 的集合，即带“结构”的数据元素的集合。“结构”是指 数据元素 之间存在的关系，分为逻辑结构和物理结构。

数据的逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。

按照数据的逻辑结构对其简单的分类：线形结构、非线形结构。

常用的逻辑结构包括：

1. 集合：元素之间“同属一个集合”。
2. 线性结构：元素存在 一对一 的相互关系。
3. 树形结构：元素存在 一对多 的相互关系。
4. 图形结构：元素存在 多对多 的相互关系。

其中树形结构和图形结构属于非线形结构。

数据的物理结构（存储结构）

数据的物理结构，指数据的逻辑结构在计算机存储空间的存放形式。也称存储结构。

数据的物理结构是数据结构在计算机中的表示（又称映像），包括 数据元素的机内表示 和 关系的机内表示。

具体的实现方法有顺序、链接、索引、散列等多种，即：

1. 顺序存储结构
2. 链式存储结构
3. 索引存储结构
4. 散列存储结构
   所以，一种数据结构的逻辑结构可以表示成一种或多种存储结构。

数据元素的机内表示（映像方法）：用 二进制位bit的位串 表示** 数据元素**，也称 节点node。当数据元素由若干个数据项组成时，位串中与数据项对应的子位串称为 数据域data field

关系的机内表示（映像方法）：数据元素之间的关系的机内表示分为 顺序映像 和 非顺序映像，常用两种存储结构为顺序存储结构和链式式存储结构。
顺序映像：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，顺序存储结构 在物理存储单元上是连续的、顺序的。
非顺序映像：借助元素元素存储位置的指针 Pointer 来表示数据元素之间的逻辑关系。链式存储结构 在物理存储单元上是非连续的、非顺序的。

数据的运算

1. 查找
2. 插入
3. 删除
4. 更新
5. 排序

分类

数据结构有很多种，一般来说，按照数据的逻辑结构对其简单的分类：线形结构、非线形结构（包括树结构、图结构）。

线性结构

各个结点之间具有线性关系。

按数据结构的语言描述，有以下特点：

1. 非空集。
2. 有且仅有一个开始结点和一个终端结点。
3. 每个结点最多只有一个直接前驱结点和一个直接后继结点。

常见的线性结构：线性表、栈、队列、串等。

线性表 Linear List：

分为顺序存储（数组）和链式存储（链表 Linked List）。

栈 Stack：

特殊的线性表，在表的一个固定端进行数据结点的插入（入栈）和删除（出栈）。栈中没有元素称为空栈。
使用场景：实现递归功能，越先放进入的东西越晚才能拿出来，例如斐波那契数列。

队列 Queue：

特殊的线性表，在表的一端（队尾）进行数据结点的插入操作（入队），另一端（对头）进行删除操作（出队）。队列中没有元素称为空队列。
使用场景：多线程阻塞队列管理。

数组 Array

一维、二维（矩阵）、三维数组

一维数组结构是线性表的基本表现形式，而 n 维数组可理解为是对线性存储结构的一种扩展。

数组是在内存中连续存储多个元素的结构，在内存中的分配也是连续的。

按数组元素分为 整形数组、字符型数组、指针数组、结构数组等
一维、二维、多维等表现形式

线形链表 Linked List：

单向链表、循环链表、双向链表
链表是一种数据元素按照链式存储结构进行存储，在物理存储上有非连续的特点。链表由一系列数据结点构成，每个结点包括数据域和指针域两部分。其中指针域保存了下一个元素存放的地址，以此来实现逻辑顺序。
根据链表的特点能形成不同的结构：单向链表、循环链表、双向链表、二叉链表（非线形结构）

按数组元素分为 整形数组、字符型数组、指针数组、结构数组等
一维、二维、多维等表现形式

非线形结构

各个结点之间具有多个对应关系。

按数据结构的语言描述，有以下特点：

1. 非空集。
2. 一个结点可能有多个直接前驱结点和多个直接后继结点。

常见的非线形结构：树结构、图结构、散列表、数组、广义表等。

树 Tree：

二叉树，完全二叉树（堆），AVL自平衡二叉查找树，线索二叉树，二叉查找树，多路查找树，红黑树（HashMap底层源码），B+树（mysql数据库索引结构）等

相关概念和知识点：根结点、子结点、父母结点、左子树、右子树、前序遍历、中序遍历、后续遍历

二叉树结构在 添加、删除运算都很快，在查找方面也有很多算法优化。既有链表的好处，也有数组的好处，在处理大批量动态数据贩卖呢非常有用。

堆 Heap：

是一种特殊的树形数据结构，完全二叉树。
数组的存储结构
二叉堆，大顶堆，小顶堆，斐波那契堆

建堆，向下调整，向上调整

根据堆有序的特点，一般用来做数组排序，即堆排序。

图 Graph：

图由 结点Vertex的有穷集合 和 边Edge的集合组成。
为了与树结构加以区别，在图结构中将结点称为顶点。

不带权图中，若两点不相邻，邻接矩阵对应位置为 0；
带权图（网）中，若两点不相邻，邻接矩阵对应位置为 ∞；

定义：

• 二元组的定义 G = (V, E) ，E与V不相交。亦可写成V(G)和E(G)。E的元素都是二元组，E = (x, y);
• 三元组的定义 G = (V, E, I)，E与V不相交。I称为关联函数，I将E中的每一个元素映射到VxV。

有向图，无向图，有向无环图，权，连通图，生成树等

图有着复杂的存储结构：邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等。

散列表 Hash：

也叫哈希表，根据 键Key和值Value 进行访问的数据结构。
过程：将 Key 通过固定的 哈希算法 生成一个 唯一的整形数字，然后将这个唯一的整形数字对数组长度取余，取余结果当作数组的下标，然后将 Value存储在以该数字为下标的数组空间里，即 数组+数组 的结构。

充分利用数组的查找优势，所以查找速度很快，但是删除元素较慢，所以衍生的结构有 数组+链表、数组+红黑树等。

哈希表的应用：Java中的集合类如：HashMap、HashTable等。jdk1.8以前采用 数组+链表 的结构，也叫拉链法。jdk1.8以后换成了 数组+红黑树 的结构。

哈希表的问题：哈希冲突，处理不好浪费时间，导致应用崩溃。

二叉链表

树的二叉链表实现方式（孩子兄弟表示法）
以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。

常用数据结构 的结构体定义

单链表,循环链表

typedef struct Node 
{
    ElemType data;      //数据域，可替换成任意数据类型
    struct Node *next;  //指针域
} Node, *LinkedList;

双链表

typedef struct DuLNode
{
    ElemType data;          //数据域
    struct DuLNode *pre;   //指针域-前驱结点
    struct DuLNode *next;  //指针域-后继结点
} DuLNode, *DuLLinkList;

栈-数组

typedef struct Stack
{
    ElemType data[max];
    int top;
} Stack;

栈-链表

// 结点定义
typedef struct Node
{
    ElemType data;      //数据域
    struct Node *next;  //指针域
}Node;

// 栈定义
typedef struct Stack
{
    Node *top;
    int count;
}Link_Stack;

顺序队列 - 链表

//结点定义
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;

// 队列定义
typedef struct Queue
{
    Node *front;
    Node *rear;
} Queue;

注意：假溢出问题

循环队列 - 数组

typedef struct CircleQueue
{
    ElemType data[max];
    int rear;
    int front;
} CircleQueue;

树

// 树的结点
typedef struct Tree
{
    ElemType data;
    struct Node *left;
    struct Node *right;
} Node;

// 树根
typedef struct Tree
{
    Node *root;
} Tree;

二叉链表

typedef struct CSNode
{
    ElemType data;
    struct CSNode *firstchild;
    struct CSNode *netsiling;
} CSNode, *CSTree;

感谢以下文章作者

C语言网 数据结构
C语言中文网 数据结构