萝卜头IT论坛

了解更多
搜索
查看: 170|回复: 3
收起左侧

[每日话题] Java数据结构——线性表

[复制链接]
发表于 2021-4-24 17:06:16 | 显示全部楼层 |阅读模式
Java数据结构——线性表的顺序存储实现
一、描述
线性结构特点:
(1)存在唯一的一个被称作“第一个”的数据元素
(2)存在唯一的一个被称作“最后一个”的数据元素
(3)除第一个之外,集合中的每个数据元素均只有一个前驱
(4)除最后一个之外,集合中的每个数据元素均只有一个后继
线性表:是n个数据元素的有限序列。常用的两种存储结构为:线性表的顺序存储结构和线性表的链式存储结构。
线性表的顺序表示:指的是用一组地址连续的存储单元依次存储线性表的数据元素。

本篇主要讲线性表的顺序存储。
二、源码
2.1 SequenceList.java
package com.yds.list;
import java.util.Arrays;
public class SequenceList<T>{
    //默认长度
    private int DEFAULT_SIZE = 2;
    //定义一个数组用于保存线性表的长度
    private Object[] elementData;
    //用于保存数组长度
    private int capacity;
    //保存顺序表中当前元素的个数
    private int size = 0;
    /**
     * 构造一个默认长度的空线性表
     */
    public SequenceList(){
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }
    /**
     * 用一个初始化元素来创建线性表
     * @param element 初始化元素
     */
    public SequenceList(T element){
        this();
        elementData[0] = element;
        size++;
    }
    /**
     * 用一个元素和指定长度来创建线性表
     * @param element 元素
     * @param initSize 指定长度
     */
    public SequenceList(T element,int initSize){
        capacity = 1;
        if(capacity<initSize){
            capacity = initSize +2;
        }
        elementData = new Object[capacity];
        elementData[0] = element;
        size++;
    }
   /**
     * 向顺序表中插入元素
     * @param element   待插入的元素
     * @param index 待插入的位置
     */
    public void insert(T element,int index){
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("数组越界异常");
        }
        ensureCapacity(size+1);
        //把index以后的元素都后移一位
        System.arraycopy(elementData, index, elementData, index+1, size-index);
        elementData[index] = element;
        size++;
    }
    /**
     * 表长
     * @return
     */
    public int length(){
        return size;
    }
    /**
     * 向表中添加元素
     * @param element
     */
    public void add(T element){
        insert(element, size);
    }
    /**
     * 得到线性表存储的对象
     * @param index 获得的位置
     * @return  得到的结果
     */
    public T get(int index){
        if(index<0||index>size)
            throw new IndexOutOfBoundsException("数组越界异常");
        return (T)elementData[index];
    }
    /**
     * 判断线性表是否为空
     * @return
     */
    public boolean isEmpty(){
        return size==0;
    }
    /**
     * 清空线性表
     */
    public void clear(){
        Arrays.fill(elementData, null);
        size = 0;
    }
    /**
     * 获取指定位置的前一个元素
     * @param index 线性表位置,若是取线性表最后一个元素,必须index = size,
     * size为线性表元素个数
     * @return
     */
    public T priorElem(int index){
        if(index>0&&index<size+1)
            return (T)elementData[index-1];
        else {
            throw new IndexOutOfBoundsException("数组越界异常");
        }
    }
    /**
     * 删除指定位置的元素
     * @param index
     */
    public void delete(int index){
        if(index<0||index>size-1){
            throw new IndexOutOfBoundsException("数组越界异常");
        }else{
            //把数组前移一位
            System.arraycopy(elementData, index+1, elementData, index, size-index-1);
            size--;
            //清空最后一个元素
            elementData[size]=null;
        }
    }
    /**
     * 获取指定线性表位置的后一个元素
     * @param index 线性表位置,若是取线性表第0个元素,必须index=-1
     * @return
     */
    public T nextElem(int index){
        if (index==-1) {
            return (T)elementData[0];
        }
        else if (index<size-1&&index>-1) {
            return (T)elementData[index+1];
        }else{
            throw new IndexOutOfBoundsException("数组越界异常");
        }
    }
    /**
     * 确保数组所需长度大于数组原有长度
     * @param mCapacity 数组所需长度
     */
    private void ensureCapacity(int mCapacity){
        if(mCapacity>capacity){
            capacity=mCapacity+2;
//          System.out.println("capacity:"+capacity);
            elementData = Arrays.copyOf(elementData, capacity);
        }
    }
}   
2.2 JavaMain.java
package com.yds.list;
public class JavaMain {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        SequenceList<String> list = new SequenceList<String>();
        System.out.println("isEmpty:"+list.isEmpty());
        String La[] = {
                "3"
        };
        for (int i = 0; i < La.length; i++) {
            list.add(La[i]);
        }
        System.out.println("isEmpty:"+list.isEmpty());
        for (int i = 0; i < La.length; i++) {
            System.out.println(list.get(i));
        }
        System.out.println("length:"+list.length());
        System.out.println("priorElem:"+list.priorElem(1));
        list.insert("7", 0);
        System.out.println("--------------------");
        for (int i = 0; i < list.length(); i++) {
            System.out.println(list.get(i));
        }
        System.out.println("length:"+list.length());
        System.out.println("--------------------");
        System.out.println("priorElem:"+list.priorElem(1));
        System.out.println("nextElem:"+list.nextElem(0));
        System.out.println("--------------------");
        list.delete(1);
        for (int i = 0; i < list.length(); i++) {
            System.out.println(list.get(i));
        }
        list.clear();
        System.out.println("isEmpty:"+list.isEmpty());
        System.out.println("----------SequenceList(T element)----------");
        SequenceList<String> list1 = new SequenceList<String>("5");
        for (int i = 0; i < La.length; i++) {
            list1.add(La[i]);
        }
        for (int i = 0; i < list1.length(); i++) {
            System.out.println(list1.get(i));
        }
        System.out.println("-------SequenceList(T element,int initSize)--------");
        SequenceList<String> list2 = new SequenceList<String>("5",3);
        for (int i = 0; i < La.length; i++) {
            list2.add(La[i]);
        }
        for (int i = 0; i < list2.length(); i++) {
            System.out.println(list2.get(i));
        }
    }
3 结果截图
回复

使用道具 举报

发表于 2021-4-24 19:59:06 | 显示全部楼层
支持楼主的教程,认真学习中。
回复

使用道具 举报

发表于 2021-4-26 10:00:04 | 显示全部楼层
学习了
回复

使用道具 举报

发表于 2021-6-5 12:53:44 | 显示全部楼层
学习学习!
回复

使用道具 举报

联系站长(Contact)|萝卜头IT论坛 ( 苏ICP备15050961号-1 )

GMT+8, 2021-6-22 18:49 , Processed in 0.181169 second(s), 20 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表