電子發燒友App
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））;
}
}
責任編輯：ct
工商網監
評論