数据结构笔记

发表于 | 更新于: | 分类于 | | 阅读次数:
阅读时长 ≈ 14

20190412155505554092398.png

好久没有温习数据结构了，今天来整理整理。

堆栈（stack）

堆栈（英语：stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。

常与有序的线性数据集合队列相提并论。

堆栈常用一维数组或链表来实现。

20190411155497516974025.png

软件堆栈

堆栈可以用数组和链表两种方式实现，一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事，所以较流行的做法是Stack结构下含一个数组。如果空间实在紧张，也可用链表实现，且去掉表头

堆栈有时候也常用来指代堆栈段。
堆栈段（stack segment）通常是指采用堆栈方式工作的一段内存区域。当程序被执行时，程序可能会将其执行的状态加入栈的顶部；当程序结束时，它必须把栈顶的状态数据弹出（pop）。

硬件堆栈

架构层次上的堆栈通常被用以申请和访问内存。

队列（queue）

队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
2019041115549770099188.png

单链队列

单链队列使用链表作为基本数据结构，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高

循环队列

循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

链表（link）

链表是一种数据结构，和数组同级。比如，Java 中我们使用的 ArrayList，其实现原理是数组。而
LinkedList 的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。

20190412155505588166695.png

单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
20190412155505656985771.png
一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个（需要储存反向的指针，见下面的双向链表）节点。

双向链表

每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）
20190412155505679974905.png
双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

循环链表

在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存， 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

指向整个列表的指针可以被称作访问指针。
20190412155505730643443.png
循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大(详见下面实例代码)。当然，如果只会在最后插入数据（或者只会在之前），处理也是很容易的。

另外有一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。

常见用途

常用于组织删除、检索较少，而添加、遍历较多的数据。 如果与上述情形相反，应采用其他数据结构或者与其他数据结构组合使用。

数组 (Array)

数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。

一维数组

一维（或单维）数组是一种线性数组，其中元素的访问是以行或列索引的单一下标表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//JAVA数组的两种创建方式
public static void main(String[] args){
    int[] arry1 = {1,2,3};
    int[] arry2 = new int[3];
    arry2[0] = 1;
    arry2[1] = 2;
    arry2[2] = 3;
    for (int i : arry1) {
        System.out.println(i);
    }
    for (int i : arry2) {
        System.out.println(i);
    }
}

多维数组

多维数组就是数组中嵌套数组，我们在多维数组之中采用一系列有序的整数来标注，如在[ 3,1,5 ] 。这种整数列表之中整数的个数始终相同，且被称为数组的“维度”。关于每个数组维度的边界称为“维”。维度为k的数组通常被称为k维。

如下所示：
{
{0,0,0,1,0,0,0},
{0,0,1,0,1,0,0},
{0,1,0,0,0,1,0},
{1,0,0,0,0,0,1},
{0,1,0,0,0,1,0},
{0,0,1,0,1,0,0},
{0,0,0,1,0,0,0}
}

数组特点

因为数组在存储数据时是按顺序存储的，存储数据的内存也是连续的，所以他的特点就是寻址读取数据比较容易，插入和删除比较困难。
简单解释一下为什么，在读取数据时，只需要告诉数组要从哪个位置（索引）取数据就可以了，数组会直接把你想要的位置的数据取出来给你。插入和删除比较困难是因为这些存储数据的内存是连续的，要插入和删除就需要变更整个数组中的数据的位置。举个例子：一个数组中编号0->1->2->3->4这五个内存地址中都存了数组的数据，但现在你需要往4中插入一个数据，那就代表着从4开始，后面的所有内存中的数据都要往后移一个位置。这可是很耗时的。

20190423155598767763310.png

程序设计

数组设计之初是在形式上依赖内存分配而成的，所以必须在使用前预先请求空间。这使得数组有以下特性：

  1. 请求空间以后大小固定，不能再改变（数据溢出问题）；
  2. 在内存中有空间连续性的表现，中间不会存在其他程序需要调用的数据，为此数组的专用内存空间；
  3. 在旧式编程语言中（如有中阶语言之称的C），程序不会对数组的操作做下界判断，也就有潜在的越界操作的风险（比如会把数据写在运行中程序需要调用的核心部分的内存上）。

