当前位置： 首页 > article >正文

Java数据结构---顺序表

article 2024/10/22 19:49:40

目录

一、线性表

二、顺序表

2.1、顺序表的定义

 2.2、顺序表的接口实现

三、ArrayList

3.1、 ArrayList简介

3.2、ArrayList的实现 

3.3、ArrayList实现的完整代码

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。  

二、顺序表

2.1、顺序表的定义

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

 2.2、顺序表的接口实现

public interface List {
    // 新增元素,默认在数组最后新增
    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 位置的元素设为 value
    public void set(int pos, int value);
    //删除第一次出现的关键字key
    public void remove(int toRemove);
    // 获取顺序表长度
    public int size();
    // 清空顺序表
    public void clear();
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display();
    //判断数组是否满了
    public boolean isFulled();
}

三、ArrayList

3.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底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

3.2、ArrayList的实现 

在实现顺序表之前，我们要先定义一个数组、一个整型变量和一个构造方法：

    public int[] als;
    public int usedSize;
    public MyArrayList() {
        this.als =new int[10];
    }

 

//新增一个元素，默认在数组最后新增
//新增一个元素，默认在数组最后新增
    @Override
    public void add(int data) {
        if(isFulled()){
            reSize();
        }
        als[usedSize]=data;
        usedSize++;
    }
//判断顺序表是否已满
//判断顺序表是否已满
    @Override
    public boolean isFulled() {
        return usedSize==als.length;
    }
    //若顺序表已满，进行扩容
    private void reSize(){
        als= Arrays.copyOf(als,2*als.length);
    }
//在pos位置新增元素data
//在pos位置新增元素data
    @Override
    public void add(int pos, int data) {
        if(pos<=usedSize&&pos>=0){
            if(isFulled()){
                reSize();
            }
            for(int i=usedSize-1;i>=pos;i--){
                als[i+1]=als[i];
            }
            als[pos]=data;
            usedSize++;
        }else{
            throw new PosOutOfException("数据不合法");//该异常为我自身设定，各位使用时需另外设定
        }
    }

 异常设置的代码：

public class PosOutOfException extends RuntimeException{
    public PosOutOfException(String message) {
        super(message);
    }
}

//判断是否包含元素toFind
//判断是否包含元素toFind
    @Override
    public boolean contains(int toFind) {
        for(int i=0;i<usedSize;i++){
            if(als[i]==toFind){
                return true;
            }
        }
        return false;
    }

//查找某个元素对应的位置,如果未找到，返回-1
//查找某个元素对应的位置,如果未找到，返回-1
    @Override
    public int indexOf(int toFind) {
        int num=-1;
        for(int i=0;i<usedSize;i++){
            if(als[i]==toFind){
                num=i;
                break;
            }
        }
        return num;
    }
// 获取 pos 位置的元素
// 获取 pos 位置的元素
    @Override
    public int get(int pos) {
        if(pos>=0&&pos<usedSize){
            return als[pos];
        }else{
            throw new PosOutOfException("pos位置不合法");
        }
    }
// 给 pos 位置的元素设为 value
// 给 pos 位置的元素设为 value
    @Override
    public void set(int pos, int value) {
        if(pos>=0&&pos<usedSize){
            als[pos]=value;
        }else{
            throw new PosOutOfException("pos位置不合法");
        }
    }

 

//删除第一次出现的关键字toRemove
//删除第一次出现的关键字toRemove
    @Override
    public void remove(int toRemove) {
        int index=indexOf(toRemove);
        if(index==-1){
            return;
        }
        for(int i=index;i<usedSize-1;i++){
            als[i]=als[i+1];
        }
        usedSize--;
    }
// 获取顺序表长度
// 获取顺序表长度
    @Override
    public int size() {
        return this.usedSize;
    }
// 清空顺序表
// 清空顺序表
    @Override
    public void clear() {
        usedSize=0;
    }
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    @Override
    public void display() {
        for(int i=0;i<usedSize;i++){
            System.out.print(als[i]+" ");
        }
    }

注意：调用方法时用“.”来调用，以下以display()为例：

 

public class Main {
    public static void main(String[] args) {
        MyArrayList myArrayList=new MyArrayList();
        myArrayList.add(1);
        myArrayList.add(2);
        myArrayList.add(66);
        myArrayList.display();
    }
}

