线性表的定义与实现

简介: 假设我们有 n 个同类型数据元素的有限序列,记为:L = (a1, a2, a3, ..., ai, ..., an)它就构成了一个线性表。前面说过任何一种逻辑结构都可以使用两种存储结构(顺序存储,链式存储)来实现,使用顺序存储时,会在内存中分配连续的空间来存储数据元素,在程序代码中经常使用数组来实现。但问题来了,很多时候我们无法知道到底预先分配多大的空间合适,如果数据量较大时,内存中不存在那么大的连续空间,所以会导致内存分配失败。这个时候,就可以使用链式存储来实现,具体选用哪种方案根据需求决定。


一、定义



假设我们有 n 个同类型数据元素的有限序列,记为:

L = (a1, a2, a3, ..., ai, ..., an)

它就构成了一个线性表。前面说过任何一种逻辑结构都可以使用两种存储结构(顺序存储,链式存储)来实现,使用顺序存储时,会在内存中分配连续的空间来存储数据元素,在程序代码中经常使用数组来实现。但问题来了,很多时候我们无法知道到底预先分配多大的空间合适,如果数据量较大时,内存中不存在那么大的连续空间,所以会导致内存分配失败。这个时候,就可以使用链式存储来实现,具体选用哪种方案根据需求决定。

链式存储可以使用任何地址的空间存放数据元素,也就是可以空间不连续,它的实现也很简单,就是在存放每个数据结点,里面包含数据元素和一个指向后一个数据元素的引用(或指针)。

微信图片1111.png

使用顺序存储实现的线性表叫做顺序表,使用链式存储实现的线性表叫做链表


二、线性表基本操作分析



前面章节说到,分析数据结构要分析各种结构的基本操作,我们首先定义线性表的一组基本操作,然后编写代码来实现。首先分析线性表的插入、删除、查找、遍历等基本操作,再使用不同的存储结构来实现。


1. 插入


我们已经创建了两种存储结构的线性表,数据元素为 (a1, a2, a3, a4, a5),现在需要在 a2 的的后面插入一个新的数据元素 a6,在使用顺序存储实现时,我们需要将 a2 后面的数据 a3, a4, a5 都要往后移动才能插入。在使用链式存储时,而只需要定位到 a2,然后把 a2.next 赋给新结点 a6.next,再把新结点 a6 赋给 a2.next,通过引用的交换就可以将新数据插入到链表中,由此可看出链表比顺序表的插入效率要高。


微信图片2222.png

2. 删除


如果我们要删除线性表中的一个数据元素,和插入有点类似,比如需要在给定线性表 (a1, a2, a3, a4, a5) 中删除第三个元素 a3,在顺序结构中,需要把 a3 后面的数据 a4, a5 都要往前移动,再把最后一个数据元素清空。在链式结构中,只需要定位到 a3 前一个元素 a2,然后把 a2.next.next 赋值给 a2.next 就可以删掉链表中的 a3,所以,链表的删除操作不需要移动后面的元素,效率比顺序表要高。


微信图片3333.png

3. 查找


如果我们需要在线性表中通过下标查找数据元素,在顺序存储中,因为数据是有序存放在一个内存段中的,所以直接可以使用下标来获取,而在链式存储中,数据是无序的,所以要从头结点开始遍历来找到对应下标的数据元素,由此可知,链表的查找效率低于顺序表。

微信图片4444.png

4. 遍历


当我们要对一个线性表进行遍历时,虽然不管是使用顺序存储还是链式存储,都要对所有元素进行读取,效率看上去不相上下,但不要忘了,顺序表是存在连续空间上的,所以在遍历的时候只需要进行地址偏移就可以读取到所有元素,而链表每读取元素的后一个元素,都要进行一次寻址操作,所以效率也是低于顺序表的。


微信图片5555.png

下面新建一个线性表常规操作的接口,然后我们用顺序结构(数组)和链式结构来实现这个接口,来实现对线性表的操作,读者可以分别对两种存储结构实现的接口的时间复杂度进行分析。

public interface LinearTable<T> {
    /**
     * 初始化线性表数据
     */
    LinearTable<T> init(T... t);
    /**
     * 判断线性表是否为空
     */
    boolean empty();
    /**
     * 清空线性表
     */
    boolean clear();
    /**
     * 返回线性表的大小
     */
    int size();
    /**
     * 插入数据元素
     */
    boolean insert(int pos, T t);
    /**
     * 删除数据元素
     */
    boolean delete(int pos);
    /**
     * 通过位置查找数据元素
     */
    T findElement(int pos);
    /**
     * 通过数据元素查找位置
     */
    int findPosition(T t);
    /**
     * 打印线性表所有数据
     */
    void print();
}

三、线性表基本操作实现



顺序结构使用数组来存储数据,链式结构使用结点来存储数据。


1. 顺序存储实现

