数据结构

在学习数据结构之前我想先有一个大体的概念，所以在网上查了一些资料记录如下

常见的数据结构

1.线性结构
2.树形结构
3.图形结构
4.集合

一、线性结构（线性结构是一个有序数据元素的集合）

常用的线性结构有：线性表，栈，队列，双队列，串。
关于广义表、数组，是一种非线性的数据结构。
常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图

特征：
1．集合中必存在唯一的一个"第一个元素"；
2．集合中必存在唯一的一个"最后的元素"；
3．除最后元素之外，其它数据元素均有唯一的"后继"；
4．除第一元素之外，其它数据元素均有唯一的"前驱"。
数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。
如（a0,a1,a2,…,an）,a0为第一个元素，an为最后一个元素，此集合即为一个线性结构的集合。
相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。

栈、队列和线性表：
可采用顺序存储和链式存储的方法进行存储
顺序存储：借助数据元素在存储空间中的相对位置来表示元素之间的逻辑关系
链式存储：借助表示数据元素存储地址的指针表示元素之间的逻辑关系

栈（后进先出或先进后出的线性结构）

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
分为：顺序栈，链栈

队列（先进先出的线性结构）

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
分为：顺序队列，循环队列

线性表

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。
分为：顺序表，单向链表，双向链表，循环链表，双向循环链表。

二、树形结构（一层次的嵌套结构。 一个树形结构的外层和内层有相似的结构， 所以这种结构多可以递归的表示）

常见树形结构：二叉树，完全二叉树，二叉查找树，平衡二叉树，树，堆，并查集，B树。

二叉树

二叉树是一种递归数据结构，是含有n(n>=0)个结点的有限集合。
二叉树具有以下特点：
二叉树可以是空树；二叉树的每个结点都恰好有两棵子树，其中一个或两个可能为空；二叉树中每个结点的左、右子树的位置不能颠倒，若改变两者的位置，就成为另一棵二叉树

完全二叉树

从根起，自上而下，自左而右，给满二叉树的每个结点从1到n连续编号，如果每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，则称为完全二叉树

二叉查找树

二叉查找树又称二叉排序树，或者是一课空二叉树，或者是具有如下特征的二叉树：
a、若它的左子树不空，则左子树上所有结点的值均小于根结点的值
b、若它的右子树不空，则右子树上所有结点的值均大于根结点的值
c、它的左、右子树也分别是二叉查找树

平衡二叉树

平衡二叉查找树简称平衡二叉树，平衡二叉树或者是棵空树，或者是具有下列性质的二叉查找树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1

树

树是含有n(n>=0)个结点的有限集合，在任意一棵非空树种： a、有且仅有一个特定的称为根的结点
b、当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且T1,T2,…,Tm称为根的子树

堆

堆是具有以下特性的完全二叉树，其所有非叶子结点均不大于（或不小于）其左右孩子结点。若堆中所有非叶子结点均不大于其左右孩子结点，则称为小顶堆（小根堆），若堆中所有非叶子结点均不小于其左右孩子结点，则称为大顶堆（大根堆）

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题

B树

在B-树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。

三、图形结构

图形结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。
分为有向图和无向图

参考资料：百度百科，博客园等

目录

一、什么是数据结构

二、常用数据结构有哪些

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 算法的空间复杂度与时间复杂度

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

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

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

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

一、什么是数据结构

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

数据结构与算法的关系：

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

二、常用数据结构有哪些

2.1 基本数据结构

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

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

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

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

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

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

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

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

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

2.2.2 线性表

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

2.2.3 队列

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

2.2.4 栈

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

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

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

2.2.6 图(Graph)

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

2.2.7 堆 (Heap)

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

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

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

2.3 数据存储结构比较

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

2.4 数据结构的操作

查询、删除、插入等

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

大O复杂度表示法

一、什么是数据结构
1、数据结构的起源
1968年，美国的高纳德教授开设了一门基本算法的课程，开创了数据结构的先河。
数据结构是一门研究数据之间关系和操作的学科，而非是计算方法。
数据结构+算法=程序 沃思凭借这名个论点，获得图灵奖，这句话展示出了程序的本质。
2、数据结构的基本概念
数据：所有能够输入到计算机中去描述事物的符号。
数据项：有独立含义的数据最小单位，也叫域。
数据元素：数据的基本单位也叫节点、记录。
数据结构：数据元素和数据关系的集合。
算法：数据结构所具备的功能，解决特定的问题的方法。
3、数据结构的三个方面
数据的逻辑结构
数据的存储结构
数据结构的运算

