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

目录
  • 线性表的定义
  • 线性表的基本运算
  • 线性表的存储之顺序存储
    • 定义线性表
    • 添加元素
    • 查找元素
    • 删除元素
    • 打印线性表
    • 实现的完整代码
    • 测试一下

线性表的定义

线性表的逻辑特征:

  • ①有且仅有一个称为开始元素的a1,她没有前趋,仅有一个后继结点a2;
  • ②有且仅有一个称为终端元素的an,他没有后继,只有一个直接前驱a(n-1);
  • ③其余元素ai(2≤i≤n-1)称为内部元素,他们都有且仅有一个直接前驱a(i-1)和直接后继a(i+1)。

线性表的图像表示

线性表的基本运算

  • 线性表初始化
  • 求表长
  • 按索引值查找元素
  • 按值查找
  • 插入元素
  • 删除

线性表的存储之顺序存储

线性表顺序存储的定义:线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组连续的存储单元里,用这种方式存储的线性表称为顺序表。

定义线性表

定义线性表的默认空间大小,定义一个数组,定义数组的长度,初始化一个size用来保存里面元素的个数。

 	/** 定义线性表默认空间大小 */
    private final Integer ListSize=100;
    /**定义数组长度*/
    private Integer Len;
    /** 定义线性表保存的数据类型
     * 使用泛型*/
    private Object[] list;
    /**存一个当前元素的个数*/
    private Integer size=0;
    /**定义默认线性表*/
    public SeqList(){
        Len = ListSize;
        this.list = new Object[Len];
        size++;
    }

初始化线性表

把线性表里面的元素全部置空

	/**清空线性表*/
    public void clear(){
        for (int i = 0; i < size; i++) {
            list[i]=null;
        }
        size=0;
    }

添加元素

这里采用尾插法,即每次默认将元素放在最后面

	/**添加元素到指定位置*/
    public void insert(T element , int index){
        if(index>=Len || index<0){
            throw new IndexOutOfBoundsException("输入的索引值超过了线性表的范围");
        }
        Capacity(size+1);
        //将添加元素的元素往后移一位
        for (int i = size-2; i >= index-1; i--) {
            list[i+1]=list[i];
        }
        list[index-1]=element;
        size++;
    }
    /**添加元素到末尾*/
    public void add(T element){
        insert(element,size);
    }

查找元素

这个模块分为按索引值查找,和按元素值查找

	/**线性表的查找
     * 按索引值查找*/
    public T getNode(int index){
        return (T)list[index-1];
    }
    /**按元素值查找返回索引值*/
    public int LocateNode(T t){
        for(int i=0;i<list.length;i++){
            if(list[i].equals(t)){
                return i+1;
            }
        }
        System.out.println("没有找到该元素!");
        return -1;
    }

删除元素

删除元素,又分为删除指定元素,和删除最后一个元素

    /**删除指定位置的元素*/
    public T delete(int index){
        if(!OutIndex(index)){
            throw new IndexOutOfBoundsException("删除位置不在线性表的索引范围内!");
        }
        for (int i = index-1; i < size-1; i++) {
            list[i]=list[i+1];
        }
        /*if(size - index >0){
            System.arraycopy(list,index,list,index-1,size-index);
        }*/
        list[size-1]=null;
        size--;
        return (T) list;
    }
    /**删除最后一个元素*/
    public T remove(){
        return delete(size-1);
    }

打印线性表

打印线性表,其实就是重写一个toString方法,将线性表打印出来

/**循环打印线性表*/
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        if(isEmpty()){
            return "[]";
        }
        else {
            sb.append("[");
            for (int i = 0; i < size-1; i++) {
                int a=0;
                if(list[i]!=null){
                    sb.append(list[ i ]);
                }
                else {
                    break;
                }
                sb.append(",");
            }
            sb.append("]");
            sb.deleteCharAt(sb.indexOf(",]"));
        }
        return sb.toString();
    }

实现的完整代码

