胖虎的工具箱-编程导航 胖虎的工具箱-编程导航

【一起学数据结构与算法】顺序表的实现

3年前 (2022) 程序员胖胖胖虎阿
441 0 0

❤️❤️个人主页：摸鱼王胖嘟嘟
🌟🌟作品专栏：一起学数据结构与算法系列
📑给大家推荐一款非常火的面试、刷题、学习神器
👉牛客网
👉点击注册一起刷题、学习、讨论收获大厂offer吧！
【一起学数据结构与算法】顺序表的实现

目录

  • 前言
  • 一、顺序表
    • 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();
    }
}

版权声明：程序员胖胖胖虎阿 发表于 2022年9月15日 下午5:24。
转载请注明：【一起学数据结构与算法】顺序表的实现 | 胖虎的工具箱-编程导航

相关文章

IDEA2019激活工具(windows/mac idea专业版激活工具激活至2099年)
程序员胖胖胖虎阿
599
IDEA最新永久 激活码(IDEA安装及激活破解教程,绝对有效)
程序员胖胖胖虎阿
427
CGB2202面向对象第7天
程序员胖胖胖虎阿
277
Gemini.Workflow 双子工作流入门教程一：定义流程：流程图属性
程序员胖胖胖虎阿
282
JavaSE——字符串常量池(StringTable)
程序员胖胖胖虎阿
367
java中的各种锁总结(简单全面版)
程序员胖胖胖虎阿
320

暂无评论

暂无评论...

JetBrains全家桶正版账号

官方正版 JetBrains 账号

登录即可使用全家桶 不限操作系统 官方授权 支持全家桶所有软件 不限版本
🔥 最低 32元/年
致力于称为最好的程序员导航网站

友链申请 免责声明 关于我们

Copyright © 2022  胖虎的工具箱-编程导航   陇ICP备2022001249号