数据结构（一）之顺序表详解

太过爱你忘了你带给我的痛 2023-09-27 13:26 102阅读 0赞

**目录**

一、线性表的定义

二、顺序表的详解

三、顺序表的增删改查操作实现

--------------------

## 一、线性表的定义 ##

线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

线性表分为顺序存储和链式存储。

在这里我们先引出顺序表的定义，本篇文章主要讲顺序表。

链表文章见下一篇文章[链表详细介绍][Link 1]

![b1e10fa01ab84efca13742460b86517f.png][]

## 二、顺序表的详解 ##

顺序表的存储方式是用一段**物理地址连续**的存储单元来存放数据元素，一般都是使用一维数组形式存放。

对顺序表的数据元素实现增删改查相当于对数组进行增删改查操作。

**顺序表的长度可以用size表示即顺序表中数据元素的个数，数组的长度用length表示，此时需要知道的是size ![\\leqslant][leqslant] length。**

顺序表可以分为静态顺序表和动态顺序表。静态顺序表是采用定长的数组进行存储，动态顺序表则是使用动态变化的数组存储。

因此当我们对顺序表实现增操作时，此时就需要考虑以下几点：

（1）当在顺序表中增加某元素时，判断顺序表的长度是否充足，如果当插入新元素时，顺序表长度不够则需要考虑对数组进行扩容，调用Java的copyOf进行扩容，例如：对数组进行2倍扩容

**array =Arrays.copyOf（array，array.length\*2）**

（2）插入新元素位置是否合法

顺序表是一段连续的物理地址进行数据存储，只能仅有一个前驱和一个后继，通俗讲就是数据元素必须紧密挨着

## 三、顺序表的增删改查操作实现 ##

（1）定义一个顺序表

public class  myList () {
       public int[] array; //定义数组
       public int size; //定义顺序表的有效长度
       public myList() {
           this.array = new int[8]; //构造方法，创建一个数组容量为8的数组
       } 
    
    }

（2）遍历并打印顺序表

public void display() { //自定义的打印方法，不是顺序表的方法
    for(int i=0;i<this.size;i++) {
        System.out.print(this.array[i]+" ");
    }
         System.out.println();
    }

(3) 判断某个元素是否在顺序表中

public boolean contains(int toFind) {
       for(int i=0; i<this.size; i++){ 
             if(this.array[i]==toFind){
              return true;
        }
     }
             return false;
    }

(4)查找某个元素对应的位置下标

public int indexOf(int data){
      for(int i=0;i<this.size;i++){
           if(array[i]==data){
                   return i;
         }
      }
                return -1;
    }

(5) 获取pos位置的元素

//获取pos位置的元素
    public int get(int pos){
      if(pos<0 || pos>=this.size){
           System.out.println("pos位置不合法");
             return ;
      } 
         return array[pos];
    }

（6）顺序表插入新元素

> 新增元素，默认在数组最后新增

// 新增元素,默认在数组最后新增
    public void add(int data) {
       if(this.size == this.array.length) {  //判断插入新元素时，顺序表是否需要扩容
           this.array = Arrays.copyOf(this.array,this.array.length*2)
      }
       array[this.size] = data;
       this.size++；//插入新元素，顺序表长度要增加
    }

> 在pos位置插入新元素

此时需要**判断pos位置是否合法**以及**当插入新元素时，顺序表是否需要扩容**

// 在 pos 位置新增元素
    public void add(int pos, int data) {
       if (pos<0 || pos>this.size) {//判断pos位置的合法性
          System.out.println("pos位置不合法");//当pos位置不合法时抛出异常
           return ;
    }
       if(this.size == this.array.length){
           this.array = Arrays.copeOf(this.array,this.array.length*2)
    }
          for(int i=this.size-1;i>=pos;i--){ //依次从后往前遍历数组，直到找到pos下标
               array[i+1]=array[i]; //插入新元素，后面元素依次往后移
      }
            array[pos]=data; 
            this.size++;
     }

（7）将pos位置的元素改为value

//将pos位置的元素改为value
    public void set(int pos，int value){ 
       if(pos<0 || pos>=this.size){ //检查pos位置的合法性
           System.out.println("pos位置不合法");//当pos位置不合法时抛出异常
           return ;
      }
             array[pos]=value;
    }

（8）删除第一次出现的元素

//删除第一次出现的元素data
    public void remove(int data){
        int a = indexOf(data)//调用返回元素位置下标的方法,用a来接受返回下标值(参考操作4)
        if(a==-1){
        System.out.println("顺序表没有元素data");
     }
       for(int i = a;i < this.size-1;i++){ //this.size-1表示删除元素后长度减一，跳出for循环
         array[i]=array[i+1];
        }
        this.size--;
        array[this.size-1]=0;
      }

以上就是顺序表的增删改查操作，由于顺序表是用一段连续的物理地址单元来存储数据元素，每当执行增删操作时，都需要把元素依次往后或者往前移动，效率很低，不适合频繁的进行增删操作。

但顺序表有一个优点：适合根据给定下标进行查找数据元素，效率很快。

[Link 1]: https://blog.csdn.net/qq_73471456/article/details/128424715?spm=1001.2014.3001.5502
[b1e10fa01ab84efca13742460b86517f.png]: https://img-blog.csdnimg.cn/b1e10fa01ab84efca13742460b86517f.png
[leqslant]: https://latex.csdn.net/eq?%5Cleqslant