Java線性表的順序表示及實作方法
- WBOY轉載
- 2023-05-11 16:28:061765瀏覽
一、什麼是順序表？
順序表是在電腦記憶體中以數組的形式保存的線性表，線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的資料元素儲存在相鄰的實體儲存單元中，即透過資料元素物理儲存的相鄰關係來反映資料元素之間邏輯上的相鄰關係，採用順序儲存結構的線性表通常稱為順序表。順序表是將表中的結點依序存放在電腦記憶體中一組位址連續的儲存單元中。
二、順序表的實作
在順序表的定義中可以看到，順序表是一組位址連續的儲存單元，本質上是一種增加了一些基本操作功能的陣列
在本文中要實現的功能有：
取得順序表中的元素數量
取得順序表目前的容量
順序表是否為空
在指定索引位置新增元素
在順序表末端新增元素
#在順序表頭新增元素
取得指定索引位置的元素
取得順序表第一個元素
#取得順序表最後一個元素
#修改指定索引位置的元素
#判斷順序表中是否包含指定元素
取得順序表中指定元素的索引
刪除指定索引位置的元素
#刪除並傳回順序表第一個元素
#刪除並傳回順序表最後一個元素
刪除順序表中的指定元素
對順序表進行動態的擴充和縮容
1. 準備工作
| #實作工具 | 版本 |
|---|---|
| ##IntelliJ IDEA | |
| #JDK |
在IntelliJ IDEA 中新建普通的Java專案即可
# 在新建好Java工程後，我們創建自己的順序表類，在這裡我對當前類別命名為Array，在這裡實作泛型，同時Array類別中需要有兩個成員屬性：
存放資料的陣列：
data，類型為泛型陣列當前順序表中元素的數量：
size，類型為int
#兩個成員屬性的存取權限都應該為private，使用者不能夠直接進行修改，只能透過對應的getter方法進行取得。在成員屬性中我們將存放資料的陣列和順序表中的元素數量只是進行了聲明，但是並未進行初始化，因此==初始化的過程就需要在建構方法中進行==
有參考構造：在進行有參構造時，我們只需要指定傳入的參數為一個
int類型的資料capacity，代表順序表的初始容量，因此對data進行初始化泛型陣列即可。同時目前順序表中是沒有元素的，代表順序表中的元素個數size的初始值為0。無參考建構：當使用者沒有指定了順序表的初始容量時我們可以自訂初始容量為10，只需要透過
this( 10)進行有參構造的呼叫即可。
注意： 在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方法的實作我們放到後面進行具體的講解，在這裡我們知道如果當前順序表容量已滿，將順序表容量擴大為當前順序表容量的二倍
第二個問題的出現情況只有兩種，索引小於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));
}
}以上是Java線性表的順序表示及實作方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！