Java数据结构顺序表的详细讲解

目录
  • 写在前面
  • 1.线性表
  • 2.顺序表的实现
    • 2.1增加数据
      • 2.1.1尾部增加数据
      • 2.1.2任意位置增加数据
    • 2.2查找数据
    • 2.3删除数据
    • 2.4修改数据
  • 3.ArrayList
    • 3.1ArrayList的实例化
    • 3.2ArrayList常用的方法

写在前面

关于数据结构,Java官方其实已经帮我们写好并封装起来了,在真正需要使用的时候直接调用即可,但为了更好的理解数据结构,我会按照源码的思路写一个简化后的数据结构,默认接收的数据为int

1.线性表

线性表是多个具有相同特性的数据元素的序列,线性表在逻辑上是一条连续的直线,但在实际存储上却不一定

顺序表则是线性表的一种,是用一段物理地址连续的存储单元依次存储数据元素的线性结构,通常是使用数组来实现

2.顺序表的实现

新建一个类叫做ArrList,顺序表的底层是数组,所以类里面也要有数组,其次还需要一个计数器来判断数组目前使用的空间是多少,那么顺序表的框架就完成了

public class ArrList {
    public int[] arr;
    public int count;
    public ArrList() {
        this.arr = new int[5];  //初始给5个大小空间
    }
}

接下来就是顺序表的增删改查等操作了

2.1增加数据

增加数据有两个方法:末尾增加数据和任意位置增加数据

2.1.1尾部增加数据

在这之前需要进行的一项工作是判断顺序表的空间是否已满,如果空间已满的话需要进行扩容,判断顺序表空间是否已满的依据是计数器的值和数组的长度是否相等

public boolean isFull() {
        return this.count==this.arr.length;
    }
public void tailAdd(int data) {
        //首先判断顺序表是否已满
        if(isFull()) {
            //顺序表已满,需要扩容,这里是扩大为原来的两倍
            this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
        }
        //程序走到这,不管有没有扩容,此时顺序表都是未满,直接添加数据
        this.arr[this.count]=data;
        this.count++;
    }

2.1.2任意位置增加数据

任意位置添加数据的话首先要判断输入的值是否是合法的,有一点要注意:如果输入的值和计数器的值是相等的,那么此时就是在顺序表末尾添加数据,这个数是合法的

public void add(int index,int data) {
        //首先需要判断index的值是否合法,不合法直接抛出异常
        if(index<0||index>this.count) {
            throw new ArrayIndexOutOfBoundsException("位置非法");
        }
        if(isFull()) {
            //顺序表已满,需要扩容
            this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
        }
        if(index==this.count) {
            this.arr[this.count]=data;
            this.count++;
        } else {
            //中间位置添加数据需要先把从此处开始到末尾的数据都往后移动一位,从后往前移
            for (int i = this.count-1; i >=index ; i--) {
                this.arr[i+1]=this.arr[i];
            }
            this.arr[index]=data;
            this.count++;
        }
    }

2.2查找数据

输入一个值,遍历顺序表进行查找,有则返回下标,没有返回-1

public int find (int data) {
       for (int i = 0; i < this.count; i++) {
            if(this.arr[i]==data) {
                return i;
            }
        }
        return -1;
    }

之所以返回值是int而不是boolean是因为后面的删除和修改数据的方法会使用到此方法

2.3删除数据

找到要删除的值的下标,从此处开始用后面的值对前面的值进行覆盖,最后将尾部的值改为0

public void delData(int data) {
        int i=find(data);
        if(i!=-1) {
            for (int j = i; j <this.count-1 ; j++) {
                this.arr[j]=this.arr[j+1];
            }
            this.count--;
            this.arr[this.count]=0;
        }
    }

2.4修改数据

修改指定位置的值,依旧首先要判断位置是否合法

public void setIndex (int index,int data) {
        if(index<0||index>=this.count) {
            throw new ArrayIndexOutOfBoundsException("位置非法");
        }
        this.arr[index]=data;
    }

最后是销毁顺序表,不需要吧数组进行销毁,否则下次使用的时候还需要再实例化一个对象,只需要让计数器为0即可

public void clear () {
        this.count=0;
    }

3.ArrayList

Java中的顺序表叫做ArrayList,这是一个泛型类,这个类继承了多个其它类以及接口,其中包括List接口,List提供了很多抽象方法,ArrayList实现此接口对这些方法进行重写

3.1ArrayList的实例化

ArrayList有三种构造方法

ArrayList() 无参构造
ArrayList(Collection<? extends E> c) 利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity) 指定顺序表初始容量

