当前位置:首页 > 嵌入式培训 > 嵌入式学习 > 讲师博文 > Java数据结构——线性表

Java数据结构——线性表 时间:2019-07-10      来源:济南中心,吴老师

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 结果截图

上一篇:STM32F407之SD卡读数据介绍

下一篇:STM32之外设定时器

热点文章推荐
华清学员就业榜单
高薪学员经验分享
热点新闻推荐
前台专线:010-82525158 企业培训洽谈专线:010-82525379 院校合作洽谈专线:010-82525379 Copyright © 2004-2018 北京华清远见科技发展有限公司 版权所有 ,京ICP备16055225号,京公海网安备11010802025203号