【数据结构与算法】3.顺序表

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】3.顺序表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构与算法】3.顺序表,数据结构与算法,Java,java,开发语言,算法,数据结构

📚博客主页:爱敲代码的小杨.

✨专栏:《Java SE语法》

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️

🙏小杨水平有限,欢迎各位大佬指点,相互学习进步!

【数据结构与算法】3.顺序表,数据结构与算法,Java,java,开发语言,算法,数据结构

1.线性表

定义:线性表是 n 个具有相同特性的数据元素的有序序列。线性表是一种在实际中广泛使用的数据结构,常用的线性表:顺序表、链表、栈、队列…

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

【数据结构与算法】3.顺序表,数据结构与算法,Java,java,开发语言,算法,数据结构

2. 顺序表

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

2.1 顺序表结构

代码实现:

public class MyArrayList implements IList{

    public int[] elem;
    public int usedSize; // 记录数组元素个数
    public static final int DEFAULT_CAACITY = 5; // 默认容量

    public MyArrayList() {
        elem = new int[DEFAULT_CAACITY];
    }
}

2.2 实现顺序表接口

代码实现:

public interface IList {
    // 新增元素,默认在数组最后新增
    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 isFull();
    
    // 判断数组是否为空
    public boolean isEmpty();
}

2.3 打印顺序表

代码实现:

	/**
     * 打印顺序表的所有的元素
     */
    @Override
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }

2.2 实现新增元素

新增元素思想:

  1. 判断数组是否存满元素,如果存满则增加容量,否则存储在elem[usedSize]位置
  2. 判断pos位置是否合法,则抛出异常
  3. 从最后一个元素开始先前遍历到pos位置,分别将它们都向后移动一个位置,再将元素存放到pos位置

代码实现:

	/***
     * 添加元素,默认添加到数组的最后位置
     * @param data
     */
    @Override
    public void add(int data) {
        // 1.判断是否满了 满了就要扩容
        if (isFull()) {
            expansion();
        }
        elem[usedSize] = data;
        usedSize++;
    }

    /***
     * 给pos位置添加元素data
     * 从后往前移动元素 再将元素放进数组
     * @param pos
     * @param data
     */
    @Override
    public void add(int pos, int data) {
        checkPosOfAdd(pos);
        if (isFull()) {
            expansion();
        }
        for (int i = usedSize - 1; i >= pos; i--) {
            elem[i + 1] = elem[i];
        }
        elem[pos] = data;
        usedSize++;
    }

    /***
     * 判断数组是否存满
     * @return
     */
    @Override
    public boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 扩容数组
     */
    public void expansion() {
        elem = Arrays.copyOf(elem, 2 * elem.length);
    }

    /**
     * 判断pos位置是否合法
     * @param pos
     */
    private void checkPosOfAdd(int pos) {
        if (pos < 0 || pos > usedSize) {
            throw new PosException("pos位置:" + pos);
        }
    }

异常类:

public class PosException extends RuntimeException {
    public PosException() {

    }

    public PosException(String msg) {
        super(msg);
    }
}

2.3 实现查找元素

代码实现:

	/***
     * 查找当前元素,是否存在
     * @param toFind
     * @return
     */
    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (toFind == elem[i]) {
                return true;
            }
        }
        return false;
    }

    /***
     * 查找当前元素,并返回下标
     * @param toFind
     * @return
     */
    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (toFind == elem[i]) {
                return i;
            }
        }
        return -1;
    }

2.3 获取指定位置的值

思路:

  1. 判断pos位置是否合法,则抛出异常
  2. 判断数组是否为空,否则抛出异常
  3. 返回elem[pos]的值

代码实现:

	/***
     * 获取pos位置的值
     * @param pos
     * @return
     */
    @Override
    public int get(int pos) {
        // 1.判断pos是否合法
        checkPosOfGet(pos);

        // 2.判断数组是否为空
        if (isEmpty()) {
            throw new EmptyException("顺序表为空");
        }

        return elem[pos];
    }

     /**
     * 判断pos是否合法
     * @param pos
     */
    private void checkPosOfGet(int pos) {
        if (pos < 0 || pos >= usedSize) {
            throw new PosException("pos位置:" + pos);
        }
    }

    /***
     * 判断数组是否为空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return usedSize == 0;
    }

异常类:

public class EmptyException extends  RuntimeException {
    public EmptyException() {

    }

    public EmptyException(String msg) {
        super(msg);
    }
}

2.4 删除元素

思路:

  1. 判断顺序表是否为空,如果为空抛出异常
  2. 查找要删除的元素
  3. 从删除元素的下标遍历到usedSize - 1位置,分别将后一个元素移动到前几个位置。

代码实现:

	/***
     * 删除toRemove这个数字
     * @param toRemove
     */
    @Override
    public void remove(int toRemove) {
        // 1.判断数组是否为空
        if (isEmpty()) {
            throw new EmptyException("顺序表为空,不能删除");
        }
        int index = indexOf(toRemove);
        for (int i = index; i < usedSize - 1; i++) {
            elem[i] = elem[i + 1];
        }
        usedSize--;
    }

