数据结构（二）线性表

本文主要是介绍数据结构（二）线性表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. 概念

线性结构的定义：

​ 在数据元素的非空有限集中，存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个之外，集合中的每个数据元素均只有一个前驱；除最后一个之外，集合中每个数据元素均只有一个后继。

​ 线性结构包括线性表、堆栈、队列、字符串、数组等等，其中最常用的是线性表。

线性表：

​ 线性表是n个数据元素的有限序列，其元素可以是一个数、一个符号，也可以是多个数据项组成的复合形式，甚至可以是一页书或其他更复杂的信息。

同一个线性表中的数据元素必须属于同一种数据类型。

2. 基本操作

1. 初始化——构造一个空的线性表
2. 插入——在线性表的第 i 个位置之前插入一个新元素
3. 删除——删除线性表中的第 i 个数据元素
4. 查找——找出线性表中满足特定条件的元素的位置
5. 获取——获取线性表中的第 i 个数据元素
6. 修改——修改线性表中第 i 个元素
7. 判空——判断当前线性表是否为空
8. 求长度——求线性表中的数据元素的个数
9. 正序遍历——遍历输出线性表中的元素
10. 销毁——销毁一个已经存在的线性表

3. 线性表的顺序实现

图：

代码

// 线性表的顺序实现
public class SequenceList<T> {
    private int initLength = 10;    // 数组初始化长度
    private T[] arrList;  // 使用数组来实现线性表
    private int length;     // 线性表长度

    public SequenceList() {
        this.arrList = (T[]) new Object[initLength];
        length = 0;
    }

    public SequenceList(int len) {
        if (len < 1) {
            System.out.println("初始长度不合法！");
            System.exit(1);
        }
        this.arrList = (T[]) new Object[len];
        length = 0;
    }

    // 判空
    public boolean isEmpty() {
        return length == 0;
    }

    // 清空线性表
    public void clear() {
        length = 0;
    }

    // 返回线性表长度
    public int getSize() {
        return length;
    }

    // 遍历输出
    public void printArrList() {
        for (int i = 0; i < length; i++) {
            System.out.print(arrList[i] + "\t");
        }
        System.out.println();
    }

    // 在指定的位置插入元素
    public boolean insert(T value, int pos) {
        if (pos < 1 || pos > length + 1) {
            System.out.println("pos值不合法，无法进行插入操作！");
            return false;
        }
        // 如果线性表长度=数组长度-1，就扩充数组长度
        if (length == arrList.length - 1) {
            T[] temp = (T[]) new Object[length * 2];
            for (int i = 0; i < length; i++) {
                temp[i] = arrList[i];
            }
            arrList = temp;
        }
        // 将元素向后移一位
        for (int i = length; i >= pos; i++) {
            arrList[i] = arrList[i - 1];
        }
        arrList[pos - 1] = value;   // 插入值
        length++;
        return true;
    }

    // 删除指定位置的元素
    public T remove(int pos) {
        if (isEmpty()) {
            System.out.println("线性表为空，不能进行删除操作！");
            return null;
        }
        if (pos < 1 || pos > length) {
            System.out.println("pos值不合法，不能进行删除操作！");
            return null;
        }
        T temp = arrList[pos - 1];
        // 将第pos到length之间的元素前移一位
        for (int i = pos; i <= length; i++) {
            arrList[i - 1] = arrList[i];
        }
        length--;
        return temp;
    }

    // 修改指定位置的元素
    public boolean modify(T value, int pos) {
        if (isEmpty()) {
            System.out.println("线性表为空，不能进行修改操作！");
            return false;
        }
        if (pos < 1 || pos > length) {
            System.out.println("pos值不合法，不能进行修改操作！");
            return false;
        }
        arrList[pos - 1] = value;
        return true;
    }

    // 查询指定元素的位置
    public int find(T value) {
        if (isEmpty()) {
            System.out.println("线性表为空，不能进行查询操作！");
            return -1;
        }
        for (int i = 0; i < length; i++) {
            if (arrList[i].equals(value)) {
                return i + 1;
            }
        }
        return -1;
    }

    // 查询指定位置的元素
    public T value(int pos) {
        if (isEmpty()) {
            System.out.println("线性表为空，不能进行修改操作！");
            return null;
        }
        if (pos < 1 || pos > length) {
            System.out.println("pos值不合法，不能进行修改操作！");
            return null;
        }
        return arrList[pos - 1];
    }
}

