ArrayList 与 顺序表
ArrayList与顺序表
线性表
线性表是n个具有相同性质的数据元素的有限序列，常见的线性表有：顺序表、链表、栈、队列……
线性表在逻辑上是线性结构的，也就是连续的一条直线，但是在物理结构上不一定是连续的，线性表在物理上存储时，主要是以数组和链式结构的形式进行存储。
这里要知道什么是物理上和逻辑上
物理上：其实就是内存上
逻辑上: 就是思维上
顺序表
ArrayList与顺序表线性表顺序表顺序表的定义MyArrayList 类打印顺序表新增数据方法(add)判定是否包含某个元素查找某个元素对应的位置获取 pos 位置的元素将pos 位置的元素设为 value --更新删除第一次出现的关键字key获取顺序表长度清空顺序表ArrayList类顺序表的3种遍历方法扑克牌练习CardDemo类Test类杨辉三角顺序表的优缺点
顺序表的定义
顺序表是一段物理地址连续的存储单元一次存储数据元素的线性结构，一般由数组来进行了存储，在数组上进行数据的增删查改。
MyArrayList 类
数据结构的知识是十分严谨的，所以在实现的时候一定要考虑得细致一点
//先写出MyArrayLis类的字段和构造方法 class MyArrayList { public int[] elem; public int usedSized;//usedSized是当前数组里面存的有效数据 public static final int DEFAULT_CAPACITY=10;//初始数组的大小 public MyArrayList() { //构造方法 1、没有返回值 2、方法名与类名一致 this.elem = new int[DEFAULT_CAPACITY]; } }
打印顺序表
// 打印顺序表--只要一直打印到所有的有效数字就行了 public void display() { for (int i = 0; i < usedSized; i++) { System.out.print(this.elem[i]+" "); } System.out.println(); }
新增数据方法(add)
要新增数据就要考虑是否需要进行扩容，之后再进行具体实现
// 新增元素,默认在数组最后新增--必须要考虑是否数组是否会满（扩容问题） public void add(int data) { if(isFull()){ elem= Arrays.copyOf(elem, elem.length * 2);//Arrays.copyOf的返回值是数组，所以还要用elem接收一下 } elem[usedSized]=data; usedSized++; } //判断数组是否满了，一定要和数组长度进行比较，不要和DEFAULT_CAPACITY比较，因为可能之后还要扩容，到时候就不能用DEFAULT_CAPACITY了，所以这里用的是elem.length public boolean isFull() { return usedSized == elem.length; }
add方法实现在pos下标位置处新增一个数据
1、检查下表是否合法
2、判断数组是否已满
3、具体实现
要实现抛异常，最好可以自定义异常
package sequence_table; /* 自定义一个异常(下标不合法的异常) */ public class PosIndexNotLegalException extends RuntimeException { public PosIndexNotLegalException() { } public PosIndexNotLegalException(String message) { super(message); } }
具体实现新增数据
/* checkPosAdd是为了检查一下要新增的下标是否合法，设为private是因为在类外也不会去掉用这个方法， */ private void checkAddPosAdd(int pos) { if (pos < 0 || pos > usedSized) { throw new PosIndexNotLegalException("pos位置不合法");//抛异常 } } // 在 pos 位置新增元素--add方法实现了重载 public void add(int pos, int data) { try { checkAddPosAdd(pos);//判断pos下表是否合理 if (isFull()) { //判断数组是否满了 elem= Arrays.copyOf(elem, elem.length * 2); } for (int i = usedSized-1; i >= pos ; i--) { elem[i + 1] = elem[i]; } elem[pos]=data; usedSized++; } catch (PosIndexNotLegalException e) { e.printStackTrace(); } }
判定是否包含某个元素
public boolean contains(int toFind) { for (int i = 0; i < usedSized; i++) { if (elem[i] == toFind) { return true; } } return false; }
查找某个元素对应的位置
public int indexOf(int toFind) { for (int i = 0; i < usedSized; i++) { if (elem[i] == toFind) { return i; } } return -1; }
获取 pos 位置的元素
1、判断下标的合法性
2、具体实现
/* 判断get方法的pos是否合法，与上面判断add的pos是否合法的区别就是不能取到usedSize */ private void checkGetPosAdd(int pos) { if (pos < 0 || pos >= usedSized) { throw new PosIndexNotLegalException("get方法的pos位置不合法"); } }
public int get(int pos) {
try {
checkGetPosAdd(pos);
return elem[pos];
} catch (PosIndexNotLegalException e) {
//要是真的不合法，就要在这里处理pos不合法的问题
e.printStackTrace();
}
return -1;
} 将pos 位置的元素设为 value --更新
public void set(int pos, int value) {
try{
checkGetPosAdd(pos);//判断下标合法性
elem[pos] = value;
}catch(PosIndexNotLegalException e){
e.printStackTrace();
}
} 删除第一次出现的关键字key
public void remove(int toRemove) {
int pos=indexOf(toRemove);//index方法中要是找不到toRemove就返回-1
if (pos == -1) {
System.out.println("不存在这样的数字");
return;
}
for (int i = pos; i <usedSized-1; i++) {
elem[i] = elem[i + 1];
}
usedSized--;
} 获取顺序表长度
public int size() {
return usedSized;
} 清空顺序表
public void clear() {
//由于这里不是引用类型，所有就不用for循环了，直接将usedSize置为0即可
/*for (int i = 0; i < usedSized; i++) {
elem[i] = null;
}*/
usedSized=0;
} 以上就是顺序表的方法的实现
其实Java已经给我们提供了顺序表的代码了，那就是是ArrayList类
ArrayList类
public class Test {
public static void main(String[] args) {
ArrayList<Integer> arrayList1 = new ArrayList<>();
arrayList1.add(0);
arrayList1.add(1);
arrayList1.add(2, 78);
System.out.println(arrayList1);//打印
}
} 截取数据
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("JavaSE");
list.add("JavaWeb");
list.add("JavaEE");
list.add("JVM");
list.add("测试课程");
List<String> ret = list.subList(1, 3);//截取，左闭右开
System.out.println(ret);
} 顺序表的3种遍历方法
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("JavaSE");
list.add("JavaWeb");
list.add("JavaEE");
list.add("JVM");
list.add("测试课程");
List<String> ret = list.subList(1, 3);//截取，左闭右开
//1、直接打印
System.out.println(ret);
System.out.println("==============");
//2、for循环
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
System.out.println("==============");
//3、foreach
for (String x:list) {
System.out.println(x);
}
}
//打印结果为：
[JavaWeb, JavaEE]
==============
JavaSE
JavaWeb
JavaEE
JVM
测试课程
==============
JavaSE
JavaWeb
JavaEE
JVM
测试课程 其实还有一种迭代器的方法来打印顺序表中的数据
public static void main(String[] args) {
Iterator<String> it = list.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
} 扑克牌练习
CardDemo类
package CardDemo;
import sun.plugin.javascript.navig4.Link;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
class Card{
public int rank;
public String suit;//花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
@Override
public String toString() {
return suit+" "+rank;
}
}
public class CardDemo {
public static final String[] suits={"♥","♠","♦","♣"};//展现四种花色
public List<Card> buyPlayingCard() { //买扑克牌
List<Card> cards = new ArrayList<>();
for (int i = 1; i <= 13; i++) { //牌的数值
for (int j = 0; j < 4; j++) { //四种花色
Card card=new Card(i,suits[j]);//其中的一张牌
cards.add(card);
}
}
return cards;
}
public void shuffle(List<Card> cards) { //将整副拍传进来，进行洗牌
for (int i = cards.size() - 1; i > 0; i--) {
Random random = new Random();
int index = random.nextInt(i);
swap(cards, index, i);
}
}
public void swap(List<Card> cards, int i, int j) {
Card tmp = cards.get(i);
cards.set(i, cards.get(j));
cards.set(j,tmp);
}
public List<List<Card>> test(List<Card> cards) { //接牌
List<Card> hand1 = new ArrayList<>();//分别列举出3个人手里的牌
List<Card> hand2 = new ArrayList<>();
List<Card> hand3 = new ArrayList<>();
List<List<Card>> hands = new ArrayList<>();//将3个人建立关系（嵌套）
hands.add(hand1);
hands.add(hand2);
hands.add(hand3);
//要求3个人，每个人轮流抓5张牌
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
Card card = cards.remove(0);//第一个人转到最上面的牌之后，第二个人抓原本第二，现在最上面的牌，以此类推
hands.get(j).add(card); //hands.get(j)先找到是哪一个人，接着再add接牌
}
}
return hands;//所有人手里的牌
}
} Test类
package CardDemo;
import java.util.List;
public class Test {
public static void main(String[] args) {
CardDemo cardDemo = new CardDemo();
List<Card> ret=cardDemo.buyPlayingCard();
System.out.println(ret);
System.out.println("洗牌");
cardDemo.shuffle(ret);
System.out.println(ret);
System.out.println("接牌");
List<List<Card>> ret2 = cardDemo.test(ret);//将洗乱的传进去
for (int i = 0; i < ret2.size(); i++) {
System.out.println("第" + i + "个人的牌" + ret2.get(i));
}
System.out.println("剩余的牌");
System.out.println(ret);
}
} 杨辉三角
首先要知道杨辉三角的特点
在这里我们要将一行杨辉三角看做一个顺序表，再将整个杨辉三角（所有行）看做一个顺序表
之所以要写成顺序表的嵌套，就是因为想将一行和所有行串联起来
import java.util.ArrayList;
import java.util.List;
//顺序表实现杨辉三角
/*
list代表杨辉三角的一行
ret代表整个杨辉三角，也就是所有行
*/
public class YanghuiTriangle {
public List<List<Integer>> generate(int numRows) {
List<Integer> list=new ArrayList<>();
List<List<Integer>> ret = new ArrayList<>();
list.add(1);//在第一行里面添加一个1
ret.add(list);//将第一行放到整个杨辉三角里面
for (int i = 1; i < numRows; i++) { //从第二行开始循环
List<Integer> curRow = new ArrayList<>();//当前行
curRow.add(1);//通过循环，使每一行的第一个数字都是1
List<Integer> prevRow = ret.get(i-1);//上一行
/*
//开始放要计算的数字（两个1中间的数字）
j是下标，第一个元素是1，所以j从1开始，最后一个元素是1，所以j<i-1
*/
for (int j = 1; j < i; j++) {
int num = prevRow.get(j) + prevRow.get(j-1);
curRow.add(num);
}
curRow.add(1);//最后一个数字放1
ret.add(curRow);//将每一行都放到ret（杨辉三角整体里面）
}
return ret;
}
} 顺序表的优缺点
优点：由于顺序表是将数据存储在一块连续的内存空间里面，所以空间利用率高
由于顺序表是通过下标直接存储数据，所以读取速度快
缺点：
顺序表的插入和删除都要遍历一遍所有的数据来移动数据
分配内存不够灵活，当需要读取的数据多于顺序表的数据时，就会出现”溢出“，反之，就会出现内存空间的浪费
要是想要解决以上的问题，就要学习另一种数据结构---链表。
游卡公司福利 135人发布