java数组与集合框架（一） -- 数据结构，数组

数据结构

概述

为什么要讲数据结构？

        任何一个有志于从事IT领域的人员来说，数据结构（Data Structure）是一门和计算机硬件与软件都密切相关的学科，它的研究重点是在计算机的程序设计领域中探讨如何在计算机中组织和存储数据并进行高效率的运用，涉及的内容包含：数据的逻辑关系、数据的存储结构、排序算法（Algorithm）、查找（或搜索）等。

我们举一个形象的例子来理解数据结构的作用：

        战场：程序运行所需的软件、硬件环境

        敌人：项目或模块的功能需求

        指挥官：编写程序的程序员

        士兵和装备：一行一行的代码

        战术和策略：数据结构

                没有战术，打仗事倍功半

                有战术，打仗事半功倍

        总结：简单来说，数据结构，就是一种程序设计优化的方法论，研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，目的是加快程序的执行速度、减少内存占用的空间。

        因此，数据结构和算法是一名程序开发人员的必备基本功，不是一朝一夕就能练成绝世高手的。冰冻三尺非一日之寒，需要我们平时不断的主动去学习积累。

数据结构的应用

        计算机的主要工作就是把数据（Data）经过某种运算处理转换为实用的信息（Information） 。具体介绍一些数据结构的应用：

1）树形结构

        树形结构是一种相当重要的非线性数据结构，广泛运用在人类社会的族谱、机关的组织结构、计算机的操作系统结构、平面绘图应用、游戏设计等方面。

上图：四叉树示意图

上图：地形与四叉树的对应关系

2）最短路径

        最短路径是指在众多不同的路径中距离最短或者所花费成本最少的路径。寻找最短路径最常见的应用是公共交通运输系统的规划或网络的架设，如都市公交系统、铁路运输系统、通信网络系统等。

        现在很多汽车和手机都安装了GPS导航，用于定位和路况查询。其中路程的计算就是以最短路径的理论作为程序设计的依据，为旅行者提供不同的路径作为选择方案。

3）搜索理论

        所谓“搜索引擎”，是一种自动从因特网的众多网站中查找信息，再经过一定的整理后提供给用户进行查询的系统，例如百度、谷歌、搜狗等。

        注意，Search这个单词在网络上习惯上翻译为“搜索”，如搜索引擎。而在数据结构的算法描述中，习惯翻译成“查找”。在计算机科学中，“搜索”和“查找”大部分情况下可以互相转换。

        Pascal之父Nicklaus Wirth：“Algorithms+Data Structures=Programs”

        上面我们提到的数据结构和算法是程序设计实践中最基本的内涵。程序能否快速而高效地完成预定的任务，取决于是否选对了数据结构，而程序是否能清楚而正确地把问题解决，则取决于算法。算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。

        所以大家认为：“Algorithms + Data Structures = Programs”（出自：Pascal之父Nicklaus Wirth）

        数据结构只是静态的描述了数据元素之间的关系。

        高效的程序需要在数据结构的基础上设计和选择算法。

总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体。

数据结构的研究对象

数据间的逻辑结构

集合

        数据元素之间只有“同属于一个集合”的关系

线性关系

        数据元素之间存在一个对一个的关系，对应Java中的线性表：顺序表、链表、栈、队列

树形结构

        数据元素之间存在一个对多个的关系，对应Java中的树。比如：二叉树

网状结构(或图状结构)

        数据元素之间存在多个对多个的关系，对应Java中的图

数据的存储结构(或物理结构)

        参考书籍：数据结构与算法分析Java语言描述（第2版）[美] 卡拉罗（Carrano,F.M.） 著 金名，等 译

        大话数据结构 （作 者：程杰 著）

真实结构

        在内存中真实存在的, 用来存放多个数据的内存结构。

线性表之顺序表（或静态数据结构）：数组(Array)、ArrayList

        特点：① 使用连续分配的内存空间；②一次申请一大段连续的空间, 需要事先声明最大可能要占用的固定内存空间

        优点：设计简单，读取与修改表中任意一个元素的时间都是固定的

        缺点：① 容易造成内存的浪费；② 删除或插入数据需要移动大量的数据

        存储思路

       所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据，所有数据都紧密排布，不能有间隔

                

                                 