class SeqList<T>{
    /** 定义线性表默认空间大小 */
    private final Integer ListSize=100;
    /**定义数组长度*/
    private Integer Len;
    /** 定义线性表保存的数据类型
     * 使用泛型*/
    private Object[] list;
    /**存一个当前元素的个数*/
    private Integer size=0;
    /**定义默认线性表*/
    public SeqList(){
        Len = ListSize;
        this.list = new Object[Len];
        size++;
    }
    /**定义自定义长度的线性表*/
    public SeqList(int length){
        Len = length;
        list = new Object[Len];
        size++;
    }
    /**获取当前线性表的长度*/
    public int getLen(){
        return Len;
    }
    /**获取当前线性表元素的个数*/
    public int getSize(){
        return size;
    }
    /**根据元素查找在线性表中的位置,未找到返回-1*/
    public int getIndex(T element){
        for (int i = 0; i < size; i++) {
            if(list[i].equals(element)){
                return i;
            }
        }
        return -1;
    }
    /**判断是否表满或表空*/
    private boolean OutIndex(int index){
        //return size==Len;//不扩容的话,可以这样写,但是怕扩容
        if(index>size || index<0){
            return false;
        }
        else {
            return true;
        }
    }
    /**根据索引值返回元素*/
    private T getElement(int index){
        if(!OutIndex(index)){
            throw new IndexOutOfBoundsException("输入的索引值超过了线性表的范围");
            /* System.out.println("输入索引超过了线性的范围");
            return null; */
        }
        return (T)list[index];
    }
    /**扩容*/
    private T Capacity(int capacity){
        if(capacity<Len){
            Len = Len+(Len+1)/2;
            if(capacity<Len){
                Capacity(Len);
            }
            else {
                list = Arrays.copyOf(list,Len);
                return (T) list;
            }
        }
        return (T)list;
    }
    /**添加元素到指定位置*/
    public void insert(T element , int index){
        if(index>=Len || index<0){
            throw new IndexOutOfBoundsException("输入的索引值超过了线性表的范围");
        }
        Capacity(size+1);
        //将添加元素的元素往后移一位
        for (int i = size-2; i >= index-1; i--) {
            list[i+1]=list[i];
//            System.out.println("i="+i);
        }
        list[index-1]=element;
        size++;
    }
    /**添加元素到末尾*/
    public void add(T element){
        insert(element,size);
    }
    /**判断元素表是否为空*/
    public boolean isEmpty(){
        return size==0;
    }
    /**删除指定位置的元素*/
    public T delete(int index){
        if(!OutIndex(index)){
            throw new IndexOutOfBoundsException("删除位置不在线性表的索引范围内!");
        }
        for (int i = index-1; i < size-1; i++) {
            list[i]=list[i+1];
        }
        /*if(size - index >0){
            System.arraycopy(list,index,list,index-1,size-index);
        }*/
        list[size-1]=null;
        size--;
        return (T) list;
    }
    /**删除最后一个元素*/
    public T remove(){
        return delete(size-1);
    }
    /**清空线性表*/
    public void clear(){
        for (int i = 0; i < size; i++) {
            list[i]=null;
        }
        size=0;
    }
    /**线性表的查找
     * 按索引值查找*/
    public T getNode(int index){
        return (T)list[index-1];
    }
    /**按元素值查找返回索引值*/
    public int LocateNode(T t){
        for(int i=0;i<list.length;i++){
            if(list[i].equals(t)){
                return i+1;
            }
        }
        System.out.println("没有找到该元素!");
        return -1;
    }
    /**循环打印线性表*/
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        if(isEmpty()){
            return "[]";
        }
        else {
            sb.append("[");
            for (int i = 0; i < size-1; i++) {
                int a=0;
                if(list[i]!=null){
                    sb.append(list[ i ]);
                }
                else {
                    break;
                }
                sb.append(",");
            }
            sb.append("]");
            sb.deleteCharAt(sb.indexOf(",]"));
        }
        return sb.toString();
    }
}

测试一下

测试代码

	public static void main(String[] args) {
        SeqList<String> seqList = new SeqList<String>();
        //添加一个元素
        seqList.add("pier");
        seqList.add("真好看");
        seqList.add("90度点头");
        System.out.println("添加后的线性表为\n\t"+seqList.toString());
        seqList.insert("pipi",1);
        System.out.println("在位置1的地方添加元素后的线性表为\n\t"+seqList.toString());
        seqList.delete(1);
        System.out.println("删除第二个元素后的线性表为\n\t"+seqList.toString());
        System.out.println("pier时第"+seqList.LocateNode("pier")+"个元素");
        System.out.println("第1个元素是"+seqList.getNode(1)+"。");
    }