结果如下：

 

 

3.3、ArrayList实现的完整代码

import java.util.Arrays;

public class MyArrayList implements List{
    public int[] als;
    public int usedSize;
    public MyArrayList() {
        this.als =new int[10];
    }
    //新增一个元素，默认在数组最后新增
    @Override
    public void add(int data) {
        if(isFulled()){
            reSize();
        }
        als[usedSize]=data;
        usedSize++;
    }
    //判断顺序表是否已满
    @Override
    public boolean isFulled() {
        return usedSize==als.length;
    }
    //若顺序表已满，进行扩容
    private void reSize(){
        als= Arrays.copyOf(als,2*als.length);
    }
    //在pos位置新增元素data
    @Override
    public void add(int pos, int data) {
        if(pos<=usedSize&&pos>=0){
            if(isFulled()){
                reSize();
            }
            for(int i=usedSize-1;i>=pos;i--){
                als[i+1]=als[i];
            }
            als[pos]=data;
            usedSize++;
        }else{
            throw new PosOutOfException("数据不合法");//该异常为我自身设定，各位使用时需另外设定
        }
    }
    //判断是否包含元素toFind
    @Override
    public boolean contains(int toFind) {
        for(int i=0;i<usedSize;i++){
            if(als[i]==toFind){
                return true;
            }
        }
        return false;
    }
    //查找某个元素对应的位置,如果未找到，返回-1
    @Override
    public int indexOf(int toFind) {
        int num=-1;
        for(int i=0;i<usedSize;i++){
            if(als[i]==toFind){
                num=i;
                break;
            }
        }
        return num;
    }
    // 获取 pos 位置的元素
    @Override
    public int get(int pos) {
        if(pos>=0&&pos<usedSize){
            return als[pos];
        }else{
            throw new PosOutOfException("pos位置不合法");
        }
    }
    // 给 pos 位置的元素设为 value
    @Override
    public void set(int pos, int value) {
        if(pos>=0&&pos<usedSize){
            als[pos]=value;
        }else{
            throw new PosOutOfException("pos位置不合法");
        }
    }
    //删除第一次出现的关键字toRemove
    @Override
    public void remove(int toRemove) {
        int index=indexOf(toRemove);
        if(index==-1){
            return;
        }
        for(int i=index;i<usedSize-1;i++){
            als[i]=als[i+1];
        }
        usedSize--;
    }
    // 获取顺序表长度
    @Override
    public int size() {
        return this.usedSize;
    }
    // 清空顺序表
    @Override
    public void clear() {
        usedSize=0;
    }
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    @Override
    public void display() {
        for(int i=0;i<usedSize;i++){
            System.out.print(als[i]+" ");
        }
    }
}

 以上便是本篇文章的全部内容，感谢大家的支持！下期见~~~

 

 

 

 

 

 

 


http://www.kler.cn/news/360576.html

相关文章：

  • vue3纯前端验证码示例
  • 初识Flink
  • 【MM2024】面向 StableDiffusion 的多目标图像编辑算法 VICTORIA
  • Rust的泛型基础与实践
  • Linux: network: tcp:__sk_mem_raise_allocated；确保公平
  • 6 卷积神经网络
  • 深度学习：可解释人工智能（Explainable AI，XAI）
  • 视频去字幕软件哪个好，新手无痕去水印方案
  • 微调小型Llama 3.2（十亿参数）模型取代GPT-4o
  • 基于微信小程序的家政服务管理系统
  • 【云原生kubernetes系列--coredns篇】
  • vue3中el-select v-model=““给v-model默认值一些注意事项；
  • 离散数学实验三c语言(判断运算的性质：封闭性、可结合性、可交换性、幺元、零元、逆元、计算元素的阶、判断是否为特殊的代数系统)
  • 【多模态】CLIP模型技术学习
  • Python教程：Python父类方法重写
  • vue多选框组件
  • 毕业设计—基于 Inception-ResNet模型的皮肤癌分类系统实现
  • JAVA Maven的简单介绍
  • 句柄是什么？有什么用？举例说明
  • opencv彩色图像拷贝加速