[数据结构与算法] 数据结构笔记(线性表之顺序表)

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

-> 数据结构与算法 -> 数据结构笔记(线性表之顺序表) -> 正文阅读

[数据结构与算法]数据结构笔记(线性表之顺序表)

文章目录

1.什么是线性表？

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串等
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

2.什么是顺序表？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
在java中动态顺序表只有动态开辟的数组存储
动态顺序表的优点：动态顺序表更灵活, 根据需要动态的分配空间大小.

项目详细分配：

TestDemo.java 实现测试方法
MyArrayList.java 实现相关顺序表功能

定义顺序表

TestDemo.java 实现测试方法：
在这里插入图片描述

 public class TestDemo {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
    }
}

在这里插入图片描述

    public int []elem;  //底层数组
    public int useSize; //数组中的有效长度
    public int capacity = 10; //数组长度初始化为10
    public MyArrayList(){  //实现一个构造方法，为数组规定数组长度
        this.useSize = 0;
        this.elem = new int[this.capacity];
    }

在这里插入图片描述

顺序表功能

? 顺序表之打印顺序表

📝算法思想：

在打印顺序表之前，让我们想一想，要打印顺序表将要具备哪些条件？
数组不能为空
依次遍历数组中的每一个元素，打印到屏幕上
那就必须先实现一个判空方法即isEmpty方法

     public boolean isEmpty(){
        if(this.useSize == 0){  //如果数组的有效长度为0，说明数组为空
            return true;
        }
        return false;
    }

接着就在打印方法中调用isEmpty方法，实现打印数据

     //打印顺序表
    public void display(){
        //判断数组是否为空
        if(isEmpty()){
            System.out.println("数组为空");
            return;
        }
        for(int i = 0;i<this.useSize;i++){
            System.out.println(this.elem[i]);
        }
        System.out.println();
    }

? 顺序表之向顺序表中增添数据

📝 算法思想：

如果插入数据的位置不合理，就抛出异常
如果线性表长度大于或等于数组长度，就抛出异常或动态增加容量
移动从最后一个元素开始向前遍历到第i个元素位置，将他们都向后移动一个单位
将要插入的数插入在i位置
有效长度+1

在这里插入图片描述

在添加数据之前，我们再想一想，有没有条件限制？如果你将要数据的下标是否合法？
原数组是否是满的？
这些方面都需要考虑，要做一个严谨的程序员，哈哈哈😀😀😀。

   //判断数组是否是满的
    public boolean isFull(){
        if(this.useSize == this.capacity){//当有效数组长度等于数组长度时，说明数组此时已经被数据沾满
            return true;
        }else{
            return false;
        }
    }

//在pos位置新增元素
    public void add(int pos,int value){
        //判断数组是否是满的
        //判断pos是否和法
        if(pos < 0 || pos > this.useSize){ //当传来的下标小于0或者大于有效数组长度是，就直接返回，pos不合法
            return ;
        }
        if(isFull()){
            System.out.println("数组已满，开始扩容");
        }
        this.elem = Arrays.copyOf(this.elem,2*this.capacity);
        this.capacity*=2; //当原数组的总长度被沾满时，把数组的长度扩大2倍
        //开始插入
        for(int i = this.useSize;i>=pos;i--){
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = value;
        this.useSize++;
    }

? 顺序表之判断是否包含某个元素

📝算法思想：

首先进行顺序表的判空处理，因为当数组为空时，无法判断是否包含某个元素
在顺序表中逐次遍历，直到找到某个值，如果想提高算法效率这里可以用二分搜索的方法，这样算法的时间复杂度就变成了O(logN),时间复杂的就会降低

   //判定是否包含某个元素
    public void isContains(int value){
        //判断数组是否为空
        if(isEmpty()){
            System.out.println("数组为空");
            return;
        }
        for(int i = 0;i<this.useSize;i++){
            if(this.elem[i] == value){
                System.out.println("找到了这个数字");
            }else{
                System.out.println("找你到这个数字");
            }
        }
    }

? 顺序表之找出某个元素在顺序表中的对应位置

📝算法思想：

首先进行顺序表的判空处理，因为当数组为空时，无法判断是否包含某个元素
依次遍历顺序表中的每一个值，找到某个元素后返回其下标

    //查找某个元素的对应位置
    public int search(int value){
        if(isEmpty()){
            System.out.println("数组为空");
            return -1;
        }
        for(int i = 0;i<this.useSize;i++){
            if(this.elem[i] == value){
             return i;
            }
        }
        return -1;
    }

? 顺序表之根据下标返回对应位置元素

📝算法思想：

首先进行顺序表的判空处理，因为当数组为空时，无法判断是否包含某个元素
判断pos下标的合法性
返回对应位置元素

    //获得pos位置的元素
    public int getPos(int pos){
        if(isEmpty()){
            System.out.println("数组为空");
            return -1;
        }
        return this.elem[pos];
    }

? 顺序表之修改某个元素

📝算法思想：

判空处理
判断pos下标的合法性
修改原始数据

     //给pos位置的元素设为value
    public void change(int pos,int value){
        if(isEmpty()){
            System.out.println("数组为空");
            return;
        }
        if(pos<0 || pos > this.useSize){
            return;
        }
        this.elem[pos] = value;
    }

? 顺序表之删除数据

📝算法思想：

做判空处理
查找顺序表中是否有将要删除的数据
如果删除位置不合理，抛出异常
取出删除的元素
从删除元素位置开始遍历到最后一个元素位置，分别将他们的位置向前移动一个位置
顺序表有效长度-1

在这里插入图片描述

     //删除第一次出现的关键词key
    public void remove(int tomove){
        //判断数组是否为空
        if(isEmpty()){
            System.out.println("数组为空");
            return;
        }
        //判断数组中是否有这个删除的数
         int index = search(tomove);
        if(index == -1){
            System.out.println("数组中没有这个数");
        }
        //删除
        for(int i = index;i<this.useSize-1;i++){
            this.elem[i] = this.elem[i+1];
        }
        //当要删除顺序表中最后一个数据的时候，不进入循环，数组有效长度-1，就可以删除
        this.useSize--;
    }

? 顺序表之清空数据

📝算法思想：

把顺序表中的每个元素都置为0；
把有效顺序表长度置为0

  //获得顺序表长度
    public int longth(){
        return this.useSize;
    }
    //清空顺序表
    public void clear(){
        for(int i = 0;i<this.useSize;i++){
            this.elem[i] = 0;
        }
        this.useSize = 0;
    }

汇总：
💯TestDemo.java文件：

 public class TestDemo {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
    }
}

