1.8 |
|
IntelliJ IDEAJava项目即可
在新建好Java工程后，我们创建自己的顺序表类，在这里我对当前类命名为Array，在这里实现泛型，同时Array类中需要有两个成员属性：
存放数据的数组：data，类型为泛型数组
当前顺序表中元素的数量：size，类型为int
两个成员属性的访问权限都应该为private，用户不能够直接进行修改，只能通过对应的getter方法进行获取。 在成员属性中我们将存放数据的数组和顺序表中的元素数量只是进行了声明，但是并未进行初始化，因此==初始化的过程就需要在构造方法中进行==
注意： 在Java中不能直接初始化泛型数组，需要先声明Object类型的数组后通过强制类型转换的方式将Object类型的数组转换为泛型数组
package net.csdn.array;
/**
* @author zhangrongkang
* @date 2022/6/26
*/
public class Array<E> {
/**
* 存放数据的数组
*/
private E[] data;
/**
* 数组中元素的数量
*/
private int size;
/**
* 构造函数，传入数组的容量capacity构造数组
*
* @param capacity 初始数组大小
*/
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
/**
* 无参构造函数，默认数组大小为0
*/
public Array() {
this(10);
}
}使用泛型的原因：使用泛型后可以将当前顺序表中存储对象，如果不使用泛型的话只能使用自己指定类型的数据，扩展性不强。因此使用泛型后可以将当前顺序表的使用扩展到所有类对象，只需要在创建时指定相应的对象即可。
2. 获取顺序表的元素个数
/**
* 获取数组中的元素个数
*
* @return 数组当前的元素个数
*/
public int getSize() {
return size;
}对于获取当前顺序表中的元素个数来说，因为我们定义的初始成员变量size代表的含义就是当前顺序表的元素个数，但是size变量的本质为当前顺序表的指针，指向顺序表最后一个元素的下一个位置 （元素的索引从0开始，最后一个元素的索引值比元素个数值小 1），不能直接进行修改，因此要想获取需要通过size元素的getter方法
同样地，对于获取顺序表的元素个数只需要将size返回即可
3. 获取顺序表当前的容量
/**
* 获取数组当前容量
*
* @return 数组当前容量
*/
public int getCapacity() {
return data.length;
}在对顺序表进行声明的时候，就已经将用户传来的或者默认的初始容量capacity作为数组的大小对data泛型数组进行了初始化，因此当前data的length属性就是传来的capacity，（或者在后面进行动态扩容或缩容时，data.length是一直不会改变的，改变的只有size） 因此获取顺序表当前的容量将data.length返回即可
4. 顺序表是否为空
/**
* 判断数组是否为空
*
* @return 数组是否为空
*/
public boolean isEmpty() {
return size == 0;
}我们知道size代表的是顺序表中的元素个数，因此要判断当前顺序表是否为空仅需要将size是否等于0进行返回即可
5. 在指定索引位置添加元素
/**
* 向数组中索引为index位置添加元素e
*
* @param index 索引位置
* @param e 元素e
*/
public void add(int index, E e) {
// 判断数组空间是否已满
if (size == data.length) {
// 对数组进行扩容
resize(2 * data.length);
}
// 越界判断
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}当向顺序表中指定索引位置添加元素时要考虑以下几个问题：
当前顺序表中是否还有容量？
添加的元素索引值是否越界？
对于第一个问题来说，当顺序表已满没有容量时，再进行添加元素时需要进行动态的扩容，resize方法的作用就是对数组进行动态的扩容以及缩容，对于resize
Java 프로젝트를 만드세요." alt ="Java 선형 테이블의 순차적 표현 및 구현 방법" />
새로운 Java 프로젝트를 생성한 후 자체 순차 테이블 클래스를 생성합니다. 여기서는 현재 클래스의 이름을 Array로 지정하고 여기에 제네릭을 동시에 구현합니다. , Array 클래스에는 두 개의 멤버 속성이 있어야 합니다:
-
데이터를 저장할 배열:
data, 유형은 일반 배열입니다🎜
- 🎜🎜현재 시퀀스 목록의 요소 수🎜:
size, 유형은 int🎜
🎜두 멤버 속성의 액세스 권한은 비공개여야 합니다. 사용자는 이를 직접 수정할 수 없으며 해당 getter 메소드를 통해서만 얻을 수 있습니다. 멤버 속성에는 데이터를 저장할 배열 및 시퀀스 테이블의 요소 수가 선언되었지만 초기화되지 않았습니다🎜, 따라서 초기화 프로세스는 constructor==🎜
- 🎜🎜매개변수를 사용한 구성🎜: 매개변수를 사용하여 구성을 수행할 때 들어오는 매개변수가
int capacity 유형의 데이터라는 점만 지정하면 됩니다. code>는 시퀀스 테이블의 초기 용량을 나타내므로 <code>data에 대한 일반 배열을 초기화하면 됩니다. 동시에 현재 시퀀스 테이블에는 요소가 없습니다. 이는 시퀀스 테이블의 요소 개수에 대한 size의 초기 값이 0임을 의미합니다. 🎜
- 🎜🎜매개변수 없는 구성🎜: 사용자가 시퀀스 테이블의 초기 용량을 지정하지 않은 경우 초기 용량을 10으로 맞춤 설정할 수 있으며 이는
를 통해서만 수행하면 됩니다. (10) 매개변수를 사용하여 생성자를 호출하면 됩니다. 🎜
🎜🎜참고: 🎜 Java에서는 일반 배열을 직접 초기화할 수 없습니다. 먼저 Object 유형의 배열을 선언한 다음 🎜강제 유형 변환🎜을 사용해야 합니다. Object 유형 배열이 일반 배열로 변환됩니다🎜 /**
* 在数组末尾添加一个元素
*
* @param e 要添加的元素
*/
public void addLast(E e) {
add(size, e);
}🎜🎜generics를 사용하는 이유🎜: generics를 사용한 후 현재 시퀀스 테이블에 개체를 저장할 수 있습니다. 자신이 지정한 유형만 사용하면 확장성이 강하지 않습니다. 따라서 제네릭을 사용한 후에는 현재 시퀀스 테이블의 사용을 모든 클래스 객체로 확장할 수 있습니다. 생성할 때 해당 객체를 지정하기만 하면 됩니다. 🎜2. 시퀀스 테이블의 요소 수를 가져옵니다.
/**
* 在数组的头部添加元素e
*
* @param e 要添加的元素
*/
public void addFirst(E e) {
add(0, e);
}🎜현재 시퀀스 테이블의 요소 수를 가져옵니다. 왜냐하면 우리가 정의한 초기 멤버 변수 size는 의미 🎜현재 시퀀스 테이블의 요소 수🎜이지만 size 변수의 본질은 🎜현재 시퀀스 테이블의 포인터로, 시퀀스 테이블의 마지막 요소의 다음 위치를 가리킵니다. 시퀀스 테이블🎜 (요소의 인덱스는 0부터 시작하며, 마지막 요소의 인덱스 값은 1(요소 값보다 작음)이며 직접 수정할 수 없습니다. 따라서 이를 얻으려면 size 요소의 code>getter 메소드🎜🎜마찬가지로, 시퀀스 테이블의 요소 수를 얻으려면 size🎜3. 시퀀스 테이블의 현재 용량을 가져옵니다 /**
* 获取索引为index位置的元素
*
* @param index 索引位置
* @return 索引为index位置的元素
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
return data[index];
}🎜 시퀀스 테이블을 선언할 때 이미 data 일반 배열이 초기 용량 capacity를 사용하여 초기화되었습니다. code>는 사용자가 전달한 값이거나 배열의 크기로 기본값입니다. 따라서 현재 <code>data의 data가 전달된 code>length 속성입니다. 용량(또는 나중에 용량을 동적으로 확장하거나 축소할 때 data.length는 변경되지 않습니다. size만 변경되었습니다) 시퀀스 테이블의 현재 용량을 확인하려면 data.length🎜를 반환하세요. 4. 시퀀스 테이블이 비어 있는지
/**
* 获取数组中第一个元素
*
* @return 数组中第一个元素
*/
public E getFirst() {
return get(0);
}🎜 size가 따라서 현재 시퀀스 테이블이 비어 있는지 확인하려면 size가 0🎜5인지 여부만 반환하면 됩니다.
/**
* 获取数组中最后一个元素
*
* @return 数组中最后一个元素
*/
public E getLast() {
return get(size - 1);
}🎜🎜시퀀스 테이블의 지정된 인덱스 위치에 요소를 추가할 때 다음 문제를 고려해야 합니다. 🎜🎜🎜🎜아직 용량이 남아 있나요? 현재 시퀀스 목록에 있습니까? 🎜🎜- 🎜🎜추가된 요소 인덱스 값이 범위를 벗어났나요? 🎜🎜
🎜첫 번째 질문은 시퀀스 테이블이 꽉 차서 용량이 없을 때 요소 추가 시 동적 확장이 필요한 경우 resize 메소드의 역할입니다. 🎜 동적으로 배열을 확장하고 축소하려면 🎜 resize 메서드의 구현에 대해 나중에 자세히 설명하겠습니다. 여기서는 현재 시퀀스 테이블 용량이 가득 차면 시퀀스 테이블 용량이 확장된다는 것을 알고 있습니다. 🎜현재 시퀀스 테이블의 용량을 두 배로 늘립니다🎜🎜두 번째 문제는 두 가지 상황에서만 발생할 수 있습니다. 🎜인덱스가 0보다 작거나 인덱스가 현재 시퀀스 테이블의 요소 수를 초과하는 경우🎜 런타임 예외가 발생합니다🎜 🎜 🎜색인에 문제가 없으면 요소를 추가하는 과정은 다음과 같습니다. 🎜🎜
要先将要添加的索引位置后的所有元素依次向后移动一位，在移动完成后将当前索引位置的元素使用要进行添加的元素对当前位置的元素进行覆盖即可，同时添加完元素后将size++，维护指针变量
6. 在顺序表末尾添加元素
/**
* 在数组末尾添加一个元素
*
* @param e 要添加的元素
*/
public void addLast(E e) {
add(size, e);
}在末尾添加元素可以对之前写好的向指定索引位置添加元素的代码进行复用，同时在add方法中进行了校验，因此对于扩容以及索引都问题都无需我们进行考虑，将 索引位置的参数赋值为当前最后一个元素的下一个位置size 后直接调用即可。
7. 在顺序表头部添加元素
/**
* 在数组的头部添加元素e
*
* @param e 要添加的元素
*/
public void addFirst(E e) {
add(0, e);
}在顺序表的头部添加元素也是同样的道理，对指定索引位置插入元素进行复用即可，在此不进行赘述。
8. 获取指定索引位置的元素
/**
* 获取索引为index位置的元素
*
* @param index 索引位置
* @return 索引为index位置的元素
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
return data[index];
}获取指定索引位置的元素与之前在指定索引位置插入元素的思路大体一致，但是要更简单一些，无需考虑顺序表扩容以及缩容的问题，仅需要考虑传入的索引值是否合法，如果传入的索引值合法则直接将对应位置的元素进行返回即可。
9. 获取顺序表第一个元素
/**
* 获取数组中第一个元素
*
* @return 数组中第一个元素
*/
public E getFirst() {
return get(0);
}在实现了获取指定索引位置的元素后，获取顺序表的第一个元素同样是对get方法的复用，将0做为索引值进行参数传递即可。
10. 获取顺序表最后一个元素
/**
* 获取数组中最后一个元素
*
* @return 数组中最后一个元素
*/
public E getLast() {
return get(size - 1);
}获取顺序表最后一个元素也是对get方法的复用，在此不进行赘述
11. 修改指定索引位置的元素
/**
* 设置索引为index位置的元素值为e
*
* @param index 索引位置
* @param e 要进行替换的元素值
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
data[index] = e;
}在之前获取指定索引位置的元素时，先判断索引是否合法，如果合法将对应位置的元素进行返回。同理，先判断索引位置是否合法，如果合法就将当前位置的元素使用我们接收到的元素e进行替换。
12. 判断顺序表中是否包含指定元素
/**
* 判断数组中是否存在元素e
*
* @param e 元素e
* @return 是否存在元素e
*/
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}对于判断顺序表中是否存在指定元素来说，对顺序表进行线性查找，如果找到了相应的数据，就返回true，如果在对顺序表遍历结束后仍然没有找到指定元素，说明当前顺序表中不存在指定元素，返回false
注意：在这里因为是对象的比较，使用equals方法进行比较，如果是基本数据类型（如int，double等）的比较就要使用==来进行比较
13. 获取顺序表中指定元素的索引
/**
* 查找数组中元素e的索引，如果不存在返回 -1
*
* @param e 元素e
* @return 元素e在数组中的索引
*/
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}获取指定元素的索引同样使用线性查找法，使用equals进行比较，如果找到相同的元素则返回对应的索引值，如果遍历完顺序表后仍然没有找到指定元素则返回-1，说明当前元素不存在。
14. 删除指定索引位置的元素
/**
* 删除索引位置为 index 的元素并返回被删除的元素
*
* @param index 删除元素的索引
* @return 被删除的元素
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
// 先将返回值进行存储
E res = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null;
// 如果当前数组中的元素不足数组容量的一半
if (size < data.length / 2) {
// 重新分配空间
resize(data.length / 2);
}
return res;
}在之前进行元素的添加时要考虑顺序表是否还有容量，在删除元素时不需要考虑是否还有容量，但是也要考虑相应的有关于数组缩容问题。因此要考虑以下问题：
对于第一个问题的解决方法为在删除元素后，对当前顺序表的元素个数与数组的容量的一半进行比较，如果发现当前元素个数小于数组容量的一半时，我们可以继续调用resize方法重新分配数组的容量（resize方法在之后会详细解释），当前的实现结果就是将数组的容量缩容至原数组都一半，对于内存的节省来说更有好处。
第二个问题解决方式与之前处理一样，查看索引值是否小于0以及是否大于等于当前顺序表都元素个数
删除元素的本质也是将当前索引值的后一个元素开始，依次向前移动，覆盖掉前一个元素，最后再将size--，维护指针，删除结束后将临时存储的被删除的元素返回即可。
删除元素过程如下图所示：
注意：顺序表的删除本质上是用后一个元素将前一个元素依次覆盖，移动了size指针后此时指针指向的元素仍然为原本顺序表中的最后一个元素，因为在用户的实际操作中，size指向的元素无法被访问到，所以并没有什么影响。但是我们在这里使用了泛型，在Java的GC（垃圾回收机制）中因为此时顺序表的最后一个元素仍然被size指向引用，无法被回收，因此在这里手动执行data[size] = null;将当前的引用回收。
15. 删除并返回顺序表第一个元素
/**
* 删除并返回数组的第一个元素
*
* @return 数组的第一个元素
*/
public E removeFirst() {
return remove(0);
}与之前的思路一致，在有了删除指定索引位置的元素方法后，删除并返回顺序表第一个元素也是对刚才实现的remove方法进行复用，在此不做赘述。
16. 删除并返回顺序表最后一个元素
/**
* 删除并返回数组中的最后一个元素
*
* @return 数组中的最后一个元素
*/
public E removeLast() {
return remove(size - 1);
}删除顺序表中最后一个元素同样是对remove方法的复用，在此也不多做赘述。
17. 删除顺序表中的指定元素
/**
* 从数组中删除元素e
*
* @param e 数组中被删除的元素
* @return 是否删除成功
*/
public boolean removeElement(E e) {
int index = find(e);
if (index == -1) {
return false;
}
remove(index);
return true;
}删除顺序表中指定的元素本质上是对之前实现的获取顺序表中指定元素的索引方法和删除指定索引位置元素方法的复用，首先通过find方法获取到要删除元素的索引，接着对索引进行判断，查看当前元素是否存在，如果当前元素存在则将获取到的索引值作为remove方法的参数传递，将当前索引位置的元素删除即可。
18. 对顺序表进行动态的扩容和缩容
/**
* 对数组进行扩容
*
* @param newCapacity 扩容后数组的容量
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}在之前向顺序表中添加元素以及删除顺序表中的元素都涉及到了扩容以及缩容的过程，其实对于扩容以及缩容来说区别只体现在了传递来的参数与原数组容量大小的差别，扩容与缩容的思路都是声明一个新的数组，初始容量的大小为传递来的参数，接着遍历原来的数组，将每一个元素依次填充到新的数组中，之后再将data对象的引用指向新的数组newData即可。
三、运行结果
在进行结果测试前，为了方便于观察，在这里我重写了Array类的toString方法
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
builder.append("[");
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
四、总结
以上便是Java语言对线性表的顺序表示和实现，和以前使用C语言来写顺序表最大的感受就是曾经觉得很难写、很费脑的代码再次实现时感觉变得很容易了，同时对于很多的方法也有了复用的思想，对线性表的理解更加深刻。高兴于自己成长的同时也更加深刻意识到以后的路会更加的艰难，希望自己可以在未来的道路上戒骄戒躁、稳扎稳打，哪怕再困难，也不会放弃！
源码
以下是源代码
1. Array类源代码
package net.csdn.array;
/**
* @author zhangrongkang
* @date 2022/6/26
*/
public class Array {
private E[] data;
/**
* 数组中元素的数量
*/
private int size;
/**
* 构造函数，传入数组的容量capacity构造数组
*
* @param capacity 初始数组大小
*/
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
/**
* 无参构造函数，默认数组大小为0
*/
public Array() {
this(10);
}
/**
* 获取数组中的元素个数
*
* @return 数组当前的元素个数
*/
public int getSize() {
return size;
}
/**
* 获取数组当前容量
*
* @return 数组当前容量
*/
public int getCapacity() {
return data.length;
}
/**
* 判断数组是否为空
*
* @return 数组是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 在数组末尾添加一个元素
*
* @param e 要添加的元素
*/
public void addLast(E e) {
add(size, e);
}
/**
* 在数组的头部添加元素e
*
* @param e 要添加的元素
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 向数组中索引为index位置添加元素e
*
* @param index 索引位置
* @param e 元素e
*/
public void add(int index, E e) {
// 判断数组空间是否已满
if (size == data.length) {
// 对数组进行扩容
resize(2 * data.length);
}
// 越界判断
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
/**
* 获取索引为index位置的元素
*
* @param index 索引位置
* @return 索引为index位置的元素
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
return data[index];
}
/**
* 获取数组中第一个元素
*
* @return 数组中第一个元素
*/
public E getFirst() {
return get(0);
}
/**
* 获取数组中最后一个元素
*
* @return 数组中最后一个元素
*/
public E getLast() {
return get(size - 1);
}
/**
* 设置索引为index位置的元素值为e
*
* @param index 索引位置
* @param e 要进行替换的元素值
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
data[index] = e;
}
/**
* 判断数组中是否存在元素e
*
* @param e 元素e
* @return 是否存在元素e
*/
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
/**
* 查找数组中元素e的索引，如果不存在返回 -1
*
* @param e 元素e
* @return 元素e在数组中的索引
*/
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
/**
* 删除索引位置为 index 的元素并返回被删除的元素
*
* @param index 删除元素的索引
* @return 被删除的元素
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
// 先将返回值进行存储
E res = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null;
// 如果当前数组中的元素不足数组容量的一半
if (size < data.length / 2) {
// 重新分配空间
resize(data.length / 2);
}
return res;
}
/**
* 删除并返回数组的第一个元素
*
* @return 数组的第一个元素
*/
public E removeFirst() {
return remove(0);
}
/**
* 删除并返回数组中的最后一个元素
*
* @return 数组中的最后一个元素
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 从数组中删除元素e
*
* @param e 数组中被删除的元素
* @return 是否删除成功
*/
public boolean removeElement(E e) {
int index = find(e);
if (index == -1) {
return false;
}
remove(index);
return true;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
builder.append("[");
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
/**
* 对数组进行扩容
*
* @param newCapacity 扩容后数组的容量
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
}
2. 测试类源代码
package net.csdn.array;
/**
* @author zhangrongkang
* @date 2022/6/26
*/
public class ArrayMain {
public static void main(String[] args) {
System.out.println("声明新的顺序表，初始容量为10：");
Array<Integer> array = new Array<>(10);
for (int i = 0; i < 10; i++) {
array.addLast(i);
}
System.out.println(array + "\n");
System.out.println("向索引为 1 的位置添加元素 100：");
array.add(1, 100);
System.out.println(array + "\n");
System.out.println("在顺序表的头部添加 -1：");
array.addFirst(-1);
System.out.println(array + "\n");
System.out.println("在顺序表的尾部添加 101：");
array.addLast(101);
System.out.println(array + "\n");
System.out.println("移除索引位置为 2 的元素：");
array.remove(2);
System.out.println(array + "\n");
System.out.println("移除顺序表中的元素 4：");
array.removeElement(4);
System.out.println(array + "\n");
System.out.println("移除顺序表中的第一个元素：");
array.removeFirst();
System.out.println(array + "\n");
System.out.println("移除顺序表中的最后一个元素：");
array.removeLast();
System.out.println(array + "\n");
System.out.println("元素7的索引位置为：" + array.find(7));
System.out.println("数组中是否包含元素4：" + array.contains(4));
}
}
