老师布置的作业,用Java实现线性表,自己写了一个,小小的测试了一下,可能我不够细心,没发现什么bug.如果有发现什么问题,欢迎指出(✪ω✪)
代码:
interface List<T> {
boolean isEmpty(); // 判断线性表是否为空
int length(); // 求线性表长度
void clear(); // 清空线性表
void add(T elem); // 向表尾添加元素
void addAll(List<? extends T> list); // 合并两个表
T get(int index); // 获得指定位置的值
void insert(int index, T elem); // 向指定位置插入元素
void replace(int index, T elem); // 替换指定位置的值
int indexOf(T elem); // 返回元素在表中的位置
T remove(int index); // 删除指定位置的值
boolean contains(T elem); // 判断值是否在表中
}
public class SeqList<T> implements List<T> {
private int defaultCapacity = 10; // 默认容器大小
private Object[] elemData; // 存储元素的容器
private int size; // 线性表长度
public SeqList() {
elemData = new Object[defaultCapacity];
}
public SeqList(int initialCapacity) {
elemData = new Object[initialCapacity];
}
public SeqList(Object[] arr) {
this.elemData = new Object[arr.length];
System.arraycopy(arr, 0, elemData, 0, arr.length);
size = arr.length - 1;
}
/**
* 判空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 获得表长
* @return
*/
public int length() {
return size;
}
/**
* 清空
*/
public void clear() {
elemData = new Object[defaultCapacity];
size = 0;
}
public void add(T elem) {
if (size > elemData.length) {
throw new IndexOutOfBoundsException("顺序表已满!");
}
elemData[size++] = elem;
}
public void addAll(List<? extends T> list) {
for (int i = 0; i < list.length(); i++) {
insert(this.length(), list.get(i));
}
}
/**
* 获得顺序表指定位置的元素
* @param index
* @return
*/
public T get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(index + "超出线性表范围");
}
return (T) elemData[index];
}
/**
* 向指定位置插入元素,如果表满了,则进行扩容操作
* @param index
* @param elem
*/
public void insert(int index, T elem) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(index + "超出线性表范围");
}
Object[] objects = elemData;
/**
* 表满了,扩容
*/
if (size == elemData.length) {
elemData = new Object[objects.length * 2];
for (int j = 0; j < index; j++) {
this.elemData[j] = objects[j];
}
}
for (int i = size - 1; i >= index; i--) {
elemData[i + 1] = objects[i];
}
elemData[index] = elem;
size++;
}
/**
* 替换指定位置的元素
* @param index
* @param elem
*/
public void replace(int index, T elem) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(index + "超出线性表范围");
}
elemData[index] = elem;
}
/**
* 获得指定元素第一次出现的位置
* @param elem
* @return
*/
public int indexOf(T elem) {
for (int i = 0; i < size; i++) {
if (elemData[i].equals(elem)) {
return i;
}
}
return -1;
}
/**
* 删除表中指定位置的元素
* @param index
* @return
*/
public T remove(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(index + "超出线性表范围");
}
T old = (T) this.elemData[index];
for (int j = index; j < size - 1; j++) {
this.elemData[j] = this.elemData[j + 1];
}
//将表的末尾元素置空
this.elemData[this.size - 1] = null;
size--;
return old;
}
/**
* 判断表中是否包含此元素
* @param elem
* @return
*/
public boolean contains(T elem) {
return indexOf(elem) != -1;
}
public Object[] toArray() {
Object[] arr = new Object[this.length()];
for (int i = 0; i < size; i++) {
arr[i] = elemData[i];
}
return arr;
}
/**
* 将线性表反转
*
* @param list
* @return
*/
public Object[] reverseList(Object[] list) {
//计算出要移动元素的长度
int len = list.length % 2 == 0 ? list.length / 2 : list.length / 2 + 1;
for (int i = 0; i < len; i++) {
Object temp = list[list.length - i - 1];
list[list.length - i - 1] = list[i];
list[i] = temp;
}
return list;
}
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append("[");
sb.append(elemData[0]);
for (int i = 1; i < this.size; i++)
sb.append(", " + this.elemData[i]);
sb.append("]");
return sb.toString();
}
public void Print(){
for(int i = 0; i < this.size; i++){
if(elemData[i] != null)
System.out.println(elemData[i]);
}
}
}
排序顺序表:
public class SortedSeqList<T extends Comparable<? super T>> extends SeqList<T> {
public SortedSeqList() {
super();
}
public SortedSeqList(int initialCapacity) {
super(initialCapacity);
}
public SortedSeqList(Object[] arr){
super(arr);
}
/**
* 插入元素,按照元素升序排列
*
* @param elem
*/
public void insert(T elem) {
if (this.isEmpty()) {
this.insert(0, elem);
} else {
int index = this.length();
//找出待插入的位置
for (int i = 0; i < this.length(); i++) {
if (elem.compareTo(this.get(i)) < 0) {
index = i;
break;
}
}
//调用父类的插入方法
this.insert(index, elem);
}
}
/**
* 由于线性表有序,则使用二分查找提高查找效率
*
* @param elem
* @return
*/
public int binarySearch(T elem) {
int low = 0;
int mid = 0;
int high = this.length() - 1;
while (low <= high) {
mid = low + ((high - low) / 2);
if (this.get(mid).compareTo(elem) < 0) {
low = mid + 1;
} else if (this.get(mid).compareTo(elem) > 0) {
high = mid - 1;
} else {
return mid;
}
}
return mid;
}
public SortedSeqList<T> mergeTwoLists(SortedSeqList<T> another) {
Object[] arr = new Object[this.length() + another.length()];
/**
* System.arraycopy()
* 参数: Object src, int srcPos, Object dest, int destPos,int length
* src 源数组
* srcpos 源数组起始位置
* dest 目标数组
* destPos 目标数组起始位置
* length 要进行复制的长度
*/
System.arraycopy(this.toArray(), 0, arr, 0, this.length());
//也可以使用下面的
// for(int i = 0; i < this.length(); i++){
// arr[i] = this.get(i);
// }
SortedSeqList<T> new_s = new SortedSeqList<>(arr);
for (int i = 0; i < another.length(); i++) {
new_s.insert(another.get(i));
}
return new_s;
}
public T remove(T elem) {
int index = binarySearch(elem);
return this.remove(index);
}
public static void main(String[] args) {
SortedSeqList<Student> s = new SortedSeqList<>();
s.insert(new Student("20180861201", "力尚龙", "男"));
s.insert(new Student("20180861229", "任德祺", "男"));
s.insert(new Student("20180861202", "孔德水", "男"));
System.out.println("顺序表一:");
s.Print();
System.out.println();
SortedSeqList<Student> q = new SortedSeqList<>();
q.insert(new Student("20180861203", "林宇轩", "男"));
q.insert(new Student("20180861225", "游章勋", "男"));
q.insert(new Student("20180861224", "蔡凯洲", "男"));
System.out.println("顺序表二:");
q.Print();
System.out.println();
SortedSeqList<Student> mergeTwoLists = s.mergeTwoLists(q);
System.out.println("两个排序顺序表合并后:");
mergeTwoLists.Print();
}
}
Q.E.D.