public class ArrayLinearTable<T> implements LinearTable<T> {
    private Object[] elementData;
    public ArrayLinearTable(int size) {
        elementData = new Object[size];
    }
    @Override
    public LinearTable<T> init(T... t) {
        elementData = t;
        return this;
    }
    @Override
    public boolean empty() {
        return elementData.length == 0;
    }
    @Override
    public boolean clear() {
        for (int i = 0; i < elementData.length; i++) {
            elementData[i] = null;
        }
        return true;
    }
    @Override
    public int size() {
        return elementData.length;
    }
    @Override
    public boolean insert(int pos, T t) {
        if (pos > elementData.length - 1) {
            throw new ArrayIndexOutOfBoundsException();
        }
        for (int i = pos; i < elementData.length - 1; i++) {
            elementData[i + 1] = elementData[i];
        }
        elementData[pos] = t;
        return true;
    }
    @Override
    public boolean delete(int pos) {
        if (pos > elementData.length - 1) {
            throw new ArrayIndexOutOfBoundsException();
        }
        for (int i = pos; i < elementData.length - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
        elementData[elementData.length - 1] = null;
        return true;
    }
    @SuppressWarnings("unchecked")
    @Override
    public T findElement(int pos) {
        return (T) elementData[pos];
    }
    @Override
    public int findPosition(T t) {
        if (t == null) {
            return -1;
        }
        for (int i = 0; i < elementData.length; i++) {
            if (t.equals(elementData[i])) {
                return i;
            }
        }
        return -1;
    }
    @Override
    public void print() {
        System.out.println(Arrays.toString(elementData));
    }
}


2. 链式存储实现

public class LinkedLinearTable<T> implements LinearTable<T> {
    private Node head;
    private int size = 0;
    private class Node {
        private T t;
        private Node next;
        public Node() {
        }
        public Node(T t, Node next) {
            this.t = t;
            this.next = next;
        }
    }
    @Override
    public LinearTable<T> init(T... t) {
        if (t == null || t.length == 0) {
            return this;
        }
        head = new Node(t[size++], null);
        Node pre = head;
        for (int i = 1; i < t.length; i++) {
            pre.next = new Node(t[i], null);
            pre = pre.next;
            size++;
        }
        return this;
    }
    @Override
    public boolean empty() {
        return head == null;
    }
    @Override
    public boolean clear() {
        head = null;
        return true;
    }
    @Override
    public int size() {
        return size;
    }
    @Override
    public boolean insert(int pos, T t) {
        if (pos > size) {
            throw new OutOfMemoryError();
        }
        Node n = new Node(t, null);
        if (pos == 0) {
            n.next = head;
            head = n;
        } else {
            Node pre = head;
            for (int i = 0; i < pos - 1; i++) {
                pre = pre.next;
            }
            n.next = pre.next;
            pre.next = n;
        }
        size++;
        return true;
    }
    @Override
    public boolean delete(int pos) {
        if (pos > size - 1) {
            throw new OutOfMemoryError();
        }
        if (pos == 0) {
            head = head.next;
        } else {
            Node pre = head;
            for (int i = 0; i < pos - 1; i++) {
                pre = pre.next;
            }
            pre.next = pre.next.next;
        }
        size--;
        return true;
    }
    @Override
    public T findElement(int pos) {
        Node n = head;
        for (int i = 0; i < pos; i++) {
            n = n.next;
        }
        return n.t;
    }
    @Override
    public int findPosition(T t) {
        int i = 0;
        Node n = head;
        while (n != null && !t.equals(n.t)) {
            i++;
            n = n.next;
        }
        return i;
    }
    @Override
    public void print() {
        Node n = head;
        while (n != null) {
            System.out.print(n.t + ",");
            n = n.next;
        }
        System.out.println();
    }
}


四、链式存储扩展



前面讲到的链式结构实现的线性表都是单向链表,我们还可以增加结点的引用来创建更多的链表结构,比如双向链表、单向循环链表和双向循环链表等,只需要掌握一种最简单最基础的单向链表,就可以举一反三搞懂其他各种特殊链表结构。


微信图片6666.png


目录
相关文章
|
7月前
|
存储 C语言
【数据结构】顺序表的定义和运算
【数据结构】顺序表的定义和运算
168 0
|
2月前
广义表,广义表的定义和计算
广义表的定义和概念,包括空表、单元素表、嵌套子表以及如何计算广义表的长度、取表头、取表尾和计算广义表的深度。
69 1
|
2月前
|
存储 C语言 索引
你真的了解线性表中的顺序表了吗?(静态与动态顺序)
你真的了解线性表中的顺序表了吗?(静态与动态顺序)
48 0
|
2月前
|
存储 C语言
数据结构之线性表的初始化及其操作
数据结构之线性表的初始化及其操作
42 0
|
3月前
|
存储 索引
数据结构练习之线性表定义与操作
有限序列:这意味着序列的长度是固定的,不会无限延伸,这与计算机资源的限制相符。在实际应用中,数据结构的大小通常是有限制的,因为内存和存储资源是有限的。
45 4
|
4月前
|
存储
顺序表以及实现(结构篇)
顺序表以及实现(结构篇)
56 11
|
存储
数据结构 2.1 线性表的定义和基本操作
数据结构 2.1 线性表的定义和基本操作
70 0
|
存储
05 顺序表的结构与实现
05 顺序表的结构与实现
39 0
|
存储 索引
04 顺序表的基本形式
04 顺序表的基本形式
30 0
|
人工智能 C语言
线性表的定义和基本操作
线性表的定义和基本操作
146 0