Java线性表 插入、删除、查找、替换等功能

通过接口定义一组线性表中的操作

public interface MyList {int  getSize();     //返回线性表中元素的个数boolean isEmpty();     //判断线性表是否为空void insert(int i,Object e);     //在线性表的i索引值添加元素eboolean contains(Object e);     //判断线性表中是否包含元素eint indexOf(Object e);      //返回线性表中元素e的索引值Object remove(Object e);     //删除线性表中第一个与e相同的元素并返回该元素Object remove(int i);     //删除线性表中第一个索引值为i的元素并返回该元素Object replace(int i,Object e);     //使用元素e替换线性表中i位置的元素并返回旧元素Object get(int i);     //返回索引值为i的元素boolean insertBefore(Object p,Object e);     //在线性表元素p之前插入元素eboolean insertAfter(Object p,Object e);     //在线性表元素p之后插入元素eint getMax();     //返回线性表中的最大值int getMin();     //返回线性表中的最小值
}

通过数组实现线性表

public class MyArrayList implements MyList {private Object[] elements;     //定义数组保存数据元素private static final int DEFAULT_CAPACITY = 26;     //数组默认初始化容量private int size;     //保存数据元素个数//构造方法public MyArrayList() {elements = new Object[DEFAULT_CAPACITY];}public MyArrayList(int initialCapacity) {elements = new Object[initialCapacity];}//返回元素个数@Overridepublic int getSize() {return size;}//判断线性表是否为空@Overridepublic boolean isEmpty() {return size == 0;}//在线性表的i索引值添加元素e@Overridepublic void insert(int i, Object e) {//判断索引值i是否超出if (i < 0 || i > size) {throw new IndexOutOfBoundsException(i + "越界");}//如果数组溢满则对数组扩容if (size >= elements.length) {expandSpace();}//从i+1开始元素依次后移for (int j = size; j > i; j--) {elements[j] = elements[j - 1];}//把元素e存储到i位置elements[i] = e;//元素个数加一size++;}//判断线性表中是否包含元素e@Overridepublic boolean contains(Object e) {return indexOf(e) >= 0;}//返回线性表中元素e的索引值@Overridepublic int indexOf(Object e) {//遍历数组if (e == null) {//线性表中用户可能添加nullfor (int i = 0; i < size; i++) {if (elements[i] == null) {return i;}}} else {for (int i = 0; i < size; i++) {if (e.equals(elements[i])) {return i;}}}return -1;}//删除线性表中第一个与e相同的元素并返回该元素@Overridepublic Object remove(Object e) {//获得e在线性表中的索引值int index = indexOf(e);if (index < 0) {return 0;}return remove(index);}//删除线性表中第一个索引值为i的元素并返回该元素@Overridepublic Object remove(int i) {//判断i是否越界if (i < 0 || i >= size) {throw new IndexOutOfBoundsException(i + "越界");}//保存即将删除的元素Object old = elements[i];//把i+1开始的元素依次前移for (int j = i; j < size - 1; j++) {elements[j] = elements[j + 1];}elements[size - 1] = 0;//修改元素个数size--;//返回删除元素return old;}//使用元素e替换线性表中i位置的元素并返回旧元素@Overridepublic Object replace(int i, Object e) {//判断索引值是否越界if (i < 0 || i >= size) {throw new IndexOutOfBoundsException(i + "越界");}//保存元素原来的值Object old = elements[i];//替换elements[i] = e;//把原来的元素值返回return old;}//返回索引值为i的元素@Overridepublic Object get(int i) {//判断索引值是否越界if (i < 0 || i >= size) {throw new IndexOutOfBoundsException(i + "越界");}return elements[i];}//在线性表元素p之前插入元素e@Overridepublic boolean insertBefore(Object p, Object e) {//确定元素p在线性表中的位置int index = indexOf(p);if (index < 0) {//元素p不存在return false;}//插入元素insert(index, e);return true;}//在线性表元素p之后插入元素e@Overridepublic boolean insertAfter(Object p, Object e) {//确定元素p在线性表中的位置int index = indexOf(p);if (index < 0) {//元素p不存在return false;}//插入元素insert(index + 1, e);return true;}//返回线性表中的最大值@Overridepublic int getMax() {int maxIndex = (int) elements[0];for (int i = 1; i < size; i++) {if (maxIndex < (int) elements[i]) {maxIndex = (int) elements[i];}}return maxIndex;}//返回线性表中的最小值@Overridepublic int getMin() {int minIndex = (int) elements[0];for (int i = 1; i < size; i++) {if (minIndex > (int) elements[i]) {minIndex = (int) elements[i];}}return minIndex;}//重写toString方法@Overridepublic String toString() {//把线性表中的每个元素连接起来，遍历数组中的已添加的元素StringBuilder sb = new StringBuilder();sb.append("[");for (int i = 0; i < size; i++) {sb.append(elements[i]);if (i < size - 1) {sb.append(",");}}sb.append("]");return sb.toString();}//数组扩容private void expandSpace() {//定义一个更大的数组Object[] newElements = new Object[elements.length * 2];//把原来的数据复制到新数组中for (int i = 0; i < elements.length; i++) {newElements[i] = elements[i];}//让原来的数组名指向新的1数组elements = newElements;}
}

