目录

一、什么是数据结构

二、常用数据结构有哪些

2.1 基本数据结构

2.2 常用数据结构 (逻辑结构）

2.2.1 数组（静态数组、动态数组）

2.2.2 线性表

2.2.3 队列

2.2.4 栈

2.2.5 树（二叉树、查找树、平衡树、线索、堆）

2.2.6 图(Graph)

2.2.7 堆 (Heap)

2.2.8 散列表(哈希表） (Hash)

2.3 数据存储结构比较

2.4 数据结构的操作

2.5 算法的空间复杂度与时间复杂度

数据结构可以从两个方面分析：逻辑结构与物理结构(存储结构)。

其中逻辑结构指的是数据的组织方式，物理结构指的是数据在内存上的存储方式。

逻辑结构分为四种类型：集合结构，线性结构，树形结构，图形结构。

物理结构又叫存储结构，分为四种种，顺序存储结构、链式存储结构、索引结构、散列结构。

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。  

数据结构与算法的关系：

数据结构指的是“一组数据的存储结构”，算法指的是“操作数据的一组方法”。 数据结构是为算法服务的，算法是要作用再特定的数据结构上的。

数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构。 集合结构:除了同属于一种类型外，别无其它关系 ；

线性结构:元素之间存在一对一关系常见类型有: 数组,链表,队列,栈,它们之间在操作上有所区别。例如:链表可在任意位置插入或删除元素, 而队列在队尾插入元素,队头删除元素,栈只能在栈顶进行插入,删除操作；

树形结构:元素之间存在一对多的关系,常见类型有:树(有许多特例:二叉树、平衡二叉树、查找树等) 图形结构:元素之间存在多对多的关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意。

本文作者：https://www.zhihu.com/people/san-hao-bai-du-ren-79

(由于文章总是被三无号到处复制发布，选择这种方式插入原文链接影响阅读实在抱歉！)

本文原文链接：https://blog.csdn.net/qq_41687938/article/details/118227614

 在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中， 数组属于构造数据类型。  一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。顺序表、链表（单向链表、双向链表、循环链表）

栈隶属于线性表，是特殊的线性表，因为它对线性表中元素的进出做了明确的要求只能从线性表的一端进，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。即只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素 时，称为队空。

栈隶属于线性表，是特殊的线性表，因为它对线性表中元素的进出做了明确的要求。栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。即先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，最后一 个数据被第一个读出来。

树是包含n（n>0）个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件： 1）有且仅有一个结点K0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。 2）除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。 3）K中各结点，对关系N来说可以有m个后继（m>=0）。

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。

若结构中存在关键字和K相等的记录，则该记录必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。

顺序结构：一段连续的内存空间。     优点：随机访问     缺点：插入删除效率低，大小固定链式结构：不连续的内存空间     优点：大小动态扩展，插入删除效率高     缺点：不能随机访问。索引结构：为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表。     优点：对顺序查找的一种改进，查找效率高     缺点：需额外空间存储索引表散列结构：选取某个函数，数据元素根据函数计算存储位置。可能存在多个数据元素存储在同一位置，引起地址冲突。     优点：查找基于数据本身即可找到，查找效率高。存取效率高     缺点：存取随机，不便于顺序查找。

查询、删除、插入等

大O复杂度表示法