数据结构---顺序表

MoYu-zc 2021-06-24 00:19:23
数据结构 数据 结构 顺序


顺序表

顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元,依次存储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

1.实现顺序表

代码实现

public class SequenceList<T>{
//存储元素的数组
private T[] list;
//记录当前顺序表中的元素个数
private int n;
public SequenceList(int capacity) {
//初始化数组
this.list = (T[]) new Objects[capacity];
//初始化长度
this.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 list[i];
}
//向线型表中添加元素t
public void insert(T t) {
list[n++] = t;
}
//在i元素处插入元素t
public void insert(int i, T t) {
//索引i之后的元素,依次向后移动
for (int index = n; index > i; index--) {
list[index] = list[index - 1];
}
// t 放到i索引处
list[i] = t;
//元素个数+1
n++;
}
//删除指定位置i处的元素,并返回该元素
public T remove(int i) {
//删除的元素
T current = list[i];
//索引i之后的元素,依次前移
for (int index = i; index < n - 1; index++) {
list[index] = list[index + 1];
}
//元素个数-1
n--;
//返回删除元素
return current;
}
//查找t元素第一次出现的位置
public int indexOf(T t) {
for (int i = 0; i < n; i++) {
if (list[i].equals(t)) {
return i;
}
}
return -1;
}
}

代码测试

public class SequenceListTest {
public static void main(String[] args) {
//创建顺序表对象
SequenceList<String> sl = new SequenceList<>(10);
//测试插入
sl.insert("test1");
sl.insert("test2");
sl.insert("test3");
sl.insert(1,"test4");
//测试获取
String getResult = sl.get(1);
System.out.println("获取索引1处的结果为:"+getResult);
//测试删除
String removeResult = sl.remove(0);
System.out.println("删除的元素是:"+removeResult);
//测试清空
sl.clear();
System.out.println("清空后的线性表中的元素个数为:"+sl.length());
}
}

1

2.顺序表遍历

1.继承实现 Iterable 接口,重写 iterator 方法;

2.提供一个内部类 SIterator, 实现 Iterator 接口,重写 hasNext 方法和 next 方法

代码实现

public class SequenceList<T> implements Iterable<T> {
// .....之前的代码
//重写iterator方法
@Override
public Iterator<T> iterator() {
return new SIterator();
}
//内部方法类,实现Iterator接口
private class SIterator implements Iterator {
private int cusor;
//构造方法
public SIterator() {
this.cusor = 0;
}
//下一个是否存在
@Override
public boolean hasNext() {
return cusor < n;
}
//指向下一个值
@Override
public Object next() {
return list[cusor++];
}
}
}

代码测试

public static void main(String[] args) {
//创建顺序表对象
SequenceList<String> sl = new SequenceList<>(10);
//测试插入
sl.insert("test1");
sl.insert("test2");
sl.insert("test3");
sl.insert(1,"test4");
for (String s : sl) {
System.out.println(s);
}
System.out.println("-------------------------------");
//测试获取
String getResult = sl.get(1);
System.out.println("获取索引1处的结果为:"+getResult);
//测试删除
String removeResult = sl.remove(0);
System.out.println("删除的元素是:"+removeResult);
//测试清空
sl.clear();
System.out.println("清空后的线性表中的元素个数为:"+sl.length());
}

2

3.顺序表容量可变

测试

  1. 创建一个容量为 2 的顺序表
  2. 在其中插入 3 个元素
public static void main(String[] args) {
//创建顺序表对象
SequenceList<String> sl = new SequenceList<>(2);
//测试插入
sl.insert("test1");
sl.insert("test2");
sl.insert("test3");
}

3

1.添加元素时:
添加元素时,应该检查当前数组的大小是否能容纳新的元素,如果不能容纳,则需要创建新的容量更大的数组,我们这里创建一个是原数组两倍容量的新数组存储元素。

2.移除元素时:
移除元素时,应该检查当前数组的大小是否太大,这样会造成内存空间的浪费,应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4,则创建一个是原数组容量的1/2的新数组存储元素。

代码实现

修改上述代码

//根据参数newSize,重置eles的大小
public void resize(int newSize) {
//定义临时数组,指向原数组
T[] t = list;
//创建新的数组
list = (T[]) new Object[newSize];
//拷贝数组数据
for (int i = 0; i < n; i++) {
list[i] = t[i];
}
}
//向线型表中添加元素t
public void insert(T t) {
//判断是否扩容
if (n == list.length) {
resize(2 * n);
}
list[n++] = t;
}
//在i元素处插入元素t
public void insert(int i, T t) {
//判断是否扩容
if (n == list.length) {
resize(2 * n);
}
//索引i之后的元素,依次向后移动
for (int index = n; index > i; index--) {
list[index] = list[index - 1];
}
// t 放到i索引处
list[i] = t;
//元素个数+1
n++;
}
//删除指定位置i处的元素,并返回该元素
public T remove(int i) {
//删除的元素
T current = list[i];
//索引i之后的元素,依次前移
for (int index = i; index < n - 1; index++) {
list[index] = list[index + 1];
}
//元素个数-1
n--;
//元素个数小于1/4长度,容量缩小为1/2
if (n < list.length / 4) {
resize(list.length / 2);
}
//返回删除元素
return current;
}