操作

        读内存

                 查:每个元素都有一个数值下标, 可以通过下标瞬间定位到某个元素

        写内存

                 增

                         从头部插入

                         在中间插入

                         从尾部插入

                         注意：插入元素，引起部分元素后移，代价非常高

                 删

                         注意：去掉元素，引起部分元素前移，代价非常高

                 改

                         注意：只需要修改对应位置的元素的内容，不需要申请或者删除空间

                 适用范围

                         查询操作远多于插入/删除操作的场景

                         简单抽象数据结构的基石

线性表之链表（或动态数据结构）：Linked List

        特点：① 使用不连续的内存空间；② 不需要提前声明好指定大小的内存空间。一次申请一小块内存，按需申请

        优点：① 充分节省内存空间；② 数据的插入和删除方便，不需要移动大量数据

        缺点：① 设计此数据结构较为麻烦；② 查找数据必须按顺序找到该数据为止，麻烦

        存储思路

                每一个小数据单独存在一小块内存中，这个单元被称作结点(Node)

                 每一小块内存知道下一小块的地址

                                  比如：地下党，只知道自己的下线，单线联系

                 多个不连续的小内存空间组成, 通过内存地址引用形成一个链的结构

                

      表头：程序员获得表头就可以找到链表中所有的元素

     表尾：有的链表有，有的没有

实现结构：链表

        单向链表

        环形链表

        双向链表

读写操作

        读

                 查:节点是没有下标的, 只能从链表的表头开始查找某个节点

        写

                 增

                         申请一小块内存--结点

                         插入到链中

                                  从头部插入

                                  从尾部插入

                                  从中间插入

                 删

                         从链中剥离结点

                         释放这个结点的内存

                 改

                         改变这个结点中所存储的值

                 适用范围

                         插入/删除操作远多于查询操作的场景

                         复杂抽象数据结构的基石

抽象结构(ADT)

        在内存中并不存在此结构, 由程序员利用数组/链表封装成的结构

栈(Stack)

        栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

        栈的修改原则：

                栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

超市货架上的商品，一叠书

           

名词

栈顶

        插入、删除的这一端为栈顶

栈底

        相对于栈顶的另一端

空栈

        当表中没有元素时称为空栈

特点

        继承于java.util.Vector，后进先出

实现结构

顺序表实现栈

        用数组实现

                优点：算法简单

                缺点：数组大小只能事先规划声明好，太大了浪费空间，太小了不够用

链表实现栈

                优点：随时可动态改变链表长度，有效利用内存空间

                缺点：算法设计复杂

基本运算

        进栈(压栈、入栈): push(ele)

        出栈: pop()

        查看栈顶元素: peek()

        清栈: clear()

        大小: size()

        判断是否是空:empty()

        查找元素出现位置：search(Object  obj)

使用场景

二叉树和森林的遍历

CPU的中断处理

图形的深度优先查找法(DFS)

递归调用

        斐波那契数列

        汉诺塔问题

子程序的调用

队列(Queue)

        队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。

队列的修改原则：

        队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。

                

名词

        队头(front)：允许删除的一端称为队头（Front）

        队尾(rear)：允许添加的一端称为队尾（Rear）

        空队列：当队列中没有元素时称为空队列

特点

        先进先出，典型实现：PriorityQueue

实现结构

        顺序表实现队列

                                  用数组实现

                                  优点：算法简单

                                  缺点：数组大小固定，无法根据队列实际需要动态申请

        链表实现队列

                                  优点：随时可动态改变链表长度，有效利用内存空间

                                  缺点：算法设计复杂

操作

                         加入元素到队列尾部: add(Object obj)/offer(Object obj)

                         获取队列头部元素，不删除该元素:element()/peek()

                         获取队列头部元素，并删除该元素：remove()/poll()

                         清理队列: clear()

                         得到队列的大小: size()

                         判断队列是否是空的: isEmpty()

使用场景

                         图形的广度优先查找法（BFS)

                         可用于计算机各种事件处理的模拟

                                  如: 事件队列, 消息队列

                         CPU的作业调度

变形的队列

                         环形队列

                

                         双向队列

                        

                         优先队列

                        

树(Tree)

        树：

        对大量的输入数据，链表的线性访问时间太慢，不宜使用。这里是另外一种重要的数据结构----树，其大部分时间可以保证操作的运行平均时间复杂度为O(logN)。

        例如：公司组织架构，家族族谱，Linux系统的文件和目录结构

计算机世界的树

专有名词

结点：树中的数据元素都称之为结点

根节点：最上面的结点称之为根，一颗树只有一个根且由根发展而来，从另外一个角度来说，每个结点都可以认为是其子树的根

父节点：结点的上层结点，如图中，结点K的父节点是E、结点L的父节点是G

