java 线性表-----数据表示形式(源代码)

电玩女神 2023-10-13 16:05 60阅读 0赞

1.import java.util.Arrays;  
    2.  
    3.public class SequenceList<T>  
    4.{  
    5.    private int DEFAULT_SIZE = 16;  
    6.    //保存数组的长度。  
    7.    private int capacity;  
    8.    //定义一个数组用于保存顺序线性表的元素  
    9.    private Object[] elementData;  
    10.    //保存顺序表中元素的当前个数  
    11.    private int size = 0;  
    12.    //以默认数组长度创建空顺序线性表  
    13.    public SequenceList()  
    14.    {  
    15.        capacity = DEFAULT_SIZE;  
    16.        elementData = new Object[capacity];  
    17.    }  
    18.    //以一个初始化元素来创建顺序线性表  
    19.    public SequenceList(T element)  
    20.    {  
    21.        this();  
    22.        elementData[0] = element;  
    23.        size++;  
    24.    }  
    25.    /** 
    26.     * 以指定长度的数组来创建顺序线性表 
    27.     * @param element 指定顺序线性表中第一个元素 
    28.     * @param initSize 指定顺序线性表底层数组的长度 
    29.     */  
    30.    public SequenceList(T element , int initSize)  
    31.    {  
    32.        capacity = 1;  
    33.        //把capacity设为大于initSize的最小的2的n次方  
    34.        while (capacity < initSize)  
    35.        {  
    36.            capacity <<= 1;  
    37.        }  
    38.        elementData = new Object[capacity];  
    39.        elementData[0] = element;  
    40.        size++;  
    41.    }  
    42.    //获取顺序线性表的大小  
    43.    public int length()  
    44.    {  
    45.        return size;  
    46.    }  
    47.    //获取顺序线性表中索引为i处的元素  
    48.    public T get(int i)  
    49.    {  
    50.        if (i < 0 || i > size - 1)  
    51.        {  
    52.            throw new IndexOutOfBoundsException("线性表索引越界");  
    53.        }  
    54.        return (T)elementData[i];  
    55.    }  
    56.    //查找顺序线性表中指定元素的索引  
    57.    public int locate(T element)  
    58.    {  
    59.        for (int i = 0 ; i < size ; i++)  
    60.        {  
    61.            if (elementData[i].equals(element))  
    62.            {  
    63.                return i;  
    64.            }  
    65.        }  
    66.        return -1;  
    67.    }  
    68.    //向顺序线性表的指定位置插入一个元素。  
    69.    public void insert(T element , int index)  
    70.    {  
    71.        if (index < 0 || index > size)  
    72.        {  
    73.            throw new IndexOutOfBoundsException("线性表索引越界");  
    74.        }  
    75.        ensureCapacity(size + 1);  
    76.        //将index处以后所有元素向后移动一格。  
    77.        System.arraycopy(elementData , index , elementData  
    78.             , index + 1 , size - index);  
    79.        elementData[index] = element;  
    80.        size++;  
    81.    }  
    82.    //在线性顺序表的开始处添加一个元素。  
    83.    public void add(T element)  
    84.    {  
    85.        insert(element , size);  
    86.    }  
    87.    //很麻烦，而且性能很差  
    88.    private void ensureCapacity(int minCapacity)  
    89.    {  
    90.        //如果数组的原有长度小于目前所需的长度  
    91.        if (minCapacity > capacity)  
    92.        {  
    93.            //不断地将capacity * 2，直到capacity大于minCapacity为止  
    94.            while (capacity < minCapacity)  
    95.            {  
    96.                capacity <<= 1;  
    97.            }  
    98.            elementData = Arrays.copyOf(elementData , capacity);//此方法jdk1.6开始提供  
    99.        }  
    100.    }  
    101.    //删除顺序线性表中指定索引处的元素  
    102.    public T delete(int index)  
    103.    {  
    104.        if (index < 0 || index > size - 1)  
    105.        {  
    106.            throw new IndexOutOfBoundsException("线性表索引越界");  
    107.        }  
    108.        T oldValue = (T)elementData[index];  
    109.        int numMoved = size - index - 1;  
    110.        if (numMoved > 0)  
    111.        {  
    112.            System.arraycopy(elementData , index+1  
    113.                , elementData, index ,  numMoved);  
    114.        }  
    115.        //清空最后一个元素  
    116.        elementData[--size] = null;   
    117.        return oldValue;  
    118.    }  
    119.    //删除顺序线性表中最后一个元素  
    120.    public T remove()  
    121.    {  
    122.        return delete(size - 1);  
    123.    }  
    124.    //判断顺序线性表是否为空表  
    125.    public boolean empty()  
    126.    {  
    127.        return size == 0;  
    128.    }  
    129.    //清空线性表  
    130.    public void clear()  
    131.    {  
    132.        //将底层数组所有元素赋为null  
    133.        Arrays.fill(elementData , null);  
    134.        size = 0;  
    135.    }  
    136.    public String toString()  
    137.    {  
    138.        if (size == 0)  
    139.        {  
    140.            return "[]";  
    141.        }  
    142.        else  
    143.        {  
    144.            StringBuilder sb = new StringBuilder("[");  
    145.            for (int i = 0 ; i < size ; i++ )  
    146.            {  
    147.                sb.append(elementData[i].toString() + ", ");  
    148.            }  
    149.            int len = sb.length();  
    150.            return sb.delete(len - 2 , len).append("]").toString();  
    151.        }  
    152.    }  
    153.      
    154.    public static void main(String[] args)   
    155.    {  
    156.        SequenceList<String> list = new SequenceList<String>();  
    157.        list.add("aaaa");  
    158.        list.add("bbbb");  
    159.        list.add("cccc");  
    160.        //在索引为1处插入一个新元素  
    161.        list.insert("dddd" , 1);  
    162.        //输出顺序线性表的元素  
    163.        System.out.println(list);  
    164.        //删除索引为2处的元素  
    165.        list.delete(2);  
    166.        System.out.println(list);  
    167.        //获取cccc字符串在顺序线性表中的位置  
    168.        System.out.println("cccc在顺序线性表中的位置："   
    169.            + list.locate("cccc"));  
    170.    }  
    171.}