顺序表及应用

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逻辑运算符之&&、|| 与&、 |的区别及应用

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》：本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与：&& 与 & 的区别1. &&：短路与（AND）2. &：非短
阅读更多...
Spring AI集成DeepSeek三步搞定Java智能应用的详细过程

Spring AI集成DeepSeek三步搞定Java智能应用的详细过程

《SpringAI集成DeepSeek三步搞定Java智能应用的详细过程》本文介绍了如何使用SpringAI集成DeepSeek,一个国内顶尖的多模态大模型,SpringAI提供了一套统一的接口,简... 目录DeepSeek 介绍Spring AI 是什么？Spring AI 的主要功能包括1、环境准备2
阅读更多...
Spring AI与DeepSeek实战一之快速打造智能对话应用

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav
阅读更多...
MobaXterm远程登录工具功能与应用小结

MobaXterm远程登录工具功能与应用小结

《MobaXterm远程登录工具功能与应用小结》MobaXterm是一款功能强大的远程终端软件,主要支持SSH登录,拥有多种远程协议,实现跨平台访问,它包括多会话管理、本地命令行执行、图形化界面集成和... 目录1. 远程终端软件概述1.1 远程终端软件的定义与用途1.2 远程终端软件的关键特性2. 支持的
阅读更多...
Python中顺序结构和循环结构示例代码

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

《Python中顺序结构和循环结构示例代码》：本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句（1）条件语句的定义（2）条件语句的语法（a）单分支 if（b）双分支 if-else（
阅读更多...
关于Spring @Bean 相同加载顺序不同结果不同的问题记录

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

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

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
5分钟获取deepseek api并搭建简易问答应用

5分钟获取deepseek api并搭建简易问答应用

《5分钟获取deepseekapi并搭建简易问答应用》本文主要介绍了5分钟获取deepseekapi并搭建简易问答应用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需... 目录1、获取api2、获取base_url和chat_model3、配置模型参数方法一：终端中临时将加
阅读更多...
JavaScript中的isTrusted属性及其应用场景详解

JavaScript中的isTrusted属性及其应用场景详解

《JavaScript中的isTrusted属性及其应用场景详解》在现代Web开发中,JavaScript是构建交互式应用的核心语言,随着前端技术的不断发展,开发者需要处理越来越多的复杂场景,例如事件... 目录引言一、问题背景二、isTrusted 属性的来源与作用1. isTrusted 的定义2. 为
阅读更多...
Python调用另一个py文件并传递参数常见的方法及其应用场景

Python调用另一个py文件并传递参数常见的方法及其应用场景

《Python调用另一个py文件并传递参数常见的方法及其应用场景》：本文主要介绍在Python中调用另一个py文件并传递参数的几种常见方法,包括使用import语句、exec函数、subproce... 目录前言1. 使用import语句1.1 基本用法1.2 导入特定函数1.3 处理文件路径2. 使用ex
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2