4

4.时间复杂度

  • get(i) : 不难看出,不论数据元素量N有多大,只需要一次查询就可以获取到对应的元素,所以时间复杂度为 O(1) ;

  • insert(int i,T t) : 每一次插入,都需要把 i 位置后面的元素移动一次,随着元素数量N的增大,移动的元素也越多,时间复杂为 O(n) ;

  • remove(int i) : 每一次删除,都需要把 i 位置后面的元素移动一次,随着数据量N的增大,移动的元素也越多,时间复杂度为 O(n) ;

由于顺序表的底层由数组实现,数组的长度是固定的,所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的,在某些需要扩容的结点处,耗时会突增,尤其是元素越多,这个问题越明显

版权声明
本文为[MoYu-zc]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/MoYu-zc/p/14925069.html

  1. Matrix architecture practice of Boshi fund's Internet open platform based on rocketmq
  2. 字节面试,我这样回答Spring中的循环依赖,拿下20k offer!
  3. Byte interview, I answer the circular dependence in spring like this, and get 20K offer!
  4. oracle 11g查看alert日志方法
  5. How to view alert log in Oracle 11g
  6. 手写Spring Config,最终一战,来瞅瞅撒!
  7. Handwritten spring config, the final battle, come and see!
  8. 用纯 JavaScript 撸一个 MVC 框架
  9. Build an MVC framework with pure JavaScript
  10. 使用springBoot实现服务端XML文件的前端界面读写
  11. Using springboot to read and write the front interface of server XML file
  12. 【Javascript + Vue】实现随机生成迷宫图片
  13. [Javascript + Vue] random generation of maze pictures
  14. 大数据入门:Hadoop伪分布式集群环境搭建教程
  15. Introduction to big data: Hadoop pseudo distributed cluster environment building tutorial
  16. 八股文骚套路之Java基础
  17. commons-collections反序列化利用链分析(3)
  18. Java foundation of eight part wensao routine
  19. Analysis of common collections deserialization utilization chain (3)
  20. dubbogo 社区负责人于雨说
  21. Yu Yu, head of dubbogo community, said
  22. dubbogo 社区负责人于雨说
  23. Yu Yu, head of dubbogo community, said
  24. 设计模式 选自《闻缺陷则喜》此书可免费下载
  25. The design pattern is selected from the book "you are happy when you hear defects", which can be downloaded free of charge
  26. xDAI被选为 Swarm 的侧链解决方案,将百倍降低 Swarm 网络Gas费
  27. L2 - 深入理解Arbitrum
  28. Xdai is selected as the side chain solution of swarm, which will reduce the gas cost of swarm network 100 times
  29. L2 - deep understanding of arbitrum
  30. Java全栈方向学习路线
  31. 设计模式学习04(Java实现)——单例模式
  32. Java full stack learning route
  33. Design pattern learning 04 (Java implementation) - singleton pattern
  34. Mybatis学习01:利用mybatis查询数据库
  35. Mybatis learning 01: using mybatis to query database
  36. Java程序员从零开始学Vue(01)- 前端发展史
  37. Java程序员从零开始学Vue(05)- 基础知识快速补充(html、css、js)
  38. Java programmers learn Vue from scratch
  39. Java programmers learn Vue from scratch (05) - quick supplement of basic knowledge (HTML, CSS, JS)
  40. 【Java并发编程实战14】构建自定义同步工具(Building-Custom-Synchronizers)
  41. [Java Concurrent Programming Practice 14] building custom Synchronizers
  42. 【源码分析】- 在SpringBoot中你会使用REST风格处理请求吗?
  43. [source code analysis] - do you use rest style to process requests in springboot?
  44. 框架篇:见识一下linux高性能网络IO+Reactor模型
  45. Framework: see Linux high performance network IO + reactor model
  46. 基础篇:JAVA.Stream函数,优雅的数据流操作
  47. 基础篇:异步编程不会?我教你啊!CompletableFuture(JDK1.8)
  48. Basic part: Java. Stream function, elegant data stream operation
  49. Basic: asynchronous programming won't? I'll teach you! CompletableFuture(JDK1.8)
  50. 技能篇:sed教程-linux命令
  51. 数据库篇:mysql内置函数
  52. Linux 主要的发行系统版本介绍
  53. 网络篇:朋友面试之https认证加密过程
  54. Skills: sed tutorial - Linux command
  55. Database: built in functions of MySQL
  56. Introduction of Linux main distribution system versions
  57. Network: friends interview: the encryption process of HTTPS authentication
  58. [Linux]经典面试题 - 系统管理 - 备份策略
  59. 解决java socket在传输汉字时出现截断导致乱码的问题
  60. [Linux] classic interview questions system management backup strategy