《List 与顺序表：数据结构基础讲解》
·
《List 与顺序表：数据结构基础讲解》
一.List
List在JAVA中表示线性表,线性表就是里面的元素是"一个挨着一个的",它是一个接口,只要实现并重写它的方法,就可以使用;
顺序表就实现继承它,我们先不讲
两者的关系先用图示:
collection是个根接口,现在用不上
二.ArrayList
这个顺序表式一个类,我们这节课主要就是自己手搓一个简易的顺序表,学会使用顺序表,顺序表综合运用
可以看到List有这么多方法,我们一般不直接实例化顺序表ArrayList,而是通过向上转型进行多态;
List<Integer> list = new ArrayList<>();
只需要实现基本要用到的增删查改等方法就可以;
2.1ArrayList的构造方法;
ArrayList的内存存储物理上是连续的,用数组来实现是最常见的,ArrayList是基于数组来实现的;
提供两个构造方法,一个是默认空间的ArrayList,一个是自定义空间的ArrayList
同时我们在用这些方法时,不可能全部都用到,所以还需要定义一个有效长度
private int[] data;
private int useSize;//要用的有效长度;
public SqList(){
this.data = new int[1024];//默认数组长度
}
public SqList(int size){
this.data = new int[size];
}
2.2ArrayList的增加
ArrayList的增加,需要用到方法的重载,一个方法是按顺序加在后面,一个是通过下标来添加
public void add(int value){
if(useSize==data.length){
//数组的扩容
grow();
}
this.data[useSize] = value;
useSize++;
}
下标添加:
①要考虑下标是否越界;
②添加要考虑全面,后面的元素也要发生变动
③考虑数组是否够用
public void add(int indexOf,int value){
if(useSize==data.length){
//数组的扩容
grow();
}
if(indexOf < 0 && indexOf > data.length){
throw new RuntimeException("数组越界");
}
for(int i = useSize-1;i>=indexOf;i--){
data[i+1]=data[i];
}
this.data[indexOf]= value;
useSize++;
}
2.3数组的扩容(前面用过)
①创建新数组引用指向对象,是原数组的二倍
②将原来的数组赋值给新数组;
③原数组在指向新数组的对象,最后扩容成功
private void grow(){
int[] bigData = new int[data.length*2];
for (int i = 0; i < data.length; i++) {
bigData[i] = data[i];
}
data = bigData;
}
2.4ArrayList的打印
public String toString(){
StringBuffer stringbuffer = new StringBuffer("[");
for (int i = 0; i <=useSize-2; i++) {
stringbuffer.append(this.data[i]+", ");
}
stringbuffer.append(this.data[useSize-1]+"]");
return stringbuffer.toString();
}
当然我这里偷懒,大家可以自己模仿Arrays.toString()方法来写;
2.5ArrayList查找是否包含元素
public boolean contains(int value){
for (int i = 0; i < useSize; i++) {
if(data[i]==value){
return true;
}
}
return false;
}
2.6ArrayList查找是否存在元素,返回下标
public int indexOf(int value){
for (int i = 0; i < useSize; i++) {
if(data[i]==value){
return i;
}
}
return -1;
}
2.6ArrayList获取与设置
public int get(int index){
if(index<0&&index>data.length){
return -1;
}
return this.data[index];
}
public void set(int index,int value){
this.data[index] = value;
}
2.6ArrayList的删除
ArrayList的删除叫做逻辑删除,只需要useSize–,最后一个元素就相当于被删除了,我们电脑中删除文件就是逻辑删除,看不到的时候就删除了,哪怕是在回收站中也是逻辑删除,文件的内容还是在硬盘,只有新文件覆盖了,才是没了
①后一个元素覆盖前一个元素
②删除后有效长度useSize–
③注意下标是否越界
public void remove(int value){
int index = indexOf(value);
if(index<0){
throw new RuntimeException("下标越界");
}
for (int i = index; i < useSize-2; i++) {
data[i] = data[i+1];
}
useSize--;
}
2.7ArraysList的清除
public void clear(){
this.useSize = 0;
}
三.ArrayList的测试
3.1添加测试
public static void main(String[] args){
SqList Sqlist = new SqList(10);
Sqlist.add(1);
Sqlist.add(2);
Sqlist.add(3);
Sqlist.add(4);
System.out.println(Sqlist.toString());
}
成功打印出来
public static void main(String[] args){
SqList Sqlist = new SqList(10);
Sqlist.add(1);
Sqlist.add(2);
Sqlist.add(3);
Sqlist.add(4);
Sqlist.add(3,5);
System.out.println(Sqlist.toString());
}
3.2查找测试
public static void main(String[] args){
SqList Sqlist = new SqList(10);
Sqlist.add(1);
Sqlist.add(2);
Sqlist.add(3);
Sqlist.add(4);
Sqlist.add(3,5);
boolean res = Sqlist.contains(4);
System.out.println(res);
}
public static void main(String[] args){
SqList Sqlist = new SqList(10);
Sqlist.add(1);
Sqlist.add(2);
Sqlist.add(3);
Sqlist.add(4);
Sqlist.add(3,5);
System.out.println(Sqlist.toString());
System.out.println(Sqlist.indexOf(5));
}
3.3获取与设置
public static void main(String[] args){
SqList Sqlist = new SqList(10);
Sqlist.add(1);
Sqlist.add(2);
Sqlist.add(3);
Sqlist.add(4);
Sqlist.add(3,5);
Sqlist.set(3,10);
System.out.println(Sqlist.get(3));
}
3.4删除
public static void main(String[] args){
SqList Sqlist = new SqList(4);
Sqlist.add(1);
Sqlist.add(2);
Sqlist.add(3);
Sqlist.add(4);
Sqlist.remove(3);
System.out.println(Sqlist.toString());
}
3.5清除
public static void main(String[] args){
SqList Sqlist = new SqList(4);
Sqlist.add(1);
Sqlist.add(2);
Sqlist.add(3);
Sqlist.add(4);
Sqlist.clear();
System.out.println(Sqlist.toString());
}
这个地方出异常了,异常处理从上往下看,最主要原因是54行
我们的toString考虑不周,得完善;
toString方法
public String toString(){
if(useSize==0){
return "[]";
}
StringBuffer stringbuffer = new StringBuffer("[");
for (int i = 0; i < useSize-1; i++) {
stringbuffer.append(this.data[i]+", ");
}
stringbuffer.append(this.data[useSize-1]+"]");
return stringbuffer.toString();
}
看下结果:
四.ArrayList综合运用
4.1洗牌算法
先创建牌这个类
Card
public class Card {
private String rank;
private String suit;
public String getRank() {
return rank;
}
public void setRank(String rank) {
this.rank = rank;
}
public String getSuit() {
return suit;
}
public void setSuit(String suit) {
this.suit = suit;
}
public Card(String suit, String rank) {
this.suit = suit;
this.rank = rank;
}
public Card() {
}
@Override
public String toString() {
return "[" + suit + rank+"]";
}
}
CardDemo
创建一副牌,用到组合;
public class CardDemo {
public static String[] suits = new String[]{"♠️","♥️","梅花","♦️"};
public static List<Card> buyCard(){
List<Card> cards = new ArrayList<>();
for(int i = 0;i<4;i++){
for (int j = 2; j < 11; j++) {
Card card = new Card();
card.setSuit(suits[i]);
card.setRank(j+"");
cards.add(card);
}
Card cardJ = new Card(suits[i],"J");
Card cardQ = new Card(suits[i],"Q");
Card cardK = new Card(suits[i],"K");
Card cardA = new Card(suits[i],"A");
}
return cards;
}
}
先测试一下这幅牌
test
public class testDemo {
public static void main(String[] args){
CardDemo cardDemo = new CardDemo();
List<Card> buyCard = cardDemo.buyCard();
System.out.println("打印刚买的牌");
for (int i = 0; i < buyCard.size(); i++) {
System.out.print( buyCard.get(i).toString()+" ");
}
}
}
有了牌之后,我们可以进行洗牌操作,要用到随机数的生成的下标来进行交换;
private void swap(List<Card> desk,int i,int r){
Card temp = desk.get(i);
desk.set(i,desk.get(r));
desk.set(r,temp);
}
public void Sguffer(List<Card> cards){
Random random = new Random();
for (int i = cards.size()-1; i>0; i--) {
int r = random.nextInt(i);
swap(cards,i,r);
}
}
牌洗好了,我们测试打印一下
public static void main(String[] args){
CardDemo cardDemo = new CardDemo();
List<Card> buyCard = cardDemo.buyCard();
System.out.println("打印刚买的牌");
int count1 = 0;
int count2 = 0;
for (int i = 0; i < buyCard.size(); i++) {
System.out.print( buyCard.get(i).toString()+" ");
count1++;
if(count1%10==0){
System.out.println();
}
}
System.out.println();
cardDemo.Shuffer(buyCard);
System.out.println("洗完之后的牌");
for (int i = 0; i < buyCard.size(); i++) {
System.out.print( buyCard.get(i).toString()+" ");
count2++;
if(count2%10==0){
System.out.println();
}
}
}
接下来给三个人发牌,每人发五张牌;
// 发牌
List<Card> player1 = new ArrayList<>();
List<Card> player2 = new ArrayList<>();
List<Card> player3 = new ArrayList<>();
List<List<Card>> players = new ArrayList<>();
players.add(player1);
players.add(player2);
players.add(player3);
for(int i = 0;i<5;i++){
for (int j = 0; j < 3; j++) {
Card card = buyCard.remove(0);
players.get(j).add(card);
}
}
System.out.println("三个人各拿的牌");
for (int i = 0; i < 3; i++) {
System.out.println("玩家"+(i+1)+players.get(i));
}
4.2杨辉三角(例题)
杨辉三角
题解:
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> yang = new ArrayList<>();
for(int i = 0;i<numRows;i++){
List<Integer> row = new ArrayList<>();
for(int j = 0;j<=i;j++){
if(j==0||j==i){
row.add(1);
}
else{
List<Integer> preRow = yang.get(i-1);
row.add( preRow.get(j -1)+ preRow.get(j));
}
}
yang.add(row);
}
return yang;
}
}
ArrayList总代码
import javax.xml.crypto.Data;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SqList {
private int[] data;
private int useSize;//要用的有效长度;
public SqList(){
this.data = new int[1024];//默认数组长度
}
public SqList(int size){
this.data = new int[size];
}
public void add(int value){
if(useSize==data.length) {
//数组的扩容
grow();
}
this.data[useSize] = value;
useSize++;
}
public void add(int indexOf,int value){
if(useSize==data.length) {
//数组的扩容
grow();
}
if(indexOf<0&&indexOf>data.length){
throw new RuntimeException("数组越界");
}
for(int i = useSize-1;i>=indexOf;i--){
data[i+1]=data[i];
}
this.data[indexOf]= value;
}
private void grow(){
int[] bigData = new int[data.length*2];
for (int i = 0; i < data.length; i++) {
bigData[i] = data[i];
}
data = bigData;
}
public String toString(){
if(useSize==0){
return "[]";
}
StringBuffer stringbuffer = new StringBuffer("[");
for (int i = 0; i < useSize-1; i++) {
stringbuffer.append(this.data[i]+", ");
}
stringbuffer.append(this.data[useSize-1]+"]");
return stringbuffer.toString();
}
public boolean contains(int value){
for (int i = 0; i < useSize; i++) {
if(data[i]==value){
return true;
}
}
return false;
}
public int indexOf(int value){
for (int i = 0; i < useSize; i++) {
if(data[i]==value){
return i;
}
}
return -1;
}
public int get(int index){
if(index<0&&index>data.length){
return -1;
}
return this.data[index];
}
public void set(int index,int value){
this.data[index] = value;
}
public void remove(int value){
int index = indexOf(value);
if(index<0){
throw new RuntimeException("下标越界");
}
for (int i = index; i < useSize-1; i++) {
data[i] = data[i+1];
}
useSize--;
}
public void clear(){
this.useSize = 0;
}
}
更多推荐
8
0- 0
已为社区贡献1条内容
所有评论(0)