二、逻辑结构和存储结构
数据的逻辑结构：
集合：数据元素同属于一个集体，但元素之间没有任何关系。
线性结构：数据元素之间存在一对一关系（表）。
树型结构：数据元素之间存在一对多关系（倒悬树）。
图型结构：数据元素之间存在多对多关系（地图）
数据的物理结构：
顺序结构：数据元素存储在连续的内存中，用数据元素的相对位置来表示关系。
优点：随机访问，访问效率极高。
缺点：空间利用率低，对内存要求比较高，插入、删除不方便。
链式结构：数据元素存储在彼此独立的内存空间中，每个独立的元素也叫节点，每个数据元素中增加一个数据项用于存储其它元素的地址，用来表示元素之间的关系。
优点：插入、删除方便，空间利用率高。
缺点：不能随机访问，只能由前到后逐个访问。
逻辑结构和物理结构的对应关系：
表 顺序 链式
树 链式 顺序
图 顺序+链式
每种逻辑结构采用什么物理结构存储并没有明确规定，通常根据实际的难易程度以及空间、时间方面的要求，来选择最合适的物理存储结构。

三、数据结构和运算
1、建立数据结构 create
2、销毁数据结构 destory
3、清空数据结构 clean
4、数据结构排序 sort
5、删除元素 delete
6、插入元素 insert
7、访问元素 access
8、修改元素 modify
9、查询元素 query
10、遍历数据结构 ergodic show print

四、顺序表和链式表的实现
顺序表：
数据项：
存储元素的内存首地址
表的容量
元素的数量

运算：
创建、销毁、清空、 插入、删除、访问、修改、查询、排序、遍历
注意：
1、不要越界
2、要保持元素的连续性
优点：支持随机访问，修改、查询、排序效率比较高，大块连续的内存不易产生内存碎片。
缺点：对内存的要求比较高（内存连续），插入、删除元素时不方便，效率低。
链式表：
元素的数据项：
数据域：可以是各种类型的若干个数据项
指针域：指向下一元素
由若干个元素通过指针域连接在一起形成链式表。
不带头节点：第一个元素的数据域存储的就是有效的数据。
添加删除时可以会修改头节点指针，参数需要使用二维指针。
同时需要获取到上一个节点的指针，而头节点没有上一个节点，因此需要额外处理。
带头节点：第一个元素不使用，仅仅是为了用它来指向下一元素。
树型结构：
1、树的基本概念
一种表示层次关系的(一对多)数据结构。
有且仅有一个特定的节点，该节点没有前驱，被称为根节点。
剩余的n个互不相交的子集，其中每个子集也都是一棵树，被称为根节点的子树。
注意：树型结构具有递归性（树中有树）。
2、树的表示方法：倒悬树、嵌套法、凹凸法。
3、树的专业术语：
节点：组成树的基础元素，同时它也是一棵树。
节点的度：该节点子树的数量。
树的度(密度)：树中节点的数量。
叶子节点：节点的度为0的节点。
双亲和孩子：节点的子树被称为孩子节点，该节点就是它们的双亲。
兄弟：具有同一个双亲节点，被称为兄弟节点。
祖先：从根节点出发到该节点，经过的所有节点都被称为该节点的祖先。
子孙：一个节点的子树中的任意一个节点都被称为它的子孙。
节点的层次：根节点层次为1，它的孩子层次为2，孩子的防止层次为3，依次类推。
堂兄弟：双亲在同一层互为堂兄弟。
树的深度：树的最大层次为树的深度。
森林：n个不相交的树的集合被称为森林。
4、树的存储
树可以顺序存储、链式存储，也可以混合存储，由于存储的信息不同，有以下表示方式：
双亲表示法：顺序
优点：方便找到双亲，缺点：查找孩子节点不方便。
孩子表示法：
顺序：浪费空间
链式：节约空间
优点：方便找孩子，缺点：不方便找双亲结点。
兄弟表示法：
双亲只存储第一个子节点，然后链式指向所有兄弟节点。
优点：可以方便的查询到兄弟节点 缺点：查询双亲比较麻烦
数据 第一个子节点 兄弟节点头指针
二叉树：
是常用的一种数据结构，处理起来比普通简单，而且普通树可以很方便转换成二叉树。
定义：二叉树是n个有限元素的集合，由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。
二叉树的性质：
性质1：二叉树的第i层上最多有2^(i-1)个节点。
每层的节点数都是2^(i-1)，这种树叫满二叉树。
对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
性质2：深度为h的二叉树中至多含有2^h-1个节点。
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。
性质4：具有n个节点的完全二叉树深为log2^n+1。
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点。
当i>1时，该节点的双亲节点的编号为i/2(顺序存储)。
如果2i<=n，则编号为2i 则有编号为i的左孩子。
如果2i+1<=n，则编号为 2i+1 为编号为i的右孩子。
二叉树的操作：
构建、销毁、遍历、高度、密度、插入、删除、查询、求左、求右、求根
二叉树的存储：
顺序：必须按照完全二叉树的格式存储，空位置使用特殊数据代替。
数据项：
存储节点的内存
容量
二叉树的遍历：
前序：根、左、右
中序：左、根、右
后序：左、右、根
注意：前中后由根节点决定，不存在左、左根的后序，左、右子的次序不变。
注意：根据 前序+中序 或者 中序+后序 还原一棵树，前序+后序无法还原（无法判断出根节点的左右子树）。
层序：从上到下、从左到右遍历一棵树，必须与队列配合。

