数据结构（一）——线性表（线性表的顺序存储实现）_数据结构实验一线性表的顺序存储结构

1、线性表的定义

• 线性表(Linear List)是由同一类型的数据元素构成的有序序列的线性结构

• 线性表中元素的个数称为线性表的长度

• 当一个线性表中没有元素（长度为0）时，称为空表

• 表的起始位置称表头，表的结束位置称表尾

• 线性表是 n (≥0)个元素构成的有序序列( a1, a2, ……,an ) ； ai+1称为 ai的直接后继， ai-1为 ai的直接前驱；直接前驱和直接后继反映了元素之间一对一的邻接逻辑关系

2、线性表的主要操作

• 1、初始化线性表
• 2、判断线性表是否为空
• 3、获取线性表中的元素个数
• 4、返回线性表中第i个元素的值
• 5、在线性表的第i个元素前插入一个值
• 6、删除指定位置元素

3、线性表的顺序储存实现

首先需要明确的是，线性表的顺序存储不是说存的数据是按照升序或者降序来排列的，而是指用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的初始化

 public SeqList(int length){ //定义数组的长度
        //初始化一个数组，存储任意类型
        this.array =(T[])new Object[length];
        //初始化长度
        int N = 0;
    }
1
2
3
4
5
6

判断线性表是否为空

public boolean isEmpty(){
	return N==0;
}
1
2
3

获取线性表中的元素个数

  public int length(){
        return N;
    }
1
2
3

返回线性表中第i个元素的值

public T get(int i){
	return array[i];
}
1
2
3

在线性表的第i个元素前插入一个值

现在突然来了个老婆婆想插队做核酸，你出于尊老爱幼你是不是得让她，于是，她插进来了，你需要往后退一个位置，你后面所有的人都要向后退一个位置，她插入队伍后，队伍的总人数增加1人。

public void insert(int i,T t){
        //先把i下标及其后面所有的下标往后移动一位
        for (int index = N-1; index >i ; index--) {
            array[index] = array[index-1];
        }
        //再把t元素插在原来i下标所处的位置
        array[i] = t;
}
1
2
3
4
5
6
7
8

删除指定位置元素

比如现在有一对人在排队做核酸，现在4号的女朋友现在让他回家做饭，他突然不做了，那么他后面所有的人都要往前走一个位置，这个队伍的总人数就比之前少1。

public T remove(int i){
    //记录i下标的值
    T element = array[i];
    //让i下标之后的元素全都向前移动一位
    for (int index = i;index<N-1;index++){
    array[index] = array[index+1];
    }
    //元素删掉之后，N需要自减
    N--;
    return element;
}
1
2
3
4
5
6
7
8
9
10
11

4、完整代码

/**
 * @author 林中有神君
 * @create 2022-10-23 13:48
 */
public class SeqList<T> {

    private T[] array; //定义一个可变长度的数组
    private int N; //当前元素个数

    public SeqList(int length){ //定义数组的长度
        //初始化一个数组，存储任意类型
        this.array =(T[])new Object[length];
        //初始化长度
        int N = 0;
    }

    //将线性表清空
    public void clear(){
        this.N = 0;
    }

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

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

    //获取指定位置元素
    public T get(int i){
        return array[i];
    }

    //向线性表中插入元素
    public void insert(T t){
        array[N++] = t;
    }

    //线性表的遍历
    public void traverseArray(){
        for (int i = 0; i < N; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println("\n");
    }

    //在i下标前插入一个数
    public void insert(int i,T t){
        //先把i下标及其后面所有的下标往后移动一位
        for (int index = N-1; index >i ; index--) {
            array[index] = array[index-1];
        }
        //再把t元素插在原来i下标所处的位置
        array[i] = t;
    }

    //删除指定下标的元素，并返回该元素
    public T remove(int i){
        //记录i下标的值
        T element = array[i];
        //让i下标之后的元素全都向前移动一位
        for (int index = i;index<N-1;index++){
            array[index] = array[index+1];
        }
        //元素删掉之后，N需要自减
        N--;
        return element;
    }

    //查找指定元素的下标
    public int indexof(T t){
        for (int i = 0; i < N; i++) {
            if(array[i].equals(t)){
                return i;
            }
        }
        return -1;//代表没找到
    }

	//测试
    public static void main(String[] args) {
        //初始化线性表
        SeqList seqList = new SeqList(10);

        //插入数据
        seqList.insert(1);
        seqList.insert(10);
        seqList.insert(12);
        seqList.insert(7);
        seqList.insert(81);
        seqList.insert(24);
        seqList.insert(36);
        seqList.insert(8);
        seqList.insert(9);
        seqList.insert(14);

        //获取指定下标的元素
        Object obj = seqList.get(5);
        System.out.println("该下标元素的值为:"+obj);

        //删除指定下标的元素，并返回该元素
        Object rem = seqList.remove(2);
        System.out.println("删除的元素是:"+rem);

        //线性表遍历
        seqList.traverseArray();

        //在i下标前插入一个数
        seqList.insert(2,8545);
        //线性表遍历
        seqList.traverseArray();


        //获取线性表的长度
        System.out.println("线性表长度:"+seqList.length());

        //判断线性表是否为空
        System.out.println("线性表是否为空:"+seqList.isEmpty());

        //清空表
        seqList.clear();
        System.out.println("清空线性表之后的数组长度:"+seqList.length());

        //判断线性表是否为空
        System.out.println("线性表是否为空:"+seqList.isEmpty());
    }
}
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130