顺序表及应用

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。

相关文章

CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比

CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比

《CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比》CSS中的position属性用于控制元素的定位方式，不同的定位方式会影响元素在页面中的布... css 中的 position 属性用于控制元素的定位方式，不同的定位方式会影响元素在页面中的布局和层叠关
阅读更多...
SpringBoot3应用中集成和使用Spring Retry的实践记录

SpringBoot3应用中集成和使用Spring Retry的实践记录

《SpringBoot3应用中集成和使用SpringRetry的实践记录》SpringRetry为SpringBoot3提供重试机制,支持注解和编程式两种方式,可配置重试策略与监听器,适用于临时性故... 目录1. 简介2. 环境准备3. 使用方式3.1 注解方式 基础使用自定义重试策略失败恢复机制注意事项
阅读更多...
Java中JSON格式反序列化为Map且保证存取顺序一致的问题

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

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

Python使用Tkinter打造一个完整的桌面应用

《Python使用Tkinter打造一个完整的桌面应用》在Python生态中,Tkinter就像一把瑞士军刀,它没有花哨的特效,却能快速搭建出实用的图形界面,作为Python自带的标准库,无需安装即可... 目录一、界面搭建：像搭积木一样组合控件二、菜单系统：给应用装上“控制中枢”三、事件驱动：让界面“活”
阅读更多...
如何确定哪些软件是Mac系统自带的? Mac系统内置应用查看技巧

如何确定哪些软件是Mac系统自带的? Mac系统内置应用查看技巧

《如何确定哪些软件是Mac系统自带的?Mac系统内置应用查看技巧》如何确定哪些软件是Mac系统自带的？mac系统中有很多自带的应用，想要看看哪些是系统自带，该怎么查看呢？下面我们就来看看Mac系统内... 在MAC电脑上，可以使用以下方法来确定哪些软件是系统自带的：1.应用程序文件夹打开应用程序文件夹
阅读更多...
Python Flask 库及应用场景

Python Flask 库及应用场景

《PythonFlask库及应用场景》Flask是Python生态中​轻量级且高度灵活的Web开发框架,基于WerkzeugWSGI工具库和Jinja2模板引擎构建,下面给大家介绍PythonFl... 目录一、Flask 库简介二、核心组件与架构三、常用函数与核心操作 ​1. 基础应用搭建​2. 路由与参
阅读更多...
Spring Boot中的YML配置列表及应用小结

Spring Boot中的YML配置列表及应用小结

《SpringBoot中的YML配置列表及应用小结》在SpringBoot中使用YAML进行列表的配置不仅简洁明了,还能提高代码的可读性和可维护性,：本文主要介绍SpringBoot中的YML配... 目录YAML列表的基础语法在Spring Boot中的应用从YAML读取列表列表中的复杂对象其他注意事项总
阅读更多...
电脑系统Hosts文件原理和应用分享

电脑系统Hosts文件原理和应用分享

《电脑系统Hosts文件原理和应用分享》Hosts是一个没有扩展名的系统文件，当用户在浏览器中输入一个需要登录的网址时，系统会首先自动从Hosts文件中寻找对应的IP地址，一旦找到，系统会立即打开对应... Hosts是一个没有扩展名的系统文件，可以用记事本等工具打开，其作用就是将一些常用的网址域名与其对应
阅读更多...
CSS 样式表的四种应用方式及css注释的应用小结

CSS 样式表的四种应用方式及css注释的应用小结

《CSS样式表的四种应用方式及css注释的应用小结》：本文主要介绍了CSS样式表的四种应用方式及css注释的应用小结，本文通过实例代码给大家介绍的非常详细，详细内容请阅读本文，希望能对你有所帮助... 一、外部 css（推荐方式）定义：将 CSS 代码保存为独立的 .css 文件，通过 <link> 标签
阅读更多...
Python使用Reflex构建现代Web应用的完全指南

Python使用Reflex构建现代Web应用的完全指南

《Python使用Reflex构建现代Web应用的完全指南》这篇文章为大家深入介绍了Reflex框架的设计理念,技术特性,项目结构,核心API,实际开发流程以及与其他框架的对比和部署建议,感兴趣的小伙... 目录什么是 ReFlex？为什么选择 Reflex？安装与环境配置构建你的第一个应用核心概念解析组件
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2