Java實現(xiàn)順序表的操作
本文實例為大家分享了Java實現(xiàn)順序表的基本操作,供大家參考,具體內(nèi)容如下
靜態(tài)順序表:使用定長數(shù)組存儲。
動態(tài)順序表:使用動態(tài)開辟的數(shù)組存儲。
接口
package com.github.sqlist; public interface ISequence { ? ? // 在 pos 位置插入 val ? ? boolean add(int pos, Object data); ? ? // 查找關(guān)鍵字 key 找到返回 key 的下表,沒有返回 -1 ? ? int search(Object key); ? ? // 查找是否包含關(guān)鍵字 key 是否在順序表當(dāng)中(這個和search有點沖突) ? ? boolean contains(Object key); ? ? // 得到 pos 位置的值 ? ? Object getPos(int pos); ? ? // 刪除第一次出現(xiàn)的關(guān)鍵字 key ? ? Object remove(Object key); ? ? // 得到順序表的長度 ? ? int size(); ? ? // 打印順序表 ? ? void display(); ? ? // 清空順序表以防內(nèi)存泄漏 ? ? void clear(); }
實現(xiàn)接口里的每個方法
package com.github.sqlist; import java.util.Arrays; /* ?* 順序表 ?*/ public class MySequenceImpl implements ISequence { ? ? private Object[] elem; ? ? // 有效數(shù)據(jù)個數(shù) ? ? private int usedSize; ? ? private static final int DEFAULT_SIZE = 10; ? ? public SqList() { ? ? ? ? this.elem = new Object[DEFAULT_SIZE]; ? ? ? ? this.usedSize = 0; ? ? } ? ? /** ? ? ?* 判斷是否為滿 ? ? ?* @return 滿了返回true,否則返回false ? ? ?*/ ? ? private boolean isFull() { ? ? ? ? return this.elem.length == this.usedSize; ? ? } ? ? /** ? ? ?* 在 pos 位置插入 val ? ? ?* @param pos ? ? ?* ? ? ? ?要插入的位置 ? ? ?* @param data ? ? ?* ? ? ? ?要插入的值 ? ? ?* @return ? ? ?* ? ? ? ?插入成功返回true,否則返回false ? ? ?*/ ? ? @Override ? ? public boolean add(int pos, Object data) { ? ? ? ? // 1. 判斷pos位置的合法性 ? ? ? ? if (pos < 0 || pos > this.elem.length) { ? ? ? ? ? ? return false; ? ? ? ? } ? ? ? ? // 2. 判斷是否滿了,如果滿了進行擴容 ? ? ? ? if (isFull()) { ? ? ? ? ? ? this.elem = Arrays.copyOf(this.elem, 2*this.elem.length); ? ? ? ? } ? ? ? ? // 3. 把pos位置以及之后的數(shù)全部向后挪一個位置 ? ? ? ? for (int i = this.usedSize-1; i >= pos; i--) { ? ? ? ? ? ? this.elem[i+1] = this.elem[i]; ? ? ? ? } ? ? ? ? // 4. 在 pos 位置插入 val ? ? ? ? this.elem[pos] = data; ? ? ? ? // 5. 更新長度 ? ? ? ? this.usedSize++; ? ? ? ? return true; ? ? } ? ? /** ? ? ?* 判斷是否為空 ? ? ?* @return 表為空返回true,否則返回false ? ? ?*/ ? ? private boolean isEmpty() { ? ? ? ? return this.usedSize == 0; ? ? } ? ? /** ? ? ?* 查找關(guān)鍵字 key 找到返回 key 的下表,沒有返回 -1 ? ? ?* @param key 關(guān)鍵字的值 ? ? ?* @return 查找成功返回true,失敗返回false ? ? ?*/ ? ? @Override ? ? public int search(Object key) { ? ? ? ? // 1. 判斷是否為空 ? ? ? ? if (isEmpty()) { ? ? ? ? ? ? return -1; ? ? ? ? } ? ? ? ? // 2. 遍歷查找 ? ? ? ? for (int i = 0; i < this.elem.length; i++) { ? ? ? ? ? ? // 注意:判斷條件不能寫成:this.elem[i] == key ? ? ? ? ? ? if (this.elem[i].equals(key)) { ? ? ? ? ? ? ? ? return i; ? ? ? ? ? ? } ? ? ? ? } ? ? ? ? return -1; ? ? } ? ? /** ? ? ?* 查找是否包含關(guān)鍵字 key 是否在順序表當(dāng)中(這個和search有點沖突) ? ? ?* @param key 關(guān)鍵字的值 ? ? ?* @return 查找成功返回true,失敗返回false ? ? ?*/ ? ? @Override ? ? public boolean contains(Object key) { ? ? ? ? // 1. 判斷是否為空 ? ? ? ? if (isEmpty()) { ? ? ? ? ? ? return false; ? ? ? ? } ? ? ? ? // 2. 遍歷查找 ? ? ? ? for (int i = 0; i < this.elem.length; i++) { ? ? ? ? ? ? // 注意:判斷條件不能寫成:this.elem[i] == key ? ? ? ? ? ? if (this.elem[i].equals(key)) { ? ? ? ? ? ? ? ? return true; ? ? ? ? ? ? } ? ? ? ? } ? ? ? ? return false; ? ? } ? ? /** ? ? ?* 得到 pos 位置的值 ? ? ?* @param pos 得到的值的位置 ? ? ?* @return 成功得到 pos位置的值返回true,否則返回false ? ? ?*/ ? ? @Override ? ? public Object getPos(int pos) { ? ? ? ? // 1. 判斷位置是否合法 ? ? ? ? if (pos<0 || pos>=this.elem.length) { ? ? ? ? ? ? return null; ? ? ? ? } ? ? ? ? // 2. 位置合法 ? ? ? ? return this.elem[pos]; ? ? } ? ? /** ? ? ?* 刪除第一次出現(xiàn)的關(guān)鍵字 key ? ? ?* @param key 關(guān)鍵字 ? ? ?* @return ? ? ?*/ ? ? @Override ? ? public Object remove(Object key) { ? ? ? ? // 1. 先查表看有沒有這個關(guān)鍵字 ? ? ? ? // index:關(guān)鍵字下標(biāo) ? ? ? ? int index = search(key); ? ? ? ? // 2. 若表里沒有這個關(guān)鍵字 ? ? ? ? if (index == -1) { ? ? ? ? ? ? return null; ? ? ? ? } ? ? ? ? // 3. 表里有這個關(guān)鍵字 ? ? ? ? Object data = this.elem[index]; ? ? ? ? int i; ? ? ? ? // 刪除第一次出現(xiàn)的關(guān)鍵字 key,把key后面的數(shù)全部向前挪一個位置 ? ? ? ? for (i = index; i < this.usedSize; i++) { ? ? ? ? ? ? elem[i] = elem[i+1]; ? ? ? ? } ? ? ? ? this.usedSize--; ? ? ? ? this.elem[i+1] = null; ? ? ? ? return data; ? ? } ? ? /** ? ? ?* 得到順序表的長度 ? ? ?* @return 順序表的長度 ? ? ?*/ ? ? @Override ? ? public int size() { ? ? ? ? return this.usedSize; ? ? } ? ? /** ? ? ?* 打印順序表 ? ? ?*/ ? ? @Override ? ? public void display() { ? ? ? ? for (int i = 0; i < this.usedSize; i++) { ? ? ? ? ? ? System.out.print(this.elem[i] + " "); ? ? ? ? } ? ? ? ? System.out.println(); ? ? } ? ? /** ? ? ?* 清空順序表以防內(nèi)存泄漏 ? ? ?*/ ? ? @Override ? ? public void clear() { ? ? ? ? for (int i = 0; i < this.usedSize; i++) { ? ? ? ? ? ? this.elem[i] = null; ? ? ? ? } ? ? } }
測試方法的正確性
package com.github.sqlist; public class TestDemo1 { ? ? public static void main(String[] args) { ? ? ? ? MySequenceImpl mySequence = new MySequenceImpl(); ? ? ? ? for (int i = 0; i < 10; i++) { ? ? ? ? ? ? mySequence.add(i,i); ? ? ? ? } ? ? ? ? System.out.println("在最大值10的范圍內(nèi)插入數(shù)據(jù):"); ? ? ? ? mySequence.display(); ? ? ? ? System.out.println(); ? ? ? ? for (int i = 10; i < 20; i++) { ? ? ? ? ? ? mySequence.add(i,i); ? ? ? ? } ? ? ? ? System.out.println("擴容:"); ? ? ? ? mySequence.display(); ? ? ? ? System.out.println(); ? ? ? ? System.out.println("隨機位置插入數(shù)據(jù):"); ? ? ? ? mySequence.add(9,"list"); ? ? ? ? mySequence.display(); ? ? ? ? System.out.println(); ? ? ? ? System.out.println("search查找一個數(shù)據(jù):"+mySequence.search("list")); ? ? ? ? System.out.println("contains查找一個數(shù)據(jù):"+mySequence.contains("list")); ? ? ? ? System.out.println(); ? ? ? ? System.out.println("查找某一個位置對應(yīng)的值:"+mySequence.getPos(9)); ? ? ? ? System.out.println(); ? ? ? ? System.out.println("刪除一個數(shù)據(jù):"+mySequence.remove(8)); ? ? ? ? mySequence.display(); ? ? ? ? System.out.println(); ? ? ? ? System.out.println("得到順序表的長度:"+mySequence.size()); ? ? } }
測試結(jié)果:
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
Java多線程run方法中直接調(diào)用service業(yè)務(wù)類應(yīng)注意的問題及解決
這篇文章主要介紹了Java多線程run方法中直接調(diào)用service業(yè)務(wù)類應(yīng)注意的問題及解決,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-06-06J2EE Servlet基礎(chǔ)在瀏覽器上運行HelloServlet的方法
這篇文章主要介紹了J2EE Servlet基礎(chǔ)在瀏覽器上運行HelloServlet的方法,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-10-10RestTemplate發(fā)送請求時Cookie的影響及注意事項說明
這篇文章主要介紹了RestTemplate發(fā)送請求時Cookie的影響及注意事項說明,具有很好的參考價值,希望對大家有所幫助。2023-07-07springboot jackson自定義序列化和反序列化實例
這篇文章主要介紹了spring boot jackson自定義序列化和反序列化實例,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-10-10@CacheEvict 清除多個key的實現(xiàn)方式
這篇文章主要介紹了@CacheEvict 清除多個key的實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2021-02-02