测试类

public class MyListTest {public static void main(String[] args) {//创建一个MyArrayList对象 测试MyArrayList list = new MyArrayList();//判断是否为空 测试System.out.println(list.isEmpty());System.out.println(list.getSize());//添加元素 测试list.insert(0, "Cheng");list.insert(1, "Shuang");list.insert(0, "2001");System.out.println(list.isEmpty());System.out.println(list.getSize());//把线性表中的内容输出 测试System.out.println(list);//判断元素是否存在 测试System.out.println(list.indexOf("2001"));System.out.println(list.indexOf("Shuang"));System.out.println(list.indexOf("2019"));System.out.println(list.contains("2001"));System.out.println(list.contains("2000"));//删除 测试list.remove("2001");System.out.println(list);//替换 测试list.insert(0, "Poke");list.insert(0, "Tao");list.insert(0, "Jie");list.insert(0, "Hao");System.out.println(list);list.replace(0, "Van");System.out.println(list);//返回指定索引的元素 测试System.out.println(list.get(0));System.out.println(list.get(1));System.out.println(list.get(2));System.out.println(list.get(3));//在指定的元素前面或后面插入 测试list.insertBefore("Van", "YYDS");System.out.println(list);list.insertAfter("Jie", "Ge");System.out.println(list);list.insertAfter("AWei", "BinBin");System.out.println(list);/*//最大最小值 测试list.insert(0, 22);list.insert(1, 26);list.insert(2, 28);list.insert(3, 24);list.insert(4, 16);list.insert(5, 12);System.out.println(list);System.out.println(list.isEmpty());System.out.println(list.getMax());System.out.println(list.getMin());*/}
}

实例
1、编写程序，实现以下操作:在线性表中插入一个元素,再删除指定位置的元素,分别输出插入、删除后的线性表。
2、在顺序表中设计函数实现以下操作:
(1).求顺序表中的最大值和最小值。
(2).在顺序表中删除具有最小值的元素(假设顺序表中元素都不相同) ,并由函数返回被删除元素的值,空出的位置由最后一个元素填补。

import java.util.Scanner;public class Test {public static void main(String[] args) {//创建一个MyArrayList对象MyArrayList list = new MyArrayList();Scanner s = new Scanner(System.in);System.out.println("请输入线性表长度：");int a = s.nextInt();System.out.println("请依次输入线性表元素：");for (int i=0;i<a;i++){int b = s.nextInt();list.insert(i,b);}System.out.print("线性表：");System.out.println(list);System.out.println("请输入需插入的索引值与元素：");int c = s.nextInt();int d = s.nextInt();list.insert(c,d);System.out.print("线性表：");System.out.println(list);System.out.println("请输入需删除的元素的索引值：");int e = s.nextInt();list.remove(e);System.out.print("线性表：");System.out.println(list);System.out.print("最小值：");System.out.println(list.getMin());int h = list.indexOf(list.getMin());list.remove(h);System.out.println("最小值已被删除。");System.out.println("空出的位置由最后一个元素填补。");list.insert(h,list.get(a-2));list.remove(a-1);System.out.print("线性表：");System.out.println(list);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！