【数据结构(二)】顺序表与ArrayList

2024-04-07 12:04

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

❣博主主页: 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);//删除第一次出现的关键字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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/882549

相关文章

Spring如何使用注解@DependsOn控制Bean加载顺序

《Spring如何使用注解@DependsOn控制Bean加载顺序》:本文主要介绍Spring如何使用注解@DependsOn控制Bean加载顺序,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录1.javascript 前言2. 代码实现总结1. 前言默认情况下,Spring加载Bean的顺

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co

MySQL中SQL的执行顺序详解

《MySQL中SQL的执行顺序详解》:本文主要介绍MySQL中SQL的执行顺序,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql中SQL的执行顺序SQL执行顺序MySQL的执行顺序SELECT语句定义SELECT语句执行顺序总结MySQL中SQL的执行顺序

SpringBoot中配置文件的加载顺序解读

《SpringBoot中配置文件的加载顺序解读》:本文主要介绍SpringBoot中配置文件的加载顺序,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot配置文件的加载顺序1、命令⾏参数2、Java系统属性3、操作系统环境变量5、项目【外部】的ap

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

Java中ArrayList和LinkedList有什么区别举例详解

《Java中ArrayList和LinkedList有什么区别举例详解》:本文主要介绍Java中ArrayList和LinkedList区别的相关资料,包括数据结构特性、核心操作性能、内存与GC影... 目录一、底层数据结构二、核心操作性能对比三、内存与 GC 影响四、扩容机制五、线程安全与并发方案六、工程

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要