概述

数据结构(data structure)是带有构造个性的数据元素的汇合，它钻研的是数据的逻辑构造和数据的物理构造以及它们之间的互相关系，并对这种构造定义相适应的运算，设计出相应的算法，并确保通过这些运算当前所失去的新构造仍放弃原来的构造类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的汇合，即带“构造”的数据元素的汇合。“构造”就是指数据元素之间存在的关系，分为逻辑构造和存储构造。

数据的逻辑构造和物理构造是数据结构的两个密切相关的方面，同一逻辑构造能够对应不同的存储构造。算法的设计取决于数据的逻辑构造，而算法的实现依赖于指定的存储构造

数据结构的钻研内容是结构简单软件系统的根底，它的核心技术是合成与形象。通过合成能够划分出数据的3个档次；再通过形象，舍弃数据元素的具体内容，就失去逻辑构造。相似地，通过合成将解决要求划分成各种性能，再通过形象舍弃实现细节，就失去运算的定义。上述两个方面的联合能够将问题变换为数据结构。这是一个从具体（即具体问题）到形象（即数据结构）的过程。而后，通过减少对实现细节的思考进一步失去存储构造和实现运算，从而实现设计工作。这是一个从形象（即数据结构）到具体（即具体实现）的过程。

简而言之数据结构是——以某种特定的布局形式存储数据
这种“布局形式”决定了数据结构对于某些操作是高效的，而对于其余操作则是低效的。首先咱们须要了解各种数据结构，能力在解决理论问题时选取最合适的数据结构。

数据结构分类

  • [1、数组]
  • [2、栈]
  • [3、队列]
  • [4、链表]
  • [5、树]
  • [6、散列表]
  • [7、堆]
  • [8、图]


每一种数据结构都有着独特的数据存储形式

1、数组(Array)：
数组是最简略、也是应用最宽泛的数据结构。栈、队列等其余数据结构均由数组演变而来。每个数据元素都关联一个正数值，咱们称之为索引，它表明数组中每个元素所在的地位。大部分语言将初始索引定义为零。
数组是能够再内存中间断存储多个元素的构造，在内存中的调配也是间断的，数组中的元素通过数组下标进行拜访，数组下标从0开始，例如上面这段代码就是将数组的第一个元素赋值为 1

长处：
1、依照索引查问元素速度快
2、依照索引遍历数组不便

毛病：
1、数组的大小固定后就无奈扩容了
2、数组只能存储一种类型的数据
3、增加，删除的操作慢，因为要挪动其余的元素。

一维数组 --- int[] a = new int [4];
-------- 数组也是一个变量，是存储一组雷同类型的变量

申明一个变量就是在内存中划出一块适合的空间

申明一个数组就是在内存中划出一块间断的空间

二维数组 ---int [] [] arr = new int[3] [4];

3示意这个二维数组有3个一维数组，名称是arr[0],arr[1],arr[2]，4示意每一个一维数组有4个元素。

2、栈(Stack)

栈是一种只能在尾部进行插入或删除的线性表。其中，容许插入或删除的一端称为栈顶（Top），是变动的，另一端称为栈底，是固定不变的。栈的插入操作称为入栈/进栈/压栈。栈的删除操作称为出栈/退栈。

栈的特点是：先进后出，或者说是后进先出。


栈的基本操作：
new Stack();
Push——在顶部插入一个元素
Pop——返回并移除栈顶元素
isEmpty——如果栈为空true
Top——返回顶部元素，但并不移除它

3、队列(Queue)
队列是一种比拟非凡的线性构造。它只容许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中最先插入的元素也将最先被删除，对应的最初插入的元素将最初被删除。因而队列又称为“先进先出”（FIFO—first in first out）的线性表，与栈(FILO-first in last out)刚好相同。从一端放入元素的操作称为入队，取出元素为出队，示例图如下：

队列事实例子：售票亭排队队伍。如果有新人退出，他须要到队尾去排队，而非队首——排在后面的人会先拿到票，而后来到队伍。
右图是蕴含三个元素（A，B，C）的队列，其中在头部（front)的A将被最先移除。
移除先入队的元素、插入新元素实用场景。

应用场景：
因为队列先进先出的特点，在多线程阻塞队列治理中十分实用。（例如：优先级队列）。


*解决“假溢出”，能够用循环列队

通过两个堆栈实现一个队列:
栈的构造是先进后出，队列的构造是先进先出，那么用两个栈模仿一个队列的思路b就是一个栈用来入列，另一个栈用来出列。

1）入列：顺次往stack1中插入a、b、c
2）出列：若stack2为空的话，那么stack1中元素顺次出栈，压入stack2中，此时stack2中的元素从栈顶往栈底方向顺次是c、b、a，而后顺次弹出元素a和b
3）入列：往stack1中插入d元素
4）出列：此时stack2中仍然有元素c，那么c比d先入列，则c应该比d先出列，所以此时出列元素为c
5）出列：此时stack2中没有元素，那么stack1中有元素d出栈压入stack2，stack2中的元素d弹出（即入列）


队列实现的三种形式：
（1）通过数组实现一个队列；
（2）通过汇合实现一个对列；JDK中,LinkedList类实现了Queue接口，能够当Queue应用。
（3）通过两个堆栈实现一个队列。

队列的基本操作：
push()-——在栈顶减少元素
pop()-——在栈顶移除元素
Enqueue()——在队列尾部插入元素Dequeue()——移除队列头部的元素isEmpty()——如果队列为空，则返回trueTop()——返回队列的第一个元素

