Java实现线性表的顺序存储

本文实例为大家分享了Java实现线性表的顺序存储,供大家参考,具体内容如下

顺序表:用一组地址连续的存储单元依次存储各个元素,使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表

package algorithm.datastructure.seqlist;

/*顺序表
*
* 用一组地址连续的存储单元依次存储各个元素,使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表
*
*/
public class SeqList {

  private int length;//顺序表长度
  private int[] list;//数组,连续的存储空间

  //初始化,构造一个空的线性表
  public SeqList(int listLength) {
    list = new int[listLength];
  }
  //销毁表
  public void destroyList() {
    list = null;
    this.length = 0;
  }
  //将线性表置为空表
  public void clearList() {
    for (int i = 0; i < getLength(); i++) {
      list[i] = 0;
    }
  }

  //判断线性表是否未空表
  public Boolean isEmpty() {
    return getLength() == 0;
  }

  //获取线性表元素个数
  public int getLength() {
    return length;
  }

  //根据下标获取线性表元素
  public int getElem(int i) {
    if (i < 0 || i >= getLength()) {
      try {
        throw new Exception("线性表下标越界");
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    return list[i];
  }

  //返回某元素(第一个)的前驱
  public Integer priorElem(int element) {
    for (int i = 0; i < getLength(); i++) {
      if (element == list[i]) {
        if (i == 0) {
          return null;
        } else {
          return list[i - 1];
        }
      }
    }
    return null;
  }

  //获取某元素(第一个)的后继
  public Integer nextElem(int element) {
    for (int i = 0; i < getLength(); i++) {
      if (element == list[i]) {
        if (i == getLength() - 1) {
          return null;
        } else {
          return list[i + 1];
        }
      }
    }
    return null;
  }

  //扩容,这里设置容量变为原来两倍
  public void ensureCapacity(int capacity) {
    if (capacity >= list.length) {//扩容
      int tempList[] = new int[list.length * 2];
      for (int i = 0; i < list.length; i++) {
        tempList[i] = list[i];
      }
      list = tempList;
    }
  }

  //在指定位置插入元素
  public Boolean insertElement(int index, int element) {
    if (index < 0 || index >= list.length) {
      try {
        throw new Exception("下标错误");
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    if (index == getLength()) {
      return insertTailElement(element);
    }
    for (int i = 0; i < getLength(); i++) {
      if (i == index) {
        ensureCapacity(getLength() + 1);
        //index位置后面的元素后移
        for (int j = getLength() - 1; j >= index; j--) {
          list[j + 1] = list[j];
        }
        list[index] = element;
        length++;
      }
    }
    return true;
  }

  //尾部插入元素
  public Boolean insertTailElement(int element) {
    ensureCapacity(length + 1);
    list[++length] = element;
    return true;
  }
  //删除尾部元素
  public int deleteTailElement() {
    if (getLength() == 0) {
      try {
        throw new Exception("下标错误");
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    int tailElement = list[getLength() - 1];
    list[getLength() - 1] = 0;
    length--;
    return tailElement;
  }

  //删除元素
  public int deleteElement(int index) {
    if (index < 0 || index >= list.length) {
      try {
        throw new Exception("下标错误");
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    if (index == getLength()) {
      return deleteTailElement();
    }
    for (int i = 0; i < getLength(); i++) {
      if (i == index) {
        int tailElement = list[index];
        //index位置后面的元素前移
        for (int j = index; j < getLength() - 1; j++) {
          list[j] = list[j + 1];
        }
        list[getLength() - 1] = 0;
        length--;
        return tailElement;
      }
    }
    return 0;
  }

  //遍历顺序表
  public void traverseList() {
    for (int i = 0; i < getLength(); i++) {
      System.out.println(list[i]);
    }
  }

  public static void main(String[] args) {
    //测试
    SeqList seqList = new SeqList(2);
    System.out.println(seqList.insertTailElement(1));
    System.out.println(seqList.insertTailElement(2));
    System.out.println(seqList.insertTailElement(3));
    System.out.println(seqList.insertTailElement(4));
    System.out.println(seqList.getElem(0));
    System.out.println(seqList.getElem(1));
    System.out.println(seqList.getElem(2));
    System.out.println(seqList.getElem(3));

    System.out.println(seqList.insertElement(0, 4));
    System.out.println(seqList.getElem(0));
    System.out.println(seqList.getElem(1));
    System.out.println(seqList.getElem(2));
    System.out.println(seqList.getElem(3));
    System.out.println(seqList.getElem(4));
    System.out.println(seqList.priorElem(3));
    System.out.println(seqList.priorElem(4));
    System.out.println(seqList.nextElem(4));
    System.out.println(seqList.nextElem(3));
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
//    System.out.println(seqList.deleteTailElement());
    System.out.println(seqList.deleteElement(0));
    System.out.println(seqList.deleteElement(1));
    seqList.traverseList();
  }
}

以上就是用Java简单实现的顺序表,在Java中,如果要实现功能更复杂,性能更高的顺序表,可参考ArrayList源码。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Java实现线性表的链式存储

    本文实例为大家分享了Java实现线性表的链式存储,供大家参考,具体内容如下 链表:一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的. package algorithm.datastructure.linklist; import java.util.NoSuchElementException; /* * 链表 * 物理存储上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现 * * */ public class LinkedLi

  • java线性表的存储结构及其代码实现

    Java数据结构学习笔记第一篇: 用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系 线性结构:数据元素之间存在一个对一个的关系 树形结构:数据元素之间存在一个对多个关系 图形结构或网状结构:数据元素之间存在多个对多个的关系 对于数据不同的逻辑结构,计算机在物理磁盘上通常有两种屋里存储结构 顺序存储结构 链式存储结构 本篇博文主要讲的是线性结构,而线性结构主要是线性表,非线性结构主要是树和图. 线性表的基本特征: 总存在唯一的第一个数据元素

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

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

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

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

  • python数据结构之线性表的顺序存储结构

    用Python仿照C语言来实现线性表的顺序存储结构,供大家参考,具体内容如下 本文所采用的数据结构模板为 <数据结构教程>C语言版,李春葆.尹为民等著. 该篇所涉及到的是线性表的顺序存储结构. 代码: # !/usr/bin/env python # -*- coding: utf-8 -*- __author__ = 'MrHero' class Node(object): """ 线性表的存储结构 和 C 语言中的链式存储结构类似 ""&q

  • java实现线性表及其算法

    线性表 线性表是最简单和最常用的一种数据结构,它是有n个体数据元素(节点)组成的有限序列.其中,数据元素的个数n为表的长度,当n为零时成为空表,非空的线性表通常记为: (a1,a2,- ,ai-1,ai, ai+1,-,an) 一. 线性表的顺序存储及算法 线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里,用这种方法存储的线性表称为顺序表. 1.顺序表的结构定义 public class SeqList { /* 初始空间为10 */ private stat

  • Java数据结构之线性表

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

  • Java线性表的顺序表示及实现

    目录 前言 一.什么是顺序表? 二.顺序表的实现 1. 准备工作 2. 获取顺序表的元素个数 3. 获取顺序表当前的容量 4. 顺序表是否为空 5. 在指定索引位置添加元素 6. 在顺序表末尾添加元素 7. 在顺序表头部添加元素 8. 获取指定索引位置的元素 9. 获取顺序表第一个元素 10. 获取顺序表最后一个元素 11. 修改指定索引位置的元素 12. 判断顺序表中是否包含指定元素 13. 获取顺序表中指定元素的索引 14. 删除指定索引位置的元素 15. 删除并返回顺序表第一个元素 16.

  • php线性表顺序存储实现代码(增删查改)

    复制代码 代码如下: <?php /* *文件名:linearList.php * 功能:数据结构线性表的顺序存储实现 * author:黎锦焕 * @copyright:www.drw1314.com */ class linearList { private $arr; private $length; const MAXSIZE=100; /* *构造函数,判断空表还是飞空表,并且进行实例化 * @param array $arr 输入的数组 * @param int $n 输入数组的长度

  • C语言线性表顺序存储结构实例详解

    C语言线性表顺序存储结构实例详解 1. 什么是顺序存储结构? 用一段地址连续的存储单元依次存储线性表的数据元素. 2.线性表的顺序存储结构 #include<stdio.h> #include<stdlib.h> #define Max 80 //存储空间初始分配量 #define Increment 10 //存储空间分配增量 typedef struct { int *elem; // 存储空间基地址,此处为int型,视情况而定 int length; // 元素表当前长度 i

随机推荐