devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法——7.线性表（顺序表即动态数组）_线性表动态结构有哪些

作者：Monodyee | 2024-06-05 01:39:20

赞

踩

线性表动态结构有哪些

这篇文章我们来讲一下线性表

1.线性表概述

线性表是最基本、最简单，也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。

下面介绍两个术语：

前驱元素：若A元素在B元素前面，则称A为B的前驱元素

后继元素：若B元素在A元素后面，则称B为A的后继元素

线性表的特征：

  1. 数据元素之间具有“一对一”的逻辑关系
  2. 第一个数据元素没有前驱，这个数据元素称为头结点
  3. 最后一个数据元素没有后继，这个数据元素称为尾结点
  4. 除了第一个和最后一个数据元素外，其他元素有且仅有一个前驱和后继

如果把线性表用数学语言来定义，则可以表示为（a1，a2，a3，...ai-1，ai，ai+1，...an）ai-1领先与ai，ai领先与ai+1，称ai-1是ai的前驱，ai+1是ai的后继

如下图所示：

线性表的分类：

线性表中数据存储的方式可以是顺序存储也可以是链式存储，按照存储方式的不同，把线性表分为顺序表和链表。 

2.顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

注意：

顺序表是依靠数组来实现的，但是顺序表不是数组，二者是有区别的。数组的长度是死的，一旦定义，就不能增加或删除元素，而顺序表是活的，是可以动态的增删元素的。顺序表和数组除了这点外，其余的特性完全一样，比如都只能存同一种数据，内存中物理地址都相邻等等。可以说，顺序表是动态的数组。这点一定要区分清楚！！！

顺序表的API设计：

3.顺序表的实现

下面，我们用代码来实现一下顺序表

代码如下：

  1.  
  2. public class SequenceList<T> {
  3.  
  4.     //存储元素的数组
  5.     private T[] eles;
  6.     //记录当前顺序表中元素的个数
  7.     private int N;
  8.  
  9.     //构造方法
  10.     public SequenceList(int capacity){
  11.         //初始化数组
  12.         this.eles = (T[]) new Object[capacity];
  13.         //初始化长度(默认的存储元素为0，因为刚创建初始化时，它一个元素都没有存)
  14.         this.N = 0;
  15.     }
  16.  
  17.     //将线性表置为空表
  18.     public void clear(){
  19.         this.N = 0;
  20.     }
  21.  
  22.     //判断顺序表是否为空表
  23.     public boolean isEmpty(){
  24.         return N==0;
  25.     }
  26.  
  27.     //获取线性表的长度
  28.     public int length(){
  29.         return N;
  30.     }
  31.  
  32.     //获取指定位置的元素
  33.     public T get(int i){
  34.         return eles[i];
  35.     }
  36.  
  37.     //向线性表中插入元素
  38.     public void insert(T t){
  39.         eles[N++] = t;
  40.     }
  41.  
  42.     //往指定索引i处添加元素t
  43.     public void insert(int i,T t){
  44.         //先把i索引处的元素及其后面的元素依次向后移动一位
  45.         for (int index = N-1; index >i ; index--) {
  46.             eles[index] = eles[index - 1];
  47.         }
  48.         //再把t元素方到i索引处
  49.         eles[i] = t;
  50.     }
  51.  
  52.     //删除指定位置i处的元素，并返回该元素
  53.     public T remove(int i){
  54.         //记录索引i处的值
  55.         T current = eles[i];
  56.         //索引i后面的元素依次向前移动一位
  57.         for (int index = i; index < N-1; index++) {
  58.             eles[index] = eles[index+1];
  59.         }
  60.         //元素个数减一
  61.         N--;
  62.         return current;
  63.     }
  64.  
  65.     //查找元素t第一次出现的位置
  66.     public int indexOf(T t){
  67.         for (int i = 0; i < N; i++) {
  68.             if (eles[i] == t)
  69.                 return i;
  70.         }
  71.         return -1;
  72.     }
  73. }

前提：

这里事先先说明一下一些情况，这样后面解释类中的方法是如何写的时候就比较容易理解。

下面，跟着我的描述来思考。

我们要做什么？我们要创建一个顺序表。前面说了，这个顺序表就是一个动态数组，它可以实现元素的插入啊，删除啊，求长度啊等等等等一系列操作（这些操作数组无法完成）。那么这个顺序表的本质是什么？是数组。数组的本质是什么？数组的本质是一块连续空间，然后将这些空间分割为一系列小块，然后在这些小块中放数据。哦，那我们就知道了，顺序表的本质也是在内存中开辟一块空间，然后将大空间分割为小空间，然后在小空间里面放数据。只不过顺序表可以实现一些插入删除的操作罢了。至此，顺序表的本质我们明白了。

