| 1.8 |
| # 🎜🎜#Créez simplement un nouveau projet Java ordinaire dans 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
Après avoir créé un nouveau projet Java, nous créons notre propre classe de tableaux séquentiels. Ici, je nomme la classe actuelle Array et j'implémente ici les génériques, en même temps , la classe Array doit avoir deux attributs membres :
-
Un tableau pour stocker des données :
data, le type est un tableau générique🎜
- 🎜🎜Le nombre d'éléments dans la liste de séquence actuelle🎜 :
size, le type est int🎜
🎜Les autorisations d'accès aux deux attributs membres doivent être privées. Les utilisateurs ne peuvent pas les modifier directement et ne peuvent les obtenir que via les méthodes getter correspondantes. Dans les attributs des membres, le nombre d'éléments dans le tableau et la table de séquence où nous stockerons les données est simplement déclaré, mais pas initialisé🎜, le processus d'initialisation doit donc être effectué dans la liste constructor==🎜
- 🎜🎜Construction avec paramètres🎜 : Lors de la construction avec paramètres, il suffit de spécifier que le paramètre entrant est une donnée de type
int capacity code>, représente la capacité initiale de la 🎜table de séquence🎜, il suffit donc d'initialiser le tableau générique pour <code>data. En même temps, il n'y a aucun élément dans la table de séquence actuelle, ce qui signifie que la valeur initiale de size, qui représente le nombre d'éléments dans la table de séquence, est 0. 🎜
- 🎜🎜Construction sans paramètre🎜 : Lorsque l'utilisateur ne spécifie pas la capacité initiale de la table de séquence, nous pouvons personnaliser la capacité initiale à 10, ce qui ne doit être fait que via
this (10) Appelez simplement le constructeur avec des paramètres. 🎜
🎜🎜Remarque : 🎜 Vous ne pouvez pas initialiser directement un tableau générique en Java. Vous devez d'abord déclarer un tableau de type Object, puis utiliser la 🎜conversion de type forcée🎜 pour. Le tableau de type Object est converti en un tableau générique🎜 /**
* 在数组末尾添加一个元素
*
* @param e 要添加的元素
*/
public void addLast(E e) {
add(size, e);
}🎜🎜Raison de l'utilisation des génériques🎜 : Après avoir utilisé des génériques, vous pouvez stocker des objets dans la table de séquence actuelle. Si vous n'utilisez pas de génériques, vous pouvez. utilisez uniquement votre propre type de données spécifié, l'évolutivité n'est pas forte. Par conséquent, après avoir utilisé des génériques, vous pouvez étendre l'utilisation de la table de séquence actuelle à tous les objets de classe. Il vous suffit de spécifier l'objet correspondant lors de sa création. 🎜2. Obtenez le nombre d'éléments dans la table de séquence
/**
* 在数组的头部添加元素e
*
* @param e 要添加的元素
*/
public void addFirst(E e) {
add(0, e);
}🎜Pour obtenir le nombre d'éléments dans la table de séquence actuelle, car la variable membre initiale size que nous avons définie représente le ce qui signifie que c'est 🎜le nombre d'éléments dans la table de séquence actuelle🎜, mais l'essence de la variable size est 🎜le pointeur de la table de séquence actuelle, pointant vers la position suivante du dernier élément dans la table de séquence actuelle. table de séquence🎜 (l'index de l'élément commence à 0, La valeur d'index du dernier élément est inférieure de 1 à la valeur de l'élément et ne peut pas être modifiée directement. Par conséquent, si vous souhaitez l'obtenir, vous devez utiliser le méthode getter de l'élément size🎜🎜De même, pour obtenir le nombre d'éléments dans la table de séquence, retournez simplement size🎜3. la capacité actuelle de la table de séquence
/**
* 获取索引为index位置的元素
*
* @param index 索引位置
* @return 索引为index位置的元素
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException();
}
return data[index];
}🎜Lors de la déclaration de la table de séquence, elle l'est déjà. Le tableau générique data est initialisé en utilisant la capacité initiale capacity passée par le user ou la taille par défaut du tableau. Par conséquent, les data des data actuels. L'attribut code>length est le capacity, (ou lors d'une expansion ou d'une réduction dynamique de la capacité ultérieurement, <code>data.length ne changera jamais. Seul size a été modifié). Donc, pour obtenir la capacité actuelle du table de séquence, retournez simplement data.length🎜4. La table de séquence est-elle vide
/**
* 获取数组中第一个元素
*
* @return 数组中第一个元素
*/
public E getFirst() {
return get(0);
}🎜 Nous savons que size représente le nombre d'éléments dans le table de séquence, donc pour déterminer si la table de séquence actuelle est vide, il vous suffit de renvoyer si size est égal à 0🎜5 Ajoutez des éléments à la position d'index spécifiée /**
* 获取数组中最后一个元素
*
* @return 数组中最后一个元素
*/
public E getLast() {
return get(size - 1);
}. 🎜🎜Lors de l'ajout d'éléments à la position d'index spécifiée dans la table de séquence, les problèmes suivants doivent être pris en compte : 🎜🎜🎜🎜Y a-t-il encore de la capacité dans la liste de séquence actuelle ? 🎜🎜- 🎜🎜La valeur de l'index de l'élément ajouté est-elle hors limites ? 🎜🎜
🎜Pour la première question, lorsque la table de séquence est pleine et n'a pas de capacité, une expansion dynamique est requise lors de l'ajout d'éléments. Le rôle de la méthode resize C'est le cas. pour 🎜 étendre et réduire dynamiquement le tableau 🎜 Nous expliquerons en détail l'implémentation de la méthode resize ici, nous savons que si la capacité actuelle de la table de séquence est pleine, la capacité de la table de séquence sera étendre. à deux fois la capacité de la table de séquence actuelle🎜🎜Le deuxième problème ne peut se produire que dans deux situations 🎜Lorsque l'index est inférieur à 0 ou que l'index dépasse le nombre d'éléments dans la table de séquence actuelle🎜, lancez simplement une exception d'exécution🎜. 🎜 🎜Après qu'il n'y ait aucun problème avec l'index, le processus d'ajout d'éléments est comme indiqué ci-dessous : 🎜🎜
要先将要添加的索引位置后的所有元素依次向后移动一位，在移动完成后将当前索引位置的元素使用要进行添加的元素对当前位置的元素进行覆盖即可，同时添加完元素后将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));
}
}
