数据结构知识（java版）- 3. 线性表之顺序表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构知识（java版）- 3. 线性表之顺序表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7152字，纯文字阅读大概需要11分钟。
内容图文
1. 什么是顺序表
1.1 顺序表定义
将表中元素一个接一个的存入一组连续的存储单元中（如图1所示），这种存储结构是顺序存储结构，简称顺序表。顺序表是线性表汇总最通用的存储结构。
1.2 顺序表特性
如图1所示，顺序表最重要的特性是，数据元素在内存中的存储位置是连续的。
1）因此优点也是显而易见的：只需要知道起始位置和下标就可以访问表中任意元素，查询较快，时间复杂度是O(1)；不容易造成空间碎片化。
2）缺点也很明显：对某一个元素的操作，需要影响其所有的后继元素，因此增删改较慢，时间复杂度是O(n)；并且对空间要求高，需要一整块的存储位置。
1.3 顺序表起始下标为什么从0开始
程序猿有个爱好，所有序号都要从0开始，而不是1。这不仅是信仰，背后也是有深层原因的，就拿顺序表来说，从0开始下标可以减少查询操作的运算次数。
假设顺序表List的初始位置是Loc，数据元素大小是len：
1）如果下标是从1开始时，我们取第n个元素时，下标k=n ：查询Loc+len*(k-1) 位置
2）如果下标是从0开始时，我们取第n个元素时，下标k=n-1 ：查询Loc+len*k 位置
由此可见，下标从0开始比从1开始，每一次查询节省了一次减法运算。
2. 顺序表实现（动态顺序表）
这里用java数组实现了一个动态顺序表，使用的逻辑结构是一般线性表（其中【动态】是指表的大小可以随表中数据元素的增减而扩容缩容）。
这里注意下数组与顺序表的异同：
1）数组是编程语言定义的数据类型，在大多数编程语言中都有；顺序表是一种数据存储结构。二者是完全不同的概念。
2）顺序表一般都是用数组来实现的。
2.1 初始化
顺序表在初始化时，需要提前申请一块内存空间，大小是数据元素的倍数。在以下实现中，默认是10个数据元素，也可手动指定。
1 public class MDynamicList<E> {
2 private static final int DEFAULT_CAPACITY = 10; // 默认初始化的容量
3 private E[] data; // 底层是数组
4 private int size; // 记录顺序表已有的数据元素个数
5
6 public MDynamicList(int size) {
7 data = (E[]) new Object[size];
8 this.size = 0;
9 }
10
11 public MDynamicList() {
12 this(DEFAULT_CAPACITY);
13 }
14 }
2.2 基本操作
顺序表的基本操作包括：
2.2.1 增 - 在末尾添加数据元素/插入数据元素
顺序表中数据元素的内存位置是线性固定的，因此新增元素后，需要将新增位置之后的元素往后移动1位。
所以新增操作的时间复杂度是O(n)
第一步：
第二步：
第三步：
2.2.2 删 - 在指定位置删除数据元素
与新增类似，删除需要将该位置之后的数据元素往前移动1位，时间复杂度也是O(n)
2.2.3 改 - 在指定位置更新数据元素
只需先找到目标元素，然后更改即可，时间复杂度是O(1)
2.2.4 查 - 查询指定位置数据元素
按照公式【起始位置+n*数据元素大小】进行查询，时间复杂度是O(1)
2.3 完整代码
2.3.1 完整java代码实现
1 package com.lrspace.learn.ds.list;
2
3 /**
4 * Author: llx
5 * Description: 动态顺序表
6 * Date: 2021/2/15
7 */
8 public class MDynamicList<E> {
9 private static final int DEFAULT_CAPACITY = 10; // 默认初始化的容量
10 private E[] data; // 底层是数组
11 private int size; // 记录顺序表已有的数据元素个数
12
13 public MDynamicList(int size) {
14 data = (E[]) new Object[size];
15 this.size = 0;
16 }
17
18 public MDynamicList() {
19 this(DEFAULT_CAPACITY);
20 }
21
22 /**
23 * 返回顺序表的元素个数
24 *
25 * @return 已有元素个数
26 */
27 public int size() {
28 return this.size;
29 }
30
31 /**
32 * 在末尾添加数据元素
33 *
34 * @param newE 待添加的元素
35 */
36 public void add(E newE) {
37 /* 如果顺序表已满，则需要扩容 */
38 if (size == data.length) {
39 E[] data_ = data;
40 data = (E[]) new Object[size * 2];
41 for (int i = 0; i < size; i++) {
42 data[i] = data_[i];
43 }
44 }
45 data[size] = newE;
46 size++;
47 }
48
49 /**
50 * 插入数据元素
51 *
52 * @param pos 待插入的位置
53 * @param newE 待插入的元素
54 */
55 public void insert(int pos, E newE) {
56 if (pos >= size || pos < 0) {
57 throw new IllegalArgumentException("error: the input pos " + pos + " is exceed the bound.");
58 }
59 /* 如果顺序表已满，则需要扩容 */
60 if (size == data.length) {
61 E[] data_ = data;
62 data = (E[]) new Object[size * 2];
63 for (int i = 0; i < size; i++) {
64 data[i] = data_[i];
65 }
66 }
67 for (int i = size - 1; i >= pos; i--) {
68 data[i + 1] = data[i];
69 }
70 data[pos] = newE;
71 size++;
72 }
73
74 /**
75 * 删除数据元素
76 *
77 * @param pos 待删除元素的位置
78 */
79 public void delete(int pos) {
80 if (pos >= size || pos < 0) {
81 throw new IllegalArgumentException("error: the input pos " + pos + " is exceed the bound.");
82 }
83 for (int i = pos; i < size; i++) {
84 data[i] = data[i + 1];
85 }
86 data[size - 1] = null;
87 size--;
88 }
89
90 /**
91 * 更新数据元素
92 *
93 * @param pos 待更新元素的位置
94 * @param newE 待更新成为的元素
95 */
96 public void update(int pos, E newE) {
97 if (pos >= size || pos < 0) {
98 throw new IllegalArgumentException("error: the input pos " + pos + " is exceed the bound.");
99 }
100 data[pos] = newE;
101 }
102
103 /**
104 * 查询指定位置数据元素
105 *
106 * @param pos 待查询的位置
107 * @return 查询出的元素
108 */
109 public E select(int pos) {
110 if (pos >= size || pos < 0) {
111 throw new IllegalArgumentException("error: the input pos " + pos + " is exceed the bound.");
112 }
113 return data[pos];
114 }
115
116 @Override
117 public String toString() {
118 StringBuilder out = new StringBuilder();
119 out.append("[");
120 for (int i = 0; i < size; i++) {
121 out.append(data[i].toString());
122 out.append(", ");
123 }
124 if (size > 0) {
125 out.delete(out.length() - 2, out.length());
126 }
127 out.append("]");
128 return out.toString();
129 }
130 }
2.3.2 功能验证
package com.lrspace.learn.ds.list;
import org.junit.Test;
public class MDynamicListTest {
@Test
public void size() {
/* 顺序表初始化 */
MDynamicList mDynamicList = new MDynamicList<String>();
System.out.println("顺序表初始化: " + mDynamicList.toString());
/* 在末尾添加数据元素 */
mDynamicList.add("first");
System.out.println("在末尾添加数据元素1: " + mDynamicList.toString());
mDynamicList.add("third");
System.out.println("在末尾添加数据元素3: " + mDynamicList.toString());
/* 插入数据元素 */
mDynamicList.insert(1, "second");
System.out.println("插入数据元素: " + mDynamicList.toString());
/* 删除数据元素 */
mDynamicList.delete(1);
System.out.println("删除数据元素: " + mDynamicList.toString());
/* 更新数据元素 */
mDynamicList.update(1, "second");
System.out.println("更新数据元素: " + mDynamicList.toString());
/* 查询数据元素 */
System.out.println("查询数据元素，位置0: " + mDynamicList.select(0));
System.out.println("查询数据元素，位置1: " + mDynamicList.select(1));
}
}
输出结果：
顺序表初始化: [] 在末尾添加数据元素1: [first] 在末尾添加数据元素3: [first, third] 插入数据元素: [first, second, third] 删除数据元素: [first, third] 更新数据元素: [first, second] 查询数据元素，位置0: first 查询数据元素，位置1: second
参考文档
1. 数据结构教程：http://data.biancheng.net/view/159.html
内容总结
以上是互联网集市为您收集整理的数据结构知识（java版）- 3. 线性表之顺序表全部内容，希望文章能够帮你解决数据结构知识（java版）- 3. 线性表之顺序表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。