顺序表及应用

2023-12-23 17:15
文章标签 应用 顺序 表及

本文主要是介绍顺序表及应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一. 线性表

二. 顺序表

2.1 ArrayList简介

2.2 ArrayList的简单实现

2.3 ArrayList使用

1. ArrayList是一个泛型类

2.  ArrayList中定义的变量​编辑

3. ArrayList的构造方法

 4. ArrayList常见的方法

2.4 ArrayList的遍历

 2.5 ArrayList的扩容机制

2.6 二维顺序表

​编辑

 杨辉三角

 2.7 ArrayList的使用

简单的洗牌算法

一. 线性表

线性表（ linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表： 顺序表、链表、栈、队列...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二. 顺序表

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.1 ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

【 说明 】(了解)
1. ArrayList 是以泛型方式实现的，使用时必须要先实例化
2. ArrayList 实现了 RandomAccess 接口，表明 ArrayList 支持随机访问
3. ArrayList 实现了 Cloneable 接口，表明 ArrayList 是可以 clone 的
4. ArrayList 实现了 Serializable 接口，表明 ArrayList 是支持序列化的
5. 和 Vector 不同， ArrayList 不是线程安全的，在单线程下可以使用，在多线程中可以选择 Vector 或者CopyOnWriteArrayList
6. ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2.2 ArrayList的简单实现

存放整型为例:

 接口:

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 位置的元素设为 valuepublic void set(int pos, int value) ;//删除第一次出现的关键字toRemovepublic void remove(int toRemove);//使用的元素个数public int size() ;// 清空顺序表public void clear() ;// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() ;void isFull(int[] elem);void isEmpty();
}

自定义异常:

public class EmptyException extends RuntimeException{public EmptyException(){super();}public EmptyException(String s){super(s);}
}
public class PosException extends RuntimeException {public PosException(){super();}public PosException(String s){super(s);}
}

MyArrayList:

