【数据结构（二）】顺序表与ArrayList

本文主要是介绍【数据结构（二）】顺序表与ArrayList，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

❣博主主页: 33的博客❣
▶文章专栏分类:数据结构◀
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构知识

1.前言

在计算机科学中，数据结构是处理和组织数据的方法和技术。顺序表是一种常见的线性表数据结构，它基于数组实现，提供了快速的随机访问能力。本篇文章将详细介绍顺序表的定义、特点以及常见操作。

本章重点

自己完成一个顺序表，并实现增，删，改，查等操作，实现杨辉三角，简单洗牌算法。

---

2.定义IList接口

public interface IList {//新增元素,默认在数组最后新增public void add(int data);// 在 pos 位置新增元素public void add(int pos, int data);// 判定是否包含某个元素public boolean contains(int toFind) ;// 查找某个元素对应的位置public int indexOf(int toFind);// 获取 pos 位置的元素public int get(int pos);// 给 pos 位置的元素设为 value  更新public void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove) ;// 获取顺序表长度public int size();// 清空顺序表public void clear() ;// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display();boolean isFull();public boolean isEmpty();
}

---

3.MyArraylist实现接口

3.1定义成员变量与构造方法

public static final int LEN=10;public  int[] arr;public int usesize=0;public MyArraylist(){this.arr=new int[LEN];}

---

3.2添加元素

1.添加元素到末尾

public void add(int data) {//检查是否满了，满了就扩容if(isFull()){chekCapacity();}arr[usesize]=data;usesize++;}
public void chekCapacity(){arr= Arrays.copyOf(arr,arr.length*2);}    

2.指定某一个位置添加

 public void add(int pos, int data) {if(isFull()) {chekCapacity();}if(pos<0||pos>=arr.length){System.out.println("位置不合法");}else {for(int i=usesize-1;i>=pos;i--){arr[i+1]=arr[i];}arr[pos]=data;}usesize++;}

测试结果：

---

3.3 是否包某一个元素

public boolean contains(int toFind) {for (int i=0;i<usesize;i++){if(arr[i]==toFind){return true;}}return false;}

测试结果：

---

3.4f返回某个值的下标

public int indexOf(int toFind) {for (int i=0;i<usesize;i++){if(arr[i]==toFind){return i;}}return -1;}

测试结果：

---

3.5获取某一个下标的值

public int get(int pos) {if(pos<0||pos>usesize){System.out.println("位置不合法");}return arr[pos];}

测试结果：

---

3.6删除某一个值

public void remove(int toRemove) {if(isEmpty()){System.out.println("已为空，不能删除");}else {int pos=indexOf(toRemove);for(int i=pos;i<usesize-1;i++){arr[i]=arr[i+1];}}usesize--;}

测试结果：

---

3.7遍历

public void display() {for (int i=0;i<usesize;i++){System.out.print(arr[i]+" ");}}

测试结果：

---

3.8判空与判满

public boolean isFull() {return usesize==arr.length;}
public boolean isEmpty() {return usesize==0;}
}

测试结果：

---

3.9清除所有元素

public void clear() {usesize = 0;}

测试结果：

---

4.ArrayList

实际上自己实现一个顺序表是非常简单容易的，在数据结构中已经写好了顺序表ArrayList，我们只需要用即可，但我们只有了解底层是如何实现的，才能更好的使用。

从源码我们可以看出，ArrayList实现了List接口，ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问，.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的，ArrayList实现了Serializable接口，表明ArrayList是支持序列化的。

4.1ArrayList构造

//无参构造一个空的列表
ArrayList<Integer> list1=new ArratList<>();
//构造一个容量为10的列表
ArrayList<Integer> list2=new ArratList<>(10);
// list3构造好之后，与list中的元素一致,实现了collection接口，为Integer的子类或者本身
ArrayList<Integer> list3=new ArratList<>(list2);

4.2 ArrayList常见操作

---

4.3 ArrayList的遍历

rrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器。

 public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);// 使用下标+for遍历for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();// 借助foreach遍历for (Integer integer : list) {System.out.print(integer + " ");}//迭代器Iterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();}

---

5.ArrayList具体使用

5.1杨辉三角

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> list=new ArrayList<>();List<Integer> l=new ArrayList<>();//设置第一行的数字l.add(1);list.add(l);for (int i=1;i<numRows;i++){//设置每一行第一个元素List<Integer> cur=new ArrayList<>();cur.add(1);List<Integer> pre=list.get(i-1);for (int j=1;j<i;j++){cur.add(pre.get(j)+pre.get(j-1));}//设置每一行最后一个元素cur.add(1);list.add(cur);}return list;}
}

---

5.2简单洗牌算法

Card类型

public class Card {private String suit;//花色private int rank;//数字public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public int getRank() {return rank;}public void setRank(int rank) {this.rank = rank;}@Overridepublic String toString() {return suit+":"+rank+" ";}
}

//买牌、洗牌、发牌

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
//一副新牌
public class CardDemo {final String[] suit={"♥","♦","♣","♠"};public List<Card> buycard(){List<Card> cards=new ArrayList<>();for (int i=0;i<4;i++){for (int j=0;j<13;j++){Card card=new Card(suit[i],j);cards.add(card);}}System.out.println(cards);return cards;}//洗牌
public void shuffle(List<Card> cards){Random random=new Random();for (int i=cards.size()-1;i>0;i--){int change=random.nextInt(i);//交换i位置与change位置的牌Card tmp=cards.get(i);cards.set(i,cards.get(change));cards.set(change,tmp);}System.out.println(cards);
}//三人轮流拿5张牌public void getCard(List<Card> cards){List<Card> L1=new ArrayList<>();List<Card> L2=new ArrayList<>();List<Card> L3=new ArrayList<>();List<List<Card>> list=new ArrayList<>();list.add(L1);list.add(L2);list.add(L3);for(int j=0;j<5;j++){for (int i=0;i<3;i++){Card card=cards.remove(0);list.get(i).add(card);}}System.out.println("第一个人拿牌");System.out.println(L1);System.out.println("第二个人拿牌");System.out.println(L2);System.out.println("第三个人拿牌");System.out.println(L3);}}

Test

public static void main(String[] args) {CardDemo cardDemo=new CardDemo();List<Card> cards=cardDemo.buycard();cardDemo.shuffle(cards);cardDemo.getCard(cards);
}

---

6.总结

本篇文章完成一个顺序表，并实现增，删，改，查等操作，实现杨辉三角，简单洗牌算法。

下期预告：链表与LinkedList

这篇关于【数据结构（二）】顺序表与ArrayList的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---