子节点：节点的下层结点，如图中，节点E的子节点是K节点、节点G的子节点是L节点

兄弟节点：具有相同父节点的结点称为兄弟节点，图中F、G、H互为兄弟节点

结点的度数：每个结点所拥有的子树的个数称之为结点的度，如结点B的度为3

树叶：度数为0的结点，也叫作终端结点，图中D、K、F、L、H、I、J都是树叶

非终端节点（或分支节点）：树叶以外的节点，或度数不为0的节点。图中根、A、B、C、E、G都是

树的深度（或高度）：树中结点的最大层次数，图中树的深度为4

结点的层数：从根节点到树中某结点所经路径上的分支树称为该结点的层数，根节点的层数规定为1，其余结点的层数等于其父亲结点的层数+1

同代：在同一棵树中具有相同层数的节点

二叉树(Binary Tree)

二叉树：

在普通树的基础上，让一棵树中每个节点最多只能包含两个子节点，且严格区分左子节点和右子节点（位置不能换）。

                                         

分类

                     

功能

                 增删改查

                 搜索

                                  广度优先搜索

                                  深度优先搜索

                                          前序遍历：树根->左子树->右子树

                                          中序遍历：左子树->树根->右子树

                                          后序遍历：左子树->右子树->树根

特例

排序二叉树           

满足一些条件的二叉树，才被称为排序二叉树。比如：若它的左子树不为空，左子树上的所有节点值均小于根节点值；若右子树不为空，右子树上的所有节点值均大于根节点值。

特点：可以非常方便地对树中的所有节点进行排序和检索。

红黑树

红黑树顾名思义就是结点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。下图为一颗典型的二叉树：

对于一棵有效的红黑树而言我们必须增加如下规则：

1、每个结点都只能是红色或者黑色

2、根节点是黑色

3、每片叶子都是黑色的

4、如果一个结点是红色的，则它的两个子节点都是黑色的，也就是说在一条路径上不能出现相邻的两个红色结点

5、从任意一个结点到其每个叶子的所有路径都包含着相同数目的黑色结点

        这些约束强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果就是这棵树大致上是平衡的，因为插入、删除和查找某个值得最坏情况时间都要求与树的高度成比例，这个高度理论上限允许红黑树只在最坏情况下都是高效的。

        再具体就不说了，可以参看http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html，对红黑树的讲解写得非常好。

        TreeMap和TreeSet就是红黑树的典型实现。

使用场景

哈夫曼树

        一种带权路径最短的二叉树，在信息检索中很常用

哈夫曼编码

        假设需要对一个字符串如“abcdabcaba”进行编码，将它转换为唯一的二进制码，同时要求转换出来的二进制码的长度最小。我们采用哈夫曼树来解决报文编码问题。

        1. 哈夫曼编码：在数据通信中，需要将传送的文字转换成二进制的字符串，现要求为这些字母设计编码。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下，于是频率小编码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。

        2. 哈夫曼译码：在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。

B+树

图

                 定义：由“顶点”和“边”所组成的集合

                 分类

                         无向图

                         有向图

                 图的表示法

                         邻接矩阵法

                         邻接表法

                         邻接复合链表法

                         索引表格法

                 图的遍历

                         深度优先遍历

                         广度优先遍历

                 应用场景：最短路径搜索、拓扑排序

其它

                 散列表(Hash),堆(Heap)

数组：

        数组是相同数据类型的数据按顺序组成的一种引用数据类型。

        声明数组仅仅给出了元素的数据类型和数组名字，要使用数组就必须为它分配内存空间，即实例化数组。当实例化一个数组时就申请了一段连续的内存空间存储数组中的元素。

        数组中的数据是通过数组名和数组下标来操作数据的，下标从0开始下标的专业叫法：索引

用于存储同一类型数据的一个容器。

数组的常见概念

        数组本身是引用数据类型，而数组中的元素可以是任何数据类型，包括 基本数据类型和引用。

1. 创建数组对象会在内存中开辟一整块连续的空间 ，而数组名中引用的是这块连续空间的首地址 。
2. 数组长度一旦确定 ，就不能修改 。
3. 我们可以直接通过下标 (或索引 )的方式调用指定位置元素 ，速度很快 。
4. 数组的分类：

        按照维度：一维数组、二维数组、三维数组、…

        按照元素的数据类型分：基本引用数据类型元素的组 (即对 象数组 )

