Java实现顺序表的操作 Java实现顺序表的操作

本文实例为大家分享了Java实现顺序表的基本操作，供大家参考，具体内容如下
静态顺序表：使用定长数组存储。
动态顺序表：使用动态开辟的数组存储。
接口

package com.github.sqlist; public interface ISequence {// 在 pos 位置插入 valboolean add(int pos, Object data); // 查找关键字 key 找到返回 key 的下表，没有返回 -1int search(Object key); // 查找是否包含关键字 key 是否在顺序表当中（这个和search有点冲突）boolean contains(Object key); // 得到 pos 位置的值Object getPos(int pos); // 删除第一次出现的关键字 keyObject remove(Object key); // 得到顺序表的长度int size(); // 打印顺序表void display(); // 清空顺序表以防内存泄漏void clear(); }

实现接口里的每个方法

package com.github.sqlist; import java.util.Arrays; /* * 顺序表 */public class MySequenceImpl implements ISequence {private Object[] elem; // 有效数据个数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*/@Overridepublic 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位置以及之后的数全部向后挪一个位置for (int i = this.usedSize-1; i >= pos; i--) {this.elem[i+1] = this.elem[i]; }// 4. 在 pos 位置插入 valthis.elem[pos] = data; // 5. 更新长度this.usedSize++; return true; }/*** 判断是否为空* @return 表为空返回true，否则返回false*/private boolean isEmpty() {return this.usedSize == 0; }/*** 查找关键字 key 找到返回 key 的下表，没有返回 -1* @param key 关键字的值* @return 查找成功返回true，失败返回false*/@Overridepublic int search(Object key) {// 1. 判断是否为空if (isEmpty()) {return -1; }// 2. 遍历查找for (int i = 0; i < this.elem.length; i++) {// 注意：判断条件不能写成：this.elem[i] == keyif (this.elem[i].equals(key)) {return i; }}return -1; }/*** 查找是否包含关键字 key 是否在顺序表当中（这个和search有点冲突）* @param key 关键字的值* @return 查找成功返回true，失败返回false*/@Overridepublic boolean contains(Object key) {// 1. 判断是否为空if (isEmpty()) {return false; }// 2. 遍历查找for (int i = 0; i < this.elem.length; i++) {// 注意：判断条件不能写成：this.elem[i] == keyif (this.elem[i].equals(key)) {return true; }}return false; }/*** 得到 pos 位置的值* @param pos 得到的值的位置* @return 成功得到 pos位置的值返回true，否则返回false*/@Overridepublic Object getPos(int pos) {// 1. 判断位置是否合法if (pos<0 || pos>=this.elem.length) {return null; }// 2. 位置合法return this.elem[pos]; }/*** 删除第一次出现的关键字 key* @param key 关键字* @return*/@Overridepublic Object remove(Object key) {// 1. 先查表看有没有这个关键字// index:关键字下标int index = search(key); // 2. 若表里没有这个关键字if (index == -1) {return null; }// 3. 表里有这个关键字Object data = https://www.it610.com/article/this.elem[index]; int i; // 删除第一次出现的关键字 key,把key后面的数全部向前挪一个位置for (i = index; i < this.usedSize; i++) {elem[i] = elem[i+1]; }this.usedSize--; this.elem[i+1] = null; return data; }/*** 得到顺序表的长度* @return 顺序表的长度*/@Overridepublic int size() {return this.usedSize; }/*** 打印顺序表*/@Overridepublic void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(this.elem[i] +" "); }System.out.println(); }/*** 清空顺序表以防内存泄漏*/@Overridepublic 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的范围内插入数据："); 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("随机位置插入数据："); mySequence.add(9,"list"); mySequence.display(); System.out.println(); System.out.println("search查找一个数据："+mySequence.search("list")); System.out.println("contains查找一个数据："+mySequence.contains("list")); System.out.println(); System.out.println("查找某一个位置对应的值："+mySequence.getPos(9)); System.out.println(); System.out.println("删除一个数据："+mySequence.remove(8)); mySequence.display(); System.out.println(); System.out.println("得到顺序表的长度:"+mySequence.size()); }}

测试结果：