下面回到代码中来，我们来解释代码。

成员变量：

我们顺序表的成员变量有一个数组，一个整型数据N，数组好理解，放数据用的（即顺序表的核心），那么N是用来干什么的呢？N是用来记录顺序表中的数据个数用的！！！ 这时，就有人说了“那N就是第6行数组的长度，即顺序表中数组的长度呗”，错！！！N不是顺序表中数组的长度！！！它们是两个不同的概念！！！顺序表中数组的长度在我们初始化的时候给出，N不是顺序表中数组的长度（再次强调！！！），N是顺序表中有效数据，即用户放入顺序表中数据的个数！！！

这里又涉及到对象的初始化问题了，简单的说一下吧。

当我们在测试类中，new出一个对象的时候，jvm会根据类中数组的类型对其赋予默认的初始值，比如，我们指定泛型T为int类型的，那么在我们new出对象的时候，对象内部的数组eles中的每一个元素都有其默认初始值0，这些值是无效的，而这些值的个数即为我们数组的长度。但是我们这是顺序表，我们需要用它来存数据，假设，我们对象内部数组eles的长度为5，即数组长度为5，但是我们在这个顺序表中存了3个数据，那么顺序表的有效数据就是3，这个3就是N的值，即顺序表的长度。

以上就是对N与数组长度的说明。这点一定要清楚

下面，我们再来逐个分析类中的每个方法。

3.1 构造函数

顺序表的构造方法如下：

解析：

我们需要传的仅仅只是顺序表的长度，这个顺序表的长度就是顺序表内部数组的长度，所以就有了第13行，但是，我们用的是泛型，我们不能new T[ capacity] 啊，所以我们只能new最大的类——object，类型不一致啊，没关系，前面加个强制类型转换就行。这就是第13行的逻辑

此时，我们只是初始化好了顺序表，表中没有放任何数据，那么N的值当然为0了。这就是第15行的逻辑

3.2 置空方法

代码如下：

解析：

首先，我们需要将这个顺序表当做一个整体看待！！！这个N就是记录里面存储数据的个数的，顺序表为空，那么顺序表中存储元素的个数就为0了，所以直接设置N=0就行

有人就要问了，那数组中元素怎么办呢？前面说了，将顺序表当做一个整体看待，它就是一个黑匣子，你看不到里面的内容。所以，完全可以不用管数组中的那些元素。你只需要知道，你使用时，在指定的位置存储了什么，即有限个位置的确定值就行，至于其他位置，它存的是多少，关你何事？

3.3 判断是否为空

代码如下：

解析：

顺序表为空，那就是N=0；所以直接判断N是否为0就行，这里用来隐式类型转换，返回Boolean类型的值 

3.4 获取表长度

代码如下：

解析：

顺序表的长度就是N的值，所以就直接返回N就行 

3.5 获取指定位置的值

代码如下：

解析：

元素是存在数组中的，并且在有限位中，数组的索引和顺序表的索引是一致的，所以获取顺序表指定位置的元素，就是获取数组指定位置的元素

3.6 插入元素

代码如下：

解析：

很简单啊，顺序表索引加1，然后在里面放指定的元素 

3.7 在指定位置插入元素

代码如下：

解析：

在指定位置插入指定元素，因为顺序表的本质是数组，所以就是在数组的中间插入元素。那就简单了啊，在 索引 i 处的元素及其后面的元素依次向后移动一位，一个for循环就能解决，然后在指定位置处插入指定的元素。很简单的事。

注意：这两个插入用来方法的重载，区别是参数不同。

3.8 删除并返回指定处的元素

代码如下：

解析：

这个也很简单啊。删除并返回指定位置的元素，那就先用个变量记录指定位置的元素，然后把这个元素后面的所有元素都往前移动一位，然后将那个记录元素的变量返回就行了啊，so easy！ 

3.9 找到元素第一次出现的位置

代码如下：

解析：

一个for循环加一个 if 判断的事，找到了返回指定位置的索引，找不到，返回-1 

3.10 测试

下面，我们写个测试类来测试一下：

  1.  
  2.  
  3. public class SequenceTest {
  4.     public static void main(String[] args) {
  5.         //创建顺序表对象
  6.         SequenceList<String> s1 = new SequenceList<>(10);
  7.         //测试插入
  8.         s1.insert("a");
  9.         s1.insert("b");
  10.         s1.insert("c");
  11.         s1.insert(1,"aaaaa");
  12.  
  13.         //测试获取
  14.         String getResult = s1.get(1);
  15.         System.out.println("1处的元素为："+getResult);
  16.  
  17.         //测试删除
  18.         String removeResult = s1.remove(0);
  19.         System.out.println("删除的元素是："+removeResult);
  20.  
  21.         //测试清空
  22.         s1.clear();
  23.         System.out.println("清空后的顺序表中的元素个数为："+s1.length());
  24.     }
  25. }

