Java數據結構(gou)——線性表(biao)
時間(jian)：2019-07-10 來源(yuan)：濟南中心，吳老(lao)師
Java數據(ju)結(jie)構——線性表(biao)的(de)順序(xu)存儲實現
一、描(miao)述(shu)
線(xian)性結(jie)構特點：
（1）存(cun)在唯一的(de)一個(ge)被稱作“第一個(ge)”的(de)數據元素
（2）存(cun)在唯一(yi)的一(yi)個(ge)被稱作“最(zui)后(hou)一(yi)個(ge)”的數據元(yuan)素
（3）除第(di)一個之外，集合中(zhong)的每個數據(ju)元素均只有一個前驅
（4）除(chu)最后一個(ge)之外(wai)，集合中的每(mei)個(ge)數(shu)據元素均(jun)只有一個(ge)后繼
線(xian)性表(biao)：是n個數據元素的有(you)限序列(lie)。常用的兩種存(cun)儲(chu)(chu)結構(gou)為：線(xian)性表(biao)的順(shun)序存(cun)儲(chu)(chu)結構(gou)和線(xian)性表(biao)的鏈式存(cun)儲(chu)(chu)結構(gou)。
線(xian)性表的順序表示：指的是用(yong)一組地址(zhi)連續的存儲單元依次(ci)存儲線(xian)性表的數據元素。
本篇主要(yao)講線性表的順序(xu)存儲。
二、源碼
2.1 SequenceList.java
package com.yds.list;
import java.util.Arrays;
public class SequenceList<T>{
//默(mo)認(ren)長度
private int DEFAULT_SIZE = 2;
//定(ding)義一個數組用于(yu)保存線性(xing)表的長度
private Object[] elementData;
//用于保存數(shu)組長度(du)
private int capacity;
//保存(cun)順(shun)序表(biao)中當(dang)前元素的個(ge)數
private int size = 0;
/**
* 構造一個默認長(chang)度的空線性表
*/
public SequenceList(){
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
/**
* 用(yong)一個初(chu)始化元(yuan)素來創(chuang)建線性(xing)表(biao)
* @param element 初始(shi)化元素
*/
public SequenceList(T element){
this();
elementData[0] = element;
size++;
}
/**
* 用(yong)一個(ge)元素和指定長度來創建線性(xing)表
* @param element 元(yuan)素
* @param initSize 指定長度
*/
public SequenceList(T element,int initSize){
capacity = 1;
if(capacity<initSize){
capacity = initSize +2;
}
; elementData = new Object[capacity];
elementData[0] = element;
size++;
}
/**
* 向(xiang)順(shun)序表(biao)中插入(ru)元素
; * @param element 待插入的(de)元(yuan)素
* @param index 待插入(ru)的位置(zhi)
*/
public void insert(T element,int index){
if(index<0||index>size){
throw new IndexOutOfBoundsException("數組越界異常");
}
ensureCapacity(size+1);
//把(ba)index以后的元(yuan)素都后移一(yi)位(wei)
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);
}
/**
* 得到線性表存(cun)儲的對象
* @param index 獲(huo)得(de)的(de)位置
* @return 得到的結果
*/
public T get(int index){
if(index<0||index>size)
throw new IndexOutOfBoundsException("數組(zu)越界異常");
return (T)elementData[index];
}
/**
* 判斷線性表是否為空
* @return
*/
public boolean isEmpty(){
return size==0;
}
/**
* 清空線性表(biao)
*/
public void clear(){
Arrays.fill(elementData, null);
size = 0;
}
/**
* 獲取指定位(wei)置的前一個元素
* @param index 線性表位置(zhi)，若是取線性表最后(hou)一(yi)個元素(su)，必須index = size,
* size為線性表元素個數
* @return
*/
public T priorElem(int index){
if(index>0&&index<size+1)
return (T)elementData[index-1];
else {
; throw new IndexOutOfBoundsException("數組越界異(yi)常");
}
}
/**
* 刪除指(zhi)定(ding)位置的元(yuan)素
* @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--;
//清空最后一個(ge)元素(su)
elementData[size]=null;
}
}
/**
* 獲取指定線(xian)性表位置的后一個(ge)元素
* @param index 線(xian)性表位置(zhi)，若是取線(xian)性表第0個元(yuan)素，必須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("數組越界異(yi)常");
}
}
/**
* 確保數組(zu)所需長度大于數組(zu)原有長度
* @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 結果截圖
