Java數據結構——線性表的順序存儲實現，java數據結構

Java數據結構——線性表的順序存儲實現

一、描述 
線性結構特點： 
（1）存在唯一的一個被稱作“第一個”的數據元素 
（2）存在唯一的一個被稱作“最後一個”的數據元素 
（3）除第一個之外，集合中的每個數據元素均只有一個前驅 
（4）除最後一個之外，集合中的每個數據元素均只有一個後繼

線性表：是n個數據元素的有限序列。一般有兩種存儲結構：線性表的順序存儲結構和線性表的鏈式存儲結構。

線性表的順序表示：指的是用一組地址連續的存儲單元依次存儲線性表的數據元素。

本篇主要講線性表的順序存儲。

博客撰寫人：It一zhai男 
轉載請標明地址：http://blog.csdn.net/u013293125/article/details/52926611

二、源碼 
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 結果截圖