线性表的顺序表示和实现,创建一个线性顺序表
00-1010前言一、什么是序列表？第二，序列1的实现。准备2。获取序列表3中元素的个数。获取序列表4的当前容量。序列表是否为空。在指定的索引位置6添加元素。在序列表7的末尾添加元素。在序列表8的开头添加元素。获取指定索引位置9的元素。获得序列表10的第一个元素。获得序列表11的最后一个元素。修改指定索引位置12处的元素。判断指定的元素是否包含在序列表13中。获取序列表14中指定元素的索引。删除指定索引位置15处的元素。删除并返回序列表16中的第一个元素。删除并返回序列表17中的最后一个元素。删除序列表18中的指定元素。动态扩展和收缩序列表3。运行结果4。总结源代码1。数组类源代码2。测试类源代码。
00-1010之前简单的用C语言实现了序列表：线性表在C语言中的顺序表示和实现。
当时是用C语言实现的，因为学校的课本都是用C语言实现的。在后来的学习中，Java成为我的主要语言，使用不同的语言实现序列表也可以加深我对语言的理解和应用。
00-1010序列表是以数组形式存储在计算机内存中的线性表。线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即数据元素之间的逻辑相邻关系通过数据元素的物理存储来反映。具有顺序存储结构的线性表通常称为顺序表。顺序是将一组地址连续的存储单元表中的节点依次存储在计算机内存中。
00-1010从序列表的定义可以看出，序列表是一组地址连续的存储单元,本质上是增加了一些基本运算函数的数组。
在本文中要实现的功能有：
获取序列表中元素个数，序列表当前容量是否为空，在指定索引位置添加元素，在序列表末尾添加元素，在序列表开头添加元素，获取序列表第一个元素，修改序列表最后一个元素，判断序列表是否包含指定元素，获取序列表中指定元素的索引， 删除指定索引位置的元素并返回序列表，删除第一个元素并返回序列表，删除序列表的最后一个元素，动态扩展和收缩序列表。
00-1010实现工具版本IntelliJ IDEA2021.3JDK1.8在IntelliJ IDEA中新建一个普通Java项目即可。
在构建了新的Java项目之后，我们创建了自己的顺序表类。这里，我命名当前类数组，这里我们实现泛型。同时，Array类中有两个成员属性：
存放数据的数组:数据，类型为泛型数组当前顺序表中元素的数量:大小，类型为int。两个成员属性的访问权限应该是私有的，用户不能直接修改，只能通过对应的getter方法获取。在成员属性中，我们将在数据数组和只是进行了声明，但是并未进行初始化,中的顺序表中存储元素的数量，因此==初始化的过程需要在构造方法==中执行
有参构造:当用参数构造时，我们只需要指定传递的参数是一个int类型的数据容量，它代表顺序表的初始容量,这样我们就可以初始化数据的泛型数组。同时，当前序列表中没有元素，这意味着序列表中元素数量大小的初始值为0。无参构造:当用户没有指定序列表的初始容量时，我们可以将初始容量定义为10，我们只需要通过这个(10)进行一个带参数构造的调用。在注意：Java中，你不能直接初始化泛型数组。你需要先声明对象类型的数组，然后通过强制类型转换.把对象类型的数组转换成泛型数组
包net . csdn . array；/* * * * @作者章荣康* @日期2022/6/26 */公开课ArrayEg
t; {/** * 存放数据的数组 */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 = %dn", 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<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); } /** * 获取数组中的元素个数 * * @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 = %dn", 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线性表的顺序表示及实现的文章就介绍到这了,更多相关Java线性表内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。