数据结构与算法--顺序表(Java)

誓则盟约 2024-08-24 15:05:06 阅读 92

📝个人主页🌹:誓则盟约

⏩收录专栏⏪:Java SE

🤡往期回顾🤡:Java SE--基本数据类型(详细讲解)

🌹🌹期待您的关注 🌹🌹

什么是顺序表?

顺序表是一种线性表的数据结构。顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素

顺序表的主要特点:

逻辑上相邻的元素在物理位置上也相邻。可以随机访问表中的任意元素,通过元素的位置序号可以在 <code>O(1) 的时间复杂度内直接获取对应元素。插入和删除操作的效率相对较低。例如,在顺序表的中间位置插入一个元素,需要移动大量后续元素,时间复杂度为 O(n) ;删除操作同理。

顺序表的优点:

随机访问速度快,能够快速获取指定位置的元素。存储密度高,不需要额外的指针来链接元素。

顺序表的缺点:

长度固定,不易扩展。插入和删除操作可能涉及大量元素的移动,效率较低。

        举个例子,如果有一个顺序表存储了学生的成绩 [85, 90, 78, 95, 88] ,如果要获取第三个学生的成绩,直接通过索引 2 就能快速得到 78 。但如果要在第二个位置插入一个新成绩 80 ,就需要将后面的元素 90, 78, 95, 88 依次向后移动一位,然后再插入 80 。

        顺序表在很多程序设计中都有应用,比如简单的数组实现、一些对随机访问要求较高而插入删除操作较少的场景等,今天我们用java来简单实现一下顺序表。


构造方法:    

    首先,构造一个顺序表,需要int capacity 表示顺序表的内存大小(这里先传入一个值作为参数,后面内存不够用我们会有专门申请内存的方法)、int size表示表里面元素的个数、Object [] array 来命名这个顺序表,这时候一个最基本的顺序表就被构造出来了,以下是代码实现:

public class Linear_List<E> {

private int capacity = 10;

private int size=0;

private Object [] array = new Object [capacity];

添加方法:

        要对顺序表array进行添加操作,需要传入两个参数 泛型 element 以及 int index,代表在index下标插入 泛型 element。

        注意:这里需要判断 index 和 size 的大小,如果index<0 || index>size,则理应抛出错误。

        在index位置插入元素,只需要将原来index以及index后面的元素往后移一位,空出来的位置给element即可。下面是添加方法的代码实现:

public void add(E element , int index) {

if (index<0 || index>size)

throw new IndexOutOfBoundsException("Index out of bounds");

for (int i = size; i >index; i--) {

array[i] = array[i-1];

}

array[index] = element;

size++;

}

        但是当顺序表中存储的元素数量达到当前分配的存储空间上限时,就需要进行扩容。具体来说,常见的情况有:

持续向顺序表中添加元素,导致已分配的存储空间被填满。

        例如,最初分配的顺序表空间能存储 10 个整数,当已经存储了 10 个整数后,如果还需要继续添加新的整数,就需要扩容。

事先无法准确预估元素数量,且实际存储的元素数量超出了初始的预计。

        假设一个用于存储用户订单信息的顺序表,由于促销活动导致订单数量大幅增加,超出了初始分配的空间。

业务需求发生变化,导致需要存储更多的元素。

        比如原本的系统只需要存储一个月内的交易记录,但业务调整后需要存储半年甚至更长时间的交易记录,原有的顺序表空间可能就不够了。

        在进行扩容时,通常会重新分配一块更大的连续存储空间,并将原有的元素复制到新的空间中。扩容的策略可以是按照一定的比例增加空间,例如每次扩容为原来的两倍;也可以是增加固定的大小,如每次增加一定数量的存储单元,原来的那块空间也并不会造成空间浪费,通常会被JVM的垃圾回收机制自动回收。

