Java · 线性表 · 顺序表 · 顺序表接口实现

一、线性表

线性表是 n 个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

---

二、顺序表

概念以及结构

顺序表是用一段物理地址连续的存储单元，依次存储数据元素的线性结构，一般情况下采用数组存储。
在数组上完成数据的增删改查。

顺序表一般可以分为：

• 静态顺序表：使用定长的数组存储。
• 动态顺序表：使用动态开辟的数组存储。

静态顺序表适合确定知道需要存储多少数据的场景.
静态顺序表的定长数组导致 N 定大了，浪费空间；定小了，不够用。

相比之下动态顺序表更加灵活，根据需要动态的分配空间大小.

动态顺序表的接口

我们来实现一个动态顺序表，以下是需要支持的接口.

public class SeqList {
	// 打印顺序表
	public void display() {  }
	
	// 在 pos 位置新增元素
	public void add(int pos, int data) { }
	
	// 判定是否包含某个元素
	public boolean contains(int toFind) { return true; }
	
	// 查找某个元素对应的位置
	public int search(int toFind) { return -1; }
	
	// 获取 pos 位置的元素
	public int getPos(int pos) { return -1; }
	
	// 给 pos 位置的元素设为 value
	public void setPos(int pos, int value) {  }
	
	//删除第一次出现的关键字key
	public void remove(int toRemove) {  }
	
	// 获取顺序表长度
	public int size() { return 0; }
	
	// 清空顺序表
	public void clear() {  }
}
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

顺序表的问题以及思考

1. 顺序表中间 / 头部的插入删除，时间复杂度为O(N).
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小消耗.
3. 增容一般是呈 2 倍增长，势必会造成空间浪费。例如当前容量为 100，满了之后增容到 200，我们再插入 5 个数据，就会浪费 95 个数据空间.

接口实现

public class MyArrayList {
    //顺序表名
    public int[] elem;
    //有效元素
    public int usedSize;
    //顺序表容量
    public static int capacity = 10;

    
    //构造方法创建数据
    public MyArrayList() {
        this.elem = new int[capacity];
    }
    
    
    //判断顺序表是否满
    public boolean isFull() {
//        if (this.usedSize == capacity) {
//            return true;
//        }
        return this.usedSize == capacity;
    }
    
    
    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        //判断pos位置的合法性
        if (pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法");
            return;
        }
        //判断是否需要扩容
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2*capacity);
            capacity *= 2;  //更新最大容量
        }
        //开始添加元素，其余元素后移
        for (int i = this.usedSize-1; i >= pos; i--) {
            this.elem[i+1] = this.elem[i];
        }
        //添加元素
        this.elem[pos] = data;
        //有效元素++
        this.usedSize++;
    }
    
    
    // 打印顺序表
    public void display() {
        if (this.usedSize <= 0) {
            System.out.println("顺序表为空");
            return;
        }
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
    
    
    //判断顺序表是否空
    public boolean isEmpty() {
//        if (this.usedSize <= 0) {
//            return true;
//        }
//        return false;
        //直接看有效元素
        return this.usedSize == 0;
    }
    
    
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        //判断是否空表
        if (isEmpty()) {
            System.out.println("顺序表为空~");
            return false;
        }
        //开始对比顺序表元素
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return true;
            }
        }
        //没找到
        return false;
    }

        
    // 查找某个元素对应的位置
    public int search(int toFind) {
        if (isEmpty()) {
            System.out.println("表空~");
            return -1;
        }
        //直接找
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return i;
            }
        }
        //没找到
        return -1;
    }
    
    
    // 获取 pos 位置的元素
    public int getPos(int pos) {
        //判断pos位置是否合法
        if (pos < 0 || pos >= this.usedSize) {
            System.out.println("pos有问题");
            return -1;
        }
        if (isEmpty()) {
            System.out.println("空表");
            return -1;
        }
        return this.elem[pos];
    }
    
    
    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }
    
    
    // 给 pos 位置的元素设为 value
    public void setPos(int pos, int value) {
        if (pos < 0 || pos >= this.usedSize) {
            System.out.println("pos有问题");
            return;
        }
        if (isEmpty()) {
            System.out.println("表为空");
            return;
        }
        this.elem[pos] = value;
    }
    
    
    //删除第一次出现的关键字key
    public void remove(int key) {
        if (this.usedSize == 0) {
            System.out.println("表为空");
            return;
        }
        //找key
        for (int i = 0; i < this.usedSize; i++) {
            //找到了，让后面的元素覆盖它
            if (this.elem[i] == key) {
                while (i < this.usedSize) {
                    this.elem[i] = this.elem[i+1];
                    i++;
                }
                System.out.println("删除成功");
                this.usedSize--;
                return;
            }
        }
        System.out.println("没有key值");
        return;
    }
    
    
    // 清空顺序表
    public void clear() {
        //循环给表中元素赋值初始值即可
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = 0;
        }
        //最后重置有效数据变量
        this.usedSize = 0;
    }
}
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175