济南seo网站关键词排名,商融建设集团有限公司网站,打开直播,网站上的站点地图链接是这么做的一、线性表
线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列... 线性表在逻辑上是线性结构#xff0c;也就说是连续的一条直线。但是… 一、线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 二、顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
2.1接口的实现
public class SeqList {private int[] array;private int size;private static final DEFAULT_CAPACITY;// 将顺序表的底层容量设置为DEFAULT_CAPACITYSeqList(){ }//判断是否达到容量public boolean isFull();//扩容机制public void resize();// 新增元素,默认在数组最后新增public void add(int data) { }// 在 pos 位置新增元素public void add(int pos, int data) { }// 判定是否包含某个元素public boolean contains(int toFind) { return true; }// 查找某个元素对应的位置public int indexOf(int toFind) { return -1; }// 获取 pos 位置的元素public int get(int pos) { return -1; }// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) { }//判断顺序表是否为空public boolean isEmpty();//删除第一次出现的关键字keypublic void remove(int toRemove) { }// 获取顺序表长度public int size() { return 0; }// 清空顺序表public void clear() { }// 打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的public void display() { }
}
//---------------------------------------------------------------------------------------//自定义异常public class PosOutOfException extends RuntimeException2.2方法的实现
public class SeqList {//定义数组private int[] array;//有效数据private int usedsize;private static final int DEFAULT_CAPACITY5;// 默认构造方法// 将顺序表的底层容量设置为DEFAULT_CAPACITYSeqList(){this.arraynew int[DEFAULT_CAPACITY];}// 打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的public void display() {for (int i 0; i usedsize; i) {System.out.print(array[i]);}System.out.println();}//判断是否达到容量public boolean isFull(){if(usedsizeDEFAULT_CAPACITY){return false;}return true;}//扩容机制public void resize(){arrayArrays.copyOf(array,2* array.length);}// 新增元素,默认在数组最后新增public void add(int data) {if(isFull()){resize();}this.array[usedsize]data;usedsize;}// 在 pos 位置新增元素public void add(int pos, int data) {if(!Pos(pos)){throw new posOutOfException();}if(isFull()){resize();}//挪动数据for (int i this.usedsize-1; i pos; i--) {this.array[i1]this.array[i];}this.array[pos]data;this.usedsize;}// 判定是否包含某个元素public boolean contains(int toFind) {for (int i 0; i this.usedsize; i) {if(this.array[i]toFind){return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i 0; i this.usedsize; i) {if(this.array[i]toFind){return i;}}return -1;}//判断pos位置元素是否符合要求public boolean Pos(int pos){if(posthis.usedsize||pos0){return false;}return true;}// 获取 pos 位置的元素public int get(int pos) {if(Pos(pos)true){return array[pos];}throw new posOutOfException();}// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {if(!Pos(pos)){throw new posOutOfException(set数据时位置不合法);}this.array[pos]value;}//删除第一次出现的关键字keypublic void remove(int toRemove) {if(isEmpty()){return ;}int indexindexOf(toRemove);if(indexOf(toRemove)-1){return ;}else{for (int i index; i this.usedsize-1; i) {this.array[i] this.array[i1];}}this.usedsize--;}//判断顺序表是否为空public boolean isEmpty(){return this.usedsize0;}// 获取顺序表长度public int size() {return this.usedsize;}// 清空顺序表public void clear() {for (int i 0; i this.usedsize; i) {array[i]0;}//引用类型array[i]null;this.usedsize0;}
} 三、ArrayList简介
在集合框架中ArrayList是一个普通的类实现了List接口具体框架图如下 【说明】 ArrayList是以泛型方式实现的使用时必须要先实例化ArrayList实现了RandomAccess接口表明ArrayList支持随机访问ArrayList实现了Cloneable接口表明ArrayList是可以clone的ArrayList实现了Serializable接口表明ArrayList是支持序列化的和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者CopyOnWriteArrayListArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表四、ArrayList使用
4.1ArrayList的构造 4.1.1ArrayList的无参构造
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);} 查看底层源码看ArrayList的底层代码实现 再看add方法 综上分析 当调用不带参数的构造方法的时候默认数组长度为0。当第一次add的时候才会分配内存且分配内存的容量为10。4.1.2指定顺序表初始容量的构造方法
public static void main(String[] args) {ArrayListInteger listnew ArrayList(10);list.add(10);} 查看相应源码 4.1.3借助Collection构造
class People{}
class Student extends People{}
class Animal{}
public class Demo1 {public static void main(String[] args) {ArrayListStudent listnew ArrayList();ArrayListPeople list2new ArrayList(list);//list是People的子类ArrayListAnimal list3new ArrayList();ArrayListPeople list4new ArrayList(list3);}
} 构造方法小结 public static void main(String[] args) {// ArrayList创建推荐写法// 构造一个空的列表ListInteger list1 new ArrayList();// 构造一个具有10个容量的列表ListInteger list2 new ArrayList(10);list2.add(1);list2.add(2);list2.add(3);// list2.add(hello); // 编译失败ListInteger已经限定了list2中只能存储整形元素// list3构造好之后与list中的元素一致ArrayListInteger list3 new ArrayList(list2);// 避免省略类型否则任意类型的元素都可以存放使用时将是一场灾难List list4 new ArrayList();list4.add(111);list4.add(100);}
4.2ArrayList常见操作
常见方法如下 4.2.1 add(E e)方法
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);ArrayListString list2new ArrayList();list2.add(Hello );list2.add(World!);} 4.2.2 add(int index,E element)方法
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);list.add(1,20);ArrayListString list2new ArrayList();list2.add(Hello );list2.add(World!);list2.add(0,Java:);System.out.println();} 4.2.3 addAll(Collection? extends E c)方法
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);list.add(1,20);ArrayListString list2new ArrayList();list2.add(Hello );list2.add(World!);list2.add(0,Java:);ArrayListString list3new ArrayList();list3.addAll(list2);System.out.println();} 4.2.4 remove(int index)方法
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);list.add(1,20);ArrayListString list2new ArrayList();list2.add(Hello );list2.add(World!);list2.add(0,Java:);list.remove(2);list2.remove(0);System.out.println();} 4.2.5 get(int index)方法
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);list.add(1,20);ArrayListString list2new ArrayList();list2.add(Hello );list2.add(World!);list2.add(0,Java:);System.out.println(list.get(1));System.out.println(list2.get(0));//20//Java:System.out.println();}
4.2.6 set(int index,E element)方法
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);list.add(1,20);ArrayListString list2new ArrayList();list2.add(Hello );list2.add(World!);list2.add(0,Java:);list.set(1,30);list2.set(0, );System.out.println();} 4.2.7 ListE subList(int fromIndex, int toIndex)方法注意事项
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);list.add(1,20);ListInteger list2list.subList(0,2);list2.set(0,100);System.out.println();} 这里的截取并不是返回一个新的顺序表而是指向截取的范围的引用。此时发生的并不是一个拷贝。功能总结练习 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.2.8ArrayList的输出方式 通过ARrayList源码逐步查看 4.3ArrayList的遍历操作
ArrayList 可以使用三方方式遍历for循环下标、foreach、使用迭代器
4.3.1通过for循环遍历
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);list.add(1,20);System.out.println();for (int i 0; i list.size(); i) {System.out.println(list.get(i));}//10//20//150}
4.3.2通过for-each遍历 左边右边---- 右边是要进行遍历的集合 左边是集合当中元素的类型所定义的变量 public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);list.add(1,20);System.out.println();for (Integer i:list) {System.out.println(i);}//10//20//150}
4.3.3通过迭代器遍历
public static void main(String[] args) {ArrayListInteger listnew ArrayList();list.add(10);list.add(150);list.add(1,20);System.out.println();IteratorInteger itlist.iterator();//it相当于指针走一步输出一个走一步输出一个//这就是迭代器while(it.hasNext()){//如果有下一个就输出下一个System.out.println(it.next());}//10//20//150} 注意 1. ArrayList最常使用的遍历方式是for循环下标 以及 foreach 2. 迭代器是设计模式的一种后序容器接触多了再给大家铺垫 3. 4.4ArrayList的扩容机制
ArrayList是一个动态类型的顺序表即在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式
Object[] elementData; // 存放元素的空间private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; // 默认空间private static final int DEFAULT_CAPACITY 10; // 默认容量大小public boolean add(E e) {ensureCapacityInternal(size 1); // Increments modCount!!elementData[size] e;return true;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);} return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount;
// overflow-conscious codeif (minCapacity - elementData.length 0)grow(minCapacity);}private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;private void grow(int minCapacity) {
// 获取旧空间大小int oldCapacity elementData.length;
// 预计按照1.5倍方式扩容int newCapacity oldCapacity (oldCapacity 1);
// 如果用户需要扩容大小 超过 原空间1.5倍按照用户所需大小扩容if (newCapacity - minCapacity 0)newCapacity minCapacity;
// 如果需要扩容大小超过MAX_ARRAY_SIZE重新计算容量大小if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);
// 调用copyOf扩容elementData Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0抛出OutOfMemoryError异常if (minCapacity 0)throw new OutOfMemoryError();return (minCapacity MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;} 【总结】 1. 检测是否真正需要扩容如果是调用grow准备扩容 2. 预估需要库容的大小初步预估按照1.5倍大小扩容。如果用户所需大小超过预估1.5倍大小则按照用户所需大小扩容真正扩容之前检测是否能扩容成功防止太大导致扩容失败。 3. 使用copyOf进行扩容 五、ArrayList的具体使用
5.1实现洗牌算法 public class Card {//创建牌private int rank;//牌面值private String suit;//花色//构造方法set和getpublic Card() {}public Card(int rank, String suit) {this.rank rank;this.suit suit;}public int getRank() {return rank;}public void setRank(int rank) {this.rank rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit suit;}//重写toString方法public String toString(){return suit rank;}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Cards {//四种花色的字符串数组private static final String[] SUITS{♥,♠,♣,♦};public static ListCard buyCard(){//创建52张牌每个花色13张牌ListCard listnew ArrayList();for (int i0;iSUITS.length;i){for (int j 1; j 13 ; j) {Card cardnew Card(j,SUITS[i]);list.add(card);}}return list;}//实现牌组的交换public static void shuffle(ListCard list){Random outputnew Random();for (int i list.size()-1; i 0 ; i--) {int joutput.nextInt(i);//实现牌组的交换Card tmplist.get(i);list.set(i,list.get(j));list.set(j,tmp);}}public static void main(String[] args) {//置牌ListCard listbuyCard();System.out.println(list);System.out.println(洗牌);shuffle(list);System.out.println(list);System.out.println(发牌);ListCard list1new ArrayListCard();ListCard list2new ArrayList();ListCard list3new ArrayList();//ArrayList构造方法ListListCard handnew ArrayList();hand.add(list1);hand.add(list2);hand.add(list3);for (int i 0; i 14; i) {for (int j 0; j hand.size(); j) {//摸牌动作Card tmplist.remove(0);hand.get(j).add(tmp);}}System.out.println(第一个人的牌数);System.out.println(list1);System.out.println(第二个人的牌数);System.out.println(list2);System.out.println(第三个人的牌数);System.out.println(list3);}
} 六、ArrayList的问题及思考
6.1顺序表的优点
根据指定下标索引去查找元素效率非常高时间复杂度为O(1)。更新元素也很快更新指定下标的元素。时间复杂度为O(1)。
6.2顺序表的缺点
每次插入数据都需要移动元素。极端情况下如果插入到0下标那么移动的元素复杂度O(N)。每次删除数据的时候都需要移动元素。极端情况下删除0下标的元素的时间复杂度为O(N)。当容量满后进行1.5倍扩容。然后只放了一个元素此时可能会浪费空间。
6.3总结
顺序表适用于经常进行查找元素或者更新元素的场景下此时推荐使用顺序表。