好处：

        可以对该容器中的数据进行编号，从0开始。数组用于封装数据，就是一个具体的实体。

        穷举法只能用于初始化数组，即必须和声明数组代码放在一条语句中完成。

核心思想：就是对角标的操作

        如何在java中表现一个数组呢？两种表现形式。

        元素类型[] 变量名 = new 元素类型[元素的个数]；

        元素类型[] 变量名 = {元素1，元素2...}；

        元素类型[] 变量名 = new 元素类型[]{元素1，元素2...}；

格式：数组名[索引]

        数组的长度属性： 每个数组都具有长度，而且是固定的，Java中赋予了数组的一个属性，可以获取到数组的长度，语句为： 数组名.length ，属性length的执行结果是数组的长度，int类型结果。由次可以推断出，数组的最大索引值为 数组名.length-1 。

public static void main(String[] args) {int[] arr = new int[]{1,2,3,4,5};//打印数组的属性，输出结果是5System.out.println(arr.length);}

数组的访问

        索引： 每一个存储到数组的元素，都会自动的拥有一个编号，从0开始，这个自动编号称为数组索引(index)，可以通过数组的索引访问到数组中的元素。

索引访问数组中的元素：

数组名[索引]=数值，为数组中的元素赋值

变量=数组名[索引]，获取出数组中的元素

public static void main(String[] args) {//定义存储int类型数组，赋值元素1，2，3，4，5int[] arr = {1,2,3,4,5};//为0索引元素赋值为6arr[0] = 6;//获取数组0索引上的元素int i = arr[0];System.out.println(i);//直接输出数组0索引元素System.out.println(arr[0]);
}

一维数组

一维数组的声明方式 ：

type var [] 或 type[] var ；
例如：
int inta[] ;
int int[] a1;
double b[];
String [] c;// 引用类型变量数组
Java 语言中声明数组时不能指定其长度(数组中元素的)，例如： int inta[5 ]; // 非法

动态初始化 ：数组声明且为元素分配空间与赋值的操作 分开进行

int[] arr= new int[3];
arr[0] = 3;
arr[1] = 9;
arr[2] = 8;

静态初始化 ：在定义数组的同时就为元素分配空间并赋值。

        int arr[] = new int[]{ 3, 9, 8}; 或 int[] arr = {3,9,8};

一维数组的使用

数组元素的引用

        定义并用运算符new为之分配空间后，才可以引用数组中的每个元素；数组元素的引用方式：数组名[数组元素下标]

1. 数组元素下标可以是整型常量或整型表达式。如a[3] , b[i] , c[6*i];
2. 数组元素下标从0开始；长度为n的数组合法下标取值范围: 0 —>n-1；如inta[]=new int[3];  可引用的数组元素为a[0]、a[1]、a[2]

每个数组都有一个属性length指明它的长度，例如：a.length指明数组a的长度(元素个数)

1. 数组一旦初始化，其长度是不可变的

数组元素的默认初始化值

        数组是引用类型，它的元素相当于类的成员变量，因此数组一经分配空间，其中的每个元素也被按照成员变量同样的方式被隐式初始化。例如：

Public class Test{Public static void main(String argv []){Int a[]=new int[5];System.out.println(a[3]);//a[3]的默认值为0}
}

对于基本数据类型而言，默认初始化值各有不同

对于引用数据类型而言，默认初始化值为null(注意与0不同！)

数组元素类型	元素默认初始值
byte	0
short	0
int	0
long	0L
float	0.0F
double	0.0
char	0 或写为:’\u0000’(表现为空)
boolean	false
引用类型	null

多维数组的使用

1. Java 语言里提供了支持多维数组的语法。
2. 如果说可以把一维数组当成几何中的线性图形，那么二维数组就相当于是一个表格，像右图Excel中的表格一样。
3. 对于二维数组的理解，我们可以看成是一维数组array1又作为另一个一维数组array2的元素而存在。其实，从数组底层的运行机制来看，其实没有多维数组。

二维数组[ ][ ]：数组中的数组

格式1（动态初始化）：int[ ][ ] arr= new int[3][2];

定义了名称为arr的二维数组 二维数组中有3个一维数组 每一个一维数组中有2个元素 一维数组的名称分别为arr[0], arr[1], arr[2] 给第一个一维数组1脚标位赋值为78写法是：arr[0][1] = 78;

格式2（动态初始化）：int[ ][ ] arr= new int[3][ ];

二维数组中有3个一维数组。 每个一维数组都是默认初始化值null (注意：区别于格式1） 可以对这个三个一维数组分别进行初始化 arr[0] = new int[3];    arr[1] = new int[1];   arr[2] = new int[2]; 注： int[ ][ ]arr= new int[ ][3];  //非法

格式3（静态初始化）：int[][]arr=new int[][]{{3,8,2},{2,7},{9,0,1,6}};

定义一个名称为arr的二维数组，二维数组中有三个一维数组 每一个一维数组中具体元素也都已初始化 第一个一维数组arr[0] = {3,8,2}; 第二个一维数组arr[1] = {2,7}; 第三个一维数组arr[2] = {9,0,1,6}; 第三个一维数组的长度表示方式：arr[2].length;

注意特殊写法情况：int[] x,y[]; x是一维数组，y是二维数组。 Java中多维数组不必都是规则矩阵形式

数组原理内存图

内存概述

        内存是计算机中的重要原件，临时存储区域，作用是运行程序。我们编写的程序是存放在硬盘中的，在硬盘中的程序是不会运行的，必须放进内存中才能运行，运行完毕后会清空内存。Java虚拟机要运行程序，必须要对内存进行空间的分配和管理

Java虚拟机的内存划分

        为了提高运算效率，就对空间进行了不同区域的划分，因为每一片区域都有特定的处理数据方式和内存管理方式。垃圾回收机制。

区域名称	作用
寄存器	给CPU使用，和我们开发无关。
本地方法栈	JVM在使用操作系统功能的时候使用，和我们开发无关。
方法区	存储可以运行的class文件。
堆内存	存储对象或者数组，new来创建的，都存储在堆内存。用于存储数组和对象，也就是实体。啥是实体啊？就是用于封装多个数据的。 1：每一个实体都有内存首地址值。 2：堆内存中的变量都有默认初始化值。因为数据类型不同，值也不一样。
方法栈	方法运行时使用的内存，比如main方法运行，进入方法栈中执行。存储的都是局部变量 ( 方法中定义的变量，方法上的参数，语句中的变量 )；只要数据运算完成所在的区域结束，该数据就会被释放

数组在内存中的存储

一个数组内存图

public static void main(String[] args) {int[] arr = new int[3];System.out.println(arr);//[I@5f150435
}

        以上方法执行，输出的结果是[I@5f150435，这个是什么呢？是数组在内存中的地址。new出来的内容，都是在堆内存中存储的，而方法中的变量arr保存的是数组的地址arr[0]，就会输出arr保存的内存地址中，数组中0索引上的元素

两个数组内存图

public static void main(String[] args) {int[] arr = new int[3];int[] arr2 = new int[2];System.out.println(arr);System.out.println(arr2);
}

两个变量指向一个数组

public static void main(String[] args) {// 定义数组，存储3个元素int[] arr = new int[3];//数组索引进行赋值arr[0] = 5;arr[1] = 6;arr[2] = 7;//输出3个索引上的元素值System.out.println(arr[0]);System.out.println(arr[1]);System.out.println(arr[2]);//定义数组变量arr2，将arr的地址赋值给arr2int[] arr2 = arr;arr2[1] = 9;System.out.println(arr[1]);
}

数组中常见的两个异常：

ArrayIndexOutOfBoundsException://当访问到数组中不存在的角标时，就会发生该异常。

NullPointerException//当引用型变量没有任何实体指向时，还在用其操作实体。就会发生该异常

//二分查找法。必须有前提：数组中的元素要有序。    

 public static int halfSeach_2(int[] arr,int key){int min, max, mid;min = 0;max = arr.length-1;mid = (max+min)>>1; //(max+min)/2;while(arr[mid]!=key){if( key > arr[mid] ){min = mid + 1;} else if ( key < arr[mid] ){max = mid - 1;}if( max < min ){return -1;}mid = (max+min)>>1;}return mid;}

Arrays工具类的使用

1	Boolean equals(int[] a,int[] b)	判断两个数组是否相等。
2	String toString(int[] a)	输出数组信息。
3	Void fill(int[] a,int val)	将指定值填充到数组之中。
4	Void sort(int[] a)	对数组进行排序。
5	Int binarySearch(int[] a,int key)	对排序后的数组进行二分法检索指定的值。

数组中涉及的常见算法

        1. 数组元素的赋值(杨辉三角、回形数等)

        2. 求数值型数组中元素的最大值、最小值、平均数、总和等

        3. 数组的复制、反转、查找(线性查找、二分法查找)

        4. 数组元素的排序算法

插入排序：

冒泡排序：

快速排序：