当前位置：首页 > news >正文

三、线性表

news 2025/7/31 22:17:20

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

提示：这里可以添加本文要记录的大概内容：

自学JAVA数据结构笔记，跟学视频为：黑马程序员Java数据结构与java算法全套教程，数据结构+算法教程全资料发布，包含154张java数据结构图_哔哩哔哩_bilibili

提示：以下是本篇文章正文内容，下面案例可供参考

一、线性表的概述

1.概述

线性表时最基本、最简单、也是最常用的一种数据结构，一个线性表时n个具有相同特征的数据元素的有限序列

2.特征

线性表的数据元素之间具有一种“一对一”的逻辑关系

1.第一个元素没有前驱，这个数据元素被称为头结点

2.最后一个元素没有后继，这个元素被称为尾结点

3.除了第一个和最后一个元素外，其他数据元素有且只要一个前驱和一个后继

3.分类

1.顺序存储数据元素的线性表为顺序表

2.链式存储数据元素的线性表为链表

二、顺序表的实现

1.顺序表的API

类名 SequenceList

构造方法 SequenceList(int capacity)：创建容量为capacity的SequenceList对象

成员方法 1.public void clear()：空置线性表

2.publicboolean isEmpty()：判断线性表是否为空，是返回true，否返回false 3.public int length():获取线性表中元素的个数

4.public T get(int i):读取并返回线性表中的第i个元素的值

5.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。

6.public void insert(T t):向线性表中添加一个元素t

7.public T remove(int i):删除并返回线性表中第i个数据元素。

8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。

成员变量 1.private T[] eles：存储元素的数组

2.private int N:当前线性表的长度

2.顺序表实现

顺序表类：

package List;import java.util.Iterator;
import java.util.Spliterator;
import java.util.function.Consumer;public class SequenceList <T> implements Iterable<T>{private T[] eles;private  int N;//构造方法public SequenceList(int Capacity){//初始化数组this.eles = (T[]) new Object[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){//安全性检测if (i < 0 || i >= N){throw new RuntimeException("当前元素不存在！");}return eles[i];}//向线性表中添加元素tpublic void insert(T t){//如果数组已经满了，则需要给数组扩容if(N == eles.length){resize(2 * eles.length);}eles[N ++] = t;}//给数组扩容private void resize(int newsize){//创建临时数组，将eles的数据放入临时数组T[] temp = eles;//对数组进行初始化，建立一个容量为newsize的数组eles = (T[]) new Object[newsize];//将temp内的数据重新放入elesif (N >= 0){System.arraycopy(temp, 0, eles, 0, N);}}//在i处加入元素tpublic void insert(int i,T t){//安全性检测if (i < 0 || i > N){throw new RuntimeException("插入的位置不合法");}//先判断数组是否已满//如果数组满了，给数组扩容if(N == eles.length){resize(2 * eles.length);}//将i后面数据后移for(int index = N - 1;index > i;index --){eles[index] = eles[index - 1];}//接着向i位置插入数据eles[i] = t;N ++;}//删除i处位置元素public T remove(int i){//安全性检测if (i < 0 || i > N - 1){throw new RuntimeException("当前要删除的元素不存在");}//临时值存储i位置元素T temp = eles[i];//i位置后数组元素前移for(int index = i;index < N - 1;index ++){eles[index] = eles[index + 1];}N --;//为了避免空间浪费if(N < eles.length / 4){resize(eles.length / 2);}return temp;}//查找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 void showEles() {for (int i = 0; i < N; i++) {System.out.print(eles[i] + " ");}System.out.println();}@Overridepublic Iterator<T> iterator() {return new Siterator();}//内部类重写迭代器private class Siterator implements Iterator{private int curr;public Siterator(){this.curr = 0;}@Overridepublic boolean hasNext() {return curr < N;}@Overridepublic Object next() {return eles[curr ++];}}}

测试类：

package List;public class SequenceListTest {public static void main(String[] args) {SequenceList<String> squence = new SequenceList<>(5);//测试遍历squence.insert(0, "姚明");squence.insert(1, "科比");squence.insert(2, "麦迪");squence.insert(3, "艾佛森");squence.insert(4, "卡特");System.out.println(squence.length());squence.insert(5,"aa");System.out.println(squence.length());squence.insert(5,"aa");squence.insert(5,"aa");squence.insert(5,"aa");squence.insert(5,"aa");squence.insert(5,"aa");System.out.println(squence.length());squence.remove(1);squence.remove(1);squence.remove(1);squence.remove(1);squence.remove(1);squence.remove(1);squence.remove(1);System.out.println(squence.length());}}