设计一个有序顺序表(元素已排序,递增或递减),实现插入、删除等操作,元素插入位置由其值决定。给Java代码并加注释
时间: 2024-10-17 16:07:26 浏览: 9
设计一个有序顺序表(SortedArrayList),我们可以使用Java的ArrayList作为基础数据结构,并添加自定义的方法来实现在特定位置插入和删除元素的功能。这里假设我们希望数组按升序排列:
```java
import java.util.ArrayList;
import java.util.List;
public class SortedArrayList<T extends Comparable<T>> {
private List<T> list; // 使用ArrayList作为底层存储
// 构造函数
public SortedArrayList() {
this.list = new ArrayList<>();
}
// 插入元素到适当的位置
public void insert(T value) {
int index = binarySearch(value); // 获取插入位置
if (index != -1) {
list.add(index, value);
} else {
list.add(value); // 如果未找到合适位置,则直接添加到末尾
}
}
// 查找插入位置的二分查找算法
private int binarySearch(T target) {
int low = 0, high = list.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (list.get(mid).compareTo(target) < 0) { // 如果中间元素小于目标
low = mid + 1; // 向右半部分查找
} else {
high = mid - 1; // 否则向左半部分查找
}
}
return low; // 返回插入位置(如果存在)
}
// 删除指定位置的元素
public T remove(int index) {
if (index >= 0 && index < list.size()) {
T removedValue = list.remove(index);
// 如果列表不再是有序,可以对整个列表进行排序
sort();
return removedValue;
} else {
throw new IndexOutOfBoundsException("Index out of bounds");
}
}
// 对列表进行排序(这里仅用于演示,实际场景可能会使用更高效的排序算法)
private void sort() {
list.sort(Comparator.naturalOrder());
}
// 获取列表大小
public int size() {
return list.size();
}
// 打印列表内容
@Override
public String toString() {
return list.toString();
}
//
阅读全文