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

数据结构--顺序表(详解)

article 2025/1/6 17:53:05 
                                         欢迎大家来到我的博客~
                        欢迎大家对我的博客提出指导，有错误的地方会改进的哦·~

点击这里了解更多内容

目录

  • 一、线性表
  • 二、顺序表

一、线性表

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

在这里插入图片描述

二、顺序表

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

1.定义一个接口，里面放着需要实现的方法：

public interface Ilist {
    // 新增元素,默认在数组最后新增
    public void add(int data);
    boolean isFull();
    // 在 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() ;
}

2.定义一个mySeqlist类去继承接口，然后对，每个方法进行重写。

public class mySeqlist implements Ilist{
    public final int DEFALUT_CAPTICY=10;
    public int[] array;
    //定义起始数组大小为10
    public mySeqlist() {
        this.array =new int[DEFALUT_CAPTICY];
    }

    //顺序表的元素个数
    public int usesize;
    // 新增元素,默认在数组最后新增
    @Override
    public void add(int data) {
        
    }

    @Override
    public boolean isFull() {
        return false;
    }

    @Override
    public void add(int pos, int data) {

    }

    @Override
    public boolean contains(int toFind) {
        return false;
    }

    @Override
    public int indexOf(int toFind) {
        return 0;
    }

    @Override
    public int get(int pos) {
        return 0;
    }

    @Override
    public void set(int pos, int value) {

    }

    @Override
    public void remove(int toRemove) {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {

    }

    @Override
    public void display() {

    }
}

接下来一个一个来实现这些方法，然后完成一个顺序表的实现。

打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的.


 @Override
    public void display() {
        for (int i = 0; i < usesize; i++) {
            System.out.print(array[i] + " ");
        }
    }

判断数组是否存储满了

@Override
    public boolean isFull() {
        return this.usesize==array.length;
    }

数组存储满了，然后想插入数据就得进行扩容。


private int[] grow() {
        return this.array= Arrays.copyOf(this.array,2*this.array.length);
    }

新增元素,默认在数组最后新增

    @Override
    public void add(int data) {
    //判断数组是否存储满了
        if(isFull()){
            //如果忙了就扩容
            grow();
        }
        array[usesize]=data;
        usesize++;
    }

    private int[] grow() {
        return this.array= Arrays.copyOf(this.array,2*this.array.length);
    }

    @Override
    public boolean isFull() {
        return this.usesize==array.length;
    }

再生成一个test类,每写完一个方法，然后测试是否成功

public class Test {
    public static void main(String[] args) {
        mySeqlist mylist=new mySeqlist();
        //新增
        mylist.add(1);
        mylist.add(6);
        mylist.add(10);
        mylist.display();
    }
}

运行结果：
在这里插入图片描述

在 pos 位置新增元素
可以自定义一个异常，来判断输入的pos位置是否合法

public class posillegal extends RuntimeException{ 
    public posillegal(){
        super();
    }
    public posillegal(String S){
        super(S);
    }
}

定义一个方法来判断pos是否合法

   private void Check(int pos) {
        if(pos<0||pos>usesize){
            throw new posillegal("pos位置不合法!!!");
        }
    }

在 pos 位置新增元素

   public void add(int pos, int data) {
        try{
            Check(pos);
            if(isFull()){
                //如果忙了就扩容
                grow();
            }
            for (int i = usesize; i >pos ; i--) {
                array[i]=array[i-1];
            }
            array[pos]=data;
            usesize++;
        }catch (posillegal e){
            e.printStackTrace();
        }
    }

测试：
在这里插入图片描述

点击这里了解什么是异常

判定是否包含某个元素

@Override
    public boolean contains(int toFind) {
        //先判断数组是否为空
        if(isempty()){
            return false;
        }
       if(Find(toFind)){
           return true;
       }
       return false;
    }

    private boolean isempty() {
        return usesize==0;
    }

    private boolean Find(int tofind) {
        for (int i = 0; i < usesize; i++) {
            if(array[i]==tofind){
                return true;
            }
        }
        return false;
    }

在这里插入图片描述

获取值的下标

   @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < usesize; i++) {
            if(array[i]==toFind){
                return i;
            }
        }
        return -1;
    }

在这里插入图片描述

获取pos位置的值

@Override
    public int get(int pos) {
       try{
           Check(pos);
           return array[pos];
       }catch (posillegal e){
           e.printStackTrace();
       }
       return  -1;
    }

在这里插入图片描述

把pos位置的元素设置变成value

  @Override
    public void set(int pos, int value) {
          array[pos]=value;
    }

在这里插入图片描述

去除某个值

  @Override
    public void remove(int toRemove) {
        if(isempty()){
            return;
        }
     int toremove=indexOf(toRemove);
        for (int i = toremove; i <usesize ; i++) {
            array[i]=array[i+1];
        }
        usesize--;
    }

在这里插入图片描述

求顺序表的长度

@Override
    public int size() {
        return usesize;
    }

在这里插入图片描述

清空顺序表

   @Override
    public void clear() {
          usesize=0;
    }

在这里插入图片描述

