🟡前言

21天挑战赛的第二周，本文主要讲述有关顺序表的内容

活动地址：CSDN21天学习挑战赛

🟡概述

线性表是最简单、最基本的数据结构，其特点如下：

• 第一个数据元素没有前驱，这个数据元素被称为头结点

• 最后一个数据元素没有后继，这个数据元索被称为尾结点

• 除了第一个和最后-个数据元素外，其他数据元素有且仅有一个前驱和一个后继

🟡顺序表的API设计

1️⃣构造方法

SequenceList(int capacity)

2️⃣成员方法

• public void clear()：将一个线性表置为空表

• public boolean isEmpty()：判断当前线性表是否为空表

• public int length()：获取线性表的长度

• public T get(int i)：获取当前索引对应元素

• public void insert(int i, T t)：向线性表中索引值为i处添加元素t

• public void insert(T t)：向线性表中添加元素t

• public T remove(int i)：删除i处元素值，并返回该元素

• public int indexOf(T t) ：查找t元素第一次出现位置

3️⃣成员变量

• private T[] eles：存储元素的数组
• private int N：当前线性表的长度

🟡代码实现

public class SequenceList<T>{
    private T[] eles;
    private  int N;

    //构造方法
    SequenceList(int capacity){
        eles = (T[])new Object[capacity];
        N = 0;
    }

    //将一个线性表置为空表
    public void clear(){
        N = 0;
    }

    //判断当前线性表是否为空表
    public boolean isEmpty(){
        return N == 0;
    }

    //获取线性表的长度
    public int length(){
        return N;
    }

    //获取当前索引对应元素
    public T get(int i){
        if(i < 0 || i >= N){
            throw new RuntimeException("当前元素不存在");
        }
        return eles[i];
    }

    //向线性表中索引值为i处添加元素t
    public void insert(int i, T t){
        if(i == eles.length){
            throw new RuntimeException("当前表已满，无法插入元素");
        }
        if(i < 0 || i > N){
            throw new RuntimeException("插入的位置不合法");
        }

        //将索引值为i及其以后的元素依次向后移动，空出索引值为i的位置
        for(int index = N; index > i; index--){
            eles[index] = eles[index - 1];
        }

        eles[i] = t;//将t元素放在索引值为i的位置上

        N++;//修改顺序表长度
    }

    //向线性表中添加元素t
    public void insert(T t){
        if(N == eles.length){
            throw new RuntimeException("当前表已满，无法添加元素");
        }
        eles[N++] = t;
    }

    //删除i处元素值，并返回该元素
    public T remove(int i){
        //判断要删除的元素是否在顺序表内
        if(i < 0 || i > N){
            throw new RuntimeException("删除元素不存在");
        }
        //记录i处元素值
        T result = eles[i];
        //将元素顺序向后移位
        for(int index = i; index < N-1; index++){
            eles[index] = eles[index+1];
        }
        N--;//改变线性表长度
        return result;//返回当前元素值
    }

    //查找t元素第一次出现位置
    public int indexOf(T t){
        if(t == null){
            throw new RuntimeException("查找的元素不合法");
        }
        for(int i = 0; i < N; i++){
            if(eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

🟡测试代码

public class SequenceListTest {
    public static void main(String[] args) {
        SequenceList<String> s1 = new SequenceList<>(10);
        //测试插入
        s1.insert("张三");
        s1.insert("李四");
        s1.insert("王五");
        //测试获取
        s1.insert(1,"老六");
        String getResult = s1.get(1);
        System.out.println("索引1处的结果为：" + getResult);
        //测试删除
        String removeResult = s1.remove(2);
        System.out.println("删除的元素是：" + removeResult);
        //测试清空
        s1.clear();
        System.out.println("清空后元素个数为：" + s1.length());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

🟡结语

本文只是简单实现了一下顺序表，接下来会进行优化