运行结果

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

(0)

相关推荐

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

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

  • Java 如何从list中删除符合条件的数据

    目录 从list中删除符合条件的数据 删除list中某个特定元素 从list中删除符合条件的数据 在Java语言使用中经常会遇到需要从list中去除一些数据,但是初学者经常会遇到如下的坑: Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 5, Size: 4 at java.util.ArrayList.rangeCheck(Unknown Source) at java.util.Array

  • Java数据结构之List的使用总结

    目录 泛型 什么是泛型 泛型的分类 泛型的定义简单演示 泛型背后作用时期和背后的简单原理 泛型类的使用 泛型总结 包装类 基本数据类型和包装类直接的对应关系 包装类的使用,装箱(boxing)和拆箱(unboxing) List的使用 List常用方法 使用示例 自动发牌案例 泛型 什么是泛型 泛型:即通过参数化类型来实现在同一份代码上操作多种数据类型.泛型是在C#2.0引入的.泛型(Genericity)的字面意思是指具有在多种数据类型上皆可操作的含意,与模板有些相似. 优点:泛型类和泛型方法

  • java关于list集合做删除操作时的坑及解决

    目录 关于list集合做删除操作时的坑 解决办法 对List集合的常用操作 1.list中添加,获取,删除元素 2.list中是否包含某个元素 3.list中根据索引将元素数值改变(替换) 4.list中查看(判断)元素的索引 5.根据元素索引位置进行的判断 6.利用list中索引位置重新生成一个新的list(截取集合) 7.对比两个list中的所有元素 8.判断list是否为空 9.返回Iterator集合对象 10.将集合转换为字符串 11.将集合转换为数组 12.集合类型转换 13.去重复

  • Java List移除相应元素的超简洁写法分享

    目录 List移除相应元素的超简洁写法 好了上代码 Java List 删除元素 1.删除后元素后,i-1 2.反向删除 3.使用迭代器删除(iterator)(推荐) 4.赋值给新的list List移除相应元素的超简洁写法 最近遇到了一个需求(好吧以前也遇到过),就是将一个List中的部分元素去除,如把string中带数字的元素去除,以前是各种遍历各种不爽,今天发现用Java8中的lambda写,只需三行. 好了上代码 List<String> list = new ArrayList&l

  • Java中List常用操作比for循环更优雅的写法示例

    目录 引言 简单遍历 筛选符合某属性条件的List集合 获取某属性返回新的List集合 获取以某属性为key,其他属性或者对应对象为value的Map集合 以某个属性进行分组的Map集合 其他情况 总结 引言 使用JDK1.8之后,大部分list的操作都可以使用lambda表达式去写,可以让代码更简洁,开发更迅速.以下是我在工作中常用的lambda表达式对list的常用操作,喜欢建议收藏. 以用户表为例,用户实体代码如下: public class User { private Integer

  • java 如何在list中删除我指定的对象

    目录 遍历list,删除指定对象的三种方式 1.再定义一个List,用来保存需要删除的对象 2.不用for-each循环,使用倒序循环删除 3.用迭代器删除 Iterator的工作机制 List集合删除元素的正确姿势 常用的错误方式有以下三种 遍历list,删除指定对象的三种方式 1.再定义一个List,用来保存需要删除的对象 修改部分代码: List<User> userRemove = new ArrayList<User>(); //找出要删除的用户 System.err.p

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

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

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

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

  • C语言数据结构线性表教程示例详解

    目录 线性表 顺序表 线性表 数据结构里我们时常看到什么什么表,线性表是最基本.最简单.也是最常用的一种数据结构,其他各种表的万恶之源就是这个线性表,他是个啥其实顾名思义: 一个线性表是n个具有相同特性的数据元素的有限序列.数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部.比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点). 说的这么复杂其实就是

  • C语言*与&在操作线性表的作用详解

    在数据结构线性表一章,对线性表有这些操作方法(Operation): /*Operation*/ Initlist(*L);/*初始化操作,建立一个空的线性表L*/ ListEmpty(L):/*判断线性表是否为空表,若线性表为空,返回值为true,否则返回false*/ ClearList(*L):/*将线性表清空*/ GetElem(L,i,*e):/*性表L中的第i个位置元素值返回给e*/ LocateElem(L,e):/*在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在

  • C语言实现线性表的基本操作详解

    目录 前言 一.实训名称 二.实训目的 三.实训要求 四.实现效果 五.顺序存储代码实现 六.链式存储代码实现 前言 这里使用的工具是DEV C++ 可以借鉴一下 一.实训名称 线性表的基本操作 二.实训目的 1.掌握线性表的基本概念 2.掌握线性表的存储结构(顺序存储与链式存储) 3.掌握线性表的基本操作 三.实训要求 1.线性表可以顺序表也可以用单链表实现,鼓励大家用两种方式实现. 2.创建线性表时,数据从键盘输入整形数据 3.线性表类型定义和或各种操作的实现,可以用教材给出的方法,也可以自

  • Java实现跳跃表的示例详解

    跳表全称叫做跳跃表,简称跳表,是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表.跳表在原有的有序列表上面增加多级索引,通过索引来实现快速查找.跳表不仅能提高搜索性能,同时也提高插入和删除的性能,redis中的有序集合set就是用跳表实现的,面试时候也经常会问. 这里我们原始数据个数n=10,以间隔k=2建立索引,则第一层索引10/2=5个,第二层⌈10/2^2⌉=3个,第三层⌈10/2^3⌉=2个,第四层⌈10/2^4⌉=1个.根据上图我们来分析一下,跳表的结构是一棵树(除原始数据

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

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

  • Java导出oracle表结构实例详解

     Java导出oracle表结构实例详解 最近用到的,因为plsql是收费的,不让用,找了很多方法终于发现了这个. 核心语句 SELECT DBMS_METADATA.GET_DDL(U.OBJECT_TYPE, U.object_name), U.OBJECT_TYPE FROM USER_OBJECTS U where U.OBJECT_TYPE = 'TABLE' or U.OBJECT_TYPE = 'VIEW' or U.OBJECT_TYPE = 'INDEX' or U.OBJEC

  • Java实现线性表的顺序存储

    本文实例为大家分享了Java实现线性表的顺序存储,供大家参考,具体内容如下 顺序表:用一组地址连续的存储单元依次存储各个元素,使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表 package algorithm.datastructure.seqlist; /*顺序表 * * 用一组地址连续的存储单元依次存储各个元素,使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表 * */ public class SeqList { private int length;//

  • Java 数据结构之时间复杂度与空间复杂度详解

    目录 算法效率 时间复杂度 什么是时间复杂度 推导大 O 阶的方法 算法情况 计算冒泡排序的时间复杂度 计算二分查找的时间复杂度 计算阶乘递归的时间复杂度 计算斐波那契递归的时间复杂度 空间复杂度 计算冒泡排序的空间复杂度 计算斐波那契数列的空间复杂度(非递归) 计算阶乘递归Factorial的时间复杂度 算法效率 在使用当中,算法效率分为两种,一是时间效率(时间复杂度),二是空间效率(空间复杂度).时间复杂度是指程序运行的速度.空间复杂度是指一个算法所需要的额外的空间. 时间复杂度 什么是时间

  • Java数据结构之平衡二叉树的实现详解

    目录 定义 结点结构 查找算法 插入算法 LL 型 RR 型 LR 型 RL 型 插入方法 删除算法 概述 实例分析 代码 完整代码 定义 动机:二叉查找树的操作实践复杂度由树高度决定,所以希望控制树高,左右子树尽可能平衡. 平衡二叉树(AVL树):称一棵二叉查找树为高度平衡树,当且仅当或由单一外结点组成,或由两个子树形 Ta 和 Tb 组成,并且满足: |h(Ta) - h(Tb)| <= 1,其中 h(T) 表示树 T 的高度 Ta 和 Tb 都是高度平衡树 即:每个结点的左子树和右子树的高

随机推荐