Java数据结构之顺序表的实现

目录
  • 前言
  • 一、顺序表
    • 1.1 什么是顺序表
  • 二、简单实现顺序表
    • 2.1 创建顺序表
    • 2.2 打印顺序表
    • 2.3 获取顺序表长度
    • 2.4 在 pos 位置新增元素
    • 2.5 判定是否包含某个元素
    • 2.6 查找某个元素对应的位置
    • 2.7 获取 pos 位置的元素
    • 2.8 给 pos 位置的元素设为 value
    • 2.9 删除你想要删除的元素
    • 2.10 清空顺序表
  • 三、MyArrayList.java
  • 四、Test.java

前言

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见 的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储 时,通常以数组和链式结构的形式存储。

一、顺序表

1.1 什么是顺序表

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

其实就是一个数组。那为什么还要写一个顺序表,直接用数组不就好了?不一样的,写到类里面就可以面向对象。

顺序表一般可以分为:

  • 静态顺序表:使用定长数组存储
  • 动态顺序表:使用动态开辟的数组存储

静态顺序表适用于确定知道需要存多少数据的场景.

静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用.

相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.

二、简单实现顺序表

2.1 创建顺序表

public class MyArrayList {
   public int[] elem;//数组
   public int usedSize;//数据的有效个数

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

2.2 打印顺序表

//打印顺序表
public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

2.3 获取顺序表长度

//获取顺序表长度
    public int size(){
        return this.usedSize;
   }

2.4 在 pos 位置新增元素

在顺序表里面插入元素的时候所插入的位置的前面一定是存放了元素的

//在 pos 位置新填元素
    public void add(int pos,int data){
        if(pos < 0 || pos >usedSize){
            System.out.println("pos 位置不合法!");
            return;
        }
        if(isfull()) {
            Arrays.copyOf(this.elem,2*this.elem.length);
        }
        for (int i = this.usedSize - 1; i >= pos; i--) {
            this.elem[i + 1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.usedSize++;
    }
    //判断是否满
    public boolean isfull(){
        return this.usedSize == this.elem.length;
    }

2.5 判定是否包含某个元素

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

2.6 查找某个元素对应的位置

//查找某个元素的对应位置,找不到返回-1
    public int search(int toFind){
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }

2.7 获取 pos 位置的元素

//获取pos位置的值
    public int getPos(int pos){
        if(pos < 0 || pos >= this.usedSize){
            System.out.println("pos 位置不合法");
            return -1;//这里说明一下,业务上的处理,不考虑
        }
        if(isEmpty()){
            System.out.println("顺序表为空!");
            return -1;
        }
        return this.elem[pos];
    }
    public boolean isEmpty(){
        return this.usedSize == 0;
    }

2.8 给 pos 位置的元素设为 value

 //给pos位置元素更新value
    public void setPos(int pos,int value){
        if (pos < 0 || pos >= this.usedSize){
            System.out.println("pos 位置不合法");
            return;
        }
        if(isEmpty()){
            System.out.println("顺序表为空!");
            return;
        }
        this.elem[pos] = value;
    }

2.9 删除你想要删除的元素

//删除第一次出现的关键字key
    public void remove(int toRmove){
        if (isEmpty()){
            System.out.println("顺序表为空!");
            return;
        }
        int index = search(toRmove);
        if(index == -1){
            System.out.println("没有你要删除的数字!");
            return;
        }
        for (int i = index; i < this.usedSize - 1; i++) {
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
        //this.elem[useSize] = null;如果数组当中是引用数据类型
    }

2.10 清空顺序表

//清空顺序表
    public void clear(){
        this.usedSize = 0;
    }

三、MyArrayList.java

import java.util.Arrays;

public class MyArrayList {

    public int[] elem;
    public int usedSize;

    public MyArrayList(){
        this.elem = new int[10];
    }
    //打印顺序表
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
    //获取顺序表长度
    public int size(){
        return this.usedSize;
    }
    //在 pos 位置新填元素
    public void add(int pos,int data){
        if(pos < 0 || pos >usedSize){
            System.out.println("pos 位置不合法!");
            return;
        }
        if(isfull()) {
            Arrays.copyOf(this.elem,2*this.elem.length);
        }
        for (int i = this.usedSize - 1; i >= pos; i--) {
            this.elem[i + 1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.usedSize++;
    }
    //判断是否满
    public boolean isfull(){
        return this.usedSize == this.elem.length;
    }

    //判断是否包含某个元素
    public boolean contains(int toFind){
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
    //查找某个元素的对应位置,找不到返回-1
    public int search(int toFind){
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }

    //获取pos位置的值
    public int getPos(int pos){
        if(pos < 0 || pos >= this.usedSize){
            System.out.println("pos 位置不合法");
            return -1;//这里说明一下,业务上的处理,不考虑
        }
        if(isEmpty()){
            System.out.println("顺序表为空!");
            return -1;
        }
        return this.elem[pos];
    }
    public boolean isEmpty(){
        return this.usedSize == 0;
    }
    //给pos位置元素更新value
    public void setPos(int pos,int value){
        if (pos < 0 || pos >= this.usedSize){
            System.out.println("pos 位置不合法");
            return;
        }
        if(isEmpty()){
            System.out.println("顺序表为空!");
            return;
        }
        this.elem[pos] = value;
    }

    //删除第一次出现的关键字key
    public void remove(int toRmove){
        if (isEmpty()){
            System.out.println("顺序表为空!");
            return;
        }
        int index = search(toRmove);
        if(index == -1){
            System.out.println("没有你要删除的数字!");
            return;
        }
        for (int i = index; i < this.usedSize - 1; i++) {
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
        //this.elem[useSize] = null;如果数组当中是引用数据类型
    }
    //清空顺序表
    public void clear(){
        this.usedSize = 0;
    }
}

四、Test.java

public class Test {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0,1);
        myArrayList.add(1,2);
        myArrayList.add(2,3);
        myArrayList.add(3,4);
        myArrayList.add(4,5);
        myArrayList.display();
        System.out.println(myArrayList.contains(3));
        System.out.println(myArrayList.getPos(3));
        myArrayList.setPos(0,99);
        myArrayList.display();
    }
}

以上就是Java数据结构之顺序表的实现的详细内容,更多关于Java顺序表的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java数据结构之顺序表篇

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

  • Java实现一个顺序表的完整代码

    实现一个顺序表 接口实现 定义一个MyArrayList类,在类中实现以下函数 public class MyArrayList { } 数组的定义 public int[] elem;//定义一个整形数组 public int usize;//usize表示数组的长度 public MyArrayList(){ this.elem = new int[5]; } 打印顺序表 for循环打印顺序表的每一位 public void display(){ for (int i = 0; i < th

  • 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.线性表 线性表是多个具有相同特性的数据元素的序

  • Java 数据结构深入理解ArrayList与顺序表

    目录 一.ArrayList简介 二.ArrayList的使用 1.ArrayList的构造 2.ArrayList的遍历 3.ArrayList的常见操作(方法) 4.ArrayList的扩容机制 三.模拟实现一个顺序表(Object[]) 一.ArrayList简介 在集合框架中,ArrayList是一个普通的类,实现了List接口,具体框架图如下: ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表. 二.ArrayList的使用 1.ArrayList的构造

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

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

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

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

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

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

  • Java数据结构之顺序表的实现

    目录 前言 一.顺序表 1.1 什么是顺序表 二.简单实现顺序表 2.1 创建顺序表 2.2 打印顺序表 2.3 获取顺序表长度 2.4 在 pos 位置新增元素 2.5 判定是否包含某个元素 2.6 查找某个元素对应的位置 2.7 获取 pos 位置的元素 2.8 给 pos 位置的元素设为 value 2.9 删除你想要删除的元素 2.10 清空顺序表 三.MyArrayList.java 四.Test.java 前言 线性表(linear list)是n个具有相同特性的数据元素的有限序列.

  • java数据结构实现顺序表示例

    复制代码 代码如下: import java.util.Arrays;/** * 顺序线性表的实现 */public class LineList<E>{ private int size;   //长度 private Object[] array;  //底层数组 private final int default_length=16; //默认长度 /**  * 无参构造方法  */ public LineList(){  size = 0;  //使用默认长度构造数组  array =

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

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

  • Java全面讲解顺序表与链表的使用

    目录 线性表 顺序表 链表 小结 线性表 线性表 ( linear list ) 是 n 个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见 的线性表:顺序表.链表.栈.队列.字符串 ... 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构(内存上)上并不一定是连续的,线性表在物理上存储时,通常以数组(在物理上是连续的)和链式结构(在物理上不连续)的形式存储. 顺序表 顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下采

  • C#数据结构之顺序表(SeqList)实例详解

    本文实例讲述了C#数据结构之顺序表(SeqList)实现方法.分享给大家供大家参考,具体如下: 线性结构(Linear Stucture)是数据结构(Data Structure)中最基本的结构,其特征用图形表示如下: 即:每个元素前面有且只有一个元素(称为"前驱"),同样后面有且只有一个元素(称为"后继")--注:起始元素的前驱认为是空,末尾元素的后继认为也是空,这样在概念上就不冲突了. 线性表(List)是线性结构的一种典型实现,它又可以分为:顺序表(SeqLi

  • Python数据结构之顺序表的实现代码示例

    顺序表即线性表的顺序存储结构.它是通过一组地址连续的存储单元对线性表中的数据进行存储的,相邻的两个元素在物理位置上也是相邻的.比如,第1个元素是存储在线性表的起始位置LOC(1),那么第i个元素即是存储在LOC(1)+(i-1)*sizeof(ElemType)位置上,其中sizeof(ElemType)表示每一个元素所占的空间. 追加直接往列表后面添加元素,插入是将插入位置后的元素全部往后面移动一个位置,然后再将这个元素放到指定的位置,将长度加1删除是将该位置后面的元素往前移动,覆盖该元素,然

  • C语言数据结构之顺序表和单链表

    一.顺序表的创建.删除和插入 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> struct sqlist { int date[10]; int length; }; void InitList(sqlist& L) { for (int i = 0;i < 10;i++) { L.date[i] = 0; } L.length = 0; } void charu(sqlist& L) { for (int j =

  • Java数据结构之线性表

    线性表是其组成元素间具有线性关系的一种数据结构,对线性表的基本操作主要有,获取元素,设置元素值,遍历,插入,删除,查找,替换,排序等.而线性表可以采用顺序储存结构和链式储存结构,本节主要讲解顺序表.单链表以及双链表的各种基本操作. 1:线性表抽象的数据类型 线性表:是由n(n>=0)个数据相同的元素组成的有限序列.线性表的定义接口如下 public interface IList<T> { /** * 是否为空 * @return */ boolean isEmpty(); /** *

随机推荐