要说明的是:调用无参数构造方法,默认数组的大小为0,之后在调用里面的方法(比如add方法)的时候会有专门的扩容的方法将其扩容为10,之后如果数组满了的话扩容为之前的1.5倍(源码里面套的方法太多就不展示了)

3.2ArrayList常用的方法


boolean add(E e)


尾插


void add(int index, E element)


将元素插入到 index 位置


boolean addAll(Collection<? extends E> c)


尾插 c 中的元素


E remove(int index)


删除 index 位置元素


boolean remove(Object o)


删除遇到的第一个指定的值


E get(int index)


获取下标 index 位置元素


E set(int index, E element)


修改下标 index 位置的元素


void clear()


销毁顺序表


boolean contains(Object o)


判断指定元素是否在表中


int indexOf(Object o)


返回第一个指定元素所在下标


int lastIndexOf(Object o)


返回最后一个指定元素的下标


List<E> subList(int fromIndex, int toIndex)


截取指定部分的元素

最后的截取方法是在原数组上进行截取

到此这篇关于Java数据结构顺序表的详细讲解的文章就介绍到这了,更多相关Java顺序表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java 精炼解读数据结构的顺序表如何操作

    目录 前言 一.什么是顺序表 顺序表的概念及结构 创建顺序表 获取顺序表长度 在pos位置新增元素 判定是否包含某个元素 查找某个元素对应的位置 获取pos位置的元素 给pos位置的元素设为value 删除你想要删除的元素 总结: 前言 线性表(linear list)是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见 的线性表:顺序表.链表.栈.队列.字符串... 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构上并不一定是连续的,线性表在物

  • Java实现顺序表的操作

    本文实例为大家分享了Java实现顺序表的基本操作,供大家参考,具体内容如下 静态顺序表:使用定长数组存储.动态顺序表:使用动态开辟的数组存储. 接口 package com.github.sqlist; public interface ISequence {     // 在 pos 位置插入 val     boolean add(int pos, Object data);     // 查找关键字 key 找到返回 key 的下表,没有返回 -1     int search(Objec

  • Java 顺序表专题解读

    目录 一 .前言 二.顺序的定义 三.实现顺序表 3.1顺序表的API设计 3.2 顺序表的代码实现 插入示意图 : 3.3完整的API概览: 四.顺序表的测试: 一 .前言 顺序表常用的一种,学习并了解显得十分重要,顺序表为以后的学习打下了基石. 二.顺序的定义 顺序表示在计算机内存中以数组的形式保存的线性表,在内存中占用一组连续的存储 单元,在此中依次存储各个元素. 三.实现顺序表 3.1顺序表的API设计 3.2 顺序表的代码实现 定义一个泛型类(泛型类的好处就是可以接受任意类型) //定

  • Java数据结构之顺序表和链表精解

    目录 前言 1. 顺序表 代码实现 2. 链表 链表图解 代码实现 前言 两个数据结构:顺序表和链表 数据结构是一门学科,和语言无关. 数据 + 结构:一种描述和组织数据的方式. 1. 顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删查改.其逻辑上和物理上都是连续的. 问题引入:一个数组放在这,我们如何才能自己不去数,让程序自己进行计数? 答:在引入变量,每次放一个元素就更新一次.(如下图,为问题的示意) 也就是说顺序表的底层

  • Java实现顺序表和链表结构

    目录 前言: 顺序表 定义: 实现方法: 代码实现: 链表 定义: 分类: 实现方法: 代码实现: 顺序表 & 链表 总结 前言: 线性表(linear list)是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表.链表.栈.队列.字符串. 顺序表 定义: 用一段物理地址连续的存储单元依次存储数据元素的线性结构(逻辑上连续,物理上也连续) (1)静态顺序表:使用定长数组存储. (2)动态顺序表:使用动态开辟的数组存储 [注意]静态顺序表的定长数

  • Java数据结构顺序表从零基础到精通进阶

    目录 一.什么是线性表 二.顺序表 三.手撕顺序表 属性定义 构造方法 接口实现 确保顺序表空间 增加元素 打印顺序表 判断顺序表中是否包含某个元素 查找元素 获取 pos 位置的元素 将 pos 位置的元素值设为 value 删除第一次出现的关键字key 获取顺序表长度 清空顺序表 删除所有的key 一.什么是线性表 线性表是最基本.最简单.也是最常用的一种数据结构.线性表*(linear list)*是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列.常见的线性表有顺序表,链

  • Java数据结构之顺序表篇

    目录 一.线性表 二.顺序表 1.概念及结构 2.顺序表的实现 打印顺序表 获取顺序表的有效长度 在pos位置新增元素 判断是否包含某个元素 查找某个元素对应的位置 获取/查找pos位置的元素 给pos位置的元素设为value 删除第一次出现的关键字key 清空顺序表 3.顺序表的优.缺点 三.顺序表的实现代码汇总 一.线性表 线性表( linear list ) 是 n 个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见 的线性表:顺序表.链表.栈.队列.字符串

  • Java数据结构顺序表用法详解

    目录 1.什么是顺序表 2.顺序表的基本功能和结构 3.顺序表基本功能的实现和解析 1.判断线性表是否为空 2.获取指定位置的元素 3.向线性表表添加元素 4.在位置i处插入元素 5.删除指定位置的元素,并返回该元素 6.查找t第一次出现的位置 7.手动扩容方法 1.什么是顺序表 在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等.一组数据中包含的元素个数可能发生变化(可以增加或删除元素). 对于这种需求,最简单的解决方

  • Java数据结构顺序表的详细讲解

    目录 写在前面 1.线性表 2.顺序表的实现 2.1增加数据 2.1.1尾部增加数据 2.1.2任意位置增加数据 2.2查找数据 2.3删除数据 2.4修改数据 3.ArrayList 3.1ArrayList的实例化 3.2ArrayList常用的方法 写在前面 关于数据结构,Java官方其实已经帮我们写好并封装起来了,在真正需要使用的时候直接调用即可,但为了更好的理解数据结构,我会按照源码的思路写一个简化后的数据结构,默认接收的数据为int 1.线性表 线性表是多个具有相同特性的数据元素的序

  • C语言数据结构顺序表的进阶讲解

    目录 前言 一.顺序表的构造VS功能 1.顺序表的构造 2.接口实现(功能) 二.功能具体分析 1.初始化 2.销毁 3.检查size与capacity是否溢出 4.尾增功能(实现) 5.打印 三.实现具体功能代码页(SeqList.c) 四.总结 前言 在学习链表之前先掌握顺序表 什么是顺序表? 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储,在数组上完成数据的增删查改. 顺序表一般可分为: 1.静态顺序表:使用定长数组存储. 2.动态顺序表:使用动态开辟

  • C语言编程简单却重要的数据结构顺序表全面讲解

    目录 前言 一.线性表定义 二.顺序表实现 1概念及结构 2静态顺序表 2.1实现顺序表接口,第一步要对顺序表进行初始化 2.2对顺序表的增删查改的接口函数(以尾插为例) 3动态顺序表 3.1动态顺序表初始化 3.2动态顺序表-尾插 3.3动态顺序表-头插 3.4动态顺序表-尾删 3.5动态顺序表-头删 3.6动态顺序表-任意位置插入数据 3.7动态顺序表-任意位置删除数据 结束 前言 本文主要介绍顺序表的定义和常见静态顺序表的用法. 一.线性表定义 线性表(line list)是n个具有相同特

  • Java 数据结构线性表之顺序存储详解原理

    目录 线性表的定义 线性表的基本运算 线性表的存储之顺序存储 定义线性表 添加元素 查找元素 删除元素 打印线性表 实现的完整代码 测试一下 线性表的定义 线性表的逻辑特征: ①有且仅有一个称为开始元素的a1,她没有前趋,仅有一个后继结点a2: ②有且仅有一个称为终端元素的an,他没有后继,只有一个直接前驱a(n-1): ③其余元素ai(2≤i≤n-1)称为内部元素,他们都有且仅有一个直接前驱a(i-1)和直接后继a(i+1). 线性表的图像表示 线性表的基本运算 线性表初始化 求表长 按索引值

  • Java实现顺序表的操作详解

    目录 一.顺序表是什么 二.自定义异常 空引用异常 下标越界异常 三.顺序表的方法 顺序表的实现 获取顺序表长度 顺序表是否为空 顺序表是否为满 打印顺序表 末尾新增元素 指定位置新增元素 判断是否包含某元素 查找某个元素对应的位置 获取 pos 位置的元素 给 pos 位置的元素赋值 删除第一次出现的关键字key 清空顺序表 四.自定义顺序表 一.顺序表是什么 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删查改. 数组不就是一个现

  • Java实现顺序表的增删查改功能

    创建顺序表 在java语言中要实现顺序表,首先创建一个类,因为顺序表本身就像数组,所以我们这里定义一个int类型的数组和usedata为有效数据,构造方法里先申请可以存放10个数据的空间. public class MyArraylist1 { public int[] elem;//存储数据的有效个数 public int usedata;//有效数据的个数 //构造方法 public MyArraylist1() { this.elem = new int[10]; } 主要实现以下方法 p

随机推荐