测试结果如下图：

 完美！ 

4.顺序表的遍历

一般作为容器存储数据的数据结构，都需要向外部提供遍历的方式。所以，下面，我们也来看一下顺序遍历方式

在java中，遍历集合一般都是用for-each循环，如果想让我们的SequenceList也能支持for-each循环，则需要如下操作：

  1. 让SequenceList实现 Iterable 接口，重写iterator方法；
  2. 在SequenceList内部提供一个内部类SIterable，实现iterator接口，重写hasNext方法和next方法

代码如下：

  1.  
  2.  
  3. import java.util.Iterator;
  4.  
  5. public class SequenceList<T> implements Iterable<T>{
  6.  
  7.     //存储元素的数组
  8.     private T[] eles;
  9.     //记录当前顺序表中元素的个数
  10.     private int N;
  11.  
  12.     //构造方法
  13.     public SequenceList(int capacity){
  14.         //初始化数组
  15.         this.eles = (T[]) new Object[capacity];
  16.         //初始化长度(默认的存储元素为0，因为刚创建初始化时，它一个元素都没有存)
  17.         this.N = 0;
  18.     }
  19.  
  20.     //将线性表置为空表
  21.     public void clear(){
  22.         this.N = 0;
  23.     }
  24.  
  25.     //判断顺序表是否为空表
  26.     public boolean isEmpty(){
  27.         return N==0;
  28.     }
  29.  
  30.     //获取线性表的长度
  31.     public int length(){
  32.         return N;
  33.     }
  34.  
  35.     //获取指定位置的元素
  36.     public T get(int i){
  37.         return eles[i];
  38.     }
  39.  
  40.     //向线性表中插入元素
  41.     public void insert(T t){
  42.         eles[N++] = t;
  43.     }
  44.  
  45.     //往指定索引i处添加元素t
  46.     public void insert(int i,T t){
  47.         //先把i索引处的元素及其后面的元素依次向后移动一位
  48.         for (int index = N; index >i ; index--) {
  49.             eles[index] = eles[index - 1];
  50.         }
  51.         //再把t元素方到i索引处
  52.         eles[i] = t;
  53.         //元素个数加1
  54.         N++;
  55.     }
  56.  
  57.     //删除指定位置i处的元素，并返回该元素
  58.     public T remove(int i){
  59.         //记录索引i处的值
  60.         T current = eles[i];
  61.         //索引i后面的元素依次向前移动一位
  62.         for (int index = i; index < N-1; index++) {
  63.             eles[index] = eles[index+1];
  64.         }
  65.         //元素个数减一
  66.         N--;
  67.         return current;
  68.     }
  69.  
  70.     //查找元素t第一次出现的位置
  71.     public int indexOf(T t){
  72.         for (int i = 0; i < N; i++) {
  73.             if (eles[i] == t)
  74.                 return i;
  75.         }
  76.         return -1;
  77.     }
  78.  
  79.     //遍历
  80.     @Override
  81.     public Iterator<T> iterator() {
  82.  
  83.         return new SIterator();
  84.     }
  85.  
  86.     private class SIterator implements Iterator{
  87.         private int cusor;
  88.         public SIterator(){
  89.             this.cusor = 0;
  90.         }
  91.         //判断当前容器中还有没有下一个元素
  92.         @Override
  93.         public boolean hasNext() {
  94.             return cusor < N;
  95.         }
  96.         //获取当前容器中的下一个元素的
  97.         @Override
  98.         public Object next() {
  99.             return eles[cusor++];
  100.         }
  101.     }
  102.  
  103. }

遍历的原理上面讲了，这里就不过多赘述了。

注意，在指定位置添加元素的方法做出了一点小修改，最终方法如下图：

画个图，自己看一下就明白了。

5.顺序表的容量可变

我们上面实现的顺序表，真的是一个完整是顺序表吗？Of Course Not ！！Why？？Because 它的容量不可变啊。就比如说，我定义它的长度为5，但是我偏要存10个数据，行吗？Of Course Not Too ！！你看java中的List列表是这样的？当然不是了。所以，它还缺一个容量可变的功能。下面，让我们来实现它！

