電子發(fā)燒友App
Java數(shù)據(jù)結(jié)構(gòu)——線性表的順序存儲(chǔ)實(shí)現(xiàn)
一、描述
線性結(jié)構(gòu)特點(diǎn)：
（1）存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素
（2）存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素
（3）除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)
（4）除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼
線性表：是n個(gè)數(shù)據(jù)元素的有限序列。常用的兩種存儲(chǔ)結(jié)構(gòu)為：線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
線性表的順序表示：指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
本篇主要講線性表的順序存儲(chǔ)。 二、源碼
2.1 SequenceList.java
package com.yds.list;
import java.util.Arrays;
public class SequenceList《T》{
//默認(rèn)長(zhǎng)度
private int DEFAULT_SIZE = 2;
//定義一個(gè)數(shù)組用于保存線性表的長(zhǎng)度
private Object［］ elementData;
//用于保存數(shù)組長(zhǎng)度
private int capacity;
//保存順序表中當(dāng)前元素的個(gè)數(shù)
private int size = 0;
/**
* 構(gòu)造一個(gè)默認(rèn)長(zhǎng)度的空線性表
*/
public SequenceList（）{
capacity = DEFAULT_SIZE;
elementData = new Object［capacity］;
}
/**
* 用一個(gè)初始化元素來(lái)創(chuàng)建線性表
* @param element 初始化元素
*/
public SequenceList（T element）{
this（）;
elementData［0］ = element;
size++;
}
/**
* 用一個(gè)元素和指定長(zhǎng)度來(lái)創(chuàng)建線性表
* @param element 元素
* @param initSize 指定長(zhǎng)度
*/
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（“數(shù)組越界異常”）;
}
ensureCapacity（size+1）;
//把index以后的元素都后移一位
System.arraycopy（elementData， index， elementData， index+1， size-index）;
elementData［index］ = element;
size++;
}
/**
* 表長(zhǎng)
* @return
*/
public int length（）{
return size;
}
/**
* 向表中添加元素
* @param element
*/
public void add（T element）{
insert（element， size）;
}
/**
* 得到線性表存儲(chǔ)的對(duì)象
* @param index 獲得的位置
* @return 得到的結(jié)果
*/
public T get（int index）{
if（index《0||index》size）
throw new IndexOutOfBoundsException（“數(shù)組越界異常”）;
return （T）elementData［index］;
}
/**
* 判斷線性表是否為空
* @return
*/
public boolean isEmpty（）{
return size==0;
}
/**
* 清空線性表
*/
public void clear（）{
Arrays.fill（elementData， null）;
size = 0;
}
/**
* 獲取指定位置的前一個(gè)元素
* @param index 線性表位置，若是取線性表最后一個(gè)元素，必須index = size，
* size為線性表元素個(gè)數(shù)
* @return
*/
public T priorElem（int index）{
if（index》0&&index《size+1）
return （T）elementData［index-1］;
else {
throw new IndexOutOfBoundsException（“數(shù)組越界異常”）;
}
}
/**
* 刪除指定位置的元素
* @param index
*/
public void delete（int index）{
if（index《0||index》size-1）{
throw new IndexOutOfBoundsException（“數(shù)組越界異常”）;
}else{
//把數(shù)組前移一位
System.arraycopy（elementData， index+1， elementData， index， size-index-1）;
size--;
//清空最后一個(gè)元素
elementData［size］=null;
}
}
/**
* 獲取指定線性表位置的后一個(gè)元素
* @param index 線性表位置，若是取線性表第0個(gè)元素，必須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（“數(shù)組越界異常”）;
}
}
/**
* 確保數(shù)組所需長(zhǎng)度大于數(shù)組原有長(zhǎng)度
* @param mCapacity 數(shù)組所需長(zhǎng)度
*/
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（“l(fā)ength：”+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（“l(fā)ength：”+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））;
}
}
責(zé)任編輯：ct
工商網(wǎng)監(jiān)
評(píng)論