平衡二叉树：
前提是有序的二叉树，它的左右子树的高相差不超过1，它的所有的子树也要满足这个要求。
如果一个有序二叉树呈单支状（接近单支），它的效率接近链表，因此只有达到平衡时它的效率才最高。
由于节点的位置受值的影响，因此只能进行调整，而不能强行修改。

二叉树不平衡的基础原因：
      x                            y 
     / \                         /   \
    y   t1  以为轴向右旋转       z     x
   / \                         / \   / \
  Z   t2                      t3 t4 t2 t1
 / \
t4  t3

  x                                  y
 / \                               /   \
t1  y                             x     z
   / \      心y为轴向左旋转       / \   / \
  t2  z                         t1 t2 t3 t4
     / \                             
    t3  t4

      x                 x                z
     / \               / \             /   \
    y   t1            z   t1          y     x
   / \               / \             / \   / \
  t4  z             y   t2          t4 t3 t2 t1
     /  \          / \
    t3   t2       t4  t3
以z为轴向左旋转    以z为轴向右旋转    最终达到平衡

    x                 x                   z
   / \               / \                /   \
  t1  y             t1  z              x     y
     / \               / \            / \   / \
    z  t4             t2  y          t1 t2 t3  t4
   / \                   / \
  t2  t3                t3 t4
以z为轴向右旋转    心z为轴向左旋转

红黑树：
也一种自平衡的二叉树，它不是根据子树的高度来调整平衡的，而是给节点设置一个颜色，来达到平衡。
优点：插入与删除的效率，比AVL树要高。
缺点：没有AVL均匀，查找效率没AVL树高。

图(Graph)型结构：
什么图型结构：由顶点的有穷且非空和顶点之间边的集合.
通常表示：G(V,E)，G表示一个图，V是图中顶点集合(元素)，E是图中边(元素之间的关系)的集合。

无向图：
边用(A,B)方式表示，点与点之间是互通的。
在无向图中，任意两个顶点之间都有边，该图称为无向完全图，则含有n个顶点的无向完全图有，n*(n-1)/2条边。
有向图：
边用<A,B>方式表示，仅仅是A到到B点，有向图的边也叫弧，A是弧尾，B是弧头。
在有向图中，任意两个顶点之间都方向相反的两条弧，这种图叫有向完全图，则含有n个顶点的有向完全图有，n*(n-1)。
注意：不存在顶点到自身的边，且一条边不重复出现，这种图叫简单图，数据结构中只研究简单图。

图的点多边少的图叫稀疏图，反之的叫稠密图，图的点与点之间边带数据，这些数据叫作边的权重，带权重的图被称为网。

依附于顶点的边的数量叫作顶的度，有向图双分为出度(从顶出的的弧的数量)和入度(指向顶点的弧的数量)。

路径：顶点到顶点经过的边叫路径，边的数量叫路径的长度。
第一个顶点到最后一个顶的路径是相同的，这种路径叫回路或者环。
序列顶点中不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点，其余顶点不重复出现的回路叫简单回路。

如果顶点V到顶点V1有路径，则称V和V1是连通的，如果图中和任意顶点之间是连通的，则称图为连通图，如果一个图中有n个顶点那么至少需要n-1条边才能达到连通图，仅需要n-1边的连通叫生成树，如果再配合上权重，代价最的叫最小生成树。

树的存储结构：
阾接矩阵：
用一个一维数组来存储n个顶点，用一个n*n二维数组来存储边。
char V[n] = {A,B,C,D,E,F,G};
A B C D E F G
A [0][0][0][1][1][0][0]
B [0][0][0][0][0][0][0]
C [0][0][0][0][0][0][0]
D [1][0][0][0][0][0][0]
E [0][0][0][0][0][0][0]
F [0][0][0][0][0][0][0]
G [0][0][0][0][0][0][0]
二维数组中E[i][j]的值为1，则表示项V[i]，到顶点V[j]有边。
注意：由于不存在自己到自己的边，主对角线上的值为假。
如果存储的是无向图则二维数组中的值沿主对角线对称，可以压缩为一维数组。