import java.util.Arrays;public class MyArrayList implements IList{public int[] elem;public int usedSize;public static final int DEFAULT_CAPACITY = 5;public MyArrayList(){elem = new int[DEFAULT_CAPACITY];}
//判断是否为空, 若为空, 扩容@Overridepublic void isFull(int[] elem) {if(usedSize ==elem.length){this.elem = Arrays.copyOf(elem,2*elem.length);}}@Overridepublic void add(int data) {isFull(this.elem);elem[usedSize] = data;usedSize++;}
//适用Add方法:检查pos位置的合法性public void checkPosOfAdd(int pos){if(pos<0 || pos>usedSize){//可以是usedSize位置throw new PosException("pos位置错误");}}@Overridepublic void add(int pos, int data) {isFull(this.elem);checkPosOfAdd(pos);for (int i = usedSize-1 ; i >= pos; i++) {elem[i+1] = elem[i];}elem[pos] = data;usedSize++;}@Overridepublic boolean contains(int toFind) {for (int i = 0; i < usedSize; i++) {if(elem[i] == toFind){return true;}}return false;}@Overridepublic int indexOf(int toFind) {for (int i = 0; i < usedSize; i++) {if(elem[i] == toFind){return i;}}return -1;}
//适用于get set方法:检查pos位置的合法性public void checkPosOfGet(int pos){if(pos<0 || pos>=usedSize){//pos位置不能为useSizethrow new PosException("pos位置错误");}}
//判断是否为空, 若为空, 抛异常@Overridepublic void isEmpty() {if(usedSize==0){throw new EmptyException("顺序表为空");}}@Overridepublic int get(int pos) {checkPosOfGet(pos);isEmpty();return elem[pos];}@Overridepublic void set(int pos, int value) {checkPosOfGet(pos);isEmpty();elem[pos] = value;}@Overridepublic void remove(int toRemove) {isEmpty();int index = indexOf(toRemove);for(int i=index;i< usedSize-1 ;i++){elem[i] = elem[i+1];}usedSize--;}@Overridepublic int size() {return usedSize;}@Overridepublic void clear() {usedSize = 0;}@Overridepublic void display() {for (int i = 0; i < usedSize; i++) {System.out.print(elem[i]+" ");}System.out.println(" ");}}

2.3 ArrayList使用

实际上, 我们在使用顺序表时, 不需要自己定义, 我们只需要拿来用即可, 那么我们可以分析一下源码, 方便我们使用:

1. ArrayList是一个泛型类

 我们看到, ArrayList是一个泛型类, 那么我们在实例化对象时, 写法为:

ArrayList<Integer> arrayList = new ArrayList<>();

2.  ArrayList中定义的变量

我们大致可以猜出:

DEFAULT_CAPACITY = 10; ---  默认容量 为10 

size   ----相当于上述我们定义的usedSize, 数组中使用的个数

其他的我们往下看:

3. ArrayList的构造方法

a. 带有一个容量参数的构造方法

b. 不带参数的构造方法

 c. 带有一个接口参数的构造方法

 ① Collection< ? extends E> 代表参数的类型

      c 代表变量

②Collection是一个接口

意味着下面的具体类都能用Collection接收

③< ? extends E>   ? 是一个通配符, 意味着传入的参数必须是E类型或E的子类类型, E表示的是原ArrayList中的参数类型

 举例:

这个构造方法的意义是: 利用另一个集合, 构造当前集合 

例:

结果为:

 也可对其进行操作:

 补充: 

1. 第一次add时, 分配了内存, 大小为10 

2. 当空间不足时需扩容, 以1.5倍扩容, 意味着第二次容量应为15

 4. ArrayList常见的方法

我们来详细了解一下subList方法:

 

当我们修改list的值, 发现:

 arrayList1的值也被修改了.

实际上, subList方法, 截取时, 不是产生了新的对象, 只是指向了原顺序表的某个下标.

2.4 ArrayList的遍历

第一种:for循环

// 使用下标 +for 遍历
for ( int i = 0 ; i < arrayL ist . size (); i ++ ) {
        System . out . print (arrayL ist . get ( i ) + " " );
}

 第二种: for-each

// 借助 foreach 遍历
for ( Integer x   : arrayList ) {
        System . out . print ( integer + " " );
}
System . out . println ();

第三种: 使用迭代器

可以使用迭代器的原因是: 继承了Iterable接口

从前往后: 

Iterator < Integer > it = arrayList .iterator ();
while ( it . hasNext ()){
        System . out . print ( it . next () + " " );
}

或

ListIterator < Integer > it = arrayList .l istIterator ();
while ( it . hasNext ()){
        System . out . print ( it . next () + " " );
}

注: ListIterator是Iterator的子类

 从后往前:

ListIterator < Integer > it = arrayList .l istIterator ();
while ( it . hasPrevious ()){
        System . out . print ( it .previous () + " " );
}

 2.5 ArrayList的扩容机制

源码了解即可, 就不在这里展示

【 总结 】
1. 检测是否真正需要扩容，如果是调用 grow 准备扩容
2. 预估需要扩容的大小
初步预估按照 1.5 倍大小扩容
如果用户所需大小超过预估 1.5 倍大小，则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用 copyOf 进行扩容

面试题:

给出两个字符串, 将字符串1中的和字符串2相同的字符删掉, 例:  str1 = "welcome to cvte" str2 = "come"

思路: 遍历str1, 判断此字符是否出现在str2中, 若没出现, 将此字符串存到顺序表中.

2.6 二维顺序表

 语法结构:

List<List<Integer>> ret = new ArrayList<>();

画图理解:

 添加元素:

实例:

 杨辉三角

思路:

1. 每一行的第一个数字和最后一个数是1 

2. 每一行中间的数字 假设这个数字在[ i ][ j ]位置, 那么[ i ][ j ] = [ i -1 ][ j ] +[ i -1 ][ j -1 ]

首先定义一个二维顺序表, 先将第一个数和最后一个数加入

public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();for (int i = 0; i < numRows; i++) {List<Integer> list = new ArrayList<>();//1. 第一个元素设为1list.add(1);//2. 中间元素//3. 最后一个元素设为1list.add(1);ret.set(i,list);}}

 中间元素, 首先我们要创建列下标, 并找到第i-1行, 进行[ i ][ j ] = [ i -1 ][ j ] +[ i -1 ][ j -1 ]

 public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();List<Integer> list = new ArrayList<>();list.add(1);ret.add(list);for (int i = 1; i < numRows; i++) {List<Integer> curList = new ArrayList<>();//1. 第一个元素设为1curList.add(1);//2. 中间元素for (int j = 1; j < i; j++) {List<Integer> prevList = ret.get(i-1);int x = prevList.get(j-1)+prevList.get(j);prevList.add(x);}//3. 最后一个元素设为1curList.add(1);ret.add(curList);}return ret;}

 2.7 ArrayList的使用

简单的洗牌算法

(一副扑克牌, 不包含大小王, 共4个花色, 13个数字 )

首先我们要创建一个牌对象Card, 并提供构造方法, 重写toString方法

public class Card {public String suit;//花色public int rank;//数字@Overridepublic String toString() {return "Card{" +"suit='" + suit + '\'' +", rank=" + rank +'}';//若不想要本方法打印输出, 可以自定义,如:
//  return suit+rank+" ";}public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}
}

 

下面创建一个CardGame类, 来实现对牌的操作

public class CardGame {public static final String[] suits = {"♠","♥","♣","♦"};}

 

再创建一个Main类, 用来放main方法, 进行运行测试代码

public class Main {public static void main(String[] args) {}
}

 

下面实现一个买牌的操作, 即创建一副扑克牌

 //CardGame
public List<Card> butCard(){List<Card> cardList = new ArrayList<>();//创建一个顺序表用来存放Card,构成一副牌for (int i = 0; i < 4; i++) {//四个花色for (int j = 1; j <= 13; j++) {//13个数字String suit = suits[i];Card card = new Card(suit,j);//实例化一张牌cardList.add(card);//添加到顺序表中}}return cardList;}

 

下面实现一个洗牌的操作, 通过交换的方式, 每一个下标的数据和其他下标的数据进行交换

生成0~100的随机数(不包括100)

   Random random = new Random();int index = random.nextInt(100);
 public void shuffle(List<Card> cardList){Random random = new Random();for (int i = cardList.size()-1; i > 0; i--) {
//从后往前遍历, 让i位置和0~i的随机数位置进行交换数据int index = random.nextInt(i);swap(cardList, i,index);}}private static void swap(List<Card> cardList,int i,int j ){Card tmp = cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}

 

 下面实现一个抓牌的操作, 共三个人, 轮流抓牌, 每人抓5张

可以用二维顺序表来实现, 定义一个person顺序表, 共三个数据, 每个数据指向一个CardList

public List<List<Card>> getCard(List<Card> cardList){List<Card> person1 = new ArrayList<>();List<Card> person2 = new ArrayList<>();List<Card> person3 = new ArrayList<>();List<List<Card>> person = new ArrayList<>();person.add(person1);person.add(person2);person.add(person3);for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {Card card = cardList.remove(0);//没抓一张牌代表删去顺序表的第一个数据person.get(j).add(card);}}return person;}

完整代码+实现:

//Card.java
public class Card {public String suit;//花色public int rank;//数字@Overridepublic String toString() {/* return "Card{" +"suit='" + suit + '\'' +", rank=" + rank +'}';*/return suit+rank+" ";}public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}
}//CardGame.java
public class CardGame {public static final String[] suits = {"♠","♥","♣","♦"};public List<Card> butCard(){List<Card> cardList = new ArrayList<>();for (int i = 0; i < 4; i++) {for (int j = 1; j <= 13; j++) {String suit = suits[i];Card card = new Card(suit,j);cardList.add(card);// cardList.add(new Card(suits[i],j));  匿名对象}}return cardList;}public void shuffle(List<Card> cardList){Random random = new Random();for (int i = cardList.size()-1; i > 0; i--) {int index = random.nextInt(i);swap(cardList, i,index);}}private static void swap(List<Card> cardList,int i,int j ){Card tmp = cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}public List<List<Card>> getCard(List<Card> cardList){List<Card> person1 = new ArrayList<>();List<Card> person2 = new ArrayList<>();List<Card> person3 = new ArrayList<>();List<List<Card>> person = new ArrayList<>();person.add(person1);person.add(person2);person.add(person3);for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {Card card = cardList.remove(0);person.get(j).add(card);}}return person;}
}//Main.java
public class Main {public static void main(String[] args) {CardGame cardGame = new CardGame();List<Card> ret =  cardGame.butCard();System.out.println("买牌:");System.out.println(ret);System.out.println("洗牌:");cardGame.shuffle(ret);System.out.println(ret);System.out.println("抓牌:");List<List<Card>> person = cardGame.getCard(ret);for (int i = 0; i < person.size(); i++) {System.out.println("person"+(i+1)+":"+ person.get(i));}System.out.println("剩余的牌:"+ret);}
}

这篇关于顺序表及应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/528793。

相关文章

Java Stream 的 Collectors.toMap高级应用与最佳实践

Java Stream 的 Collectors.toMap高级应用与最佳实践

《JavaStream的Collectors.toMap高级应用与最佳实践》文章讲解JavaStreamAPI中Collectors.toMap的使用,涵盖基础语法、键冲突处理、自定义Map... 目录一、基础用法回顾二、处理键冲突三、自定义 Map 实现类型四、处理 null 值五、复杂值类型转换六、处理
阅读更多...
分布式锁在Spring Boot应用中的实现过程

分布式锁在Spring Boot应用中的实现过程

《分布式锁在SpringBoot应用中的实现过程》文章介绍在SpringBoot中通过自定义Lock注解、LockAspect切面和RedisLockUtils工具类实现分布式锁,确保多实例并发操作... 目录Lock注解LockASPect切面RedisLockUtils工具类总结在现代微服务架构中，分布
阅读更多...
Python标准库之数据压缩和存档的应用详解

Python标准库之数据压缩和存档的应用详解

《Python标准库之数据压缩和存档的应用详解》在数据处理与存储领域,压缩和存档是提升效率的关键技术,Python标准库提供了一套完整的工具链,下面小编就来和大家简单介绍一下吧... 目录一、核心模块架构与设计哲学二、关键模块深度解析1.tarfile：专业级归档工具2.zipfile：跨平台归档首选3.
阅读更多...
使用IDEA部署Docker应用指南分享

使用IDEA部署Docker应用指南分享

《使用IDEA部署Docker应用指南分享》本文介绍了使用IDEA部署Docker应用的四步流程：创建Dockerfile、配置IDEADocker连接、设置运行调试环境、构建运行镜像,并强调需准备本... 目录一、创建 dockerfile 配置文件二、配置 IDEA 的 Docker 连接三、配置 Do
阅读更多...
深入浅出SpringBoot WebSocket构建实时应用全面指南

深入浅出SpringBoot WebSocket构建实时应用全面指南

《深入浅出SpringBootWebSocket构建实时应用全面指南》WebSocket是一种在单个TCP连接上进行全双工通信的协议,这篇文章主要为大家详细介绍了SpringBoot如何集成WebS... 目录前言为什么需要 WebSocketWebSocket 是什么Spring Boot 如何简化 We
阅读更多...
Java Stream流之GroupBy的用法及应用场景

Java Stream流之GroupBy的用法及应用场景

《JavaStream流之GroupBy的用法及应用场景》本教程将详细介绍如何在Java中使用Stream流的groupby方法,包括基本用法和一些常见的实际应用场景,感兴趣的朋友一起看看吧... 目录Java Stream流之GroupBy的用法1. 前言2. 基础概念什么是 GroupBy？Stream
阅读更多...
python中列表应用和扩展性实用详解

python中列表应用和扩展性实用详解

《python中列表应用和扩展性实用详解》文章介绍了Python列表的核心特性：有序数据集合,用[]定义,元素类型可不同,支持迭代、循环、切片,可执行增删改查、排序、推导式及嵌套操作,是常用的数据处理... 目录1、列表定义2、格式3、列表是可迭代对象4、列表的常见操作总结1、列表定义是处理一组有序项目的
阅读更多...
C#中的Converter的具体应用

C#中的Converter的具体应用

《C#中的Converter的具体应用》C#中的Converter提供了一种灵活的类型转换机制,本文详细介绍了Converter的基本概念、使用场景,具有一定的参考价值,感兴趣的可以了解一下... 目录Converter的基本概念1. Converter委托2. 使用场景布尔型转换示例示例1：简单的字符串到
阅读更多...
Spring Boot Actuator应用监控与管理的详细步骤

Spring Boot Actuator应用监控与管理的详细步骤

《SpringBootActuator应用监控与管理的详细步骤》SpringBootActuator是SpringBoot的监控工具,提供健康检查、性能指标、日志管理等核心功能,支持自定义和扩展端... 目录一、 Spring Boot Actuator 概述二、 集成 Spring Boot Actuat
阅读更多...
PyTorch中的词嵌入层(nn.Embedding)详解与实战应用示例

PyTorch中的词嵌入层(nn.Embedding)详解与实战应用示例

《PyTorch中的词嵌入层(nn.Embedding)详解与实战应用示例》词嵌入解决NLP维度灾难,捕捉语义关系,PyTorch的nn.Embedding模块提供灵活实现,支持参数配置、预训练及变长... 目录一、词嵌入(Word Embedding)简介为什么需要词嵌入？二、PyTorch中的nn.Em
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2