1.逻辑结构和物理结构

1.1逻辑结构：数据对象中数据元素之间的关系

  • 集合结构：数据元素除了同属于一个集合之外，她们没有任何关系
  • 线性结构：数据元素之间一对一关系
  • 树形结构：数据元素之间存在一对一或一对多的层级关系

  • 图形结构：数据元素是多对多的关系

    1.2物理结构(存储结构)：数据的逻辑结构在计算机中的存储形式

    存储结构分四类：顺序存储、链接存储、索引存储 和 散列存储。
    顺序结构和链接结构适用在内存结构中。
    索引结构和散列结构适用在外存与内存交互结构。

  • 顺序结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

  • 链式结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的
  • 索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。
  • 散列存储：散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。（本质: 一个数组和多个单链表的组合而成的复合数据结构）

哈希表(散列存储)：用散列法存储的线性表被称为哈希表，使用的函数被称为散列函数或者哈希函数，f(k)被称为散列地址或者哈希地址。通常情况下，散列表的存储空间是一个一维数组，而其哈希地址为数组的下标

2. 知识补充

2.1指针，地址，指针变量

指针： 指针就是内存地址，是变量的地址 (*p)
地址：地址也作为一种值，能被存储、比较、赋值，并称地址数据为指针类型 (&a)
指针变量：指针变量是存放地址的变量 a；

  1. int a=3;
  2. int *p;
  3. p=&a;

2.2结构体

结构体类型：包含不同类型的成员；
结构体指针，就是指向结构体变量的指针

2.3链表

链表是一种数据结构，必须利用指针变量来实现；数据结构包括（number结构类型，Object类型，Array类型等等）；链表是根据需要开辟内存单元，链表有一个头指针，存放一个地址，该地址指向一个元素（每个链表都有一个头指针，必不可少）；链表中的每一个元素称为节点；节点包含两个部分，用户需要的实际数据，下一个节点的地址(next);链表中的地址是不连续的；要找某一元素，必须先找到上一个元素，根据他提供的下一个元素地址才能找到下一个元素
备注： 形参不占内存中的存储单元；如果函数不需要返回值则不需要return语句

2.4 内存中的 堆与栈

2.4.1用户空间程序三个阶段

  • .data段：包含了已经初始化了的数据项，这些数据在程序开始运行前就拥有自己的值，这些值是可执行文件的一部分，当可执行文件被加载到内存中用于执行时，这些数据也被加载到内存中。
  • .bss段：并不是所有数据项在程序开始之前都拥有值，例如你可以定义一个缓冲区来存在某些数据，这个缓冲区是.bss段中定义的。
  • .text段：以上两个段都是源程序所需要的数据，而真正组成程序的机器指令则存放在.text段中。一般情况下，在.text段中不进行数据项的定义。.text段包含名为标号(label)的符号，这些符号用于标识跳转和调用程序代码位置。

汇编中常说的堆栈，其实是栈，并不包含堆。

  • 栈（操作系统）：由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈，栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放
  • 堆（操作系统）： 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些
  • 堆（数据结构）：堆可以被看成是一棵树，如：堆排序
  • 栈（数据结构）：一种后进先出的数据结构

image.png

3.线性表

线性表是零个或多个具有相同特性的数据元素组成的有限序列(特点：有序，有限，没有前驱元素只有后继元素),每个元素为单元素
3.1 存储结构

  • 顺序存储： 优点：不需要额外引用地址空间 缺点：增删移动大量元素
  • 链式存储： 节点包含数据域、指针域， 优缺点相反

3.2 单链表
一个节点只包含数据域和一个指针域
3.3 静态链表
有人想出了用数组来代替指针，来描述单链表，让每个数组的元素都由两个数据域组成，数组的每个下标都对应两个数据域，一个用来存放数据元素，一个用来存放next指针
3.4 循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
3.5 双向链表
在单链表的基础上，再在每个结点中设置一个指向其前驱结点的指针域，这样一个结点既可以指向它的前面又可以指向它的下一个，我们把这种链表称为双向链表。

4. 栈和队列

4.1 栈

栈是限定仅在表尾进行插入和删除操作的线性表

4.1.1栈的存储结构

栈是线性表的特例，所以栈的顺序存储结构其实就是线性表顺序存储结构的简称，我们简称为顺序栈。把栈顶放在单链表的头部，用链表来存储栈的的数据结构称为链栈。

4.2 队列

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

4.2.1 循环队列
顺序表存储，顺序表成本高(移动指针)，引入循环队列。为了避免假溢出，让队列的头尾进行相连，这种头尾相连的顺序存储结构称为循环队列。

  1. // 存储结构：
  2. typedef struct{    
  3.   int data[maxsize]; //定义数组 
  4.   int front;         //队首指针   
  5.   int rear;          //队尾指针
  6. }SqQuene;            //顺序队列定义

4.2.2 链列
链队就是采用链式存储结构存储队列。

  1. // 链队类型定义：
  2. typedef struct
  3. {
  4.     QNode *front;        //队头指针
  5.     QNode *rear;         //队尾指针
  6. }LiQuene;                //链队类型定义
  7. // 节点定义
  8. typedef struct QNode
  9. {
  10.     int data;             //数据域
  11.     struct QNode *next;   //指针域
  12. }QNode;                   //队结点类型定义

