数据结构(Java版)第四期：ArrayLIst和顺序表(上)

目录

一、顺序表

1.1. 接口的实现

二、ArrayList简介

2.1. ArrayList的构造

2.2. ArrayList的常见操作

2.3. ArrayList的扩容机制 

三、ArrayList的具体使用

3.1. 洗牌算法

3.2. 杨辉三角

一、顺序表

       上一期我们讲到过，顺序表本质上和数组是差不多的，只不过数组只能访问或修改某个元素，而作为顺序表，需要实现更多的功能。

1.1. 接口的实现

 //新增元素,默认在数组最后新增public void add(int data) {  }// 在pos位置新增元素public void add(int pos, int data) {  }//判定是否包含某个元素public boolean contains(int toFind) { return true; }//查找某个元素对应的位置public int indexOf(int toFind) { return -1; }//获取pos位置的元素public int get(int pos) { return -1; }// 给pos位置的元素设为value 
public void set(int pos, int value) {    
//删除第⼀次出现的关键字key 
public void remove(int toRemove) {    
// 获取顺序表⻓度public int size() { return 0; }
//清空顺序表public void clear() {    
}

二、ArrayList简介

2.1. ArrayList的构造

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//第一种方式，创建ArrayList对象，构造空的顺序表ArrayList<String> arrayList1 = new ArrayList<>();//第二种方式List<String> list = new ArrayList<>();}
}

      其中ArrayList里面，也是实现了List的接口。也就是说，我们完全可以通过向上转型，把List引用指向ArrayList的实例。

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

       我们来看下面两段代码的，两个都是构造空的顺序表，二者有什么区别呢？第一个是创建了一个盒子，盒子里面为空，而第二个却连盒子都没有。

ArrayList<String> arrayList1 = new ArrayList<>();
ArrayList<String> arrayList2 = null;
//使用arrayList1复制一份，生成arrayList3
ArrayList<String> arrayList3 = new ArrayList<>(arrayList1);
//构造的同时，可以去指定初始容量
ArrayList<String> arrayList4 = new ArrayList<>(10);

        当前构造出来的ArrayList初始容量为10，这里与数组的区别是：数组我们在一开始就规定好了它的容量，不能在进行修改了；而ArrayList的容量可以进行动态扩容，只要机器内存允许，就能一直扩容，把想要的元素容纳进去。

2.2. ArrayList的常见操作

（1）add尾插操作 

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");System.out.println(list);}
}

（2）获取元素个数

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//获取元素个数，数组提供了.length属性获取到元素个数，集合类提供了size()方法获取元素个数List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");System.out.println(list.size());}
}

      事实上，不仅是List，只要是集合类，都可以通过.size来获取长度。

（3）ArrayList的访问和修改

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//获取或者设置list中的元素List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");//进行了自动扩容System.out.println(list.get(0));System.out.println(list.get(1));System.out.println(list.get(2));System.out.println(list.get(3));System.out.println(list.get(4));}
}

        如果我们运行一下，此时也会出现下标越界访问的异常。 

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//获取或者设置list中的元素List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");//进行了自动扩容list.set(0,"eee");System.out.println(list);}
}

（4）ArrayList的遍历

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");//遍历是可能会进行各种操作的，不一定是打印for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();//for-each写法for (String s : list) {System.out.print(s+" ");}}
}

       并不是所有的类都能写进for-each里面，要求这个类必须能够实现Iterable接口。实现Iterable接口中的iterator方法，得到一个迭代器对象，进行近一步循环遍历。

public interface List<E> extends Collection<E>
public interface Collection<E> extends Iterable<E> 
Iterator<E> iterator();

      迭代也是计算机中的专业术语，可以理解成“逐渐接近目标”。集合类中用到迭代。上面的for-each循环，我们可以看作是以下代码的简化。

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){System.out.println(iterator.next());
}

          hasNext用于判断有没有下一个元素，iterator.next用于取出当前元素，并准备下一个元素。hasNext的工作机理可以如下图所示，按照箭头从上到下依次去遍历。