4、链表（Linked list）
链表是物理存储单元上非间断的、非程序的存储构造，乍一看可能有点像数组，但在内存调配、内部结构以及数据插入和删除的基本操作方面均有所不同。链表就像一个节点链，其中每个节点蕴含着数据和指向后续节点的指针。链表还蕴含一个头指针，它指向链表的第一个元素，但当列表为空时，它指向null或无具体内容。


**单链表：如果拜访任意结点每次只能从头开始程序向后拜访
单循链表：能够从任何一个结点开始，程序向后拜访达到任意结点
双向链表：能够从任何结点开始任意向前向后双向拜访**

链表的长处：
链表是很罕用的一种数据结构，不须要初始化容量，能够任意加减元素；
增加或者删除元素时只须要扭转前后两个元素结点的指针域指向地址即可，所以增加，删除很快；

毛病：
因为含有大量的指针域，占用空间较大；
查找元素须要遍历链表来查找，十分耗时。
实用场景：
数据量较小，须要频繁减少，删除操作的场景，个别用于实现文件系统、哈希表和邻接表。

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

图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，别离有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储构造。



就像一个站能够连贯多个地铁站

图的示意办法有两种：二维数组示意（邻接矩阵）；链表示意（邻接表）


1，邻接矩阵须要为每个顶点都调配n个边的空间，其实有很多边是不存在的，会造成空间损失。
2，邻接表只关怀存在的边，不关怀不存在的边，因而没有空间节约，邻接表由数组+链表组成。

6.树(Tree)
因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具备以下的特点：

  • 每个节点有零个或多个子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点能够分为多个不相交的子树；

应用场景：树形构造被广泛应用于人工智能和简单算法，它能够提供解决问题的无效存储机制。

树的相干概念术语：

以下是树形构造的次要类型：

  • N元树
  • 均衡树
  • 二叉树
  • 二叉搜寻树
  • AVL树
  • 红黑树
  • 2-3树

其中，二叉树和二叉搜寻树是最罕用的树。

/** * 创立一个树结构： * *           李磊 *        |         | *    韩梅梅       丽丽 *                   | *                 李刚 */public class TreeNode {            private int age;    // 节点属性，年龄        private String name;   //节点属性，姓名        TreeNode proTreeNode;    //下级节点        List<TreeNode> list = new ArrayList<TreeNode>(); //孩子节点        public int getAge() {            return age;        }        public void setAge(int age) {            this.age = age;        }        public String getName() {            return name;        }        public void setName(String name) {            this.name = name;        }        public TreeNode getProTreeNode() {            return proTreeNode;        }        public void setProTreeNode(TreeNode proTreeNode) {            this.proTreeNode = proTreeNode;        }        public void addTreeNode(TreeNode treeNode){            list.add(treeNode);            treeNode.proTreeNode = this;        }            public TreeNode getTreeNode(Integer i){            return list.get(i);        }        public void removeTreeNode(TreeNode treeNode){            list.remove(treeNode);            treeNode.proTreeNode = null;        }        public String toString(){            return "姓名："+name+";年龄："+age+"。";        }        public static void main(String[] args) {        TreeNode treeNode0 = new TreeNode();        treeNode0.setAge(11);        treeNode0.setName("李磊");        TreeNode treeNode1 = new TreeNode();        treeNode1.setAge(13);        treeNode1.setName("韩梅梅");        TreeNode treeNode2 = new TreeNode();        treeNode2.setAge(15);        treeNode2.setName("丽丽");        TreeNode treeNode3 = new TreeNode();        treeNode3.setAge(15);        treeNode3.setName("李刚");        treeNode0.addTreeNode(treeNode1); //父节点关联孩子节点        treeNode0.addTreeNode(treeNode2); //父节点关联孩子节点        treeNode2.addTreeNode(treeNode3); //丽丽节点下挂李刚        System.out.println(treeNode1+"======自身节点");   //打印节点自身        System.out.println(treeNode2.getTreeNode(0)+"======打印树节点");  //打印树节点        System.out.println(treeNode1.getProTreeNode()+"======打印父接口");  //打印父接口    }           }

7.散列表/哈希表（Hashing）

哈希表也叫散列表，是依据关键码值(Key value)而间接进行拜访的数据结构。也就是说，它通过把关键码值映射到表中一个地位来拜访记录，以放慢查找的速度，这个映射函数叫做散列函数，寄存记录的数组叫做散列表。

记录的存储地位=f(key)

而当应用哈希表进行查问的时候，就是再次应用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就能够充分利用到数组的定位性能进行数据定位。

Hash的利用:

1、Hash次要用于信息安全畛域中加密算法，它把一些不同长度的信息转化成芜杂的128位的编码,这些编码值叫做Hash值. 也能够说，Hash就是找到一种数据内容和数据寄存地址之间的映射关系。
2、Hash表在海量数据处理中有着广泛应用。


从图中能够看出，右边很显著是个数组，数组的每个成员包含一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。咱们依据元素的一些特色把元素调配到不同的链表中去，也是依据这些特色，找到正确的链表，再从链表中找出这个元素。

哈希表的利用场景很多，当然也有很多问题要思考，比方哈希抵触的问题，如果解决的不好会节约大量的工夫，导致利用解体。

8.堆(heap)

堆是一种比拟非凡的数据结构，能够被看做一棵树的数组对象，具备以下的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵齐全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

因为堆有序的特点，个别用来做数组中的排序，称为堆排序

数据的逻辑构造