        通常把扩容操作放在添加方法内部,因为在添加元素时才会有可能需要用到扩容操作,以下是添加了扩容操作的添加方法的代码实现:

public void add(E element, int index) {

// 如果索引不在有效范围内,抛出异常

if (index < 0 || index > size)

throw new IndexOutOfBoundsException("Index out of bounds");

// 如果当前元素数量达到容量,进行扩容操作

if (size >= capacity) {

int newCapacity = capacity * 2; // 新容量为原容量的两倍

Object[] newArray = new Object[newCapacity]; // 创建新的数组

System.arraycopy(array, 0, newArray, 0, size); // 将原数组内容复制到新数组

array = newArray; // 更新数组引用

capacity = newCapacity; // 更新容量

}

// 将指定索引及之后的元素向后移动一位

for (int i = size; i > index; i--) {

array[i] = array[i - 1];

}

array[index] = element; // 在指定索引位置插入新元素

size++; // 元素数量加 1

}

删除方法:

        首先,要检查删除操作中指定的索引是否合法。如果索引小于 0 或者大于等于顺序表的当前元素数量,就会抛出一个索引越界的异常,因为这样的索引不存在有效的元素可删除。

        若索引合法,就将指定索引位置之后的元素依次向前移动一位,覆盖要删除的元素位置。然后,把原本顺序表的最后一个位置设置为 null,并将顺序表的元素数量减 1,表示完成了一个元素的删除操作。以下是删除方法的代码实现:

public E remove(int index) {

if (index<0 || index>size-1) throw new IndexOutOfBoundsException("Index out of bounds");

E key = (E) array[index];

for (int i = index; i <size; i++) {

array[i] = array[i+1];

}size--;

return key;

}

判空和get方法:

        判空方法通常用于判断顺序表是否为空。这可以通过检查顺序表中元素的数量来实现。如果元素数量为 0 ,则认为顺序表为空。

        get方法用于获取顺序表中指定索引位置的元素。在实现时,需要先检查索引的合法性,如果索引不合法(小于 0 或大于等于元素数量),则抛出异常。如果索引合法,就返回该索引位置的元素。以下是两种方法的代码实现:

public boolean is_Empty(){

return size==0;

}

public E get(int index) {

if (index<0 || index>size-1) throw new IndexOutOfBoundsException("Index out of bounds");

return (E) array[index];

}

转字符串输出(toString)方法:

        toString方法其主要目的是将顺序表的相关信息以字符串的形式进行展示。通常会先获取顺序表中实际存储元素的数组部分,并将其转换为字符串表示。同时,还会获取顺序表中当前元素的数量。

        当调用顺序表对象的 toString 方法时,就能得到一个清晰反映顺序表内部状态的字符串描述,方便进行输出、调试或其他需要以字符串形式获取顺序表信息的操作。以下是toString方法的代码实现:

public String toString() {

StringBuilder builder = new StringBuilder();

for (int i = 0; i < size; i++){

builder.append(array[i]).append(" "); }

return builder.toString();

}

完整代码实现:

public class Linear_List<E> {

private int capacity = 10;

private int size=0;

private Object [] array = new Object [capacity];

public void add(E element , int index) {

if (index<0 || index>size)

throw new IndexOutOfBoundsException("Index out of bounds");

if (size>=capacity){ // 扩容

int newCapacity = capacity*2;

Object[] newArray = new Object[newCapacity];

System.arraycopy(array,0,newArray,0,size);

array = newArray;

capacity = newCapacity;

}

for (int i = size; i >index; i--) {

array[i] = array[i-1];

}

array[index] = element;

size++;

}

public E remove(int index) {

if (index<0 || index>size-1) throw new IndexOutOfBoundsException("Index out of bounds");

E key = (E) array[index];

for (int i = index; i <size; i++) {

array[i] = array[i+1];

}size--;

return key;

}

public boolean is_Empty(){

return size==0;

}

public E get(int index) {

if (index<0 || index>size-1) throw new IndexOutOfBoundsException("Index out of bounds");

return (E) array[index];

}

public String toString() {

StringBuilder builder = new StringBuilder();

for (int i = 0; i < size; i++) { builder.append(array[i]).append(" "); }

return builder.toString();

}

}


“静静地目送,享受这一刻,在混乱之中。”——《xingyu_xuan》



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。