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 結果截圖
