开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 《数据结构-第一章》之顺序表 -> 正文阅读

[数据结构与算法]《数据结构-第一章》之顺序表

前言

在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!”

博客主页：KC老衲爱尼姑的博客主页

博主的github，平常所写代码皆在于此

刷题求职神器

共勉：talk is cheap, show me the code

作者是爪哇岛的新手，水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

文章目录

线性表

线性表

线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。线性表的逻辑上是连续的,物理上不一定连续的，比如数组它在逻辑上和物理上都是连续的,但是链表在逻辑上是连续的在物理上是不连续的。常见的线性表有数组,栈,队列,链表。

数组在内存的存储

在这里插入图片描述

链表在内存的存储

在这里插入图片描述

线性表定义如下

线性表是具有相同数据类型的n（n≥0）个类型相同的数据元素组成的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其他更复杂的信息。线性表通常记为：（a1，…，ai－1，，ai，ai＋1，，…，an），其中n为表长，n＝0时称为空表。表中相邻元素之间存在着顺序关系，ai－1领先于ai，ai领先于ai＋1，称ai－1是ai的直接前驱元素，ai＋1是ai的直接后继元素。当i＝1，2，…，n－1时，ai有且仅有一个直接后继；当i＝2，3，…，n时，ai有且仅有一个直接前驱ai－1；当i＝1，2，…，n－1时，有且仅有一个直接后继ai＋1，而a1是表中第一个元素，它没有前驱，an是最后一个元素，无后继。

前驱:线性表中除了第一个元素以外都有前驱

后继:线性表中除了最后一个元素以外都有后继

顺序表

顺序表是用一段物理地址连续的存储单元依次存储元素的线性结构。一般情况下采用数组存储,在数组上完成数据的增删查改。像Java中的ArrayList就是顺序表,底层是一个Object数组。接下来就使用数组来实现一个简单的顺序表。

接口实现

public class SeqList {
// 打印顺序表
public void display() { }
// 新增元素,默认在数组最后新增
public void add(int data) { }
// 在 pos 位置新增元素
public void add(int pos, int data) { }
// 判定是否包含某个元素
public boolean contains(int toFind) { return true; }
// 查找某个元素对应的位置
public int indexOf(int toFind) { return -1; }
// 获取 pos 位置的元素
public int get(int pos) { return -1; }
// 给 pos 位置的元素设为 value
public void set(int pos, int value) { }
//删除第一次出现的关键字key
public void remove(int toRemove) { }
// 获取顺序表长度
public int size() { return 0; }
// 清空顺序表
public void clear() { }
}

属性

    private static final int capacity = 3;//初始化数组的容量
    private int elem[];//存储元素的数组
    private int userSized;//记录顺序表中元素的个数

构造方法

使用无参构造在创建顺序表的时候,为其分配默认的容量

    public MyArrayList() {
        this.size = 0;
        elementData = new int[CAPACITY];
    }

常用方法

打印顺序表