树（tree）

20190423155598863865385.png
在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

特点

  • 每个节点都只有有限个子节点或无子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树；
  • 树里面没有环路(cycle)

无序树

树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；

有序树

树中任意节点的子节点之间有顺序关系，这种树称为有序树；

二叉树

每个节点最多含有两个子树的树称为二叉树；

完全二叉树

20190505155704196961130.png
在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。

满二叉树

20190505155704198798481.png
这种树的特点是每一层上的节点数都是最大节点数。

将n叉树转换为二叉树

二叉树当且仅当根节点没有右子结点时可转换为n叉树。

例如，在左边的树中，A有6个子结点{B,C,D,E,F,G}。它能被转换成右边的二叉树。
2019050515570431592083.png

将一棵树转换为二叉树的方法：

  1. 在兄弟之间加一连线；
  2. 对每个结点，除了其左孩子外，去除其与其余孩子之间的联系；
  3. 以树的根结点为轴心，将整树顺时针转45度。
平衡二叉树（AVL树）

平衡二叉搜索树（英语：Balanced Binary Tree）是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。它能在O( {\displaystyle \log n} \log n)内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。

常见的平衡二叉搜索树
排序二叉树(二叉查找树（英语：Binary Search Tree))

20190505155704553664072.png
二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；
  4. 没有键值相等的节点。

霍夫曼树

带权路径最短的二叉树称为哈夫曼树或最优二叉树；

B树

带权路径最短的二叉树称为哈夫曼树或最优二叉树；

图（Graph）

20190505155704655183365.png
图（Graph）用于表示物件与物件之间的关系，是图论的基本研究对象。一张图由一些小圆点（称为顶点或结点）和连结这些圆点的直线或曲线（称为边）组成。
稍微通俗易懂一点的阐述

定义

二元组定义

一张图 {\displaystyle G} G 是一个二元组 {\displaystyle (V,E)} (V,E)，其中 {\displaystyle V} V称为顶点集， {\displaystyle E} E称为边集。它们亦可写成 {\displaystyle V(G)} V(G)和 {\displaystyle E(G)} E(G)。 {\displaystyle E} E的元素是一个二元组数对，用 {\displaystyle (x,y)} (x,y)表示，其中 {\displaystyle x,y\in V} x,y \in V。

三元组定义

一张图 {\displaystyle G} G 是一个三元组 {\displaystyle (V,E,I)} (V,E,I)，其中 {\displaystyle V} V称为顶集（Vertices set）， {\displaystyle E} E称为边集（Edges set）， {\displaystyle E} E与 {\displaystyle V} V不相交； {\displaystyle I} I称为关联函数， {\displaystyle I} I将 {\displaystyle E} E中的每一个元素映射到 {\displaystyle V\times V} V\times V。如果 {\displaystyle I(e)=(u,v)(e\in E,u,v\in V)} I(e)=(u,v) (e\in E, u,v \in V)那么称边 {\displaystyle e} e连接顶点 {\displaystyle u,v} u,v，而 {\displaystyle u,v} u,v则称作 {\displaystyle e} e的端点， {\displaystyle u,v} u,v此时关于 {\displaystyle e} e相邻。同时，若两条边 {\displaystyle i,j} i,j有一个公共顶点 {\displaystyle u} u，则称 {\displaystyle i,j} i,j关于 {\displaystyle u} u相邻。

分类

有向图和无向图

如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。

简单图

  • 没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；
  • 每条边所关联的是两个不同的顶点
    满足这两个条件则称为简单图（Simple graph）。

多重图

若允许两结点间的边数多于一条，又允许顶点通过同一条边和自己关联，则为多重图的概念。它只能用“三元组的定义”。

散列表（Hash table）

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

end 😄

0%