数据结构-2.顺序表

1.线性表

线性是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表有: 顺序表 , 链表 , 栈 , 队列...

线性表在逻辑上是线性结构, 也就是连续的一条直线 . 但是在物理结构上并不是连续的, 线性表在物理上存储时, 通常以数组和链式结构的形式存储.

2.顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构, 一般情况下采用数组存储. 在数组上完成数据的增删查改.

2.1接口的实现

public class MyArrayList {private int[] elem;//用来存放数据元素private int usedSize;//代表当前顺序表当中的有效数据个数private static final int DEFAULT_SIZE = 10;//顺序表的空间大小public MyArrayList() {this.elem = new int[DEFAULT_SIZE];}//自给容量public MyArrayList(int initCapacity) {this.elem = new int[initCapacity];}//判断顺序表空间是否装满了public boolean isFull() {if(this.usedSize == this.elem.length) {return true;}return false;}// 新增元素,默认在数组最后新增public void add(int data) {//进入if说明顺序表空间不足,需要扩容if(isFull()) {this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}//顺序表空间足够,还没满this.elem[this.usedSize] = data;this.usedSize++;}// 在 pos 位置新增data元素public void add(int pos, int data) {if(pos < 0 || pos > this.usedSize) {throw new RuntimeException(pos+" 位置不合法! ");//System.out.println("位置不合法! ");//return;}//顺序表空间不足if(this.isFull()) {this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}//顺序表空间足够int tmp = this.usedSize;while(tmp > pos) {this.elem[tmp] = this.elem[tmp-1];tmp--;}this.elem[pos] = data;this.usedSize++;}// 判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < this.usedSize; i++) {//如果是两个引用类型的数据判断是否相等,则用equals或者compareTo//区别就是equals的返回值是true或者false而compareTo的返回值是intif(this.elem[i] == toFind) {return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {//如果是两个引用类型的数据判断是否相等,则用equals或者compareTo//区别就是equals的返回值是true或者false而compareTo的返回值是intif(this.elem[i] == toFind) {return i;}}return -1;}// 获取 pos 位置的元素public int get(int pos) {//pos不合法checkPos(pos);//pos合法return this.elem[pos];}// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {checkPos(pos);this.elem[pos] = value;}private void checkPos(int pos) {if(pos < 0 || pos >= this.usedSize) {throw new RuntimeException(pos+" 位置不合法! ");}}//删除第一次出现的关键字keypublic void remove(int toRemove) {int index = indexOf(toRemove);if(index == -1) {System.out.println("没有这个数据! ");return;}while(index < usedSize-1) {this.elem[index] = this.elem[index+1];index++;}usedSize--;}// 获取顺序表长度public int size() {return this.usedSize;}// 清空顺序表public void clear() {this.usedSize = 0;}// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(elem[i] + " ");}System.out.println();}

温馨提示: 初学者最好自己能实现顺序表的接口,后面使用ArrayList类才不至于只知其一不知其二.

3.AraayList介绍

在集合框架中,ArrayList是一个普通的类, 实现了List接口,具体框架图如下:

说明:

1.ArrayList是以泛型方式实现的, 使用时必须要先实例化

2.ArrayList实现了RandomAccess接口, 表明ArrayList支持随机访问

3.ArrayList实现了Cloneable接口, 表明ArrayList是可以clone的

4.ArrayList实现了Serializable接口, 表明ArrayList是支持序列化的

5.和Vector不同, ArrayList不是线程安全的, 在单线程下可以使用, 在多线程下可以选择Vector或者

CopyOnWriteArrayList

6.ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表.

4.ArrayList的使用

4.1ArrayList的构造

ArrayList()无参构造很容易,就不做解释了, 其实就跟2.1中MyArryList的无参构造一样,名字一换就行了.

2.重点解释第二个构造方法.

List<Integer> list2 = new LinkedList<>();list2.add(1);list2.add(2);list2.add(3);List<Integer> list3 = new ArrayList<>(list2);list3.add(44);System.out.println(list3);

发现list3中包含list2的元素, 构造出来的新的顺序表list3包含list2中所有的元素, 这就是这种构造方法的意义所在.

4.2 ArrayList常见操作

ArrayList 虽然提供的方法比较多, 但是常用方法如下所示:

还有三个常用方法 :

int indexOf(Object o) 返回第一个o所在下标
int lastIndexOf(Object o) 返回最后一个o的下标
List<E> subList(int fromlndex, int tolndex) 截取部分list

以下是set方法和 subList方法的代码示例:

ArrayList<Integer> list1 = new ArrayList<>();list1.add(666);list1.add(321);list1.add(43);list1.add(123);list1.add(32);list1.add(55);List<Integer> list2 = list1.subList(1,4);//[1,4)list2.set(0,555);System.out.println(list2);//一般情况下,能够直接通过sout输出引用指向对象当中的内容的时候,//此时一定重写了toString方法,要么是父类,要么是自己重写了

其余方法不做代码解释, 自行实现即可

4.3ArrayList的遍历

ArrayList 可以使用三种方式遍历: for循环 + 下标, for-each , 使用迭代器.

for (int i = 0; i < list1.size(); i++) {System.out.print(list1.get(i)+ " ");}System.out.println();System.out.println("===========================");//3.for-each遍历for(Integer x : list1) {System.out.print(x + " ");}System.out.println();System.out.println("============================");//4.迭代器遍历//第一种写法:(父类)/**/Iterator<Integer> it = list1.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();//第二种写法:(子类)ListIterator<Integer> listIterator = list1.listIterator();while(listIterator.hasNext()) {System.out.print(listIterator.next() + " ");}System.out.println();System.out.println("===================================");//从后往前遍历:ListIterator<Integer> listIterator2 = list1.listIterator(list1.size());while(listIterator.hasPrevious()) {System.out.print(listIterator2.previous() + " ");}System.out.println();

注意:

1. ArrayList最长使用的遍历方式是: for循环+下标以及 foreach

2. 迭代器是设计模式的一种, 后面的文章再细说

4.4ArrayList的扩容机制

从上图可以看出,即使list的长度为1,空间已满,还是可以往里添加元素. 其中的玄机一定在add方法中.

鼠标放在add上,按住ctrl(键盘最左下),鼠标左键点过去可以看到 ↓

刚开始没add时,size = 0;

所以, minCapacity = size + 1 = 1;

补充: Java中在写AarryList时, 就定义了一个常量 DEFAULT_CAPACITY = 10; 同样的,在这里也可以发现 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA 不相信可以自查.

继续解释扩容机制:

总结:

1. 检测是否真正需要扩容, 如果是调用grow准备扩容

2. 预估需要的空间大小

初步预估按照1.5倍大小扩容

如果需要的大小超过预估的1.5倍大小,则按照所需大小扩容

3. 使用copyOf进行扩容

5.ArrayList的具体使用

5.1杨辉三角

public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();List<Integer> row = new ArrayList<>();row.add(1);ret.add(row);//上面已经处理完第一行了//下面开始处理第二行for (int i = 1; i < numRows; i++) {List<Integer> curRow = new ArrayList<>();curRow.add(1);//新的一行的第一个值//这里处理中间列//拿到上一行List<Integer> prevRow = ret.get(i-1);for (int j = 0; j < i; j++) {int x = prevRow.get(j) + prevRow.get(j-1);curRow.add(x);}curRow.add(1);//新的一行的最后一个值ret.add(curRow);}return ret;}