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））;

}

}