2.5 获取顺序表的长度

思路:顺序表的长度就等于usedSize的值

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

2.6 清空顺序表

思路:将usedSize的值置为空

	/***
     * 清空顺序表 防止内存泄漏
     */
    @Override
    public void clear() {
        usedSize = 0;
    }

3.代码

代码链接🔗

4. OJ题

杨辉三角
【数据结构与算法】3.顺序表,数据结构与算法,Java,java,开发语言,算法,数据结构文章来源地址https://www.toymoban.com/news/detail-818703.html

到了这里,关于【数据结构与算法】3.顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构 之 顺序表 ArrayList (Java)

    🎉欢迎大家观看AUGENSTERN_dc的文章(o゜▽゜)o☆✨✨ 🎉感谢各位读者在百忙之中抽出时间来垂阅我的文章,我会尽我所能向的大家分享我的知识和经验📖 🎉希望我们在一篇篇的文章中能够共同进步!!! 🌈个人主页: AUGENSTERN_dc 🔥个人专栏: C语言  |  Java | 数据结构 ⭐个

    2024年03月17日
    浏览(34)
  • 头歌(C语言)-数据结构与算法-队列-第1关:实现一个顺序存储的队列

    任务描述 相关知识 顺序存储的队列 顺序队列的主要操作 编程要求 测试说明 任务描述 本关任务:实现 step1/SeqQueue.cpp 中的 SQ_IsEmpty 、 SQ_IsFull 、 SQ_Length 、 SQ_In 和 SQ_Out 五个操作函数,以实现判断队列是否为空、是否为满、求队列长度、队列元素入队和出队等功能。 相关知

    2024年02月06日
    浏览(162)
  • 数据结构(Java实现)-ArrayList与顺序表

    什么是List List是一个接口,继承自Collection。 List的使用 List是个接口,并不能直接用来实例化。 如果要使用,必须去实例化List的实现类。在集合框架中,ArrayList和LinkedList都实现了List接口。 线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 常见的线性表

    2024年02月11日
    浏览(38)
  • 【Java】实现顺序表基本的操作(数据结构)

    在了解顺序表之前我们要先了解什么是线性表,线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构

    2024年02月03日
    浏览(53)
  • 数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。

    最短路径的算法有两个, Dijkstra算法 和 Floyd算法 。 Dijkstra算法 解决的是 单源 最短路径问题 。 Floyd算法解决的是 多源 最短路径问题,并且可以处理负权图 。 今天要讲的就是Dijkstra算法。 加: feng--Insist (大写的i),进java交流群讨论互联网+技术。可索要PPT等资料。 其他资料

    2024年02月11日
    浏览(58)
  • 【Java数据结构】顺序表、队列、栈、链表、哈希表

    是一个有类型参数(type parameter)的范型表(generic class) 能够自动调整容量,并且不需要写额外的代码 存放数据使用数组但是可以编写一些额外的操作来强化为线性表,底层依然采用顺序存储实现的线性表,称为顺序表 创建 常见操作 一旦确认数组列表大小恒定,不再发生

    2024年02月02日
    浏览(44)
  • 头歌(C语言)-数据结构与算法-栈的实现-第1关:实现一个顺序存储的栈

    任务描述 相关知识 栈的基本概念 栈结构的定义(C) 顺序栈的操作 编程要求 测试说明 任务描述 本关任务是实现 step1/SeqStack.cpp 中的 SS_IsFull 、 SS_IsEmpty 、 SS_Length 、 SS_Push 和 SS_Pop 五个操作函数,以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。 相关

    2024年02月07日
    浏览(65)
  • 【数据结构和算法初阶(C语言)】复杂链表(随机指针,随机链表的复制)题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题: 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(87)
  • 数据结构与算法——顺序表(顺序存储结构)及初始化详解

    顺序表 ,全名 顺序存储结构 ,是线性表的一种。通过《什么是线性表》一节的学习我们知道,线性表用于存储逻辑关系为“一对一”的数据,顺序表自然也不例外。 不仅如此,顺序表对数据的物理存储结构也有要求。 顺序表存储数据时,会提前申请一整块足够大小的物理

    2024年02月16日
    浏览(41)
  • [数据结构 - C语言] 顺序表

    目录 1、线性表 2、顺序表 2.1 顺序表的概念 2.2 接口 3、接口实现 3.1 初始化 3.2 销毁 3.3 容量检测 3.4 打印数据 3.5 顺序表的头插 3.6 顺序表的尾插 3.7 顺序表的头删、尾删 3.8 顺序表查找 3.9 指定位置插入数据 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性

    2023年04月21日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包