💯MyArrayList文件：

 public class MyArrayList {
    public int []elem;
    public int useSize;
    public static int capacity = 10;
    public MyArrayList(){
        this.useSize = 0;
        this.elem = new int[this.capacity];
    }
    //判断数组是否为空
    public boolean isEmpty(){
        if(this.useSize == 0){
            return true;
        }
        return false;
    }
    //打印顺序表
    public void display(){
        //判断数组是否为空
        if(isEmpty()){
            System.out.println("数组为空");
            return;
        }
        for(int i = 0;i<this.useSize;i++){
            System.out.println(this.elem[i]);
        }
        System.out.println();
    }
    //判断数组是否是满的
    public boolean isFull(){
        if(this.useSize == this.capacity){
            return true;
        }else{
            return false;
        }
    }
    //在pos位置新增元素
    public void add(int pos,int value){
        //判断数组是否是满的
        //判断pos是否和法
        if(pos < 0 || pos > this.useSize){
            return ;
        }
        if(isFull()){
            System.out.println("数组已满，开始扩容");
        }
        this.elem = Arrays.copyOf(this.elem,2*this.capacity);
        this.capacity*=2;
        //开始插入
        for(int i = this.useSize;i>=pos;i--){
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = value;
        this.useSize++;
    }
    //判定是否包含某个元素
    public void isContains(int value){
        //判断数组是否为空
        if(isEmpty()){
            System.out.println("数组为空");
            return;
        }
        for(int i = 0;i<this.useSize;i++){
            if(this.elem[i] == value){
                System.out.println("找到了这个数字");
            }else{
                System.out.println("找你到这个数字");
            }
        }
    }
    //查找某个元素的对应位置
    public int search(int value){
        if(isEmpty()){
            System.out.println("数组为空");
            return -1;
        }
        for(int i = 0;i<this.useSize;i++){
            if(this.elem[i] == value){
             return i;
            }
        }
        return -1;
    }

    //获得pos位置的元素
    public int getPos(int pos){
        if(pos<0 || pos > this.useSize){
            return -1;
        }
        if(isEmpty()){
            System.out.println("数组为空");
            return -1;
        }
        return this.elem[pos];
    }
    //给pos位置的元素设为value
    public void change(int pos,int value){
        if(isEmpty()){
            System.out.println("数组为空");
            return;
        }
        if(pos<0 || pos > this.useSize){
            return;
        }
        this.elem[pos] = value;
    }

    //删除第一次出现的关键词key
    public void remove(int tomove){
        //判断数组是否为空
        if(isEmpty()){
            System.out.println("数组为空");
            return;
        }
        //判断数组中是否有这个删除的数
         int index = search(tomove);
        if(index == -1){
            System.out.println("数组中没有这个数");
        }
        //删除
        for(int i = index;i<this.useSize-1;i++){
            this.elem[i] = this.elem[i+1];
        }
        this.useSize--;
    }
    //获得顺序表长度
    public int longth(){
        return this.useSize;
    }
    //清空顺序表
    public void clear(){
        for(int i = 0;i<this.useSize;i++){
            this.elem[i] = 0;
        }
        this.useSize = 0;
    }
}