Java實現一個順序表的完整代碼
實現一個順序表
接口實現
定義一個MyArrayList類,在類中實現以下函數
public class MyArrayList { }
數組的定義
public int[] elem;//定義一個整形數組 public int usize;//usize表示數組的長度 public MyArrayList(){ this.elem = new int[5]; }
打印順序表
for循環打印順序表的每一位
public void display(){ for (int i = 0; i < this.usize; i++) { System.out.print(this.elem[i]+" "); } System.out.println(); }
在pos位置新增元素
先定義一個isFull函數判斷順序表是否滿瞭,滿瞭返回true,沒滿則返回false
public boolean isFull(){ if (this.usize == this.elem.length){ return true; } return false; }
將pos位置後的元素後移,順序表順序表長度增加一位
public void add(int pos, int data){ //判斷順序表是否滿瞭 if (isFull()){ System.out.println("順序表已滿"); //擴容 this.elem = Arrays.copyOf(this.elem,2*this.usize); } //判斷pos的合法性 if (pos < 0 || pos > this.usize){ System.out.println("pos位置不合法"); return; } //將pos位置後的數字後移 for (int i = this.usize-1; i >= pos; i--) { this.elem[i+1] = this.elem[i]; } this.elem[pos] = data; this.usize++; }
判定是否包含某個元素
public boolean contains(int key){ for (int i = 0; i < this.usize; i++) { if (this.elem[i] == key){ return true; } } return false; }
查找某個對應元素的位置
返回它的位置
public int search(int key){ for (int i = 0; i < this.usize; i++) { if (this.elem[i] == key){ return i; } } return -1; }
獲取pos位置的元素
定義一個isEmpty函數判斷順序表是否為空
public boolean isEmpty(){ return this.usize == 0; }
public int getPos(int pos){ //判斷順序表是否為空 if (isEmpty()){ return -1; } //判斷pos 位置是否合法 if (pos < 0 || pos >= this.usize){ return -1; } return this.elem[pos]; }
給pos位置的元素設為value 更新為新的數字
public void setPos(int pos,int value){ //判斷順序表是否為空 if (isEmpty()){ return; } //判斷pos位置是否合法 if (pos < 0 || pos >= this.usize){ return; } this.elem[pos] = value; }
刪除第一次出現的關鍵字key
查找到關鍵字,從關鍵字所在的位置開始到順序表結束每一項前移,覆蓋掉關鍵字,長度減少一位
public void remove(int key){ int index= search(key); if (key == -1){ System.out.println("關鍵字不存在"); return; } for (int i = key; i < this.usize-1; i++) { this.elem[i] = this.elem[i+1]; } this.usize--; }
獲取順序表長度
public int size(){ return this.usize; }
清空順序表
順序表長度直接為0
public void clear(){ this.usize = 0; }
實現這個順序表
定義一個測試類,測試這些函數的輸出
public class TestDemo { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(); //給這個順序表寫入1,2,3,4,5 myArrayList.add(0,1); myArrayList.add(1,2); myArrayList.add(2,3); myArrayList.add(3,4); myArrayList.add(4,5); //打印這個順序表 myArrayList.display(); //判定5這個元素是否在該順序表中 System.out.println(myArrayList.contains(5)); //查找5這個元素 返回它的位置 System.out.println(myArrayList.search(5)); //獲取3位置的元素 System.out.println(myArrayList.getPos(3)); //將4位置的元素重新賦值為9 myArrayList.setPos(4,9); //打印新的順序表 myArrayList.display(); //刪除第一次出現的元素4 myArrayList.remove(4); //打印新的順序表 myArrayList.display(); //獲取順序表的長度 System.out.println(myArrayList.size()); System.out.println("清空"); //清空順序表 myArrayList.clear(); //打印新的順序表 myArrayList.display(); } }
得到結果:
順序表的優缺點
優點:順序表查找方便,知道這個元素的位置就可以直接找到這個元素。
缺點:擴容一般成2倍增長,會有一定的空間浪費。
推薦閱讀:
- None Found