🟡前言
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; } }
🟡测试代码
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()); } }
🟡结语
本文只是简单实现了一下顺序表，接下来会进行优化
