北京做网站比较有名的公司有哪些,珠海做网站哪家专业,中裕隆建设有限公司网站,自己做的美食在哪个网站上卖顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构#xff0c;一般情况下采用数组存储。在数组上完成数据的增删查改。在物理和逻辑上都是连续的。
模拟实现
下面是我们要自己模拟实现的方法#xff1a; 首先我们要创建一个顺序表#xff0c;顺序表…顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。在物理和逻辑上都是连续的。
模拟实现
下面是我们要自己模拟实现的方法 首先我们要创建一个顺序表顺序表包含一个数组一个由于计数的计数器还有一个默认的初始容量我这里定义初始容量为5比较好判断扩容是否成功。这里以整型数组为例 private int[] array;private int usedSize;//目前数据总数private static final int DEFAULT_CAPACITY 5;//默认容量默认构造方法
这里我们直接在构造方法里给数组进行初始化 public MyArrayList() {array new int[DEFAULT_CAPACITY];}尾插
尾插是指直接在所有数据的后面插入新数据这里我们要注意数组容量是否已满所以我们先写一个isFull方法判断数组是否容量已满 private boolean isFull() {if(usedSize array.length) {return true;}return false;}这个方法设置成private是因为这个方法只是给本类的方法提供的不需要对外公开。 如果数组已满那么我们就需要扩容这里我扩容2倍 private void grow() {array Arrays.copyOf(array,array.length * 2);}现在来写尾插代码 public void add(int data) {//判满if(isFull()) {grow();}//插入数据array[usedSize] data;}pos位置插入数据
首先我们要先检查pos位置是否合法如果不合法的话就不用进行插入操作直接抛出异常我们先写异常代码
public class PosException extends RuntimeException{public PosException(String message) {super(message);}
}检查pos位置是否合法 private void checkPosInAdd(int pos) throws PosException {if(pos 0 || pos usedSize) {throw new PosException(pos位置不合法);}}现在写插入代码首先判断pos是否合法然后判断是否要扩容最后我们进行插入操作即可在插入代码中我们使用try-catch来处理异常。 public void add(int pos,int data) {try{checkPosInAdd(pos);//检查位置是否合法if(isFull()) { //判满grow();}//移动数据for (int i usedSize; i pos ; i--) {array[i1] array[i];}//插入数据array[pos] data;usedSize;}catch (PosException e) {System.out.println(pos位置不合法);e.printStackTrace();}}contains
是否包含某个元素使用布尔值进行返回这里直接遍历数组查找即可。 public boolean contains(int toFind) {for (int i 0; i usedSize; i) {if(array[i] toFind){return true;}}return false;}indexOf
查找某个元素的下标找到则返回该元素的下标没有找到则返回 -1 public int indexOf(int toFind) {for (int i 0; i usedSize; i) {if(array[i] toFind) {return i;}}return -1;}get
找到pos位置的元素这里要注意先判断pos是否合法,但是这里的检查pos和上面我们写过的checkPosInAdd是不一样的这里的pos必须是有元素的下标范围也就是不包含usedSize这个下标因为这个是没有有效数据的是待插入的空位所以我们要再写一个检查pos方法 private void checkPosInFind(int pos) throws PosException {if(pos 0 || pos usedSize) {throw new PosException(pos位置不合法);}}public int get(int pos) {try{checkPosInFind(pos);return array[pos];}catch (PosException e) {System.out.println(pos位置不合法);e.printStackTrace();}return -1;}set
更新pos位置的数据还是要判断pos位置是否合法这里使用发判断方法应该为checkPosInFind public void set(int pos, int data) {try{checkPosInFind(pos);array[pos] data;}catch (PosException e) {System.out.println(pos位置不合法);e.printStackTrace();}}remove
删除第一次出现的关键字key public void remove(int key) {for (int i 0; i usedSize; i) {if(array[i] key) {for (int j i; j usedSize - 1; j) {array[j] array[j1];}usedSize--;return;}}}size
获取顺序表的长度,这里直接返回usedSize即可 public int size() {return usedSize;}display
打印顺序表该方法是便于测试真正的顺序表并没有这个方法 public void display() {for (int i 0; i usedSize; i) {System.out.print(array[i] );}System.out.println();}clear
清空顺序表直接将usedSize赋值为0即可下次使用的时候会直接覆盖之前的数据的。 public void clear() {usedSize 0;}完整代码
import java.util.Arrays;public class MyArrayList {private int[] array;private int usedSize;//目前数据总数private static final int DEFAULT_CAPACITY 5;//默认容量public MyArrayList() {array new int[DEFAULT_CAPACITY];}/*判满满则返回true,否则返回false*/private boolean isFull() {if(usedSize array.length) {return true;}return false;}//扩容 2倍扩容private void grow() {array Arrays.copyOf(array,array.length * 2);}//尾插public void add(int data) {//判满if(isFull()) {grow();}//插入数据array[usedSize] data;}//判断pos是否合法/*不合法则抛出异常增加方法*/private void checkPosInAdd(int pos) throws PosException {if(pos 0 || pos usedSize) {throw new PosException(pos位置不合法);}}//指定pos位置插入数据public void add(int pos,int data) {try{checkPosInAdd(pos);//检查位置是否合法if(isFull()) { //判满grow();}//移动数据for (int i usedSize; i pos ; i--) {array[i1] array[i];}//插入数据array[pos] data;usedSize;}catch (PosException e) {System.out.println(pos位置不合法);e.printStackTrace();}}//是否包含某个元素public boolean contains(int toFind) {for (int i 0; i usedSize; i) {if(array[i] toFind){return true;}}return false;}//查找某个元素的下标public int indexOf(int toFind) {for (int i 0; i usedSize; i) {if(array[i] toFind) {return i;}}return -1;}//判断pos是否合法/*查找方法不合法则抛出异常*/private void checkPosInFind(int pos) throws PosException {if(pos 0 || pos usedSize) {throw new PosException(pos位置不合法);}}//获取pos位置的元素public int get(int pos) {try{checkPosInFind(pos);return array[pos];}catch (PosException e) {System.out.println(pos位置不合法);e.printStackTrace();}return -1;}//更新pos位置的数据public void set(int pos, int data) {try{checkPosInFind(pos);array[pos] data;}catch (PosException e) {System.out.println(pos位置不合法);e.printStackTrace();}}//删除第一次出现的关键字keypublic void remove(int key) {for (int i 0; i usedSize; i) {if(array[i] key) {for (int j i; j usedSize - 1; j) {array[j] array[j1];}usedSize--;return;}}}//获取顺序表的长度public int size() {return usedSize;}//打印顺序表该方法是便于测试真正的顺序表并没有这个方法public void display() {for (int i 0; i usedSize; i) {System.out.print(array[i] );}System.out.println();}//清空顺序表public void clear() {usedSize 0;}
}ArrayList 的使用
Java已经封装好顺序表供我们使用就是ArrayList现在我们来列举其中的常用的方法。
方法解释boolean add(E e)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection? extends E c)尾插 c 中的元素E remove(int index)删除index位置元素boolean remove(Object o)删除遇到的第一个oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 元素设置为 elementvoid clear()清空boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标
更多详细的方法可自行查阅官方文档
上面很多方法是我们自己模拟实现过的这里就不一一举例演示。
ArrayList 的成员方法 ArrayList 构造方法
一共提供了三个构造方法
方法解释ArrayList()无参构造ArrayList(Collection? extends E c)利用其他 Colletion 构建 ArrayListArrayList(int initialCapacity)指定顺序表初始容量
ArrayList(int initialCapacity)指定顺序表初始容量看一下源码还是很好理解的初始容量大于零就开辟一块连续的空间等于零就给一个空数组小于零则抛出异常。 首先要知道下面的关系图
从上图我们可以得知ArrayList是包含Collection这个接口的所以可以接收Colletion的参数Colletion后面的? extends E 中的 是通配符后面的文章会提到。 我们重点是看无参的构造方法 直接赋值一个空数组大家来看一下下面的代码明明是空数组但是为什么可以直接add而不会报错呢 public static void main(String[] args) {ArrayListInteger list new ArrayList();list.add(10);list.add(20);System.out.println(list);}我们点过去看看源码是什么 到了这里大家应该明白了在使用add的时候我们看到源码里写了当 s 数组长度的时候Java底层会帮我们自动扩容。
ArrayList 实例化
我们经常使用List或者ArrayList来接收顺序表实例化的对象. ListInteger list new ArrayList();ArrayListInteger list2 new ArrayList();由于List是ArrayList的接口,所以可以接收,但是注意List是接口意味着不能进行实例化,使用List接收的参数只能使用List有点方法,由于ArrayList有很多接口,一定是拓展了很多东西的,如果List接口没有包含的方法,使用List接收的参数不能调用其他方法,但是使用ArrayList接收的话,所有ArrayList实现的方法都是可以调用的,只要是公开访问即可.
ArrayList 遍历方法 ArrayList 可以使用三方方式遍历for循环下标、foreach、使用迭代器还可以直接打印里面的内容。 int size list.size();for (int i 0; i size; i) {System.out.print(list.get(i) );}System.out.println();无论是Integer还是int接收元素,Java底层会帮我们自动拆箱的. for (int x: list) {System.out.print(x );}System.out.println();for (Integer y: list) {System.out.print(y );}System.out.println();ListIteratorInteger it list.listIterator(list.size());while (it.hasPrevious()) {System.out.print(it.previous() );}System.out.println();Java的ArrayList的父类是重写过toString方法的. System.out.println(list);实践
杨辉三角 这里要注意 ListList Integer ,这个意思表示外面的list的元素是list,里面的list的元素是Integer,例如下图所示:类似二维数组~ 代码:
class Solution {public ListListInteger generate(int numRows) {ListListInteger list new ArrayList();ListInteger list0 new ArrayList();list0.add(1);list.add(list0);for(int i1;inumRows;i) {ListInteger list1 new ArrayList();for(int j0;ji;j) {if(j0 || ji) {list1.add(1);} else {list1.add(list.get(i-1).get(j-1) list.get(i-1).get(j));}}list.add(list1);}return list;}
}洗牌功能实现
public class Card {private int number;private String cardColor;public Card(int number, String cardColor) {this.number number;this.cardColor cardColor;}Overridepublic String toString() {return Card{ cardColor \ number };}
}import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class PlayCard {private static final String[] cardColor {♦,♣,♥,♠};//购买52张牌public ListCard buyCards() {ListCard list new ArrayList();for (int i 1; i 13; i) {for (int j 0; j 4; j) {Card card new Card(i,cardColor[j]);list.add(card);}}return list;}//洗牌public void shuffle(ListCard list) {Random random new Random();int size list.size();for (int i 0; i size; i) {int index random.nextInt(size);//生成 0 ~ i-1 的随机数Card card list.get(index);list.set(index,list.get(i));list.set(i,card);}}//发牌public ListListCard deal(ListCard cards) {ListListCard list new ArrayList();//创建三个人ListCard list0 new ArrayList();ListCard list1 new ArrayList();ListCard list2 new ArrayList();list.add(list0);list.add(list1);list.add(list2);int size cards.size();int size2 list.size();int count 0;boolean flag true;while(flag) {for (int j 0; j size2; j) {list.get(j).add(cards.remove(0));count;if(count size){flag false;break;}}}return list;}
}这里要注意随机数的建立,首先先实例化Ramdom对象,然后使用nextInt方法,nextInt(int bound),生成的随机数范围是0~bound-1.
