java數據構造完成次序表現例。本站提示廣大學習愛好者:(java數據構造完成次序表現例)文章只能為提供參考,不一定能成為您想要的結果。以下是java數據構造完成次序表現例正文
import java.util.Arrays;
/**
* 次序線性表的完成
*/
public class LineList<E>{
private int size; //長度
private Object[] array; //底層數組
private final int default_length=16; //默許長度
/**
* 無參結構辦法
*/
public LineList(){
size = 0;
//應用默許長度結構數組
array = new Object[default_length];
}
/**
* 指定長度停止結構
* @param length 指定初始長度
*/
public LineList(int length){
if(length<0){
throw new IllegalArgumentException("初始長度不正當:"+length);
}
//應用指定長度結構數組
array = new Object[length];
}
/**
* 指定初始化元素和長度停止結構
* @param element 初始化元素
* @param length 初始化長度
*/
public LineList(E element,int length){
if(length<1){
throw new IllegalArgumentException("初始長度不正當:"+length);
}
//應用指定長度結構數組
array = new Object[length];
//初始化第一個元素
array[0] = element;
size++;
}
/**
* 指定初始化元素停止結構
* @param element 初始化元素
*/
public LineList(E element){
//應用默許長度初始化數組
array = new Object[default_length];
//初始化第一個元素
array[0] = element;
}
/**
* 獲得元素個數
*/
public int size() {
return size;
}
/**
* 斷定能否為空
*/
public boolean isEmpty() {
return size==0;
}
/**
* 斷定能否包括此元素
*/
public boolean contains(E e) {
if(indexOf(e) == -1){
return false;
}
return true;
}
/**
* 格局化為數組
*/
public Object[] toArray() {
return Arrays.copyOf(array, size);
}
/**
* 向線性表尾部添加一個元素
* @param e
* @return
*/
public void add(E e) {
extendCapacity(size+1);
array[size]=e;
size++;
}
/**
* 擴容
* @param length 須要的長度
*/
private void extendCapacity(int length){
//以後數組長度和須要的長度取最年夜
int minCapacity = Math.max(array.length, length);
//斷定能否須要擴容
if(minCapacity - array.length>0){
//數組長度增長一半
int newLength = array.length + array.length/2;
//假如新的長度還比需求要小,將需求的長度作為數組長度
if(newLength < minCapacity){
newLength=minCapacity;
}
//數組長度不克不及跨越Integer.Max_Value
if(newLength > Integer.MAX_VALUE - 8){
newLength = Integer.MAX_VALUE;
}
//數組擴容
array = Arrays.copyOf(array, newLength);
}
}
/**
* 從線性表中移除一切此元素
* @param e 須要移除的元素
* @return
*/
public void removeAll(E e) {
if(e==null){
for(int i=0;i<size;i++){
if(array[i]==null){
fastRemove(i);
}
}
}else{
for(int i=0;i<size;i++){
if(e.equals(array[i])){
fastRemove(i);
}
}
}
}
/**
* 刪除索引處元素,前面的元素順次前移
* @param index 須要刪除的索引
*/
private void fastRemove(int index){
if(size-index-1>0){
//數組從index+1開端全體前移
System.arraycopy(array, index+1, array, index, size-1);
}
//最初一個元素請空
array[--size]=null;
}
/**
* 清空線性表
*/
public void clear() {
//將數組全體填充為null
Arrays.fill(array, null);
//將元素個數改成0
size=0;
}
/**
* 取得索引處的元素
* @param index
* @return 索引處的元素
*/
@SuppressWarnings("unchecked")
public E get(int index) {
checkIndex(index);
return (E)array[index];
}
/**
* 驗證能否為索引越界
* @param index
*/
private void checkIndex(int index){
if(index>=size || index<0){
throw new IndexOutOfBoundsException("索引越界");
}
}
/**
* 將索引處的元素修正為新的元素
* @param index 索引地位
* @param element 元素
* @return 原索引處的元素
*/
@SuppressWarnings("unchecked")
public E set(int index, E element) {
checkIndex(index);
E e = (E)array[index];
array[index]=element;
return e;
}
/**
* 在指定的索引處拔出指定的元素
* @param index 索引地位
* @param element 元素
*/
public void add(int index, E element) {
//驗證索引
checkIndex(index);
//能否須要擴容
extendCapacity(size+1);
//復制數組
System.arraycopy(array, index, array, index+1, size-index);
array[index]=element;
}
/**
* 移除索引處的元素
* @param index 索引
* @return 刪除的元素
*/
@SuppressWarnings("unchecked")
public E remove(int index) {
checkIndex(index);
//獲得索引地位的元素
E e = (E)array[index];
fastRemove(index);
return e;
}
/**
* 獲得元素第一次湧現的地位的索引
* @param e 要查找的元素
* @return 假如為-1解釋線性表沒有這個元素
*/
public int indexOf(E e) {
if(e==null){
for(int i=0;i<size;i++){
if(e==array[i]){
return i;
}
}
}
for(int i=0;i<size;i++){
if(e.equals(array[i])){
return i;
}
}
return -1;
}
/**
* 獲得元素最初一次湧現的地位的索引
* @param e 要查找的元素
* @return 假如為-1解釋線性表沒有這個元素
*/
public int lastIndexOf(E e) {
//斷定元素能否為null
if(e==null){
for(int i=size-1;i>=0;i--){
if(e==array[i]){
return i;
}
}
}
for(int i=size-1;i>=0;i--){
//假如為null這裡會跑出NullPoint異常
//所之前面要加上驗證能否為Null
if(e.equals(array[i])){
return i;
}
}
return -1;
}
/**
* 截取線性表
* @param fromIndex 開端索引
* @param toIndex 停止索引
* @return 截取的線性表
*/
@SuppressWarnings("unchecked")
public LineList<E> subList(int fromIndex, int toIndex) {
//斷定開端索引能否越界
if(fromIndex<0 || fromIndex >=size){
throw new IndexOutOfBoundsException("開端索引越界:"+fromIndex);
}
//斷定停止索引能否越界
if(toIndex >=size || fromIndex <0){
throw new IndexOutOfBoundsException("停止索引越界:"+toIndex);
}
//斷定開端索引和停止索引能否准確
if(fromIndex > toIndex){
throw new IllegalArgumentException("參數不准確,開端索引應年夜於等於停止索引");
}
LineList<E> list = new LineList<E>();
for(int i=fromIndex,j=toIndex;i<=j;i++){
list.add((E)array[i]);
}
return list;
}
}