代码如下：

  1.  
  2. import java.util.Iterator;
  3.  
  4. public class SequenceList<T> implements Iterable<T>{
  5.  
  6.     //存储元素的数组
  7.     private T[] eles;
  8.     //记录当前顺序表中元素的个数
  9.     private int N;
  10.  
  11.     //构造方法
  12.     public SequenceList(int capacity){
  13.         //初始化数组
  14.         this.eles = (T[]) new Object[capacity];
  15.         //初始化长度(默认的存储元素为0，因为刚创建初始化时，它一个元素都没有存)
  16.         this.N = 0;
  17.     }
  18.  
  19.     //将线性表置为空表
  20.     public void clear(){
  21.         this.N = 0;
  22.     }
  23.  
  24.     //判断顺序表是否为空表
  25.     public boolean isEmpty(){
  26.         return N==0;
  27.     }
  28.  
  29.     //获取线性表的长度
  30.     public int length(){
  31.         return N;
  32.     }
  33.  
  34.     //获取指定位置的元素
  35.     public T get(int i){
  36.         return eles[i];
  37.     }
  38.  
  39.     //向线性表中插入元素
  40.     public void insert(T t){
  41.         if (N==eles.length){
  42.             reSize(2*eles.length);
  43.         }
  44.         eles[N++] = t;
  45.     }
  46.  
  47.     //往指定索引i处添加元素t
  48.     public void insert(int i,T t){
  49.  
  50.         if (N==eles.length){
  51.             reSize(2*eles.length);
  52.         }
  53.         //先把i索引处的元素及其后面的元素依次向后移动一位
  54.         for (int index = N; index >i ; index--) {
  55.             eles[index] = eles[index - 1];
  56.         }
  57.         //再把t元素方到i索引处
  58.         eles[i] = t;
  59.         //元素个数加1
  60.         N++;
  61.     }
  62.  
  63.     //删除指定位置i处的元素，并返回该元素
  64.     public T remove(int i){
  65.         //记录索引i处的值
  66.         T current = eles[i];
  67.         //索引i后面的元素依次向前移动一位
  68.         for (int index = i; index < N-1; index++) {
  69.             eles[index] = eles[index+1];
  70.         }
  71.         //元素个数减一
  72.         N--;
  73.         if (N<eles.length/4){
  74.             reSize(eles.length/2);
  75.         }
  76.         return current;
  77.     }
  78.  
  79.     //查找元素t第一次出现的位置
  80.     public int indexOf(T t){
  81.         for (int i = 0; i < N; i++) {
  82.             if (eles[i] == t)
  83.                 return i;
  84.         }
  85.         return -1;
  86.     }
  87.  
  88.     //根据参数newSize来重置eles的大小
  89.     public void reSize(int newSize){
  90.         //定义一个临时数组，指向原数组
  91.         T[] temp = eles;
  92.         //创建一个新数组
  93.         eles = (T[]) new Object[newSize];
  94.         //把原数组中的元素拷贝到新数组中
  95.         for (int i = 0; i < N; i++) {
  96.             eles[i] = temp[i];
  97.         }
  98.     }
  99.  
  100.     //遍历
  101.     @Override
  102.     public Iterator<T> iterator() {
  103.         return new SIterator();
  104.     }
  105.  
  106.     private class SIterator implements Iterator{
  107.         private int cusor;
  108.         public SIterator(){
  109.             this.cusor = 0;
  110.         }
  111.         //判断当前容器中还有没有下一个元素
  112.         @Override
  113.         public boolean hasNext() {
  114.             return cusor < N;
  115.         }
  116.         //获取当前容器中的下一个元素的
  117.         @Override
  118.         public Object next() {
  119.             return eles[cusor++];
  120.         }
  121.     }
  122.  
  123. }

解析：

什么时候需要容量改变？插入元素或删除元素时。插入好理解，删除怎么说？假设，我们定义数组长度为100w，一开始也存储了100w个数据，但是我们删啊删，删到最后只剩1个数据，你还要占用100w个数据空间吗？这不浪费空间吗？所以删除时也要改变容量。

怎么改变？简单，改变顺序表中数组的大小就行，怎么变？变为原来的2倍就行。所以思路清晰了。我们先定义临时数组，存储eles的值，然后将eles的大小变为原来的2倍，然后再将临时数组中的值传给新的eles就行，so easy！

然后就是在插入元素和删除元素时判断一下就行啦，很简单。

代码上面给了，下面测试一下：

结果如下图所示：

完美！

6.小结

 这篇文章主要讲了顺序表。会者不难，难者不会。还是那句话：容量不可变前，顺序表是低级版的动态数组；容量可变后，顺序表是完全版的动态数组。它的底层就是靠数组实现的。一个数组的长度，一个记录顺序表元素个数的变量，在一定的范围内（顺序表元素个数 <= 数组的长度），二者相同，即顺序表和数组的索引相同，所以对顺序表的操作就是对数组的操作！！！就这，没啥，so easy的事。

最后，给个图。看着图，瞅着代码，多思考思考：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/674318
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号