AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构——顺序表

2021-12-27 132
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构——顺序表

目录


顺序表的实现


顺序表的遍历


顺序表的容量可变


顺序表的时间复杂度


java中ArrayList实现


线性表是n个具有相同特性的数据元素的有限序列。常见的线性表有:顺序表、链表、栈、队列等。


线性表的分类：顺序表(数组)和链表


顺序表的实现

顺序表API设计:

image.png

顺序表的代码实现

//顺序表实现
public class SequenceList<T>{
    private T[] array;  //存储元素的数组
    private int N;      //记录当前顺序表的元素个数
    //构造方法
    public SequenceList(int capacity){
        array=(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 array[i];
    }
    //向线性表中添加元素t
    public void insert(T t){
        if(N==array.length){
            throw new RuntimeException("当前表已满");
        }
        array[N++]=t;
    }
    //在i元素处插入元素t
    public void insert(int i,T t){
        if(i==array.length){
            throw new RuntimeException("当前表已满");
        }
        if(i<0||i>N){
            throw new RuntimeException("插入的位置不合法");
        }
        //把i位置空出来, i位置及后面的元素依次向后移动一位
        for(int index=N;index>i;index--){
            array[index]=array[index-1];
        }
        //把t放到i处
        array[i]=t;
        //元素的数量+1
        N++;
    }
    //删除指定位置i处的元素，并返回该元素
    public T remove(int i){
        if(i<0||i>N-1){
            throw new RuntimeException("当前要删除的元素不存在");
        }
        //记录i位置处的元素
        T result=array[i];
        //将后一个元素往前移动
        for(int index=i;index<N-1;index++){
            array[index]=array[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(array[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
}
class SequenceListTest{
    public static void main(String[] args) {
        SequenceList<String> s1=new SequenceList<>(10);
        s1.insert("龍弟");
        s1.insert("龍龍");
        s1.insert("龍哥");
        //测试获取
        String getResult = s1.get(1);
        System.out.println("获取索引1处的结果为:"+getResult);
        //测试删除
        String remove = s1.remove(0);
        System.out.println("删除的元素为:"+remove);
        s1.clear();
        System.out.println("清空后的线性表中的元素个数为:"+s1.length());
    }
}

顺序表的遍历

在java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们的SequenceList也能支持foreach循环，则 需要做如下操作：


1.让SequenceList实现Iterable接口，重写iterator方法；


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

//顺序表代码
public class SequenceList<T> implements Iterable<T>{
    //存储元素的数组
    private T[] array;
    //记录当前顺序表中的元素个数
    private int N;
    //构造方法
    public SequenceList(int capacity){
        array = (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 array[i];
    }
    //向线型表中添加元素t
    public void insert(T t){
        if (N==array.length){
            throw new RuntimeException("当前表已满");
        }
        array[N++] = t;
    }
    //在i元素处插入元素t
    public void insert(int i,T t){
        if (i==array.length){
            throw new RuntimeException("当前表已满");
        }
        if (i<0 || i>N){
            throw new RuntimeException("插入的位置不合法");
        }
        //把i位置空出来，i位置及其后面的元素依次向后移动一位
        for (int index=N;index>i;index--){
            array[index]=array[index-1];
        }
        //把t放到i位置处
        array[i]=t;
        //元素数量+1
        N++;
    }
    //删除指定位置i处的元素，并返回该元素
    public T remove(int i){
        if (i<0 || i>N-1){
            throw new RuntimeException("当前要删除的元素不存在");
        }
        //记录i位置处的元素
        T result = array[i];
        //把i位置后面的元素都向前移动一位
        for (int index=i;index<N-1;index++){
            array[index]=array[index+1];
        }
        //元素数量-1
        N--;
        return result;
    }
    //查找t元素第一次出现的位置
    public int indexOf(T t){
        if(t==null){
            throw new RuntimeException("查找的元素不合法");
        }
        for (int i = 0; i < N; i++) {
            if (array[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
    //打印当前线性表的元素
    public void showEles(){
        for (int i = 0; i < N; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    @Override
    public Iterator iterator() {
        return new SIterator();
    }
    private class SIterator implements Iterator{
        private int cur;
        public SIterator(){
            this.cur=0;
        }
        @Override
        public boolean hasNext() {
            return cur<N;
        }
        @Override
        public T next() {
            return array[cur++];
        }
    }
}
//测试代码
public class Test {
    public static void main(String[] args) throws Exception {
        SequenceList<String> squence = new SequenceList<>(5);
        //测试遍历
        squence.insert(0, "龍龍");
        squence.insert(1, "龍弟");
        squence.insert(2, "龍帝");
        squence.insert(3, "龍哥");
        squence.insert(4, "龍龍");
        for (String s : squence) {
            System.out.println(s);
        }
    }
}

顺序表的容量可变

1.添加元素时：


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


2.移除元素时：


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

//顺序表代码
public class SequenceList<T> implements Iterable<T>{
    //存储元素的数组
    private T[] array;
    //记录当前顺序表中的元素个数
    private int N;
    //构造方法
    public SequenceList(int capacity){
        array = (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 array[i];
    }
    //向线型表中添加元素t
    public void insert(T t){
        if (N==array.length){
            resize(array.length*2);
        }
        array[N++] = t;
    }
    //在i元素处插入元素t
    public void insert(int i,T t){
        if (i<0 || i>N){
            throw new RuntimeException("插入的位置不合法");
        }
        //元素已经放满了数组，需要扩容
        if (N==array.length){
            resize(array.length*2);
        }    
        //把i位置空出来，i位置及其后面的元素依次向后移动一位
        for (int index=N-1;index>i;index--){
            array[index]=array[index-1];
        }
        //把t放到i位置处
        array[i]=t;
        //元素数量+1
        N++;
    }
    //删除指定位置i处的元素，并返回该元素
    public T remove(int i){
        if (i<0 || i>N-1){
            throw new RuntimeException("当前要删除的元素不存在");
        }
        //记录i位置处的元素
        T result = array[i];
        //把i位置后面的元素都向前移动一位
        for (int index=i;index<N-1;index++){
            array[index]=array[index+1];
        }
        //当前元素数量-1
        N--;
        //当元素已经不足数组大小的1/4,则重置数组的大小
        if (N>0 && N<array.length/4){
            resize(array.length/2);
        }
        return result;
    }
    //查找t元素第一次出现的位置
    public int indexOf(T t)
        if(t==null){
            throw new RuntimeException("查找的元素不合法");
        }
        for (int i = 0; i < N; i++) {
            if (array[i].equals(t)){
            return i;
            }
        }
        return -1;
    }
    //打印当前线性表的元素
    public void showEles(){
        for (int i = 0; i < N; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    @Override
    public Iterator iterator() {
        return new SIterator();
    }
    private class SIterator implements Iterator{
        private int cur;
        public SIterator(){
            this.cur=0;
        }
        @Override
        public boolean hasNext() {
            return cur<N;
        }
        @Override
        public T next() {
            return array[cur++];
        }
    }
    //改变容量
    private void resize(int newSize){
        //记录旧数组
        T[] temp = array;
        //创建新数组
        eles = (T[]) new Object[newSize];
        //把旧数组中的元素拷贝到新数组
        for (int i = 0; i < N; i++) {
            array[i] = temp[i];
        }
    }
    public int capacity(){
        return array.length;
    }
}
//测试代码
public class Test {
    public static void main(String[] args) throws Exception {
        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.capacity());
        squence.insert(5,"aa");
        System.out.println(squence.capacity());
        squence.insert(5,"aa");
        squence.insert(5,"aa");
        squence.insert(5,"aa");
        squence.insert(5,"aa");
        squence.insert(5,"aa");
        System.out.println(squence.capacity());
        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.capacity());
    }
}

顺序表的时间复杂度


get(i):无论数据元素量N有多大，只需要一次array[i]就可以获取到对应的元素，时间复杂度为O(1);


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


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


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



java中ArrayList实现

java中ArrayList集合的底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。


1.是否用数组实现；


2.有没有扩容操作；


3.有没有提供遍历方式；


文章标签：
Java
容器
API
存储
关键词：
数据结构顺序表
游客w3cwlqch6lldk
目录
相关文章
是基德吖
|
2月前
|
存储 C语言
【数据结构】顺序表
数据结构中的动态顺序表
是基德吖
35 3
【数据结构】顺序表
秋刀鱼不做梦
|
3月前
|
存储
数据结构—顺序表（如果想知道顺序表的全部基础知识点，那么只看这一篇就足够了！）
数据结构—顺序表（如果想知道顺序表的全部基础知识点，那么只看这一篇就足够了！）
秋刀鱼不做梦
45 1
2的n次方_
|
3天前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表（Arraylist）
Java集合框架主要由接口、实现类及迭代器组成，包括Collection和Map两大类。Collection涵盖List（有序、可重复）、Set（无序、不可重复），Map则由键值对构成。集合通过接口定义基本操作，具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复，Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现，各有适用场景。其中ArrayList实现了动态数组功能，可根据需求自动调整大小。
2的n次方_
26 11
sky_qiyi
|
3月前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表（双向带头循环链表）的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表（双向带头循环链表）的优缺点、CPU高速缓存命中率
sky_qiyi
38 0
小徐在进步
|
11天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
42 5
小徐在进步
|
11天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
13 1
国中之林
|
1月前
|
存储 算法
【数据结构与算法】顺序表
【数据结构与算法】顺序表
国中之林
13 0
【数据结构与算法】顺序表
aliyun6365824167
|
1月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
16 0
aliyun6365824167
|
1月前
|
存储 测试技术
【初阶数据结构篇】顺序表的实现（赋源码）
线性表（linearlist）是n个具有相同特性的数据元素的有限序列。
aliyun6365824167
17 0
睡觉待开机
|
1月前
|
存储 编译器
【数据结构】顺序表(长期维护)
【数据结构】顺序表(长期维护)
睡觉待开机
15 0