（5）其他的一些操作

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//通过contains判读元素是否存在List<String> list1 = new ArrayList<>();list1.add("aaa");list1.add("bbb");list1.add("ccc");list1.add("ccc");list1.add("ccc");list1.add("ddd");System.out.println(list1.contains("aaa"));//通过indexOf获取元素第一次出现的位置System.out.println(list1.indexOf("ccc"));//通过lastIndexOf获取元素最后一次出现的位置list1.lastIndexOf("ccc");main1(args);main2(args);main3(args);}public static void main3(String[] args) {List<String> list1 = new ArrayList<>();list1.add("aaa");list1.add("bbb");list1.add("ccc");list1.add("ddd");//按照元素内删除list1.remove("ddd");System.out.println(list1);}public static void main2(String[] args) {List<String> list1 = new ArrayList<>();list1.add("aaa");list1.add("bbb");list1.add("ccc");list1.add("ddd");//按照下标删除元素list1.remove(2);System.out.println(list1);}public static void main1(String[] args) {List<String> list1 = new ArrayList<>();list1.add("aaa");list1.add("bbb");list1.add("ccc");list1.add("ddd");//在任意位置添加元素list1.add(1,"eee");System.out.println(list1);}
}

2.3. ArrayList的扩容机制 

       当ArrayList内存不够时，就会自动申请额外的内存空间。ArrayList内部持有一个数组，设置的初始容量相当于数组的大小。比如说我们初始容量为10，当循环到第11次的时候，发现元素已经满了；add真正写进元素之前，就要创建一个更大的数组。新的数组要把旧的数组里的元素添加进来，新的元素也要添加进新的数组里面，原来旧的数组要进行释放。

三、ArrayList的具体使用

3.1. 洗牌算法

       问题描述：现有一副扑克牌，对其进行洗牌。

      我们先来定义一个Card类，用来表示一张扑克牌。

class Card {public String suit;//表示花色public String rank;//表示点数public Card(String suit, String rank) {this.suit = suit;this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public String getRank() {return rank;}public void setRank(String rank) {this.rank = rank;}@Overridepublic String toString() {return this.suit+this.rank;}
}

     接下来要先把Card这个对象实例化，并用ArrayList把所有的牌添加进去。

public class Main {public static void main(String[] args) {//使用ArrayList表示一副扑克牌}public static ArrayList<Card> CreateDeck() {//创建一副扑克牌ArrayList<Card> deck = new ArrayList<>();String[] suits = {"♠","♦","♥","♣"};//通过两层for循环，第一层先循环花色，第二层在循环点数//每个花色中，生成对应的点数for (String suit:suits){for (int i = 2; i <= 10; i++) {Card cardNum = new Card(suit,""+i);deck.add(cardNum);//添加到扑克牌中}Card cardJ = new Card(suit,"J");Card cardQ = new Card(suit,"Q");Card cardK = new Card(suit,"K");Card cardA = new Card(suit,"A");deck.add(cardJ);deck.add(cardQ);deck.add(cardK);deck.add(cardA);}return deck;}
}

       然后我们调用CreateDeck方法，对这副牌进行一个打印。

public class Main {public static void main(String[] args) {//使用ArrayList表示一副扑克牌ArrayList<Card> deck = CreateDeck();System.out.println(deck);}
}

