数组元素的删除写法：
- 无序数组
class MyArrayList{
private Object[] arr;
private int nElems;
public MyArrayList() {
arr = new Object[10];
nElems = 0;
}
//删除指定的数据元素项
public void delete(long targetData) {
int i;
for(i=0;i<nElems;i++) {
if(targetData ==arr[i]) {
break;
}
}
if(i == nElems) {
System.out.println("没有找到要删除的数据："+targetData);
}else {
for(int j=i;j<nElems;j++) {
arr[j] = arr[j+1]; //java中删除一个元素是移动下标，即把后一个移到前一个内存中
}
nElems--;
}
}
}
或
public void delete(Object obj) {
int i=find(obj);
if(i!=-1) {
System.arraycopy(arr, i+1, arr, i,nElems-1-i);
nElems--;
}
}
- 栈删除（弹出－－即不保留数据）
//出栈功能
public Object pop() {
Object object = peek();
elemData[top] = null;
this.top--;
return object;
}
数据结构和算法的概述与几个重要算法
什么是数据结构：
－－－数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。数据结构包括数据的 逻辑结构、 数据的 存储结构 以及数据的
-
数据的逻辑结构：反映数据元素之间的关系。
有集合、线性结构、树型结构、图型结构。
image.png -
数据的存储结构： 逻辑结构在计算机内存中的实现，它包括数据元素的表示和元素之间关系的表示。
有顺序存储结构（数组）、链式存储结构（链表）、索引存储结构、散列存储结构等。
image.png - 数据的运算：对数据施加的操作，这种一系列的操作就是算法。
什么是算法：
----按照某种逻辑关系组织起来的一批数据，按一定的方式把它存放在计算机的内存里，在这个基础上为了实现某个功能（比如查找某个元素，删除某个元素，给所有元素排序等等）而进行的一些列操作，我们把这一些列的操作步骤描述出来就是算法。算法也可以解释为：计算机求解一个问题所需的一系列步骤。
算法的基本特性：
1.输入：一个算法有0个或者多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身给出了初始条件；
2.输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
3.有穷性：算法必须能在执行有限个步骤之后终止；
4.确切性：算法的每一步骤必须有确切的定义；
5.可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。
算法设计的要求：
1.正确性：设计的算法能满足具体问题的需求，并且任何合法的输入都会得出正确的输出；
2.可读性：是指算法被写好之后，该算法理解的难易程度，一个算法可读性的好坏十分重要。如果一个算法比较抽象且难以理解，那么这个算法就不利于交流和推广使用，对于修改、扩展、维护来说都十分不方便，因此，在追求高效的同时，也应是算法尽简明易懂。
3.健壮性：当输入数据非法时，算法也会做出相应的判断，而不会因为输入的错误而造成瘫痪。
4.时间效率高（时间复杂度）和需要的存储空间少（空间复杂度）
时间复杂度和空间复杂度是衡量算法优劣的重要指标：
时间复杂度：是用程序执行的次数来衡量，不是程序执行的时间。
空间复杂度：用程序执行所需要的最大内存。 - 基本的数学概念
函数的定义：
给定一个数集A，假设其中的元素为x。现对A中的元素x施加对应法则f，记作f（x），得到另一数集B。假设B中的元素为y。则y与x之间的等量关系可以用y=f（x）表示。我们把这个关系式就叫函数关系式，简称函数。函数概念含有三个要素：定义域A、值域C和对应法则f。其中核心是对应法则f，它是函数关系的本质特征。
极限：
初等数学研究的对象是不变的量，高等数据研究的对象是变动的量。比如极限。“极限”是数学中的分支——微积分的基础概念，广义的“极限”是指“无限靠近而永远不能到达”的意思。极限是一种“变化状态”的描述。此变量永远趋近的值A叫做“极限值”
对数：
在数学中，对数是对求幂的逆运算，正如除法是乘法的倒数，反之亦然。如果a的x次方等于N（a>0，且a不等于1）a^x=N，那么数x叫做以a为底N的对数logarithm），记作x=logaN。其中，a叫做对数的底数，N叫做真数。
帮助大家理解时间复杂度：
场景1：给小灰一条长10寸的面包，小灰每3天吃掉1寸，那么吃掉整个面包需要几天？
答案自然是 3 X 10 = 30天。
如果面包的长度是 N 寸呢？
此时吃掉整个面包，需要 3 X n = 3n 天。
如果用一个函数来表达这个相对时间，可以记作T（n）=3n。
场景： T（n） = 3n，执行次数是线性的。
void eat1(int n){
for(int i=0; i<n; i++){;
System.out.println("等待一天");
System.out.println("等待一天");
System.out.println("吃一寸面包");
}
}
场景2：给小灰一条长16寸的面包，小灰每5天吃掉面包剩余长度的一半，第一次吃掉8寸，第二次吃掉4寸，第三次吃掉2寸......那么小灰把面包吃得只剩下1寸，需要多少天呢？
这个问题翻译一下，就是数字16不断地除以2，除几次以后的结果等于1？这里要涉及到
数学当中的对数，以2位底，16的对数，可以简写为log16。
因此，把面包吃得只剩下1寸，需要 5 X log16 = 5 X 4 = 20 天。
如果面包的长度是 N 寸呢？
需要 5 X logn = 5logn天，记作 T（n） = 5logn。
场景： T（n） = 5logn，执行次数是对数的。
void eat2(int n){
for(int i=1; i<n; i*=2){
System.out.println("等待一天");
System.out.println("等待一天");
System.out.println("等待一天");
System.out.println("等待一天");
System.out.println("吃一半面包");
}
}
场景3： 给小灰一条长10寸的面包和一个鸡腿，小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢？
答案自然是2天。因为只说是吃掉鸡腿，和10寸的面包没有关系 。
如果面包的长度是 N 寸呢？
无论面包有多长，吃掉鸡腿的时间仍然是2天，记作 T（n） = 2。
场景： T（n） = 2，执行次数是常量的。
void eat3(int n){
System.out.println("等待一天");
System.out.println("吃一个鸡腿");
}
场景4： 给小灰一条长10寸的面包，小灰吃掉第一个一寸需要1天时间，吃掉第二个一寸需要2天时间，吃掉第三个一寸需要3天时间.....每多吃一寸，所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢？
答案是从1累加到10的总和，也就是55天。
如果面包的长度是 N 寸呢？
此时吃掉整个面包，需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。记作 T（n） = 0.5n^2 + 0.5n。
场景： T（n） = 0.5n^2 + 0.5n，执行次数是一个多项式。
void eat4(int n){
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
System.out.println("等待一天");
}
System.out.println("吃一寸面包");
}
}
渐进时间复杂度::
-----有了基本操作执行次数的函数 T（n），是否就可以分析和比较一段代码的运行时间了呢？还是有一定的困难。比如算法A的相对时间是T（n）= 100n，算法B的相对时间是T（n）= 5n^2，这两个到底谁的运行时间更长一些？这就要看n的取值了。所以，这时候有了渐进时间复杂度（asymptotic time complectiy）的概念，官方的定义如下：
1.若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。
2.记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。渐进时间复杂度用大写O来表示，所以也被称为大O表达式。
我们一般情况下就是用大O表达式来表达程序的时间复杂度的，从而衡量程序那个好那个更好那个不好。
如何从基本操作执行次数推导出时间复杂度呢？有如下几个原则：
- 如果程序的运行次数和要处理的量n的大小没有关系，用常数1表示； O(1)
- 如果程序的运行次数和要处理的量n的大小有关系，只保留关系函数中的最高阶项； O(n^2)
- 如果最高阶项存在，则省去最高阶项前面的系数。 O(n^2)
让我们回头看看刚才的四个场景。
场景1：
T（n） = 3n
最高阶项为3n，省去系数3，转化的时间复杂度为：
T（n） = O（n） 大O线性阶
image.png
场景2：
T（n） = 5logn
最高阶项为5logn，省去系数5，转化的时间复杂度为：
T（n） = O（logn） 大O对数阶
image.png
场景3：
T（n） = 2
只有常数量级，转化的时间复杂度为：
T（n） = O（1） 大O常数阶
image.png
场景4：
T（n） = 0.5n^2 + 0.5n
最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：
T（n） = O（n^2） 大O平方阶
image.png
大O表达式 算法的好坏
O（1） 最好
O（logn） 比较好
O（n） 良好
O（n^2） 不好
O（n^3） 很不好
O（2^n） 很很不好
O（n！） 最不好
举一个实例：
算法A的相对时间规模是T（n）= 100n*100，时间复杂度是O(n)
算法B的相对时间规模是T（n）= 5n2，时间复杂度是O(n2)
随着输入规模 n 的增长，两种算法谁运行更快呢？
image.png
---从表格中可以看出，当n的值很小的时候，算法A的运行用时要远大于算法B；当n的值达到1000左右，算法A和算法B的运行时间已经接近；当n的值越来越大，达到十万、百万时，算法A的优势开始显现，算法B则越来越慢，差距越来越明显。
空间复杂度:
---空间复杂度和时间复杂度很类似，当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为O(n)....
----了解了判断算法好坏的两个指标：需要的内存空间（可以 理解为运行代码需要的内存空间），代码运行的时间（可以简单的理解为代码需要执行的步数）。
程序的设计中要不就是时间换空间，要不就是用空间去换时间。并且时间和空间是可以进行相互转化的
---对于执行的慢的程序，可以通过消耗内存（即构造新的数据结构）来进行优化。而消耗内存的程序，也可以多消耗时间来降低内存的消耗。
下面举个简单的例子：比如要写一个两个值互换的算法
//时间换空间
int a = 5;
int b = 10;
a = a+b;//得到a值为15
b = a-b;//得到b值为5
a = a-b;//得到a值为10
//空间换时间
int c = 5;
int d = 10;
int e = c;//得到e为5
c= d;//得到c值为10
d= e;//得到d值为
结论：
第一个a和b互换值的算法：总共进行了3次加减运算和三次赋值运算，能够把a和b的值进行互换，没有开辟多余的内存空间。
第二个c和d互换的时候，多开辟了一个内存空间存储e，但是这样只需要进行三次赋值运算就可以把c和d的值进行互换。
----所以第一个算法空间效率高，时间效率低，第二个算法空间效率低，时间效率高。我们在程序当中，请求分页，请求分段，都属于用时间去换空间。在项目当中使用各种缓存技术，都属于利用空间去换时间。
- 一些算法。
1.冒泡排序。
//实现冒泡排序
public void bubSort() {
int outer;
int inner;
for(outer = nElems-1;outer>1;outer--) {
for(inner=0;inner<outer;inner++) {
if(arr[inner] > arr[inner+1]) {
long temp = arr[inner];
arr[inner] = arr[inner+1];
arr[inner+1] =temp;
}
}
//inner = 0; //因为定义在了循环外，所以在这要初始化为0,如果在循环定义了 --for(int inner=0;...)此处不用此语句了。只是实现排序，此处不用。
}
}
2.选择排序
---实现选择排序，从小到大.设min为最小数据的位置下标，首先设min=0,每一次外循 环找出剩下元素的最小值位置。重新赋给min再让内循环从剩下的里面找最小的。
//实现选择排序，从小到大.设min为最小数据的位置下标，首先设min=0,每一次外循 环找出剩下元素的最小值位置。重新赋给min再让内循环从剩下的里面找最小的。
public void selectSort() {
int outer;
int inner;
int min;
for(outer=0;outer<nElems-1;outer++) {
min = outer;
for(inner=outer+1;inner<nElems;inner++) {
if(arr[min]>arr[inner]) {
min=inner;
}
}
long temp = arr[outer];
arr[outer] = arr[min];
arr[min] = temp;
}
}
3.插入排序法
image.png
public void insertSort() {
int outer;
int inner;
long temp;
for(outer=1;outer<nElems;outer++) {
inner = outer;
temp = arr[outer];
while(inner>0 && arr[inner-1]>temp) {
arr[inner] = arr[inner-1];
--inner;
}
arr[inner] = temp;
}
}
总结代码：
public class ArrayTest1 {
public static void main(String args[]) {
HightArray hightArray = new HightArray(100); //注意由于数组规定，最后一个素不能插入数据，所以11个空间只能装10个数据，要不然的话出现
//1 2 3 4 5 6 7 8 Exception in thread "main" 9 10 java.lang.ArrayIndexOutOfBoundsException: 10
hightArray.insert(1);
hightArray.insert(2);
hightArray.insert(3);
hightArray.insert(4);
hightArray.insert(5);
hightArray.insert(60);
hightArray.insert(7);
hightArray.insert(8);
hightArray.insert(9);
hightArray.insert(10);
hightArray.display(); //1 2 3 4 5 60 7 8 9 10
hightArray.delete(8); //删除8
System.out.println(hightArray.find(10));
//hightArray.bubSort(); //冒泡排序
//hightArray.selectSort(); //选择排序
hightArray.insertSort(); //插入排序
hightArray.display(); //1 2 3 4 5 7 9 10 60
}
}
/**
* 建一个封装数组的类，该类与主类放在一个文件中，一个文件中不能有两个public类
*/
class HightArray{
private long[] arr;
private int nElems;
public HightArray(int size) {
arr= new long[size];
nElems = 0; //当前数组的长度
}
//插入无素
public void insert(long value) {
arr[nElems] = value;
nElems++;
}
//遍历数组所有元素
public void display() {
for(int i=0;i<nElems;i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
System.out.println(arr[nElems]);
}
//查找某一个元素
public boolean find(long searchData) {
int i; //i默认为0
for(i=0;i<nElems;i++) {
if(searchData == arr[i])
break;
}
if(i == nElems) //下标从0开始，最后一个元素下标为nElems-1，若i都为nElems了，说明没有该元素了
return false;
else
return true;
}
//删除指定的数据元素项
public void delete(long targetData) {
int i;
for(i=0;i<nElems;i++) {
if(targetData ==arr[i]) {
break;
}
}
if(i == nElems) {
System.out.println("没有找到要删除的数据："+targetData);
}else {
for(int j=i;j<nElems;j++) {
arr[j] = arr[j+1]; //java中删除一个元素是移动下标，即把后一个移到前一个内存中
}
nElems--;
}
}
//实现冒泡排序,从小到大
public void bubSort() {
int outer;
int inner;
for(outer = nElems-1;outer>1;outer--) {
for(inner=0;inner<outer;inner++) {
if(arr[inner] > arr[inner+1]) {
long temp = arr[inner];
arr[inner] = arr[inner+1];
arr[inner+1] =temp;
}
}
//inner = 0;
}
}
//实现选择排序，从小到大.设min为最小数据的位置下标，首先设min=0,每一次外循 环找出剩下元素的最小值位置。重新赋给min再让内循环从剩下的里面找最小的。
public void selectSort() {
int outer;
int inner;
int min;
for(outer=0;outer<nElems-1;outer++) {
min = outer;
for(inner=outer+1;inner<nElems;inner++) {
if(arr[min]>arr[inner]) {
min=inner;
}
}
long temp = arr[outer];
arr[outer] = arr[min];
arr[min] = temp;
}
}
//插入排序,一开始定位到第二元素，且赋给temp,内循环中，判断第二个元是否比第一个元素大，大的话
public void insertSort() {
int outer;
int inner;
long temp;
for(outer=1;outer<nElems;outer++) {
inner = outer;
temp = arr[outer];
while(inner>0 && arr[inner-1]>temp) {
arr[inner] = arr[inner-1];
--inner;
}
arr[inner] = temp;
}
}
}
无序数组
---精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据结构的基本功能
①、如何插入一条新的数据项
②、如何寻找某一特定的数据项
③、如何删除某一特定的数据项
④、如何迭代的访问各个数据项，以便进行显示或其他操作
数组的特点：
---我们实际应用中为啥不用它来进行所有的数据存储呢？那肯定是有原因呢。
①、插入快，对于无序数组，上面我们实现的数组就是无序的，即元素没有按照从大到小或者某个特定的顺序排列，只是按照插入的顺序排列。无序数组增加一个元素很简单，只需要在数组末尾添加元素即可，但是有序数组却不一定了，它需要在指定的位置插入。
②、查找慢，当然如果根据下标来查找是很快的。但是通常我们都是根据元素值来查找，给定一个元素值，对于无序数组，我们需要从数组第一个元素开始遍历，直到找到那个元素。有序数组通过特定的算法查找的速度会比无需数组快，后面我们会讲各种排序算法。
③、删除慢，根据元素值删除，我们要先找到该元素所处的位置，然后将元素后面的值整体向前面移动一个位置。也需要比较多的时间。
④、数组一旦创建后，大小就固定了，不能动态扩展数组的元素个数。如果初始化你给一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面数据个数增加了又添加不进去了。
例：ArrayTest1.java
image.png
package wuxiarray;
public class ArrayTest1 {
public static void main(String args[]) {
HightArray hightArray = new HightArray(11); //注意由于数组规定，最后一个素不能插入数据，所以11个空间只能装10个数据，要不然的话出现
//1 2 3 4 5 6 7 8 Exception in thread "main" 9 10 java.lang.ArrayIndexOutOfBoundsException: 10
hightArray.insert(1);
hightArray.insert(2);
hightArray.insert(3);
hightArray.insert(4);
hightArray.insert(5);
hightArray.insert(6);
hightArray.insert(7);
hightArray.insert(8);
hightArray.insert(9);
hightArray.insert(10);
hightArray.display(); //1 2 3 4 5 6 7 8 9 10
hightArray.delete(8);
hightArray.display(); //1 2 3 4 5 6 7 9 10
}
}
/**
* 建一个封装数组的类，该类与主类放在一个文件中，一个文件中不能有两个public类
*/
class HightArray{
private long[] arr;
private int nElems;
public HightArray(int size) {
arr= new long[size];
nElems = 0; //当前数组的长度
}
//插入无素
public void insert(long value) {
arr[nElems] = value;
nElems++;
}
//遍历数组所有元素
public void display() {
for(int i=0;i<nElems;i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
//查找某一个元素
public boolean find(long searchData) {
int i; //i默认为0
for(i=0;i<nElems;i++) {
if(searchData == arr[i])
break;
}
if(i == nElems) //下标从0开始，最后一个元素下标为nElems-1，若i都为nElems了，说明没有该元素了
return false;
else
return true;
}
//删除指定的数据元素项
public void delete(long targetData) {
int i;
for(i=0;i<nElems;i++) {
if(targetData ==arr[i]) {
break;
}
}
if(i == nElems) {
System.out.println("没有找到要删除的数据："+targetData);
}else {
for(int j=i;j<nElems;j++) {
arr[j] = arr[j+1]; //java中删除一个元素是移动下标，即把后一个移到前一个内存中
}
nElems--;
}
}
//实现冒泡排序,从小到大
public void bubSort() {
int outer;
int inner;
for(outer = nElems-1;outer>1;outer--) {
for(inner=0;inner<outer;inner++) {
if(arr[inner] > arr[inner+1]) {
long temp = arr[inner];
arr[inner] = arr[inner+1];
arr[inner+1] =temp;
}
}
//inner = 0;
}
}
//实现选择排序，从小到大.设min为最小数据的位置下标，首先设min=0,每一次外循 环找出剩下元素的最小值位置。重新赋给min再让内循环从剩下的里面找最小的。
public void selectSort() {
int outer;
int inner;
int min;
for(outer=0;outer<nElems-1;outer++) {
min = outer;
for(inner=outer+1;inner<nElems;inner++) {
if(arr[min]>arr[inner]) {
min=inner;
}
}
long temp = arr[outer];
arr[outer] = arr[min];
arr[min] = temp;
}
}
//插入排序,一开始定位到第二元素，且赋给temp,内循环中，判断第二个元是否比第一个元素大，大的话
public void insertSort() {
int outer;
int inner;
long temp;
for(outer=1;outer<nElems;outer++) {
inner = outer;
temp = arr[outer];
while(inner>0 && arr[inner-1]>temp) {
arr[inner] = arr[inner-1];
--inner;
}
arr[inner] = temp;
}
}
}
有序数组和二分查找
数组优缺点分析：
- 有序数组的优点：
采用二分查找效率高，比无序数组效率高 - 有序数组的缺点：
插入的时候，要移动元素，比无序数组效率低
有序和无序数组共同缺点：
删除的时候要都要移动元素，效率低 - 有序数组二分查找的次数，数据量越大，越显得高效
数据量——比较次数 log2N = log10N*3.322
10————4
100————7
1000————10
10000————14
100000————17
1000000————20
10000000————24
100000000————27
1000000000————30
举例：一个文件中写了两个类.ArrayTest2.java-------ArrayTest2是公共类，写了一个主函数。OrderArray封装了有序数组的结构（数据和方法）
public class ArrayTest2 {
public static void main(String args[]) {
OrderArray orderArray = new OrderArray(100);
orderArray.insert(5);
orderArray.insert(7);
orderArray.insert(9);
orderArray.insert(4);
orderArray.insert(3);
orderArray.insert(55);
orderArray.insert(77);
orderArray.insert(99);
orderArray.insert(44);
orderArray.insert(38);
orderArray.insert(50);
orderArray.insert(70);
orderArray.insert(90);
orderArray.insert(40);
orderArray.insert(30);
orderArray.display(); //3 4 5 7 9 30 38 40 44 50 55 70 77 90 99
System.out.println("查找的数据在"+(orderArray.find(38)+1)+"位置");
orderArray.delete(70); //删除70
orderArray.display(); //3 4 5 7 9 30 38 40 44 50 55 77 90 99
}
}
class OrderArray {
private long[] arr;
private int nElems;
// 构选函数初始化数组，默认为0元素
public OrderArray(int maxSize) {
arr = new long[maxSize];
nElems = 0;
}
// 插入新的数据,从小到大或从大到小排，这里是从小到大的顺序
// 1.如果新插入的数据大于前面所有的数 ，直接插入到后面。
// 2.如果新。。。。小于前面的一个数据，退出循环，考滤i位置现在的数值，再用循环从数组的最后端开始查找，找到i处，把所有这段的数据往后移一位，再arr[nElems]=data
// 3.空间（arr.length<x)不足
public void insert(long data) {
int i;
for (i = 0; i < nElems; i++) {
if (arr[i] > data) {
break;
}
}
if (i < nElems) {//i在nElems范围内说明找到了最小的大于data的数据位置
for (int j = nElems; j > i; j--) {
if (j < arr.length) //当空间容量够的话，插入
arr[j] = arr[j - 1];
}
arr[i] = data;
nElems++;
} else { //没找到大小data的数据，直接插在数组的后面。
if(nElems < arr.length) arr[nElems] = data;
nElems++;
}
}
//遍历数组所有元素
public void display() {
for(int i=0;i<nElems;i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
//查找某个指定的元素，二分查找法。
//找到了我要找的数据，返回找到的数据在数组中的索引值，没找到，返回数据组的当前长度，nElems
public int find(long searchData) {
int lowerBound =0; //下标界
int upperBound = nElems-1; //上标界，下标界不可大于上连界，大于，说明没找到数据
int curint;
int count=0;
while(true) {
count++;
curint = (lowerBound+upperBound)/2;
if(arr[curint]==searchData) { //若第一个中间位置的数据就是要找的数，退出，并返回当前索引位置
return curint;
}else if(lowerBound>upperBound) { //若没找到
return nElems; //没找到数据，返回当前数组的长度
}else { //若第一个中间位置的数据不是要找到的数据，则要继续二分，查找，
if(arr[curint] > searchData) { //如果当前的数据>要查找的到数据，则放弃查找curint后面的数据，此时upperBound=curint,
upperBound = curint -1;
}else {
lowerBound = curint+1;
}
}
//System.out.println("此时总共执行了"+count+"次");
}
}
//删除指定的某一个元素
public void delete(long data) {
int i= find(data); //二分查找更方便
if(i<nElems) {
for(int j=i;j<nElems;j++) {
arr[j]=arr[j+1];
}
nElems--;
}
}
}
稀疏数组与及压缩。
---所谓稀疏数组就是数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用。因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们
---可以采用一种压缩的方式来表示稀疏数组的内容。
假设有一个97的数组，其内容如下：
image.png
在此数组中，共有63个空间，但却只使用了5个元素，造成58个元素空间的浪费。
以下我们就使用稀疏数组重新来定义这个数组：
image.png
---需要说明，第二部分的元素列数是指数组下标的列数，跟第一部分的实际列数不相同
其中在稀疏数组中第一部分所记录的是原数组的列数和行数以及元素使用的个数
第二部分所记录的是原数组中元素的位置和内容。
----经过压缩之后，原来需要声明大小为63的数组，而使用压缩后，只需要声明大小为63的数组，仅需18个存储空间。
举例：ArrayTest3.java
public class ArrayTest3 {
public static void main(String args[]) {
long[][] arr = new long[9][7]; // 7*9=63个内存单元。这样用的话，100万个元素时太浪费空间了，但是小量时还是可以的。
arr[1][1] = 3;
arr[3][0] = 1;
arr[3][1] = 4;
arr[4][2] = 7;
arr[5][5] = 5;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
// 对稀疏数组进行压缩
Node[] arr1 = new Node[6]; // 六个节点,18个单元内存，
arr1[0] = new Node(9, 7, 5); // 第一个元素节点，指明多少行，多少列，多少个元素
arr1[1] = new Node(1, 1, 3);
arr1[2] = new Node(3, 0, 1);
arr1[3] = new Node(3, 1, 4);
arr1[4] = new Node(4, 2, 7);
arr1[5] = new Node(5, 5, 5);
System.out.println("--------对压缩后的稀疏数组进行读出输出操作，要和上面数组输出一样...........");
for (int i = 0; i < arr1[0].getRow(); i++) {
for (int j = 0; j < arr1[0].getCol(); j++) {
int k;
for (k = 1; k < arr1.length; k++) {
if (arr1[k].getRow() == i && arr1[k].getCol() == j) {
break;
}
}
if (k < arr1.length)
System.out.print(arr1[k].getVal() + " ");
else
System.out.print("0 ");
}
System.out.println();
}
}
}
class Node {
private int row;
private int col;
private long val;
public Node(int row, int col, long val) {
this.row = row;
this.col = col;
this.val = val;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public long getVal() {
return val;
}
}
/*
0 0 0 0 0 0 0
0 3 0 0 0 0 0
0 0 0 0 0 0 0
1 4 0 0 0 0 0
0 0 7 0 0 0 0
0 0 0 0 0 5 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
--------对压缩后的稀疏数组进行读出输出操作，要和上面数组输出一样...........
0 0 0 0 0 0 0
0 3 0 0 0 0 0
0 0 0 0 0 0 0
1 4 0 0 0 0 0
0 0 7 0 0 0 0
0 0 0 0 0 5 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
*/
数组与集合的关系
一、数组
-----数组是java语言内置的数据类型，他是一个线性的序列，所有可以快速访问其他的元素，数组和其他语言不同，当你创建了一个数组时，他的容量是不变的，而且在生命周期也是不能改变的，还有JAVA数组会做边界检查，如果发现有越界现象，会报RuntimeException异常错误，当然检查边界会以效率为代价。
二、集合
-----JAVA还提供其他集合，list，map，set，他们处理对象的时候就好像这些对象没有自己的类型一样，而是直接归根于Object，这样只需要创建一个集合，把对象放进去，取出时转换成自己的类型就行了。
三、数组和集合的区别
1、数组是静态的，一个数组实例具有固定的大小，一旦创建了就无法改变容量了。而集合是可以动态扩展容量，可以根据需要动态改变大小。
System.arrayCopy( arr1, 2, arr2, 5, 10);意思是：将arr1数组里从索引为2的元素开始, 复制到数组arr2里的索引为5的位置, 复制的元素个数为10个.
2、数组的存放的类型只能是一种（基本类型/引用类型）, 集合存放的类型可以不是一种(不加泛型时添加的类型是Object)。
3、数组是java语言中内置的数据类型,是线性排列的,执行效率或者类型检查都是最快的。
-
List集合。
11.仿ArrayList我们自已写一个MyArrayList.
jdk自带的源码文件在：
image.png
image.png
----下面是java.util.ArrayList的一部分源代码。我们在这只是仿一下扩容的方法grow(int minCapacity),其中用到了Arrays.copyOf(数组，新容量）。注意：它用了泛型，而我写的没有泛型，只是字符串类型的。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
----
}
自写的仿ArrayList类的 MyArrayList类：
public class ArrayTest7 {
public static void main(String args[]) {
MyArrayList aList = new MyArrayList();
aList.add("1");
aList.add("2");
aList.add("3");
aList.add("4");
aList.add("5");
aList.add("6");
aList.add("7");
aList.add("8");
aList.add("9");
aList.add("10");
aList.add("11");
aList.display(); //1 2 3 4 5 6 7 8 9 10 11
aList.delete("11");
aList.display(); //1 2 3 4 5 6 7 8 9 10
}
}
class MyArrayList{
private Object[] arr;
private int nElems;
public MyArrayList() {
arr = new Object[10];
nElems = 0;
}
//实现插入数据项，注意要实现arr数组的自动扩容
public void add(Object obj) {
if(nElems ==arr.length) {
arr = Arrays.copyOf(arr, arr.length+(arr.length >> 1));
}
arr[nElems++] = obj;
}
//遍历
public void display() {
for(int i=0;i<nElems;i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
//查找指定的元素。找到了就返回元素在数组中的索引值。找不到返回-1
public int find(Object obj) {
int i;
for(i=0;i<nElems;i++) {
if(obj.equals(arr[i]))
break;
}
if(i<nElems) {
return i;
}else {
return -1;
}
}
//删除指定的元素
public void delete(Object obj) {
int i=find(obj);
if(i!=-1) {
System.arraycopy(arr, i+1, arr, i,nElems-1-i);
nElems--;
}
//不用，System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length),删除元素的方法
/*int i;
for(i=0;i<nElems;i++) {
if(obj.equals(arr[i])) {
break;
}
}
if(i == nElems) {
System.out.println("没有找到要删除的数据："+arr[i]);
}else {
for(int j=i;j<nElems;j++) {
arr[j] = arr[j+1]; //java中删除一个元素是移动下标，即把后一个移到前一个内存中
}
nElems--;
}*/
}
}
栈和队列
- 栈。
---前面我们讲解了数组，数组主要的是用来进行数据的存储，纯粹用来存储数据的数据结构。对于无序数组，插入快，但是删除和查找都很慢，对于有序数组查找很快，但是删除和插入都很慢。
这章和下章中要讲的栈和队列与数组这类纯粹用来存储数据的数据结构不太一样。
1、栈的基本概念
----栈（英语：stack）又称为 堆栈或 堆叠，栈作为一种数据结构，是一种 只能在一端进行插入和删除操作的特殊线性表。先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。
---栈也称为后进先出表。
2、java实现栈例子。
下面举例-栈是用数组实现的，内部定义了一个数组，一个表示最大容量的值以及一个指向栈顶元素的top变量。构造方法根据参数规定的容量创建一个新栈，push()方法是向栈中压入元素，指向栈顶的变量top加一，使它指向原顶端数据项上面的一个位置，并在这个位置上存储一个数据。pop()方法返回top变量指向的元素，然后将top变量减一，便移除了数据项。要知道 top 变量指向的始终是栈顶的元素。
public class StackTest1 {
public static void main(String args[]) {
LowerStack lowerStack = new LowerStack(4);
lowerStack.push(1);
lowerStack.push(2);
lowerStack.push(3);
lowerStack.push(4);
System.out.println("栈顶元素是： "+lowerStack.peek());
while(!lowerStack.isEmpty()) {
System.out.println("弹出栈元素: "+lowerStack.pop());
}
System.out.println("栈是空的吗?: "+lowerStack.isEmpty());
}
}
class LowerStack {
private long[] elemData; // 栈的内部封装的数组，用来保存栈的数据元素。
private int maxSize; // 栈的长度
private int top; // 这个变量始终指向栈顶的第一个元素的索引，栈是空栈时，默认值是-1
// 通过构造方法初始化栈
public LowerStack(int size) {
this.maxSize = size;
elemData = new long[size];
top = -1;
}
// 压栈
public void push(long data) {
// 首先判断栈还有位置否，如果top = maxSize-1,栈是满的
if (top != (maxSize - 1)) {
elemData[++top] = data;
}
}
// 出栈
public long pop() {
return elemData[top--];
}
// 读栈顶,不删除该元素。
public long peek() {
return elemData[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == (maxSize - 1));
}
}
/*栈顶元素是： 4
弹出栈元素: 4
弹出栈元素: 3
弹出栈元素: 2
弹出栈元素: 1
栈是空的吗?: true*/
产生的问题：
①、上面栈的实现初始化容量之后，后面是不能进行扩容的（虽然栈不是用来存储
大量数据的），如果说后期数据量超过初始容量之后怎么办？（自动扩容）
②、我们是用数组实现栈，在定义数组类型的时候，也就规定了存储在栈中的数据
类型，那么同一个栈能不能存储不同类型的数据呢？（声明为Object）
③、栈需要初始化容量，而且数组实现的栈元素都是连续存储的，那么能不能不初
始化容量呢？（改为由链表实现）
2，改进上面的栈。使其可以添加元素自动扩容。
public class StackTest2 {
public static void main(String args[]) {
HightStack hightStack = new HightStack();
hightStack.push(1);
hightStack.push(2);
hightStack.push(3);
hightStack.push(4);
hightStack.push(5);
hightStack.push(6);
hightStack.push(7);
hightStack.push(8);
hightStack.push(9);
hightStack.push(10);
hightStack.push(11);
hightStack.push(12);
System.out.println("栈顶元素: "+hightStack.peek());
while(!hightStack.isEmpty()) {
System.out.println(hightStack.pop());
}
System.out.println("栈是空的吗"+hightStack.isEmpty());
}
}
class HightStack{
private Object[] elemData;
private int maxSize;
private int top;
//构造方法初始化
public HightStack() {
elemData =new Object[10];
this.maxSize = 10;
top =-1; // 默认空栈top=-1
}
//压栈
public void push(Object data) {
if((top+1)==maxSize) {
//maxSize = maxSize << 1; //相当原数变大2倍
if((maxSize << 1)-Integer.MAX_VALUE >0){ //用意，不让它无限大
maxSize = Integer.MAX_VALUE; //2的31次方减速一
}else {
maxSize = maxSize <<1;
}
elemData = Arrays.copyOf(elemData,maxSize);
}
elemData[++top] = data; //为什么用先加加呢，因为我们设置的top是从-1开妈的，但下标不能为负数
}
//获取栈顶元素
public Object peek() {
if(top==-1) {
throw new EmptyStackException();
}
return elemData[top];
}
//出栈功能
public Object pop() {
Object object = peek();
elemData[top] = null;
this.top--;
return object;
}
//判断是否为空栈
public boolean isEmpty() {
return (top ==-1);
}
//判断是否为满栈
public boolean isFull() {
return top==(maxSize-1);
}
}
3， 栈的应用场景。
1.字符串倒序。
public class StackTest3 {
public static void main(String[] args) {
String s = "xiongshao wen";
char[] sa = s.toCharArray();
Stack<Character> stack =new Stack<>();
for(char c:sa) {
stack.push(c);
}
System.out.println(s);
while(!stack.isEmpty()) {
System.out.print(stack.pop());
}
}
}
//xiongshao wen
//new oahsgnoix
2.字符串特殊符号的匹配成功否。
image.png
//验证括号的匹配
public class StackTest4 {
public static void main(String[] args) {
String s = "12[a[b{c}]>";
char[] sa = s.toCharArray();
Stack<Character> stack = new Stack<>();
char ch;
boolean flag = false; //falg:最后是false,匹配有问题，
for (char c : sa) {
if (c == '<' || c == '[' || c == '{')
stack.push(c);
if (c == '>' || c == ']' || c == '}') {
ch = stack.pop();
if((ch=='<' && c=='>') || (ch=='[' && c==']') ||(ch=='{' && c=='}')) {
flag = true;
System.out.println("匹配成功！");
}else {
flag = false;
System.out.println("符号: "+ch+"与"+c+"不匹配！");
}
}
}
if(stack.isEmpty() && flag) {
System.out.println("所有特殊符号都是匹配的！");
}else {
System.out.println("特殊号匹配是有错误的。");
}
}
}
/*
匹配成功！
匹配成功！
符号: [与>不匹配！
特殊号匹配是有错误的。
*/
总结:
根据栈后进先出的特性，我们实现了单词逆序以及分隔符匹配。所以其实栈是一个概念上的工具，具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop()，使得程序不容易出错。
对于栈的实现，我们稍微分析就知道，数据入栈和出栈的时间复杂度都为O(1)，也就是说栈操作所耗的时间不依赖栈中数据项的个数，因此操作时间很短。而且需要注意的是栈不需要比较和移动操作，我们不要画蛇添足。
- 队列.
---队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行除
操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线表。
进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
---队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。
队列分为：
①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。
②、双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。
③、优先级队列（Priority Queue），优先级队列是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。
一，单向队列实现
思路：1.插入，首先判断rear+1等不等于maxSize，如果等于，说明队列头没位置插入了，则重新赋值rear=-1.否则就插入数据eleData[++rear] =data;nELems++。
2.出队，移除。首先，从第一个元素开始出队，即先进的先出。然后，如果移到maxSize-1处，即重新front=0处开始移了。
package queue;
public class QueueTest1 {
public static void main(String args[]) {
MyQueue myQueue = new MyQueue(4);
myQueue.insert(1);
myQueue.insert(2);
myQueue.insert(3);
myQueue.insert(4);
while(!myQueue.isEmpty()) {
System.out.println(myQueue.remove());
}
}
}
class MyQueue{
private Object[] eleData;
private int maxSize; //eleDate的最大长度
private int rear; //队尾指针，插入处
private int front; //队头，出队处
private int nElems; //队列中的数据元数的个数
//构造方法，初始化队列。
public MyQueue(int size) {
this.maxSize = size;
eleData = new Object[maxSize];
rear = -1;
front = 0;
nElems = 0;
}
public void insert(Object data) {
if(nElems==maxSize) {
System.out.println("队列已满了，新的数据项不能再插入了!");
}else {
if((rear+1)==maxSize)
rear = -1;
eleData[++rear] =data;
nElems++;
}
}
public Object peek() {
if(nElems ==0)
return null;
return eleData[front];
}
public Object remove() {
Object removeObj = null;
if(nElems!=0) {
removeObj = eleData[front];
eleData[front] = null;
nElems--;
if((front+1)==maxSize) {
front = 0;
}else {
front++;
}
}
return removeObj;
}
public boolean isEmpty() {
return (nElems==0);
}
public boolean isFull() {
return (nElems==maxSize);
}
//返回队列的大小
public int getSize() {
return nElems;
}
}
//1 2 3 4
二，双端队列
---双端队列就是一个两端都是结尾或者开头的队列， 队列的每一端都可以进行插入数据项和移除数据项，这些方法可以叫做：
addFirst()、addLast()、removeFirst()、removeLast()
－－－如果只用addFirst()和removeFirst() 或者 只用addLast()和removeLast()那些就是前面讲的栈，前进后出
－－－如果交叉使用addFirst()插入数据，removeLast()取数据（反正亦然）就是前面讲的普通队列，先进先出
数组双端队列实现思路：
1.和集合一样，双端队列在内部数组容量不足时，能和集合一样动态的扩容。
2.双端队列内部维护着"头部下标"、"尾部下标"。 头部下标指向的是 队列中第一位元素， 尾部下标指向的是 下一个尾部元素插入的位置。
－－－从头部下标起始，到尾部下标截止(左闭右开区间)，连续保存着队列中的全部元素。在元素出队，入队时，通过移动头尾下标，进行队列中元素的插入、删除，从而避免了类似向量中大量内部元素的整体移动。
－－－当 头部元素入队时，头部下标向左移动一位； 头部元素出队时，头部下标向右移动一位。
－－－当 尾部元素入队时，尾部下标向右移动一位； 尾部元素出队时，尾部下标向左移动一位。
3.当元素下标的移动达到了边界时，需要将数组从逻辑上看成一个环，其头尾是相邻的：
－－－下标从数组第0位时，向左移动一位，会跳转到数组的最后一位。
－－－下标从数组最后一位时，向右移动一位，会跳转到数组的第0位。
－－－下标越界时的跳转操作，在细节上是通过下标取模实现的。
image.png
队列的基本属性：
只有当队列为空（满了没空间，也会相等，但我们用了扩容－－－expand方法后，不会让其相等了）时，头部节点和尾部节点的下标才会相等。
取模计算：
在jdk的类库中的类基于数组的双端队列实现中，强制保持内部数组容量为2的n次方(初始化时容量为2的平方的平方16，每次自动扩容容量 * 2)，因此其取模运算，可以通过按位与(&)运算来加快计算速度。
取模运算在双端队列的基本接口实现中无处不在，相比jdk的双端队列实现，我们实现的双端队列实现更加原始，效率也较差。但相对的，我们的双端队列实现也较为简洁和易于理解。在理解了基础的实现思路之后，可以在这个初始版本的基础上进一步优化，然后读人家大牛的代码，你就进步了，也明白了。
取模运算中只是进行了简单的整数运算，时间复杂度为O(1)，而在jdk的双端队列实现中，使用位运算的取模效率还要更高。
扩容操作：
扩容前：
扩容后：
image.png
－－－这样扩容后，head重赋值为0，当头部插入数据时，判断0－10<0，使之可以又从最右处开始插，这样可以与原先头部插入的数据循环相连。如果是直接把原数组的数据原封不动复制到新数组中，这样不会起到首尾相连了，会出错。
QueueTest2.java::::
package queue;
// 双端队列应用
public class QueueTest2 {
public static void main(String args[]) {
//把双端队列当栈用
/*DoubleEndedQueue queue = new DoubleEndedQueue();
queue.addFirst(1);
queue.addFirst(2);
queue.addFirst(3);
System.out.println(queue.peekFirst());*/
//把双端队列当单向队列用
/*DoubleEndedQueue queue = new DoubleEndedQueue();
queue.addFirst(1);
queue.addFirst(2);
queue.addFirst(3);
System.out.println(queue.peekLast());*/
//当双端队列用，相当于两个栈用（左右）
DoubleEndedQueue queue = new DoubleEndedQueue();
queue.addFirst(1);
queue.addFirst(2);
queue.addFirst(3);
queue.addLast(4);
queue.addLast(5);
queue.addLast(6);
queue.addLast(7);
queue.addLast(8);
queue.addLast(9);
queue.addLast(10);
queue.addLast(11);
queue.addLast(12);
queue.addLast(13);
queue.addLast(14);
queue.addLast(15);
queue.addLast(16); //在此处打断点，调试step into
queue.addLast(17);
queue.addLast(18);
//不用扩容时的内存数据为:4 5 6 7 8 9 10 11 12 13 14 15 3 2 1
System.out.println(queue.peekFirst()); //3
System.out.println(queue.peekLast()); //15
System.out.println();
System.out.println();
while(!queue.isEmpty()) {
System.out.println(queue.removeFirst()); //3 2 1 4 5 6 7...15
}
}
}
//双端队列类
class DoubleEndedQueue {
private int maxSize;
private Object[] elements;
private int head;
private int tail;
public DoubleEndedQueue() {
maxSize = 16; // maxSize一定要是2的n次方，不然的话，2的n次方减1后，转成二进制后不全为1，这样在取模时不能取到想要的数
elements = new Object[16];
head = 0;
tail = 0;
}
// 取模计算，实现指针的在数组中无限的循环。
public int getMod(int index) {
if (index < 0) {
index = index + maxSize;
}
if (index >= maxSize) {
index = index - maxSize;
}
return index;
}
// 实现队列头部的插入操作,即每次从最左处插入（初始时，即head=0-1后由于小于0，使得 取模后head=maxSize-1，即）
public void addFirst(Object data) {
head = getMod(head-1); //这里不一要maxSize是2的n次方的大小
//head = (head - 1) & (maxSize - 1); //这里一定要maxSize是2的n次方的大小，因为全为1的二进制数相与了其它数会限制在它的范围之内
elements[head] = data;
if (head == tail) { //如果空间用完时
expand(); //实现扩容
}
}
// 实现尾部插入数据，首先可知尾部的下标，不像头部时那样专门处理
public void addLast(Object data) {
elements[tail] = data;
tail = getMod(tail + 1);
if (tail == head) { //如果空间用完时
expand(); //扩容
}
}
// 头部删除数据，返回被删除的对象
public Object removeFirst() {
Object removeObj = null;
if (head != tail) { // 如果不是空队列
removeObj = elements[head];
elements[head] = null;
head = getMod(head + 1);
}
return removeObj;
}
// 尾部删除
public Object removeLast() {
Object removeObj = null;
if (head != tail) {
tail = getMod(tail - 1);
removeObj = elements[tail];
elements[tail] = null;
}
return removeObj;
}
public Object peekFirst() {
if (tail != head) {
return elements[getMod(head++)];
}else {
return null;
}
}
public Object peekLast() {
if (head != tail)
return elements[getMod(tail - 1)];
else
return null;
}
//取出双端队列元素的个数
public int getSize() {
return getMod(tail-head);
}
//判断队列是否为空
public boolean isEmpty() {
return (head == tail); //为什么这样可以呢，因为有一个扩容方法，它当head==tail时就扩容改变了head与tail不相等了
}
//扩大容量，产生新的数组，把老数组的前部分放在新数组的后部，反之亦然。为什么要这样呢，因我们产生新得数组后，head重赋为0.又addFirst时，又从数组头开始插。保证与原先插入的首尾相连
public void expand() {
int newSize = maxSize << 1; //大小扩大一倍(左位移实现）
Object[] newObjArr = new Object[newSize];
int n = maxSize - head; //获取已插入数据的个数（头部插入的个数）
//获取后端插入的数据的个数==head
System.arraycopy(elements, head, newObjArr, 0, n);
System.arraycopy(elements, 0, newObjArr, n, head);
head =0;
tail=maxSize;
this.maxSize = newSize;
this.elements = newObjArr;
}
}
三，优先级队列
---优先级队列（priority queue）是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。优先级队列 是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有：
（1）查找
（2）插入一个新元素
（3）删除
insert() 方法，先检查队列中是否有数据项，如果没有，则直接插入到下标为0的单元里，否则，从数组顶部开始比较，找到比插入值小的位置进行插入，并把 nItems 加1.
remove ()方法直接获取顶部元素。
优先级队列的插入操作需要 O(N)的时间，而删除操作则需要O(1) 的时间。
image.png
image.png
public class QueueTest3 {
public static void main(String args[]) {
PriorityQueue queue = new PriorityQueue(100);
queue.insert(1);
queue.insert(100);
queue.insert(23);
System.out.println(queue.peek());//功能没问题的话，输出最小数：1
while(!queue.isEmpty()) {
System.out.println(queue.remove()); //1 23 100
}
}
}
// 优先级队列，每个元素是按大或小排列的，即每个元素都是一个级别，如 8只能插到到10与9之间。
class PriorityQueue {
private int[] elements;
private int nElms;
public PriorityQueue(int size) {
elements = new int[size];
nElms = 0;
}
public void insert(int data) {
int j;
if (nElms == 0)
elements[nElms++] = data;
else {
j=nElms-1;
while (j >= 0 && data > elements[j]) {
elements[j+1] = elements[j];
j--;
}
elements[j+1] = data;
nElms++;
}
}
public int peek() {
if(nElms !=0)
return elements[nElms-1];
else
return -1;
}
public int remove() {
int removeData=-1;
if(nElms != 0) {
removeData = elements[nElms-1];
elements[nElms-1] = -1;
nElms--;
}
return removeData;
}
public boolean isEmpty() {
return nElms==0;
}
}
队列总结:
总结
我们介绍了队列的三种形式，分别是单向队列、双向队列以及优先级队列。其实大家听名字也可以听得出来他们之间的区别，单向队列遵循先进先出的原则，而且一端只能插入，另一端只能删除。双向队列则两端都可插入和删除，如果限制双向队列的某一段的方法，则可以达到和单向队列同样的功能。最后优先级队列，则是在插入元素的时候进行了优先级别排序，在实际应用中单项队列和优先级队列使用的比较多。后面讲解了堆这种数据结构，我们会用堆来实现优先级队列，改善优先级队列插入元素的时间。
通过前面讲的栈以及本章的队列这两种数据结构，我们稍微总结一下：
①、栈、队列（单向队列）、优先级队列通常是用来简化某些程序操作的数据结构，而
不是主要作为存储数据的。
②、在这些数据结构中，只有一个数据项可以被访问。
③、栈允许在栈顶压入（插入）数据，在栈顶弹出（移除）数据，但是只能访问最后一
个插入的数据项，也就是栈顶元素。
④、队列（单向队列）只能在队尾插入数据，队头删除数据，并且只能访问对头的数
据。而且队列还可以实现循环队列，它基于数组，数组下标可以从数组末端绕回到数组的开
始位置。
⑤、优先级队列是有序的插入数据，并且只能访问当前元素中优先级别最大（或最小）
的元素。
⑥、这些数据结构都能由数组实现，但是可以用别的机制（后面讲的链表、堆等数据结
构）实现。
解析算术表达式
1、人如何解析算术表达式
如何解析算术表达式？或者换种说法，遇到某个算术表达式，我们是如何计算的：
①、求值 3+4-5
②、求值 3+4*5
2、计算机如何解析算术表达式
对于前面的表达式 3+4-5，我们人是有思维能力的，能根据操作符的位置，以及操作符的优先级别能算出该表达式的结果。 但是计算机怎么算？
先看看什么是前缀表达式，中缀表达式，后缀表达式：这三种表达式其实就是算术表达式的三种写法，以 3+4-5为例
①、前缀表达式：操作符在操作数的前面，是一种没有括号的算术表达式，例如，- 1+ 2 3，它等价于1-(2+3)
②、中缀表达式：操作符在操作数的中间，这也是人类最容易识别的算术表达式 3+4-5
③、后缀表达式：操作符在操作数的后面，是一种没有括号的算术表达式，比如例 1： 34+5-，等价于(3+4)-5，例2： 34.6 56.2 + 58 63 * + 69 -表示中缀式子为：34.6+56.2+58*63-69 例3：34.6 56.2 + 58 + 63 * 69 -等价于(34.6+56.2+58)*63-69。
人是如何解析算术表达式的，也就是解析中缀表达式，这是人最容易识别的，但是计算机不容易识别，所以我们程序员如果要写计算表达式的程序，就应该先把中缀表达式在程序内部转换为前缀或后缀表达式！ 怎么转呢？
3、以后缀表达式为例子
后缀表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。
由于后缀表达式的运算符在两个操作数的后面，那么计算机在解析后缀表达式的时候，只需要从左向右扫描，也就是只需要向前扫描，而不用回头扫描，遇到运算符就将运算符放在前面两个操作符的中间（这里先不考虑乘方类似的单目运算），一直运算到最右边的运算符，那么就得出运算结果了。这样实现的逻辑就简单了，在计算机底层的硬件实现就要简单的多了！
①、如何将中缀表达式（写代码时候写的）转换为后缀表达式
对于这个问题，转换的规则如下：
1、初始化两个栈：运算符栈s1，中间结果栈s2
2、从左到右扫描表达式
3、遇到操作数压入s2
4、遇到运算符，比较其与s1栈顶运算符的优先级
a、如果s1栈不是空的，并且栈顶元素不是“（ ” 并且优先级比栈顶元素相等或还小就弹出s1栈顶的元素，压入s2栈
b、否则，就直接压入栈s1，循环判断a
5、遇到括号
a、遇到左括号（ ，直接压入s1栈
b、遇到有括号 ），依次弹出s1栈顶的元素，压入s2栈，知道遇到左括号为止，然后将这对括号丢掉
6、重复2-5，扫描完所有表达式
7、将s1中剩余的运算符压入s2栈
②、后缀表达式的基础上实现计算
只需要从左向右扫描，遇到运算符就将运算符放在前面两个操作符的中间，一直运算到最右边的运算符，那么就得出运算结果了。
//解析算术表达式，分两步：1实现整个中缀表达式向后缀表达式转换
public class ExpressionTest1 {
public static void main(String args[]) {
String ex="34.6+56.2+58*(63-69)";
System.out.println("原始数据："+ex);
double rs =midToRear(ex);
System.out.println();
System.out.println("运算结果为："+rs);
}
/*
//实现整个中缀表达式向后缀表达式转换,input为一个书写的中缀表达式－－只显示式子
public static void midToRear(String input) {
//初始化两个栈，s1放运算符（有时进括号,不过一会儿会弹出去。s2存放中间结果
Stack<Character> s1 =new Stack<>();
Stack<Object> s2 =new Stack<>();
//扫描表达式
int len = input.length();
char c;
char tempChar; //临时存放字符（+ ,－ ,* ,/ ,(, )...）
String number; //临时存放操作数，如33.3要用字符串表示
int lastIndex = -1;
for(int i = 0;i< len;i++) {
c=input.charAt(i);
if(Character.isDigit(c)) { //如果是数字，表示我们扫描到的是一个操作数
lastIndex = getLastIndex(input,i); //获取操作数后面的符号对应在表达式中的索引值,如：“31.45+32.41*25”，当我们拿到这个数后，获取数后的‘+’或‘*’号位置
number = input.substring(i,lastIndex);
i=lastIndex-1;
System.out.print(number+" "); //ex="34.6+56.3*52-15";输出：34.6 56.3 52 15
s2.push(number);
}else if(isOperator(c)) { //如果扫描遇到的是操作符 + － * /
while(!s1.isEmpty() && s1.peek()!='(' && priorityCompare(c,s1.peek())<=0) {
System.out.print(s1.peek()+" ");
s2.push(s1.pop());
}
s1.push(c);
}else if(c=='(') { //扫描最到插号时
s1.push(c);
}else if(c==')') {
while((tempChar=s1.pop())!='(') {
System.out.print(tempChar+" ");
s2.push(tempChar);
}
}else {
//什么都不做
}
}
while(!s1.isEmpty()) { //最后把s1栈中剩下的压入到s2栈中
System.out.print(s1.peek());
tempChar = s1.pop();
s2.push(tempChar);
}
}
*/
//实现整个中缀表达式向后缀表达式转换,input为一个书写的中缀表达式.－－－并计算结果。
public static double midToRear(String input) {
//初始化两个栈，s1放运算符（有时进括号,不过一会儿会弹出去。s2存放中间结果
Stack<Character> s1 =new Stack<>();
Stack<Object> s2 =new Stack<>();
//扫描表达式
int len = input.length();
char c;
char tempChar; //临时存放字符（+ ,－ ,* ,/ ,(, )...）
Double number; //临时存放操作数，如33.3要用字符串表示
int lastIndex = -1;
System.out.print("后缀表达式： ");
for(int i = 0;i< len;i++) {
c=input.charAt(i);
if(Character.isDigit(c)) { //如果是数字，表示我们扫描到的是一个操作数
lastIndex = getLastIndex(input,i); //获取操作数后面的符号对应在表达式中的索引值,如：“31.45+32.41*25”，当我们拿到这个数后，获取数后的‘+’或‘*’号位置
number = Double.parseDouble(input.substring(i,lastIndex));
i=lastIndex-1;
System.out.print(number+" "); //ex="34.6+56.3*52-15";输出：34.6 56.3 52 15
s2.push(number);
}else if(isOperator(c)) { //如果扫描遇到的是操作符+－*/
while(!s1.isEmpty() && s1.peek()!='(' && priorityCompare(c,s1.peek())<=0) {
System.out.print(s1.peek()+" ");
// s2.push(s1.pop());
double num2 =(double)s2.pop();
double num1 = (double)s2.pop();
s2.push(cal(num1,num2,s1.pop()));
}
s1.push(c);
}else if(c=='(') { //扫描最到插号时
s1.push(c);
}else if(c==')') {
while((tempChar=s1.pop())!='(') {
System.out.print(tempChar+" ");
double num2 =(double)s2.pop();
double num1 = (double)s2.pop();
s2.push(cal(num1, num2, tempChar));
}
}else {
//什么都不做
}
}
while(!s1.isEmpty()) { //最后把s1栈中剩下的压入到s2栈中
System.out.print(s1.peek());
double num2 =(double)s2.pop();
double num1 = (double)s2.pop();
s2.push(cal(num1, num2, s1.pop()));
}
return (double) s2.pop();
}
//实现运算的方法
public static double cal(double num1,double num2,char op) {
switch (op) {
case '+':
return num1+num2;
case '-':
return num1-num2;
case '*':
return num1*num2;
case '/':
if(num2==0) throw new IllegalArgumentException("被除数不能为0！");
return num1/num2;
default:
return 0;
}
}
//定义一个优先级比较的方法，op1<和=op2:-1,0 op1>op2: 1
public static int priorityCompare(char op1,char op2) {
if(op1 == '+' || op1=='-') {
return (op2=='*' || op2=='/')? -1 : 0;
}
if(op2 == '+' || op2=='-') {
return (op1=='*' || op1=='/')? 1 : 0;
}
return 1; //默认返回1，运行中，本例中是到不了这的，但是上面全是条件语句，所以要设一个一定有返回值的语句
}
//获取操作数后面的符号对应在表达式中的索引值,如：“31.45+32.41*25”，当我们拿到这个数后，获取数后的‘+’或‘*’号位置
public static int getLastIndex(String input,int start) {
char c;
int len = input.length();
int rs=-1; //这里不赋值，下面的返回值出错The local variable rs may not have been initialized
for(int i =start;i<len;i++) {
c=input.charAt(i);
if(c=='.') {
continue;
}else if(!Character.isDigit(c)) {
rs =i;
break; //如果不为数字，也不是‘.’，那么这个数字到i这为止了，不用再找了，退出
}else if(i==len-1) {
rs=len;
}
}
return rs;
}
//判断是否为运算符
public static boolean isOperator(char c) {
if(c=='+' || c=='-' || c=='*' || c=='/') {
return true;
}else {
return false;
}
}
}
链表
－－－我们知道数组是一种通用的数据结构，能用来实现栈、队列等很多数据结构。而链表也是一种使用广泛的通用数据结构，它也可以用来作为实现栈、队列等数据结构的基础，基本上除非需要频繁的通过下标来随机访问各个数据，否则很多使用数组的地方都可以用链表来代替。
但是我们需要说明的是，链表是不能解决数据存储的所有问题的，它也有它的优点和缺点。本章我们将介绍几种常见的链表，分别是单向链表、双端链表、有序链表、双向链表以及有迭代器的链表。并且会讲解一下抽象数据类型（ADT）的思想，如何用 ADT 描述栈和队列，如何用链表代替数组来实现栈和队列。
链表（Linked List）:
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性
的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
单向链表（Single-Linked List）
----单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。链表有一个头节点。
image.png
public class SingleLinkedListTest1 {
public static void main(String args[]) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addHead("xiong");
singleLinkedList.addHead("shao");
singleLinkedList.addHead("wen");
singleLinkedList.addHead(" he ");
singleLinkedList.addHead("xu");
singleLinkedList.addHead("hui");
singleLinkedList.addHead("feng");
singleLinkedList.display();
System.out.println();
//删除一个指定的元素he
singleLinkedList.delete(" he ");
singleLinkedList.display();
}
}
//单向链表，头部法（Node next,int size）
class SingleLinkedList{
private int size; //节点类，有两部分：数据部分与指针部分
private Node head; //节点类，有两部分：数据部分与指针部分
//构造函方法，初始化链表，初时head为空。
public SingleLinkedList() {
size =0;
head = null;
}
//内部类节点类
private class Node{
private Object data;
private Node next;
public Node(Object data) {
this.data=data;
}
@Override //重写对象方法,方便测试用，Source--Generate toString
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}
}
//向链表头部添加节点对象的方法，
public Object addHead(Object data) {
Node newNode = new Node(data);
if(size ==0) {
head = newNode;
}else {
newNode.next = head;
head = newNode;
}
size++;
return newNode;
}
//实现链表头节点，删除.返回删除的结点
public Object deleteHead() {
Object obj = head.data;
head = head.next;
size--;
return obj;
}
//查找对象
public Node find(Object data) {
Node current = head; //不能改变head指针位置，因为没有删除添加了。所以不能直接用head.next来做
int tmpsize = size; //因为我们是查找元素，所以查找时不能改变链表的长度，即就用局部变理临时存一下
while(tmpsize>0) {
if(data.equals(current.data)){
return current;
}else {
current =current.next;
}
tmpsize--;
}
return null;
}
//是不是空链表
public boolean isEmpty() {
return size==0;
}
//删除指定的节点，删除成功返回ture，失败为false
/**
* 思路：从头结点开始找（while语句）对应的Object value的data数据，如是果空表，则直接返回false不往循环外面下执行
* 如果不是空链表则备份current到preious中current等于下一个节点，这样循不找，直到找到了退出循环，执行外面的删除语句
* 删除原理： 即把下一个节点等上前一个节点，再容量减一
*/
public boolean delete(Object value) {
Node current = head;
Node previous = head;
if(isEmpty()) {
return false;
}
while(!value.equals(current.data)) { //如果值等于当前节点的值，则结束循环,表示找到了要删除的
//节点,如果没有找到，或return false都会跳出此方法不执行方法中的其它代码
if(current.next == null) {
return false;
}else { //找到了，把当前节点往下一个节点移动
previous = current;
current = current.next;
}
}
//循环终止了，若还往下执行，没有返回，则证明找到了节点。实施删除
if(current == head) {
head=head.next;
size --;
}else {
previous.next = current.next;
size --;
}
return true;
}
//遍历输出所有nonde的信息数据
public void display() {
if(size>0) { //不是空链表
Node current = head;
int tempsize = size;
if(tempsize == 1) { //链表只有一个结点
System.out.print("["+head+"]");
return;
}
while(tempsize>0) {
if(current==head) {
System.out.print("["+current.data+"->");
}else {
System.out.print(current.data+"->");
}
tempsize--;
current=current.next;
}
System.out.println(); //输出一个换行符
}else {
System.out.println("[]"); //空链表
}
}
}
--------------------------------------------------------------------------------------------------------------------
[feng->hui->xu-> he ->wen->shao->xiong->
//删除一个指定的元素" he "
[feng->hui->xu->wen->shao->xiong->
单向链表实现栈
public class StackSingleLinkedList {
public static void main(String args[]) {
StackSingleLinkList singleLinkList = new StackSingleLinkList();
singleLinkList.push("A");
singleLinkList.push("B");
singleLinkList.push("C");
System.out.println("栈的所有元素先进先出：");
singleLinkList.display();
}
}
class StackSingleLinkList{
private SingleLinkedList link; //建一个链表，利用前面的例子中的单链表类
public StackSingleLinkList() {
link = new SingleLinkedList();
}
//压栈
public void push(Object data) {
link.addHead(data);
}
//弹出栈顶元素
public Object pop() {
return link.deleteHead();
}
//判断栈是不是空
public boolean isEmpty() {
return link.isEmpty();
}
//打印
public void display() {
link.display();
}
}
双端链表----不是双向链表，
对于单向链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。
public class DoubleLinkedList {
public static void main(String args[]) {
DoubleLinkList doubleLinkList = new DoubleLinkList();
doubleLinkList.addHead("A");
doubleLinkList.addHead("B");
doubleLinkList.addTail("C");
doubleLinkList.addHead("D"); // D应该在链表的最前端
doubleLinkList.display();
doubleLinkList.delete("C");
doubleLinkList.display();
}
}
class DoubleLinkList {
private int size;
private Node head; // 头指针（引用）
private Node tail; // 尾指针（引用）
// 构造方里做个变量的初始化
public DoubleLinkList() {
size = 0;
head = null;
tail = null;
}
// 内部类节点类
private class Node {
private Object data;
private Node next;
public Node(Object data) {
this.data = data;
}
@Override // 重写对象方法,方便测试用，Source--Generate toString
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}
}
// 向链表头部添加节点对象的方法，与单链表不同的是，双端链表的最初时,头结点也是尾结点
public Object addHead(Object data) {
Node newNode = new Node(data);
if (size == 0) {
head = newNode;
tail = newNode; // 链表是空时新增加的结点即是头也是尾
} else {
newNode.next = head;
head = newNode;
}
size++;
return newNode;
}
// 实现添加尾部节点
public Object addTail(Object data) {
Node newNode = new Node(data);
if (size == 0) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
size++;
return newNode;
}
// 实现链表头节点，删除，要考虑链表中只有一个结点的话，删除头节点会影响尾指针
public Object deleteHead() {
Object object = null;
if (size == 0) {
return object;
} else if (size == 1) {
object = head.data;
head = null;
tail = null;
size--;
} else {
object = head.data;
head = head.next;
size--;
}
return object;
}
// 删除指定的节点，删除成功返回ture，失败为false
/**
* 思路：从头结点开始找（while语句）对应的Object value的data数据，如是果空表，则直接返回false不往循环外面下执行
* 如果不是空链表则备份current到preious中current等于下一个节点，这样循不找，直到找到了退出循环，执行外面的删除语句
* 删除原理： 即把下一个节点等上前一个节点，再容量减一
* @param value
* @return boolean
*/
public boolean delete(Object value) {
Node current = head;
Node previous = head;
if (isEmpty()) {
return false;
}
while (!value.equals(current.data)) { // 如果值等于当前节点的值，则结束循环,表示找到了要删除的节点
if (current.next == null) {
return false;
} else { // 找到了，把当前节点往下一个节点移动
previous = current;
current = current.next;
}
}
// 循环终止了，若还往下执行，没有返回，则证明找到了节点。实施删除
if (size == 1) {
head = null;
tail = null;
} else if (current == head) {
head = head.next;
size--;
} else if (current == tail) {
previous.next = null;
tail = previous;
size--;
} else {
previous.next = current.next;
size--;
}
return true;
}
// 遍历输出所有nonde的信息数据
public void display() {
if (size > 0) { // 不是空链表
Node current = head;
int tempsize = size;
if (tempsize == 1) { // 链表只有一个结点
System.out.print("[" + head + "]");
return;
}
while (tempsize > 0) {
if (current == head) {
System.out.print("[" + current.data + "->]");
} else {
System.out.print(current.data + "->]");
}
tempsize--;
current = current.next;
}
System.out.println(); // 输出一个换行符
} else {
System.out.println("[]"); // 空链表
}
}
// 是不是空链表
public boolean isEmpty() {
return size == 0;
}
}
有序链表
前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。
在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。无序链表优于有序数组的地方是插入的速度（因为元素不需要移动），另外链表可以有效的使用内存，而数组只能局限于一个固定的大小中。
还是先看看图形化的演示！
//有序链表，这里演示只用了整数数据，
public class OrderLinkedListTest {
public static void main(String args[]) {
OrderLinkedList order = new OrderLinkedList();
order.insert(1);
order.insert(10);
order.insert(8);
order.display();
}
}
class OrderLinkedList{
private int size;
private Node head;
//内部类节点类
private class Node{
private int data;
private Node next;
public Node(int data) {
this.data=data;
next = null;
}
@Override //重写对象方法,方便测试用，Source--Generate toString
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}
}
public OrderLinkedList() {
head = null;
}
//有序链表插入
public void insert(int data) {
Node newNode= new Node(data);
Node previous = null;
Node current =head;
while(current!=null && data > current.data) { //如果找到了大的，会退出循环，而不是
previous = current;
current = current.next;
}
if(previous == null) {
head = newNode;
head.next = current;
size++;
}else {
newNode.next = current;
previous.next = newNode;
size++;
}
}
//实现链表头节点，删除.返回删除的结点
public Object deleteHead() {
Object obj = head.data;
head = head.next;
size--;
return obj;
}
//遍历输出所有nonde的信息数据
public void display() {
if(size>0) { //不是空链表
Node current = head;
int tempsize = size;
if(tempsize == 1) { //链表只有一个结点
System.out.print("["+head+"]");
return;
}
while(tempsize>0) {
if(current==head) {
System.out.print(" ["+current.data+"->");
}else if(current.next == null){
System.out.println(current.data+"]");
}else {
System.out.print(current.data+"->");
}
tempsize--;
current=current.next;
}
System.out.println(); //输出一个换行符
}else {
System.out.println("[]"); //空链表
}
}
}
有序链表和无序数组组合起来实现排序的思路
比如有一个无序数组需要排序，前面我们在讲解冒泡排序、选择排序、插入排序这三种简单的排序时，需要的时间级别都是O(N^2)。
现在我们讲解了有序链表之后，对于一个无序数组，我们先将数组元素取出，一个一个的插入到有序链表中，然后将他们从有序链表中一个一个删除，重新放入数组，那么数组就会排好序了。和插入排序一样，如果插入了N个新数据，那么进行大概N2/4次比较。但是相对于插入排序，每个元素只进行了两次排序，一次从数组到链表，一次从链表到数组，大概需要2*N次移动，而插入排序则需要N2次移动，
效率肯定是比前面讲的简单排序要高，但是缺点就是需要开辟差不多两倍的空间，而且数组和链表必须在内存中同时存在。
public class OrderArrayLinkedListTest {
public static void main(String args[]) {
OrderArrayLinkedList linkedList = new OrderArrayLinkedList();
int[] arr = new int[]{1,12,9,8,15},order;
order=linkedList.orderArray(arr);
System.out.print("{1,12,9,8,15}排序后： ");
for(int i=0;i<arr.length;i++) {
System.out.print(order[i]+" ");
}
}
}
class OrderArrayLinkedList{
private int size;
private Node head;
------------------------------------
// 返回一个数组的排序
public int[] orderArray(int[] array) {
OrderArrayLinkedList list = new OrderArrayLinkedList();
OrderArrayLinkedList list1 = new OrderArrayLinkedList(); //测试一个空指针异常
for (int i = 0; i < array.length; i++) {
list.insert(array[i]);
}
for (int i = 0; i < array.length; i++) {
try {
array[i] = list.deleteHead(); // 删除头结点时返回删除的结果元素值
}catch (Exception e) {
//e.printStackTrace();
}
}
return array;
}
---------------------------------
}
双向链表
我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历。
class DoubleWayLinkedList {
private int size;
private Node head; // 头指针（引用）
private Node tail; // 尾指针（引用）
// 内部类节点类
class Node {
private Object data;
private Node next;
private Node prev;
public Node(Object data) {
this.data = data;
next = null;
prev = null;
}
@Override // 重写对象方法,方便测试用，Source--Generate toString
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}
}
// 构造方里做个变量的初始化
public DoubleWayLinkedList() {
size = 0;
head = null;
tail = null;
}
// 向链表头部添加节点对象的方法，与单链表不同的是，双端链表的最初时,头结点也是尾结点
public Object addHead(Object data) {
Node newNode = new Node(data);
if (size == 0) {
head = newNode;
tail = newNode; // 链表是空时新增加的结点即是头也是尾
newNode.next = null;
newNode.prev = null;
} else {
newNode.next = head;
newNode.prev = null;
head.prev = newNode ;
head = newNode;
}
size++;
return newNode;
}
// 实现添加尾部节点
public Object addTail(Object data) {
Node newNode = new Node(data);
if (size == 0) {
head = newNode;
tail = newNode;
newNode.next = null;
newNode.prev = null;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
size++;
return newNode;
}
// 实现链表头节点，删除，要考虑链表中只有一个结点的话，删除头节点会影响尾指针
public Object deleteHead() {
Object object = null;
if (size == 0) {
return object;
} else if (size == 1) {
object = head.data;
head = null;
tail = null;
size--;
} else {
object = head.data;
head.prev = null;
head = head.next;
size--;
}
return object;
}
// 删除指定的节点，删除成功返回ture，失败为false
public boolean delete(Object value) {
Node current = head;
Node previous = head;
if (isEmpty()) {
return false;
}
while (!value.equals(current.data)) { // 如果值等于当前节点的值，则结束循环,表示找到了要删除的节点
if (current.next == null) {
return false;
} else { // 找到了，把当前节点往下一个节点移动
previous = current;
current = current.next;
}
}
// 循环终止了，若还往下执行，没有返回，则证明找到了节点。实施删除
if (size == 1) {
head = null;
tail = null;
} else if (current == head) {
head = head.next;
head.prev = null;
size--;
} else if (current == tail) {
previous.next = null;
tail = previous;
size--;
} else {
previous.next = current.next;
current.next.prev = previous;
size--;
}
return true;
}
// 遍历输出所有nonde的信息数据
public void display() {
if (size > 0) { // 不是空链表
Node current = head;
int tempsize = size;
if (tempsize == 1) { // 链表只有一个结点
System.out.print("[" + head + "]");
return;
}
while (tempsize > 0) {
if (current == head) {
System.out.print("" + current.data + "->");
} else {
System.out.print(current.data + "->");
}
tempsize--;
current = current.next;
}
System.out.println(); // 输出一个换行符
} else {
System.out.println("[]"); // 空链表
}
}
// 是不是空链表
public boolean isEmpty() {
return size == 0;
}
// 获取节点个数
public int getSize() {
return size;
}
}
接口抽象数据据类型
理解抽象数据类型（ADT）
①、拥有特定特征的数据项
②、在数据上有允许的操作
抽象数据类型（ADT）是指一个数学模型及定义在该模型上的一组操作。
－－－－ADT的思想可以作为我们设计工具的理念，比如我们需要存储数据，那么就从考虑需要在数据上实现的操作开始，需要存取最后一个数据项吗？还是第一个？还是特定值的项？还是特定位置的项？回答这些问题会引出ADT的定义，只有完整的定义了ADT后，才应该考虑实现的细节。
JAVA实现具有迭代器的单链表
具体的实现思路：
1、定义一个ListInterface<T>接口（相当于一个ADT），指定了单链表中的各种基本操作：
image.png
2、定义ListWithIteratorInterface<T>接口并 extends ListInterface<T>，这样就可以将迭代器与ADT类联系起来。
因为，实现ADT的类LinkListWithIterator<T> implements
ListWithIteratorInterface<T>，从而以ListWithIteratorInterface为中界，
将LinkListWithIterator（带有迭代器的ADT）与ListInterface<T>（线性表）联系起来了。
进而，使得LinkListWithIterator<T>是一个： 带有迭代器的单链表了。
这样，就可以通过①LinkListWithIterator<T>的对象调用 getIterator() 获得一个迭代
器，②而该迭代器类又是LinkListWithIterator<T>的内部类，即可以直接迭代LinkListWithIterator的数据域。由①②， LinkListWithIterator<T>就表示一个带有迭代器的单链表了。
3、定义了一个类LinkListWithIterator<T>实现了LinkListWithIterator<T>接口（相当
于ADT的实现类），LinkListWithIterator<T>中定义了一个内部类：
IteratorForLinkedList，该内部类 implements Iterator<T>
ListInterface.java 接口(双端单链表接口）
/**
*返回当前链表中元素的个数
*/
public int getSize();
//获得索引为index的元素值，注意：索引从0开始
//public T get(int index);
//返回链表中指定元素的索引，若指定元不存在，返回-1
//public int locate(T element);
//在指定索引index处添加指定的element
//public void inset(T element,int index);
/**
* 采用尾插法为链表增加新结点
*
*/
public void add(T element);
/**
* 采用头插法为链表增加新节点
*
*/
public void addAtHeader(T element);
//删除指定索引处的节点
//public T delete(int index);
//删除线性表中的最后一个元素
//public T remove();
//清空线性表
//public void clear();
}
ListWithIteratorInterface.java接口－－获取迭代器
import java.util.Iterator;
//定义获取迭代器的接口，它继承了链表接口，形成了链表迭代器接口
public interface ListWithIteratorInterface<T> extends ListInterface<T> {
public Iterator<T> getIterator();
}
LinkListWithIterator.java 实现类：双端单向链表迭代器
//实现类：双端单向链表迭代器
public class LinkListWithIterator<T> implements ListWithIteratorInterface<T> {
private Node head;
private Node tail;
private int size;
@Override
public int getSize() {
return size;
}
@Override
public void add(T data) {
Node newNode = new Node(data);
if(size ==0) {
head = newNode;
tail = newNode;
size++;
}else {
newNode.next =head;
head = newNode;
size++;
}
}
@Override
public void addAtHeader(T data) {
Node newNode = new Node(data);
if(size ==0) {
head = newNode;
tail = newNode;
size++;
}else {
tail.next = newNode;
tail = newNode;
size++;
}
}
@Override
public Iterator<T> getIterator() {
return new IteratorForLinkedList();
}
private class Node {
private T data;
private Node next;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}
}
// 又定义一个内部类，以内部类的形式来定义迭代器,两个重要方法 hasNext(),next()
private class IteratorForLinkedList implements Iterator<T> {
private Node nextNode;
public IteratorForLinkedList() {
nextNode = head;
}
@Override
public boolean hasNext() {
return nextNode != null;
}
@Override
public T next() {
if (hasNext()) {
Node rs = nextNode;
nextNode = nextNode.next;
return rs.data;
} else {
return null;
}
}
}
}
IteratorLinkedListTest.java 测试类
public class IteratorLinkedListTest {
public static void main(String args[]) {
LinkListWithIterator<Integer> link = new LinkListWithIterator<>();
link.addAtHeader(1);
link.addAtHeader(2);
link.addAtHeader(3);
Iterator<Integer> iterator = link.getIterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
高级排序
------前面我们介绍了三种简单的排序算法冒泡、选择、插入排序算法，它们的时间复杂度大O表示法都是O(N^2)，如果数据量少，我们还能忍受，但是数据量大，那么这三种简单的排序所需要的时间则是我们所不能接受的。接着我们在讲解递归的时候，介绍了归并排序，归并排序需要O(NlogN)，这比简单排序要快了很多，但是归并排序有个缺点，它需要的空间是原始数组空间的两倍，当我们需要排序的数据占据了整个内存的一半以上的空间，那么是不能使用归并排序的。
下面介绍两种高级的排序算法：希尔排序和快速排序。
- 希尔排序
①、回顾直接插入排序
希尔排序是基于直接插入排序的，它在直接插入排序中增加了一个新特性，大大的提高了插入排序的执行效率。所以在讲解希尔排序之前，我们先回顾一下直接插入排序。
public class insertSort {
public static void main(String[] args) {
int[] dat = new int[] {3,1,2,4,5,6,9,7,8};
iS(dat);
}
//插入排序，首次把第二个元与第一个元素对比，如果后一个元小于前一个元素，则把后一个元素插入到前一个元素位置，这里是降序，所以三个变量temp临时存储前一个元素
public static void iS(int[] data) {
int temp;
int inner;
int outer;
System.out.println("排序前的数组："+Arrays.toString(data));
for(outer=1;outer<data.length;outer++) {
inner=outer;
temp=data[outer];
while(inner > 0 && temp < data[inner-1]) {
data[inner]=data[inner-1];
inner--;
}
data[inner]=temp;
}
System.out.println("排序后的数组："+Arrays.toString(data));
}
}
直接插入排序存在一个效率问题，如果一个很小的数在很靠近右边的位置 ，那么想让这个很小的数插入到左边排好序的位置，那么左边排好序的数据项都必须向右移动一位，这个步骤就是将近执行了N次复制，虽然不是每个数据项都必须移动N个位置，但是每个数据项平均移动了N/2次，N个数据项总共就是NN/2次，因此插入排序的效率是O(N^2)。
②、希尔排序图解
希尔排序通过加大插入排序中元素的间隔 ，并在这些有间隔的元素中进行插入排序， 从而使数据项能够大跨度的移动 。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，最后间隔为1时，就是我们上面说的简单的直接插入排序。
③、排序间隔选取
------对于10个元素，我们选取4的间隔，那么100个数据，1000个数据，甚至更多的数据，我们应该怎么选取间隔呢？
-----希尔的原稿中，他建议间隔选为 N/2，也就是每一趟都将排序分为两半，因此对于N=100的数组，逐渐减小的间隔序列为：50,25,12，6,3,1。这个方法的好处是不需要在开始排序前为找到初始序列的间隔而计算序列，只需要用2整除N。但是这已经被证明并不是最好的序列。
-----间隔序列中的数字互质是很重要的指标，也就是说，除了1，他们没有公约数。这个约束条件使得每一趟排序更有可能保持前一趟排序已经排好的结果，而希尔最初以N/2的间隔的低效性就是没有遵守这个准则。
所以一种希尔的变形方法是用 2.2来整除每一个间隔，对于n=100的数组，会产生序列45，20，9,4,1。这比用2会整除会显著的改善排序效果。
还有一种很常用的间隔序列：在不小于len/3下 间隔序列step3 + 1，每次循环后间隔(step-1)/3
public class shellSortTest {
public static void main(String[] args) {
int[] arr = {3,2,1,7,9,10,11,4};
shellSort(arr);
}
//希尔排序
public static void shellSort(int[] data) {
System.out.println("排序前： "+Arrays.toString(data));
int outer;
int inner;
int temp;
int len = data.length;
for(int step = len/2;step>0;step=step/2) {
for(outer=step;outer<len;outer++) {
inner = outer;
temp=data[outer];
while(inner-step>=0 && temp<data[inner-step]) {
data[inner]=data[inner-step];
inner = inner-step;
}
data[inner] = temp;
}
System.out.println("间隔数为： "+step+" "+Arrays.toString(data));
}
System.out.println("排序后的数组为："+Arrays.toString(data));
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------
排序前： [3, 2, 1, 7, 9, 10, 11, 4]
间隔数为： 4 [3, 2, 1, 4, 9, 10, 11, 7]
间隔数为： 2 [1, 2, 3, 4, 9, 7, 11, 10]
间隔数为： 1 [1, 2, 3, 4, 7, 9, 10, 11]
排序后的数组为：[1, 2, 3, 4, 7, 9, 10, 11]
-
快速排序
-----快速排序是对冒泡排序的一种改进，采用的是分治策略（一般与递归结合使用），以减少排序过程中的比较次数。
①、快速排序的基本思路
一、先通过第一趟排序，将数组原地划分为两部分 ，其中一部分的所有数据都小于另一部分的所有数据 。原数组被划分为2份
二、通过递归的处理， 再对原数组分割的两部分分别划分为两部分，同样是使得其中一部分的所有数据都小于另一部分的所有数据。 这个时候原数组被划分为了4份
三、就1,2被划分后的最小单元子数组来看，它们仍然是无序的，但是！ 它们所组成的原数组却逐渐向有序的方向前进。
四、这样不断划分到最后，数组就被划分为多个由一个元素或多个相同元素组成的单元，这样数组就有序了。
image.png
把数组分割具体的实现思路： 首先选择基准元素，一般我们选取数组中第一个元素为基准元素（假设数组是随机分布的）
image.png
----如上图，我们以6为基准数，左边向右移动，右边人向左移动，每移动一位置，比较，左边小于6继续移动，右边的人移动到大于6时的继续移动，当两边都遇到不能移动时停住，他们两个位置相互交换
image.png
----这时分成了两部分，再分别左右两部分做上述移动交操作，递归直到排序成功。
image.png
//快速冒泡排序
public class AdvancedSort2 {
public static void main(String[] args) {
int[] arr = {3,2,1,7,9,10,11,4};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
//普通冒泡排序
public static void bubbleSort(int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 宏观的快速排序算法的逻辑实现，依赖递归算法应用
public static void quickSort(int[] data, int left, int right) {
//应用的递归这种思想，边界条件即为left>=right
if(left>=right) {
return;
}else {
//递归之前把数组data，分隔成两部分，前半部分所有元素都小于后半部分，前 < 基准值 > 后
int partition = partitionLR(data,left,right);
//分割后，就可以进行递归了
quickSort(data, left, partition-1);
quickSort(data, partition+1, right);
}
}
//实现具体的数组的分割功能，返回分割下标位置
private static int partitionLR(int[] data, int left, int right) {
int i = left;
int j = right+1;
int base = data[left]; //以左边第一个元素为基准数
while(true) {
while(i<right && data[++i]<base) {
}
while(j>left && data[--j]>base) {
}
if(i>=j) {
break;
}else {
swap(data, i, j);
}
}
swap(data, left, j);
return j;
}
//数组元素交换方法
public static void swap(int[] data,int i,int j) {
int temp;
temp = data[i];
data[i]= data[j];
data[j]= temp;
}
}