5. 串

由零个或多个字符串组成的有限序列，又叫字符串。（串中的元素都是字符），通常使用顺序存储。

5.1 串的存储结构

  • 串的顺序存储结构：串值的存储空间可在程序执行过程中动态分配。在计算机中有个“堆”的自由存储区，可由C语言的动态分配函数malloc( )和free( )来管理
  • 串的链式存储结构：在考虑到空间浪费的问题上，所以一个结点可以存放一个字符，也可存放多个字符，最后一个结点若是未被占满时，用“#”或其他非串值字符补全。

串和线性表的区别：线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素，但串中更多的是查找子串位置，得到指定位置子串，替换子串等操作。
串的模式匹配算法：著名的模式匹配算法有两种：BF和KMP算法

6. 数组和广义表

6.1数组

6.1.1 定义

由类型相同的数据元素构成的有序集合。数组一般不做插入和删除操作，所以一般采用顺序存储结构。

  • 一维数组可以看成线性表

  • 二维数组是数据元素为线性表的线性表；

    6.2 广义表

    6.2.1 定义

    广义表是线性表的推广，是一种多层次的数据结构，广义表的元素可以是单元素也可以是子表，而子表的元素还可以是子表。

    6.2广义表存储结构

    通常采用链式存储结构，两种结构的节点:一种是表节点,用以表示列表,一种是元素节点,用以表示单元素.
    表节点：可由三个域组成:标志域,指示表头的指针域和指示表尾的指针域。
    元素节点只需要两个域:标志域和值域

    7. 树和二叉树

    是n(n>=0)个结点的有限集。线性表是一对一的结构，而树则是一对多的结构。

    7.1 树的相关概念

  • 高度： 节点到叶子节点最长边的总和

  • 深度： 该节点到根节点最长边的总和

  • 层级(level): 节点的Level是从1开始的，Level = Depth+1，根节点的Level=1

    7.2 二叉树

    7.2.1 二叉树类型

    二叉树是一个每个最结最多只能有两个分支的树

  • 完美/满二叉树：所有的子节点都包含两个子节点

  • 完全二叉树： 除了最后一层都是满的（都有两个子节点），并且最后一层的节点是从左往右排列的。

  • 完满二叉树：就是每个节点都有两个子节点。

    7.2.2 二叉树的遍历

  • 前序遍历：根结点 —-> 左子树 —-> 右子树

  • 中序遍历：左子树 —-> 根结点 —-> 右子树
  • 后序遍历：左子树 —-> 右子树 —-> 根结点
  • 层次遍历：只需按层次遍历即可

深度优先遍历
广度优先遍历：类似层次遍历
先序，后序，中序针对二叉树。深度、广度针对普通树。

7.2.3 平衡二叉树

平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构；

7.2.4 B_树和B+树

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树
B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；

8. 图

图是一种复杂的非线性结构。

8.1术语

  • 顶点：图中的一个点
  • 边：连接两个顶点的线段叫做边，edge
  • 相邻的：一个边的两头的顶点称为是相邻的顶点
  • 度数：由一个顶点出发，有几条边就称该顶点有几度，或者该顶点的度数是几，degree
  • 路径：通过边来连接，按顺序的从一个顶点到另一个顶点中间经过的顶点集合
  • 简单路径：没有重复顶点的路径
  • 环：至少含有一条边，并且起点和终点都是同一个顶点的路径
  • 简单环：不含有重复顶点和边的环
  • 连通的：当从一个顶点出发可以通过至少一条边到达另一个顶点，我们就说这两个顶点是连通的
  • 连通图：如果一个图中，从任意顶点均存在一条边可以到达另一个任意顶点，我们就说这个图是个连通图
  • 无环图：是一种不包含环的图
  • 稀疏图：图中每个顶点的度数都不是很高，看起来很稀疏
  • 稠密图：图中的每个顶点的度数都很高，看起来很稠密
  • 二分图：可以将图中所有顶点分为两部分的图

相关知识点：
邻接表：表示了图中与每一个顶点相邻的边集的集合
背包：只进不出，内容无序。
有向无环图：如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）

9. 哈希表

9.1 哈希函数

如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。

9.2 哈希表定义

哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。
优缺点： 快速查找，方便增删。缺点： 不支持排序

10. JavaScript中的数据结构

10.1 JavaScript 数据类型

栈内存 堆内存
存储基础数据类型 存储引用数据类型
按值访问 按引用访问
存储的值大小固定 存储的值大小不定，可动态调整
由系统自动分配内存空间 由程序员通过代码进行分配
主要用来执行程序 主要用来存放对象
空间小，运行效率高 空间大，但是运行效率相对较低
先进后出，后进先出 无序存储，可根据引用直接获取

V8中，Array 默认使用 顺序结构，数据到达一定量使用hash表结构；
参考文档：
内存中的堆和栈到底是什么
四种数据存储结构—-顺序存储 链接存储 索引存储 散列存储
数据结构学习入门
算法精解：DAG有向无环图
基础大扫荡——背包，栈，队列，链表一口气全弄懂