慈溪网站建设报价,网站维护和推广,晋江建设银行招聘网站,哈尔滨小程序开发制作公司1. 线性表
线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列… 线性表在逻辑上是线性结构#xff0c;也就说是连续的一条直线。但是在…1. 线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。
2. 顺序表
顺序表是一段物理空间连续的线性表,在底层一般使用数组来实现,在数组的基础上完成增删查改.下面是顺序表的一些接口.
2.1 接口
public interface Ilist {void add(int data);//为顺序表的尾部增加元素void add(int data ,int pos);//为指定位置添加元素void display();//打印顺序表int size ();//检测顺序表中元素的个数boolean contains(int toFind);//检测顺序表中是否包含该元素int indexOf(int toFind);//返回所要寻找第一个元素的下标int get(int index);//获取指定下标的元素void set(int index,int val);//把指定下标的元素指定为指定元素void remove(int toRomve);//移除第一个指定的元素void clear();//清空顺序表
}
下面我们来实现这些接口:
import java.util.Arrays;/*** 顺序表底层是用数组来实现的*/
public class MyArrayList implements Ilist {private int[] elem;private int size;//记录有效数据public static final int DEFAULT_CAPACITY 5;//默认容量private boolean isFull(){return size elem.length;//判断顺序表的容量是否为满}private void checkPos(int pos){if (pos 0 || pos size){throw new PosException(pos is false);//判断插入位置是否合法}}private boolean isEmpty(){return this.size 0;}public MyArrayList() {this.elem new int[DEFAULT_CAPACITY];//默认容量为5this.size 0;}//无参数的构造方法public void add(int data){//在末尾的位置添加元素if (isFull()){elem Arrays.copyOf(elem,elem.length*2);//扩容}elem [size] data;size;}public void add(int data ,int pos){//在指定位置添加元素checkPos(pos);if (isFull()){elem Arrays.copyOf(elem,elem.length*2);//扩容}for (int i size-1; i pos ; i--) {//数组整体后移elem [i1] elem [i];}elem[pos] data;size;}public void display(){//打印顺序表System.out.print([ );for (int i 0; i size; i) {//打印有效元素System.out.print(elem[i] );}System.out.print(]);}public int size (){//返回当前顺序表大小return this.size;}public boolean contains(int toFind){for (int i 0; i size; i) {//在这里不可以用elem.length,后面的扩容之后未赋值if(elem[i] toFind){return true;}}return false;}public int indexOf(int toFind){//返回要找的元素第一个返回的下标for (int i 0; i size; i) {//在这里不可以用elem.length,后面的扩容之后未赋值if(elem[i] toFind){return i;}}return -1;}public int get(int index){//获取index位置的值checkPos(index);if (isEmpty()){//存在默认容量5,若没有此方法,可能会在未初始化的位置上直接获取元素,获取成功//但是为0,不符合实际throw new EmptyException(array is empty);}return elem[index];}public void set(int index,int val){//把index位置的值改为valcheckPos(index);if (isEmpty()){//存在默认容量5,若没有此方法,可能会在未初始化的位置上直接添加元素,//添加成功,但是不符合实际throw new EmptyException(array is empty);}elem[index] val;}public void remove(int toRomve){//移除第一次出现的元素if (isEmpty()){throw new EmptyException(array is empty);}int index indexOf(toRomve);//先找到下标的位置for (int i index1; i size; i) {elem[i-1] elem[i];}elem[size-1] 0;size --;}public void clear(){size 0;}
}java
public class EmptyException extends NullPointerException{public EmptyException(String s) {super(s);}
}
public class PosException extends ArrayIndexOutOfBoundsException{public PosException(String s) {super(s);}
}
下面通过一些测试用例;来测试:
public class Main {public static void main(String[] args) {MyArrayList list new MyArrayList();list.add(0);list.add(1);list.add(3);list.add(4);list.add(2,2);list.add(5);list.display();System.out.println(list.size());list.remove(2);list.display();System.out.println(list.size());}
}3.ArrayList简介 [说明]
ArrayList是以泛型的方式实现的,使用时必须先实例化.ArrayList的底层是一段连续的存储空间,并且可以动态扩容,是一个动态类型的顺序表.
4.ArrayList的使用
4.1 ArrayList的构造方法
方法解释public ArrayList()无参构造方法public ArrayList(int initialCapacity)指定顺序表初始容量public ArrayList(Collection? extends E c)利用Collection中的容器来构造
关于第三个构造方法,不太好理解,我们下面来解释一下:ArrayList已经传入了泛型的参数,就是E,这里用来构造ArrayList的Collection类中的元素必须是E的子类.
ArrayListInteger list new ArrayList();
ArrayListInteger list1 new ArrayList(list);
ArrayListNumber list2 new ArrayList(list);
ArrayListInteger list3 new ArrayList(10);4.2 ArrayList常见操作
方法解释boolean add(E e)在尾部添加元素void add(int index,E element)在指定位置添加元素boolean addAll(Collection? extends E c)把c中的元素全部添加到顺序表尾部E remove(int index)移除指定位置的元素boolean remove(Object o)移除遇到的第一个元素oE get(int index)获取指定位置的元素E set(int index,E element)把指定位置的元素设置为指定的值void clear()清空顺序表boolean contains(Object o)检测顺序表中是否包含oint indexOf(Object o)返回第一个指定元素所在的下标int lastIndexOf(Object o)从后向前找,返回第一个元素所在的下标List subList(int fromIndex,int toIndex)截取指定范围的字符串,左闭右开
在这里说明一下两个remove方法的区别,避免混淆,第一个remove方法时移除指定位置的元素,传入的元素类型为int类型的数据,而第二个remove方法移除的是第一个遇到的元素,这里传入的参数类型是和顺序表泛型相同的类型,当一个顺序表中存储的是Integer类型的数据的时候,要注意区分下标和元素. 下面对上述方法进行演示:
public static void main(String[] args) {ListString list new ArrayList();list.add(JavaSE);list.add(JavaWeb);list.add(JavaEE);list.add(JVM);list.add(测试课程);System.out.println(list);// 获取list中有效元素个数System.out.println(list.size());// 获取和设置index位置上的元素注意index必须介于[0, size)间System.out.println(list.get(1));list.set(1, JavaWEB);System.out.println(list.get(1));// 在list的index位置插入指定元素index及后续的元素统一往后搬移一个位置list.add(1, Java数据结构);System.out.println(list);// 删除指定元素找到了就删除该元素之后的元素统一往前搬移一个位置list.remove(JVM);System.out.println(list);// 删除list中index位置上的元素注意index不要超过list中有效元素个数,否则会抛出下标越界异常list.remove(list.size()-1);System.out.println(list);// 检测list中是否包含指定元素包含返回true否则返回falseif(list.contains(测试课程)){list.add(测试课程);}// 查找指定元素第一次出现的位置indexOf从前往后找lastIndexOf从后往前找list.add(JavaSE);System.out.println(list.indexOf(JavaSE));System.out.println(list.lastIndexOf(JavaSE));// 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组ListString ret list.subList(0, 4);System.out.println(ret);list.clear();System.out.println(list.size());
}4.3 ArrayList的遍历
ArrayList有四种遍历方式,一种是通过sout直接输出,一种是for-i,一种是for-each,一种是使用迭代器.
import java.util.ArrayList;
import java.util.Iterator;
public class TestArrayList {public static void main(String[] args) {ArrayListInteger list new ArrayList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);//通过sout去遍历ArrayListSystem.out.println(list);//通过fori遍历for (int i 0; i list.size(); i) {System.out.print(list.get(i) );}System.out.println();//通过foreach遍历for (int x:list) {System.out.print(x );}System.out.println();//通过迭代器遍历IteratorInteger iterator list.iterator();while (iterator.hasNext()){System.out.print(iterator.next() );}System.out.println();}
}
4.4 ArrayList扩容机制
ArrayList是动态的顺序表,在顺序表的容量不够的时候会自动扩容,下面是底层代码对ArrayList的扩容机制. public boolean add(E e) {modCount;//底层是C/C代码add(e, elementData, size);//调用另一个重载的add方法,指定添加容积return true;}private void add(E e, Object[] elementData, int s) {if (s elementData.length)//容器满的时候需要扩容elementData grow();//调用grow方法扩容elementData[s] e;size s 1;}private Object[] grow() {return grow(size 1);//最小容积是size1,就是指定的添加容积1}private Object[] grow(int minCapacity) {//传入指定的最小容积int oldCapacity elementData.length;if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity ArraysSupport.newLength(oldCapacity,//对数组扩容minCapacity - oldCapacity, /* minimum growth */ //计算原容量和最小容积的差值oldCapacity 1 //原容量的一半 /* preferred growth */);return elementData Arrays.copyOf(elementData, newCapacity);//正式扩容} else {return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}public static int newLength(int oldLength, int minGrowth, int prefGrowth) {// preconditions not checked because of inlining// assert oldLength 0// assert minGrowth 0int prefLength oldLength Math.max(minGrowth, prefGrowth); // might overflow//若pre大,1.5被扩容,若是min大,直接加上指定的最小容积if (0 prefLength prefLength SOFT_MAX_ARRAY_LENGTH) {return prefLength;} else {// put code cold in a separate methodreturn hugeLength(oldLength, minGrowth);}}[总结]
预估要扩容的大小
初步预估按照1.5倍扩容.如果用户所需大小预估超过1.5,则按照用户所需大小扩容.
使用copyOf扩容.