好了，到这里整个顺序表就差不多完成了。下面是完整代码：

Ilist 接口

public interface Ilist {
    // 新增元素,默认在数组最后新增
    public void add(int data);
    boolean isFull();
    // 在 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() ;
}

mySeqlist类

import java.util.Arrays;

public class mySeqlist implements Ilist{
    public final int DEFALUT_CAPTICY=10;
    public int[] array;
    //定义起始数组大小为10
    public mySeqlist() {
        this.array =new int[DEFALUT_CAPTICY];
    }

    //顺序表的元素个数
    public int usesize;
    // 新增元素,默认在数组最后新增
    @Override
    public void add(int data) {
    //判断数组是否存储满了
        if(isFull()){
            //如果忙了就扩容
            grow();
        }
        array[usesize]=data;
        usesize++;
    }

    private int[] grow() {
        return this.array= Arrays.copyOf(this.array,2*this.array.length);
    }

    @Override
    public boolean isFull() {
        return this.usesize==array.length;
    }
    // 在 pos 位置新增元素
    @Override
    public void add(int pos, int data) {
        try{
            Check(pos);
            if(isFull()){
                //如果忙了就扩容
                grow();
            }
            for (int i = usesize; i >pos ; i--) {
                array[i]=array[i-1];
            }
            array[pos]=data;
            usesize++;
        }catch (posillegal e){
            e.printStackTrace();
        }
    }

    private void Check(int pos) {
        if(pos<0||pos>usesize){
            throw new posillegal("pos位置不合法!!!");
        }
    }
    // 判定是否包含某个元素
    @Override
    public boolean contains(int toFind) {
        //先判断数组是否为空
        if(isempty()){
            return false;
        }
       if(Find(toFind)){
           return true;
       }
       return false;
    }

    private boolean isempty() {
        return usesize==0;
    }

    private boolean Find(int tofind) {
        for (int i = 0; i < usesize; i++) {
            if(array[i]==tofind){
                return true;
            }
        }
        return false;
    }
   //获取值的下标
    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < usesize; i++) {
            if(array[i]==toFind){
                return i;
            }
        }
        return -1;
    }
    //获取pos位置的值
    @Override
    public int get(int pos) {
       try{
           Check(pos);
           return array[pos];
       }catch (posillegal e){
           e.printStackTrace();
       }
       return  -1;
    }
   //把pos位置的元素设置变成value
    @Override
    public void set(int pos, int value) {
          array[pos]=value;
    }
   //去除某个值
    @Override
    public void remove(int toRemove) {
        if(isempty()){
            return;
        }
     int toremove=indexOf(toRemove);
        for (int i = toremove; i <usesize ; i++) {
            array[i]=array[i+1];
        }
        usesize--;
    }
    //求顺序表的长度
    @Override
    public int size() {
        return usesize;
    }
     //清空顺序表
    @Override
    public void clear() {
          usesize=0;
    }
   //打印顺序表
    @Override
    public void display() {
        for (int i = 0; i < usesize; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

自定义 pos异常

public class posillegal extends RuntimeException{
    public posillegal(){
        super();
    }
    public posillegal(String S){
        super(S);
    }
}

测试类(测试仅供参考)

public class Test {
    public static void main(String[] args) {
        mySeqlist mylist=new mySeqlist();
        //新增
        mylist.add(1);
        mylist.add(6);
        mylist.add(10);
        mylist.add(2,8);
        mylist.display();
        System.out.println();
        //System.out.println(mylist.get(1));
        mylist.set(2,9);
        mylist.remove(6);
        mylist.display();
        System.out.println();
        System.out.println(mylist.size());
        mylist.clear();
        mylist.display();
    }
}

在这里插入图片描述
欧耶！！！我学会啦！！！


http://www.kler.cn/a/466014.html

相关文章：

  • 【机器学习】穷理至极，观微知著：微积分的哲思之旅与算法之道
  • spring mvc源码学习笔记之六
  • Apache zookeeper集群搭建
  • SQL—Group_Concat函数用法详解
  • 【问题记录】npm create vue@latest报错
  • Vue3实现PDF在线预览功能
  • windows文件名的最大长度
  • 批量上传文件
  • 微服务实战——购物车模块实战
  • 机场安全项目｜基于改进 YOLOv8 的机场飞鸟实时目标检测方法
  • 使用java语言，自定义redistemplate
  • day26-lvm逻辑卷管理
  • 微机——绪论
  • 亚信安全2025年第1期《勒索家族和勒索事件监控报告》
  • 使用MPTCP+BBR进行数据传输，让网络又快又稳
  • Win32汇编学习笔记03.RadAsm和补丁
  • PTA数据结构作业一
  • AI新闻自动化：使用Tavily Search API构建AI新闻总结助手
  • 大循环引起CPU负载过高
  • MySQL 06 章——多表查询
  • 解决ssh和git秘钥认证失败问题
  • 管理者管理上班摸鱼
  • wujie无界微前端框架初使用
  • 小程序电商实战：打造高效转化的购物平台
  • 基于RNN模型的心脏病预测(tensorflow实现)
  • 【Block总结】SGE注意力机制