      接下来是进行洗牌的操作，在Java标准库中，提供了进行洗牌的方法shuffle。 

import java.util.Collections;public class Main {public static void main(String[] args) {//使用ArrayList表示一副扑克牌ArrayList<Card> deck = CreateDeck();System.out.println("原始牌组:"+deck);//洗牌Collections.shuffle(deck);System.out.println("洗牌之后:"+deck);}
}

      我们也可以自己写一个方法，来进行洗牌。

    public static void shuffle(ArrayList<Card> deck){//把整个ArrayList从后往前遍历//每次取一张牌，生成一个随机下标，用当前的拍和随机下标的牌进行交换Random random = new Random();for (int i = deck.size(); i >0 ; i--) {int j = random.nextInt(deck.size());//生成随机下标[0,deck.size)//交换操作Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标，不能交换的时候发生修改deck.set(i, deck.get(j));deck.set(j, tmp);}}

      下面是发牌，一共有3个人，每个人发5张牌。我们可以看成一个3行5列的一个二维数组。

        ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组//先创建 3 个人手里的牌for (int i = 0; i < 3; i++) {ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌hands.add(hand);//发到每个人手里//已经添加了3个元素进去，但还是长度为0的ArrayList}

       最后是发牌的过程。

        for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {//发牌是轮流的过程.ArrayList<Card> currentHand = hands.get(j);Card card = deck.remove(0);currentHand.add(card);//一次循环，相当于取出一张牌交给玩家}}

 完整代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;class Card {public String suit;//表示花色public String rank;//表示点数public Card(String suit, String rank) {this.suit = suit;this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public String getRank() {return rank;}public void setRank(String rank) {this.rank = rank;}@Overridepublic String toString() {return this.suit+this.rank;}
}public class Main {public static void main(String[] args) {//使用ArrayList表示一副扑克牌ArrayList<Card> deck = CreateDeck();System.out.println("原始牌组:"+deck);//洗牌//Collections.shuffle(deck);System.out.println("洗牌之后:"+deck);ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组//先创建 3 个人手里的牌for (int i = 0; i < 3; i++) {ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌hands.add(hand);//发到每个人手里//已经添加了3个元素进去，但还是长度为0的ArrayList}for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {//发牌是轮流的过程.ArrayList<Card> currentHand = hands.get(j);Card card = deck.remove(0);currentHand.add(card);//一次循环，相当于取出一张牌交给玩家}}//打印每个人的手牌for (int i = 0; i < 3; i++) {System.out.println("第"+i+"个人的手牌"+hands.get(i));}}public static void shuffle(ArrayList<Card> deck){//把整个ArrayList从后往前遍历//每次取一张牌，生成一个随机下标，用当前的拍和随机下标的牌进行交换Random random = new Random();for (int i = deck.size(); i >0 ; i--) {int j = random.nextInt(deck.size());//生成随机下标[0,deck.size)//交换操作Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标，不能交换的时候发生修改deck.set(i, deck.get(j));deck.set(j, tmp);}}public static ArrayList<Card> CreateDeck() {//创建一副扑克牌ArrayList<Card> deck = new ArrayList<>();String[] suits = {"♠","♦","♥","♣"};//通过两层for循环，第一层先循环花色，第二层在循环点数//每个花色中，生成对应的点数for (String suit:suits){for (int i = 2; i <= 10; i++) {Card cardNum = new Card(suit,""+i);deck.add(cardNum);//添加到扑克牌中}Card cardJ = new Card(suit,"J");Card cardQ = new Card(suit,"Q");Card cardK = new Card(suit,"K");Card cardA = new Card(suit,"A");deck.add(cardJ);deck.add(cardQ);deck.add(cardK);deck.add(cardA);}return deck;}
}

3.2. 杨辉三角

      问题描述：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1: 输入: numRows = 5  输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2: 输入: numRows = 1 输出: [[1]]

       通过上面的图，我们可以总结出以下规律：1.第i行有i+1个列(因为要用二维数组解决，所以把第一行定义第0行)；2.每一行的第一列和最后一列都是1；3.第i行第j列的元素 = 第i-1行第j-1列的元素 + 第i-1行第j列的元素。

完整代码： 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {public List<List<Integer>> generate(int numRows) {//先写一个表示结果的二维数组List<List<Integer>> result = new ArrayList<List<Integer>>();//先来构造行for (int i = 0; i < numRows; i++) {List<Integer> rows = new ArrayList<>();//用到了向上转型。需要往这一行里面里面添加元素for (int j = 0; j < i+1; j++) {if (j==0 || j==i){rows.add(1);} else {List<Integer> prevRow = result.get(i - 1);int current = prevRow.get(j - 1) + prevRow.get(j);rows.add(current);}}//一行构造好了之后，把这一行添加到result中result.add(rows);}return result;}public static void main(String[] args) {Main m = new Main();Scanner num = new Scanner(System.in);int b = num.nextInt();List<List<Integer>> result = m.generate(b);System.out.println(result);}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/479755.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Python编程语言中的优雅艺术：数值分隔符的巧妙运用

Python编程语言中的优雅艺术：数值分隔符的巧妙运用

在Python编程的世界里&#xff0c;有许多精巧的设计让代码更优雅、更易读。今天要分享的是一个看似简单却能大幅提升代码可读性的特性 —— 数值分隔符。这个特性从Python 3.6版本开始引入&#xff0c;它用一种极其优雅的方式解决了大数值表示的难题。 数值分隔符的本质与应用…
阅读更多...
心情追忆：构建支付模块的五个基本接口设计

心情追忆：构建支付模块的五个基本接口设计

之前&#xff0c;我独自一人开发了一个名为“心情追忆”的小程序&#xff0c;旨在帮助用户记录日常的心情变化及重要时刻。我从项目的构思、设计、前端&#xff08;小程序&#xff09;开发、后端搭建到最终部署。经过一个月的努力&#xff0c;通过群聊分享等方式&#xff0c;用…
阅读更多...
实验三 z变换及离散时间LTI系统的z域分析

实验三 z变换及离散时间LTI系统的z域分析

实验原理 有理函数z 变换的部分分式展开 【实例2-1】试用Matlab 命令对函数 X ( z ) 18 18 3 − 1 − 4 z − 2 − z − 3 X\left(z\right)\frac{18}{183^{-1} -4z^{-2} -z^{-3} } X(z)183−1−4z−2−z−318​ 进行部分分式展开&#xff0c;并求出其z 反变换。 B[18]; A…
阅读更多...
Web登录页面设计

Web登录页面设计

记录第一个前端界面&#xff0c;暑假期间写的&#xff0c;用了Lottie动画和canvas标签做动画&#xff0c;登录和注册也连接了数据库。 图片是从网上找的&#xff0c;如有侵权私信我删除&#xff0c;谢谢啦~
阅读更多...
【es6】原生js在页面上画矩形及删除的实现方法

【es6】原生js在页面上画矩形及删除的实现方法

画一个矩形&#xff0c;可以选中高亮&#xff0c;删除自己效果的实现&#xff0c;后期会丰富下细节&#xff0c;拖动及拖动调整矩形大小 实现效果 代码实现 class Draw {constructor() {this.x 0this.y 0this.disX 0this.disY 0this.startX 0this.startY 0this.mouseDo…
阅读更多...
高级 K8s 面试题（Advanced K8S Interview Questions）

高级 K8s 面试题（Advanced K8S Interview Questions）

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…
阅读更多...
HiISP（一)

HiISP（一)

系列文章目录 文章目录 系列文章目录前言一、Hi3518EV200 芯片架构1.1. ARM子系统1.2. 图像子系统&#xff08;Image Subsystem&#xff09;1.3. 视频子系统&#xff08;Video Subsystem&#xff09;1.4. 存储与接口模块1.5. 通用功能模块1.6. DDR与总线1.7. 数据流1.7.1. 数据…
阅读更多...
京东物流与亿纬锂能达成战略合作，双方跨界意义何在？

京东物流与亿纬锂能达成战略合作，双方跨界意义何在？

首先&#xff0c;这一合作有助于双方实现资源共享和优势互补。京东物流作为国内领先的物流服务商&#xff0c;拥有先进的物流技术和丰富的运营经验&#xff0c;能够为亿纬锂能提供高效、安全、可靠的物流服务。而亿纬锂能作为新能源领域的佼佼者&#xff0c;拥有先进的电池技术…
阅读更多...
103.【C语言】数据结构之二叉树的三种递归遍历方式

103.【C语言】数据结构之二叉树的三种递归遍历方式

目录 1.知识回顾 2.分析二叉树的三种遍历方式 1.总览 2.前序遍历 3.中序遍历 4.后序遍历 5.层序遍历 3.代码实现 1.准备工作 2.前序遍历函数PreOrder 测试结果 3.中序遍历函数InOrder 测试结果 4.后序遍历函数PostOrder 测试结果 4.底层分析 1.知识回顾 在99.…
阅读更多...
【kafka03】消息队列与微服务之Kafka 读写数据

【kafka03】消息队列与微服务之Kafka 读写数据

Kafka 读写数据 参考文档 Apache Kafka 常见命令 kafka-topics.sh #消息的管理命令 kafka-console-producer.sh #生产者的模拟命令 kafka-console-consumer.sh #消费者的模拟命令 创建 Topic 创建topic名为 chen&#xff0c;partitions(分区)为3&#xff0…
阅读更多...
SAP开发语言ABAP开发入门

SAP开发语言ABAP开发入门

1. 了解ABAP开发环境和基础知识 - ABAP简介 - ABAP&#xff08;Advanced Business Application Programming&#xff09;是SAP系统中的编程语言&#xff0c;主要用于开发企业级的业务应用程序&#xff0c;如财务、物流、人力资源等模块的定制开发。 - 开发环境搭建 - 首先需…
阅读更多...
[护网杯 2018]easy_tornado

[护网杯 2018]easy_tornado

这里有一个hint点进去看看&#xff0c;他说md5(cookie_secretmd5(filename))&#xff0c;所以我们需要获得cookie_secret的value 根据题目tornado,它可能是tornado的SSTI 这里吧filehash改为NULL. 是tornado的SSTI 输入{{handler.settings}} (settings 属性是一个字典&am…
阅读更多...
【k8s深入学习之 Scheme】全面理解 Scheme 的注册机制、内外部版本、自动转换函数、默认填充函数、Options等机制

【k8s深入学习之 Scheme】全面理解 Scheme 的注册机制、内外部版本、自动转换函数、默认填充函数、Options等机制

参考 【k8s基础篇】k8s scheme3 之序列化_基于schema进行序列化-CSDN博客【k8s基础篇】k8s scheme4 之资源数据结构与资源注册_kubernetes 的scheam-CSDN博客 Scheme的字段总览 type Scheme struct {// gvkToType 允许通过给定的版本和名称来推断对象的 Go 类型。// map 键是…
阅读更多...
PySide6 QSS(Qt Style Sheets) Reference: PySide6 QSS参考指南

PySide6 QSS(Qt Style Sheets) Reference: PySide6 QSS参考指南

Qt官网参考资料&#xff1a; QSS介绍&#xff1a; Styling the Widgets Application - Qt for Pythonhttps://doc.qt.io/qtforpython-6/tutorials/basictutorial/widgetstyling.html#tutorial-widgetstyling QSS 参考手册&#xff1a; Qt Style Sheets Reference | Qt Widge…
阅读更多...
python控制鼠标，键盘，adb

python控制鼠标，键盘，adb

python控制鼠标&#xff0c;键盘&#xff0c;adb 听说某系因为奖学金互相举报&#xff0c;好像拿不到要命一样。不禁想到几天前老墨偷走丁胖子的狗&#xff0c;被丁胖子逮到。他面对警察的问询面不改色坚持自我&#xff0c;反而是怒气冲冲的丁胖子被警察认为是偷狗贼。我觉得这…
阅读更多...
前端Vue项目整合nginx部署到docker容器

前端Vue项目整合nginx部署到docker容器

一、通过Dockerfile整合nginx方法&#xff1a; 1&#xff0c;使用Vue CLI或npm脚本构建生产环境下的Vue项目。 npm run build or yarn build2&#xff0c;构建完成后&#xff0c;项目目录中会生成一个dist文件夹&#xff0c;里面包含了所有静态资源文件&#xff08;HTML、CSS…
阅读更多...
ChatGPT的应用场景：开启无限可能的大门

ChatGPT的应用场景：开启无限可能的大门

ChatGPT的应用场景：开启无限可能的大门 随着人工智能技术的快速发展，自然语言处理领域迎来了前所未有的突破。其中，ChatGPT作为一款基于Transformer架构的语言模型，凭借其强大的语言理解和生成能力，在多个行业和场景中展现出了广泛的应用潜力。以下是ChatGPT八个最具代表…
阅读更多...
Wireshark抓取HTTPS流量技巧

Wireshark抓取HTTPS流量技巧

一、工具准备 首先安装wireshark工具&#xff0c;官方链接&#xff1a;Wireshark Go Deep 二、环境变量配置 TLS 加密的核心是会话密钥。这些密钥由客户端和服务器协商生成&#xff0c;用于对通信流量进行对称加密。如果能通过 SSL/TLS 日志文件&#xff08;例如包含密钥的…
阅读更多...
【dvwa靶场：File Upload系列】File Upload低-中-高级别，通关啦

【dvwa靶场：File Upload系列】File Upload低-中-高级别，通关啦

目录 一、low级别,直接上传木马文件 1.1、准备一个木马文件 1.2、直接上传木马文件 1.3、访问木马链接 1.4、连接蚁剑 二、medium级别&#xff1a;抓包文件缀名 2.1、准备一个木马文件&#xff0c;修改后缀名为图片的后缀名 2.2、上传文件&#xff0c;打开burpSuite&…
阅读更多...
【深度学习|目标跟踪】StrongSort 详解(以及StrongSort++)

【深度学习|目标跟踪】StrongSort 详解(以及StrongSort++)

StrongSort详解 1、论文及源码2、DeepSort回顾3、StrongSort的EMA4、StrongSort的NSA Kalman5、StrongSort的MC6、StrongSort的BOT特征提取器7、StrongSort的AFLink8、未完待续 1、论文及源码 论文地址&#xff1a;https://arxiv.org/pdf/2202.13514 源码地址&#xff1a;https…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023