顺序表及应用

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。

相关文章

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
阅读更多...
将Python应用部署到生产环境的小技巧分享

将Python应用部署到生产环境的小技巧分享

《将Python应用部署到生产环境的小技巧分享》文章主要讲述了在将Python应用程序部署到生产环境之前,需要进行的准备工作和最佳实践,包括心态调整、代码审查、测试覆盖率提升、配置文件优化、日志记录完... 目录部署前夜：从开发到生产的心理准备与检查清单环境搭建：打造稳固的应用运行平台自动化流水线：让部署像
阅读更多...
Linux中Curl参数详解实践应用

Linux中Curl参数详解实践应用

《Linux中Curl参数详解实践应用》在现代网络开发和运维工作中,curl命令是一个不可或缺的工具,它是一个利用URL语法在命令行下工作的文件传输工具,支持多种协议,如HTTP、HTTPS、FTP等... 目录引言一、基础请求参数1. -X 或 --request2. -d 或 --data3. -H 或
阅读更多...
在Ubuntu上部署SpringBoot应用的操作步骤

在Ubuntu上部署SpringBoot应用的操作步骤

《在Ubuntu上部署SpringBoot应用的操作步骤》随着云计算和容器化技术的普及,Linux服务器已成为部署Web应用程序的主流平台之一,Java作为一种跨平台的编程语言,具有广泛的应用场景,本... 目录一、部署准备二、安装 Java 环境1. 安装 JDK2. 验证 Java 安装三、安装 mys
阅读更多...
Python中构建终端应用界面利器Blessed模块的使用

Python中构建终端应用界面利器Blessed模块的使用

《Python中构建终端应用界面利器Blessed模块的使用》Blessed库作为一个轻量级且功能强大的解决方案,开始在开发者中赢得口碑,今天,我们就一起来探索一下它是如何让终端UI开发变得轻松而高... 目录一、安装与配置：简单、快速、无障碍二、基本功能：从彩色文本到动态交互1. 显示基本内容2. 创建链
阅读更多...
JAVA利用顺序表实现“杨辉三角”的思路及代码示例

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...
Node.js 中 http 模块的深度剖析与实战应用小结

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器：基石搭建（一
阅读更多...
java中VO PO DTO POJO BO DO对象的应用场景及使用方式

java中VO PO DTO POJO BO DO对象的应用场景及使用方式

《java中VOPODTOPOJOBODO对象的应用场景及使用方式》文章介绍了Java开发中常用的几种对象类型及其应用场景,包括VO、PO、DTO、POJO、BO和DO等,并通过示例说明了它... 目录Java中VO PO DTO POJO BO DO对象的应用VO (View Object) - 视图对象
阅读更多...
Go信号处理如何优雅地关闭你的应用

Go信号处理如何优雅地关闭你的应用

《Go信号处理如何优雅地关闭你的应用》Go中的优雅关闭机制使得在应用程序接收到终止信号时,能够进行平滑的资源清理,通过使用context来管理goroutine的生命周期,结合signal... 目录1. 什么是信号处理？2. 如何优雅地关闭 Go 应用？3. 代码实现3.1 基本的信号捕获和优雅关闭3.2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2