```// 顺序表的元素类型 int
public class MyArrayList {
// 属性是什么
private int[] array; // 代表的是存在数据的数组
// array.length 代表的是数组的容量
private int size; // 记录顺序表的已有数据个数
我们提供的服务有:做网站、网站制作、微信公众号开发、网站优化、网站认证、拜城ssl等。为上千多家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的拜城网站制作公司
// 构造方法
public MyArrayList() {
// 1. 申请空间
array = new int[2];
// 2. 初始化数据个数
size = 0;
}
// 增(重点)
// 平均 O(1)
public void pushBack(int element) {
ensureCapacity();
array[size++] = element;
}
public void pushFront(int element) {
ensureCapacity();
for (int i = size; i >= 1; i--) {
array[i] = array[i - 1];
}
array[0] = element;
size++;
}
public void insert(int index, int element) {
if (index < 0 || index > size) {
System.err.println("下标错误");
return;
}
ensureCapacity();
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
array[index] = element;
size++;
}
// 删(重点)
public void popBack() {
if (size <= 0) {
System.err.println("顺序表为空");
return;
}
array[--size] = 0;
}
public void popFront() {
if (size <= 0) {
System.err.println("顺序表为空");
return;
}
for (int i = 0; i < size - 1; i++) {
array[i] = array[i + 1];
}
array[--size] = 0;
}
public void earse(int index) {
if (size <= 0) {
System.err.println("顺序表为空");
return;
}
if (index < 0 || index >= size) {
System.err.println("下标错误");
return;
}
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
array[--size] = 0;
}
// 查
// 改
// 打印
public void print() {
System.out.println("打印顺序表: 当前容量: " + array.length);
for (int i = 0; i < size; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
// 保证容量够用,否则进行扩容
private void ensureCapacity() {
if (size < array.length) {
return;
}
int newCapacity = array.length * 2;
int[] newArray = new int[newCapacity];
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
array = newArray;
}
// 返回 element 在顺序表中的下标,如果出现多次,返回第一次出现的下标
public int indexOf(int element) {
for (int i = 0; i < size; i++) {
if (array[i] == element) {
return i;
}
}
return -1;
}
public int get(int index) {
if (index < 0 || index >= size) {
System.err.println("下标错误");
return -1;
}
return array[index];
}
public void set(int index, int element) {
if (index < 0 || index >= size) {
System.err.println("下标错误");
return;
}
array[index] = element;
}
// 删除掉某一个元素,如果出现多次,删除第一次出现的
public void remove(int element) {
int index = indexOf(element);
if (index != -1) {
earse(index);
}
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void removeAll(int element) {//删除这个元素所有次出现
/* 时间:O(n^2) 时间:O(1)
int index;
while ((index = indexOf(element)) != -1) {
earse(index);
}
*/
/* 时间: O(n) 空间: O(n)
int[] newArray = new int[array.length];
int j = 0;
for (int i = 0; i < size; i++) {
if (array[i] != element) {
newArray[j++] = array[i];
}
}
array = newArray;
size = j;
*/
// 时间:O(n) 空间:O(1)
int j = 0;
for (int i = 0; i < size; i++) {
if (array[i] != element) {//遍历整个数组,把不是该元素的从数组头开始放,
array[j++] = array[i];
}
}
size = j;//j是不同于element的个数,传给size,这是整个数组里前size都是不同的
}
public static void main(String[] args) {
MyArrayList list = new MyArrayList();
list.print();
list.pushBack(1);
list.pushBack(2);
list.pushBack(3);
list.print(); // 1 2 3
list.pushFront(10);
list.pushFront(20);
list.pushFront(30);
list.print(); // 30 20 10 1 2 3
list.insert(3, 100);
list.print(); // 30 20 10 100 1 2 3
list.insert(20, 200); // 报错
list.earse(2);
list.earse(2);
list.print(); // 30 20 1 2 3
list.popFront();
list.popFront();
list.popFront();
list.print(); // 2 3
list.popBack();
list.popBack();
list.print(); // 空的
list.popBack(); // 报错
}
}
网站题目:关于顺序表的基本操作。代码+注释
文章源于:https://www.cdcxhl.com/article42/gijjhc.html
成都网站建设公司_创新互联,为您提供外贸网站建设、全网营销推广、网站维护、静态网站、网站内链、搜索引擎优化
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联