目录

• 顺序表与顺序表的增删改查
• • 线性表
  • • 线性表的定义
  • 顺序表
  • • 顺序表的概念
    • 动态顺序表的增删改查

顺序表与顺序表的增删改查

线性表

线性表的定义

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

顺序表

顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组中完成顺序表的增删改查。
顺序表一般可以分为：静态顺序表和动态顺序表。
静态顺序表：使用给定长度的数组存储。
动态顺序表：使用动态开辟的数组存储。
静态顺序表适用于知道需要存多少数据的场景。静态顺序表的定长数组导致N定打了，空间开多了浪费，开少了不够用。但是动态顺序表更灵活，根据需要动态的分配空间大小。

动态顺序表的增删改查

写一个程序来实现顺序表的增删改查。写完毕后将它封装成一个类，当你在另写程序调用它时，就相当于是面对对象编程。
程序：实现顺序表的增删改查

import java.util.Arrays;
public class SeqList {
    private int[] elem;//存储数据的数组 引用
    private int useSide;//数组的有效位数
    //创建一个数组，让它为下面的顺序表的数据存储做准备
    public SeqList(){
        this.elem = new int[10];
    }

    //----------------------------------在pos位置新增元素
    public void add(int pos,int data){
        //1.判断顺序表有没有存满了
        if(isFull()){
            System.out.println("顺序表满了！需要扩容！");
            //扩容语句，在这些操作里，只有增加数据肯能需要扩容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
            //return;
        }
        //2.判断pos所插入位置的合法性
        if(pos < 0 || pos > this.useSide){
            System.out.println("插入的位置不合法！");
            return;
        }
        //尾插，当插入的位置pos等于顺序表的有效位数useSide时，直接插入
        if(pos == this.useSide){
            this.elem[pos] =data;
            this.useSide++;
            return;
        }
        //中间插和首插，从最后的数据开始，依此向后挪一位，知道pos的位置，插入数据
        for (int i = this.useSide - 1; i >= pos ; i--) {
            this.elem[i + 1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.useSide++;
    }
    //判断当前数组是否已经满了
    public boolean isFull(){
        if(this.useSide == this.elem.length) {
            return true;
        }else
            return false;
    }
    //---------------------------------判定是否包含某个元素
    public boolean contains(int toFind){
        for (int i = 0; i < useSide; i++) {
            if( elem[i] == toFind){
                System.out.println();
                return true;
            }
        }
        return false;
    }
    //---------------------------------查找某个元素对应的位置
    public int search(int toFind){
        for (int i = 0; i < useSide; i++) {
            if (elem[i] == toFind) {
                System.out.println(i);
                return i;
            }
        }
        return -1;
    }
    //---------------------------------获取pos位置的元素
    public int getPos(int pos){
        //当顺序表为空时
        //调用isEmpty()函数
        if(this.isEmpty()){
            return -1;
        }
        //判断pos是否超过顺序表已有数据的范围
        if(pos < 0 || pos >= this.useSide){
            System.out.println("无法获取该位置的元素");
            return -1;
        }
        return this.elem[pos];
    }
    //判断顺序表是否为空
    public boolean isEmpty(){
        //另一种判断方式
//        if(this.useSide == 0){
//            return true;
//        }
//        return false;
        return this.useSide == 0;
    }
    //------------------------------------给pos位置的元素设为 value
    public void setPos(int pos,int value){
        if(this.isEmpty()){
            return;
        }
        //判断是否合法，合法则替换
        if(pos < 0 || pos >= this.useSide){
            System.out.println("该位置不合法");
        }
        this.elem[pos] = value;
    }

    //-------------------------------------删除第一次出现的关键字key
    public void remove(int key){
        //引入一个参数来定义删除的值，调用查找方法其值查找是否存在。
        int index = this.search(key);
        if (index == -1){
            System.out.println("你删除的数不存在！");
            return ;
        }
        for (int i = index; i < this.useSide - 1; i++) {
            this.elem[i] = this.elem[i + 1];
        }
        this.useSide--;
    }
    //-----------------------------------------------获取顺序表的长度
    public int size(){
        System.out.println(this.useSide);
        return this.useSide;
    }
    //-----------------------------------------------清空顺序表
    public void clear(){
        this.useSide = 0;
        System.out.println("顺序表已经清空");
    }
    //------------------------------------------打印顺序表
    public void disPlay(){
        for (int i = 0; i < this.useSide; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
}

写一个程序调用顺序表的增删改查程序，实现面对对象编程。

public class Arraylist{
    public static void main(String[] args){
        //调用SeqList类
        SeqList seqList = new SeqList();
        seqList.add(0,1);//添加数据下标0的数据为1
        seqList.add(1,3);//添加数据下标1的数据为3
        seqList.add(2,5);//添加数据下标2的数据为5
        seqList.add(3,7);//添加数据下标3的数据为7
        seqList.disPlay();//打印顺序表
        System.out.println("-------------------------");
        seqList.add(2,9);//在下标2插入数据9
        seqList.disPlay();//打印顺序表
        System.out.println("-------------------------");
        seqList.search(5);//查找数据5
        System.out.println("-------------------------");
        seqList.setPos(1,100);//修改下标1数据成100
        seqList.disPlay();//打印顺序表
        System.out.println("-------------------------");
        seqList.remove(9);//删除数据9
        seqList.disPlay();//打印顺序表
        System.out.println("-------------------------");
        seqList.size();//查看顺序表有效位数
        System.out.println("-------------------------");
        seqList.clear();//清空顺序表
    }
}

输出结果：

1 3 5 7 //打印添加数据
-------------------------
1 3 9 5 7 //打印插入数据后
-------------------------
3//打印查找数据5所在的下标
-------------------------
1 100 9 5 7 //修改值后打印
-------------------------
2//删除数据的下标位
1 100 5 7 //删除数据后打印
-------------------------
4//打印顺序表现有有效位
-------------------------
顺序表已经清空//清空顺序表