// 测试
class Test {
    public static void main(String[] args) {
        SequenceList<Integer> sl = new SequenceList<>();
        int[] arr = {12, 14, 16, 18, 20};
        for (int i = 0; i < arr.length; i++) {
            sl.insert(arr[i], i + 1);   // 插入
        }
        sl.printArrList();
        sl.remove(5);   // 删除第5个
        System.out.println("删除第5个：");
        sl.printArrList();
        sl.modify(1000, 3); // 修改第3个值为 1000
        System.out.println("修改第3个值为 1000 ：");
        sl.printArrList();
        System.out.println("查询元素14在第几个：" + sl.find(14));    // 查询
        System.out.println("线性表中第3个的值：" + sl.value(3));
        System.out.println("线性表长度：" + sl.getSize());
        sl.clear();
        sl.printArrList();
    }
}

4. 线性表的链式实现

单链表结构图：

线性表的链式实现代码：

// 节点
class Node<T> {
    T data;
    Node<T> next;
    
    public Node(Node<T> next) {
        this.next = next;
    }
    
    public Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }
}

// 实现类
class LinkList<T> {
    private Node<T> head;	// 头节点
    private int length;		// 线性表长度
    
    public LinkList() {
        length = 0;
        head = new Node<>(null);
    }
    
    // 判空
    public boolean isEmpty() {
        return length == 0;
    }
    
    // 线性表长度
    public int getSize() {
        return length;
    }
    
    // 遍历
    public void printLinkList() {
        Node<T> p = head.next;
        while(p != null) {
            System.out.print(p.data + "\t");
        }
        System.out.println();
    }
    
    // 销毁
    public void clear() {
        length = 0;
        head.next = null;
    }
    
    // 插入
    public boolean insert(T value, int pos) {
        if(pos < 1 || pos > length + 1) {
            System.out.println("插入的位置不合法！");
            return false;
        }
        int num = 1;
        Node<T> p = head, q = head.next;
        while(num < pos) {
            p = q;
            q = q.next;
            num++;
        }
        p.next = new Node<>(value, q);
        length++;
        return true;
    }
    
    // 删除
    public T remove(int pos) {
        if (isEmpty()) {
            System.out.println("线性表为空，不能进行删除操作！");
            return null;
        }
        if (pos < 1 || pos > length) {
            System.out.println("删除的位置不合法！");
            return null;
        }
        int num = 1;
        Node<T> p = head, q = head.next;
        while(num < pos) {
            p = q;
            q = q.next;
            num++;
        }
        p.next = q.next;
        length--;
        return q.data;
    }
    
    // 修改
    public boolean modify(T value, int pos) {
        if (isEmpty()) {
            System.out.println("线性表为空，不能进行修改操作！");
            return false;
        }
        if (pos < 1 || pos > length) {
            System.out.println("修改的位置不合法！");
            return false;
        }
        int num = 1;
        Node<T> p = head.next;
        while(num < pos) {
            p = p.next;
            num++;
        }
        p.data = value;
        return true;
    }
    
    // 查询指定元素的位置
    public int find(T value) {
        int num = 1;
        Node<T> p = head.next;
        while (p != null) {
            if (p.data.equals(value)) {
                return num;
            }
            p = p.next;
            num++;
        }
        return -1;
    }

    // 查询指定位置的元素
    public T getValue(int pos) {
        if (isEmpty()) {
            System.out.println("线性表为空！");
            return null;
        }
        if (pos < 1 || pos > length) {
            System.out.println("指定的位置不合法！");
            return null;
        }
        int num = 1;
        Node<T> p = head.next;
        while (num < pos) {
            p = p.next;
            num++;
        }
        return p.data;
    }

    // 测试
    public static void main(String[] args) {
        LinkList<Integer> linkList = new LinkList<>();
        int[] arr = {12, 14, 16, 18};
        for (int i = 0; i < arr.length; i++) {
            linkList.insert(arr[i], i + 1);
        }
        linkList.printLinkList();
        linkList.modify(100, 2);
        linkList.printLinkList();
        linkList.remove(4);
        linkList.printLinkList();
        System.out.println(linkList.find(100));
        System.out.println(linkList.length);
    }
}

这篇关于数据结构（二）线性表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！