遍历数组即可


    /**
     * 打印顺序表中的数据
     */
    public void display() {
        for (int i = 0; i < this.userSized; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

添加元素

默认在数组末尾添加元素

   /**
     * 新增元素,默认在数组末尾添加元素
     *
     * @param element
     */
    public void add(int element) {
        if (isFull()) {//对数组进行判断是否已经满了,满了则2倍扩容
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        this.elementData[this.size++] = element;
    }

在指定位置插入元素

在数组中插入一个元素,并不是使用数组直接访问该位置然后进行修改这个位置的值,这不是插入而是修改。在顺序表中定义一个size属性,记录数组中元素的个数,假设现在数组中有8个元素,那么size指向的位置是在数组中元素的后一个位置,我们可以将从指定插入位置到size-1位置的元素都往后挪一个位置出来,然后再将要插入的元素插入即可。

假设数组长度为11,在数组的索引2处插入一个99，插入过程如下图。

在这里插入图片描述

    /**
     * 在指定位置插入元素
     *
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        if (isFull()) {//判断是否已满
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        //判断index合法
        if (index < 0 || index > this.size) {
            return;
        }
        //从要插入元素的位置开始将元素都后移
        for (int i = this.size-1; i >= index; i--) {
            this.elementData[i + 1] = this.elementData[i];
        }
        //插入元素
        this.elementData[index] = element;
        this.size++;
    }

判定是否包含某个元素

直接遍历数组找到目标值

   /**
     * 判断数组中是否包含该元素
     * @param toFind
     * @return
     */
    public boolean contains(int toFind) {
        if (isEmpty()){
            return true;
        }
        for (int i=0;i<this.size;i++) {
            if (this.elementData[i]==toFind) {
                return true;
            }
        }
        return false;
    }

查找某个元素对应的位置(头到尾)

  /**
     * 查找某个元素对应的位置(从头到尾)
     * @param toFind
     * @return
     */
    public int indexOf(int toFind) {
        for (int i = 0; i < this.size; i++) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

查找某个元素对应的位置(尾–>头)


    /**
     * 查找某个元素对应的位置(从尾都头)
     * @param toFind
     * @return
     */
    public int lastIndexOf(int toFind) {
        for (int i=this.size-1;i>=0;i--) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

获得pos位置的值

首先进进判空,在判断pos是否合法,最后直接访问。

  /**
     *  pos 位置的元素
     * @param pos
     * @return
     */
    public int get(int pos) {
        if (isEmpty()) {
            throw new RuntimeException("MyArrayList为空");
        }
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos位置不合法");
        }
        return this.elementData[pos];
    }

设置pos位置的值

首先进进判空,在判断pos是否合法,最后直接修改。

  /**
     * 给 pos 位置的元素设为 value
     * @param pos
     * @param value
     */
    public void set(int pos, int value) {
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos不合法");
        }
        this.elementData[pos] = value;
    }

删除第一次出现的关键字

先找到要删除的位置,然后判断该位置是否合法,然后该位置后面的元素都往前移动一个位置,就可以完成删除。

    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
        int index = searchIndex(key);
        if (index<0||index>this.size) {
            throw new RuntimeException("index不合法");
        }
        for (int i=index; i<this.size-1; i++) {
            this.elementData[i] = this.elementData[i+1];
        }
        this.size--;
    }

获取顺序表的长度

直接返回size即可

    /**
     * 返回数组的长度
     *
     * @return
     */
    public int size() {
        return this.size;
    }

清空顺序表

注意:如果是基本类型,直接将size置空,如果是引用类型要将所有元素置为null,再将size置为0。

    /**
     * 清空数组
     */
    public void clear(){
        this.size = 0;
    }

顺序表所有的源代码

package com.kc.demo;

import java.util.Arrays;

public class MyArrayList {
    private static int[] elementData;
    private static final int CAPACITY = 5;//初始化数组的容量
    private int size;

    public MyArrayList() {
        this.size = 0;
        elementData = new int[CAPACITY];
    }

    /**
     * 遍历数组
     */
    public void display() {
        for (int i = 0; i < this.size; i++) {
            System.out.print(this.elementData[i] + " ");
        }
        System.out.println();
    }

    /**
     * 新增元素,默认在数组末尾添加元素
     *
     * @param element
     */
    public void add(int element) {
        if (isFull()) {
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        this.elementData[this.size++] = element;
    }

    /**
     * 在指定位置插入元素
     *
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        if (isFull()) {
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        //判断index合法
        if (index < 0 || index > this.size) {
            return;
        }
        for (int i = this.size-1; i >= index; i--) {
            this.elementData[i + 1] = this.elementData[i];
        }
        this.elementData[index] = element;
        this.size++;
    }

    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
        int index = searchIndex(key);
        if (index<0||index>this.size) {
            throw new RuntimeException("index不合法");
        }
        for (int i=index; i<this.size-1; i++) {
            this.elementData[i] = this.elementData[i+1];
        }
        this.size--;
    }

    /**
     * 查找该元素数组中第一次出现的位置
     * @param key
     * @return
     */
    private int searchIndex(int key){
      for (int i=0;i<this.size;i++) {
          if (this.elementData[i]==key) {
              return i;
          }
      }
      return -1;
    }

    /**
     * 判断数组中是否包含该元素
     * @param toFind
     * @return
     */
    public boolean contains(int toFind) {
        if (isEmpty()){
            return true;
        }
        for (int i=0;i<this.size;i++) {
            if (this.elementData[i]==toFind) {
                return true;
            }
        }
        return false;
    }

    /**
     * 判断数组是否已经满了
     * @return
     */
    private boolean isFull() {
        if (this.size == CAPACITY) {
            return true;
        }
        return false;
    }

    /**
     * 查找某个元素对应的位置(从头到尾)
     * @param toFind
     * @return
     */
    public int indexOf(int toFind) {
        for (int i = 0; i < this.size; i++) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 查找某个元素对应的位置(从尾都头)
     * @param toFind
     * @return
     */
    public int lastIndexOf(int toFind) {
        for (int i=this.size-1;i>=0;i--) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 给 pos 位置的元素设为 value
     * @param pos
     * @param value
     */
    public void set(int pos, int value) {
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos不合法");
        }
        this.elementData[pos] = value;
    }

    /**
     *  pos 位置的元素
     * @param pos
     * @return
     */
    public int get(int pos) {
        if (isEmpty()) {
            throw new RuntimeException("MyArrayList为空");
        }
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos位置不合法");
        }
        return this.elementData[pos];
    }

    /**
     * 判断数组是否为空
     * @return
     */
    private boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 返回数组的长度
     *
     * @return
     */
    public int size() {
        return this.size;
    }

    /**
     * 清空数组
     */
    public void clear(){
        this.size = 0;
    }
}