1. AI技术聚合首页
  2. IT

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

扎眼的阳光 • • IT • 阅读 8

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

目录

  • 1.前言
  • 2.定义IList接口
  • 3.MyArraylist实现接口
    • 3.1定义成员变量与构造方法
    • 3.2添加元素
    • 3.3 是否包某一个元素
    • 3.4f返回某个值的下标
    • 3.5获取某一个下标的值
    • 3.6删除某一个值
    • 3.7遍历
    • 3.8判空与判满
    • 3.9清除所有元素
  • 4.ArrayList
    • 4.1ArrayList构造
    • 4.2 ArrayList常见操作
    • 4.3 ArrayList的遍历
  • 5.ArrayList具体使用
    • 5.1杨辉三角
    • 5.2简单洗牌算法
  • 6.总结

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);
    //删除第一次出现的关键字key
    public 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;
    }

    @Override
    public 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

版权声明：本文为博主作者：PU-YUHAN原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/weixin_69049913/article/details/137226871

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
扎眼的阳光的头像扎眼的阳光普通用户
0
上一篇 2024年4月16日
下一篇 2024年4月16日

相关推荐