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