欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之线性表的链式存储(Java表示)

程序员文章站 2022-06-03 18:31:45
...

目录

线性表的链式存储

一些基本概念

主要操作实现

1. 求表长

2. 查找

3. 插入

4. 删除

5. 小结

Java代码实现


 

线性表的链式存储

一些基本概念

数据结构之线性表的链式存储(Java表示)

  • 数据域:在链表中用来存放数值。
  • 链接域:在链表中用来存放指针的,用一带箭头的线段表示。

主要操作实现

1. 求表长

数据结构之线性表的链式存储(Java表示)

  • 时间复杂度:O(n)
  • 求表长的思路
    顺序表由于存储是连续的,求表长就是Last+1。但是链式存储表中,存储不是连续的,所以需要将链表从头到尾遍历一遍:设定一个移动指针p和计数器cnt,初始化后,p从表的第一个节点开始向后逐步向后移,同时计数器cnt加1,当后面不再有节点时,cnt的值就是节点个数也就是表长。

2. 查找

数据结构之线性表的链式存储(Java表示)

  • (1)按序号查找:FindKth
    • 时间复杂度:O(n)
    • 按序号查找的思路
      顺序表的按序号查找要得到第K个元素的值就是list[K-1]。但是链式存储表中需要:从链表的第一个元素节点开始,判断当前节点是否是第K个,如果是则返回该节点的值,否则继续下一个,直到表结束为止,如果没有第K个节点则返回错误信息。
  • (2)按值查找:Find
    • 时间复杂度:O(n)
    • 按值查找的思路
      按值查找也是从头到尾的遍历,直到找到为止:从链表的第一个元素节点开始,判断其当前节点的值是否等于要查找的值X,如果是则返回该节点的位置否则继续下一个直到表结束为止。找不到则返回错误信息。

3. 插入

数据结构之线性表的链式存储(Java表示)

数据结构之线性表的链式存储(Java表示)

  • 平均查找次数:n/2
  • 时间复杂度:O(n)
  • 插入的说明
    线性表的插入是在指定位序i(1<=i<=n+1)前插入一个新元素X。当前插入位序为1时,代表插入到链表的头;i为n+1时表示插入到链表的最后
  • 插入的思路
    基本思路是如果i不为1则找到位序为i-1的节点pre;若存在则申请一个新节点并在数据域上填上相应值X,如果将新节点插入到节点pre后,返回结果链表;如果不存在则返回错误信息。

4. 删除

数据结构之线性表的链式存储(Java表示)

数据结构之线性表的链式存储(Java表示)

  • 平均查找次数:n/2
  • 时间复杂度:O(n)
  • 删除的思路
    在单向链表中删除指定位序i的元素,首先要找到被删除节点的前一个元素,然后再删除节点并释放空间。

5. 小结

在单链表上插入、删除一个节点,必须知道其前驱节点。

单链表不具有按序号随机访问的特点,只能从头指针开始一个个顺序进行。

 

Java代码实现

Node.java

public class Node {
    private Object data;
    private Node next;

    public Node(){
        super();
    }

    public Node(Object data,Node next){
        super();
        this.data=data;
        this.next=next;
    }

    public Node(Object data){
        super();
        this.data=data;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

MyLinearList.java

/**
 * 线性表链式存储常用操作集实现
 *
 * @author lck100
 */
public class MyLinearList {

    private MyLinearList() {
        super();
    }

    /**
     * 获取表长
     *
     * @return 返回链表长度
     */
    private int length(Node sourceNode) {
        // node指向表的第一个结点
        Node node = sourceNode;
        // 计数器,用来统计链表结点个数,初始为0个
        int j = 0;
        // 结点为null时表示没有下一个结点了,跳出循环,返回链表长度
        while (node != null) {
            // 当前node指向第j个结点
            node = node.getNext();
            j++;
        }
        return j;
    }

    /**
     * 按序号查找值
     *
     * @param i          查找的序号
     * @param sourceNode 当前要操作的链表
     * @return 如果查找成功返回该结点,否则返回null
     */
    private Node findKth(int i, Node sourceNode) {
        Node node = sourceNode;
        // 计数器,统计当前是第几个结点
        int j = 1;
        // 循环的条件是结点不能为null并且j必须小于i
        while (node != null && j < i) {
            node = node.getNext();
            j++;
        }
        // 判断计数器的值是否等于要查询的位序,如果是返回结点否则返回null
        if (j == i) {
            return node;
        } else {
            return null;
        }
    }

    /**
     * 按值查找
     *
     * @param obj        要查找的值
     * @param sourceNode 要操作的链表
     * @return 如果查找成功返回该值所在结点
     */
    private Node find(Object obj, Node sourceNode) {
        Node node = sourceNode;
        // 循环判断结点的值是否与要查询的值相等,相等则返回当前结点
        while (node != null && node.getData() != obj) {
            node = node.getNext();
        }
        return node;
    }

    /**
     * 在指定位置插入
     *
     * @param i          要插入的位序
     * @param data       要插入的数据
     * @param sourceNode 要操作的链表
     * @return 返回插入成功的链表
     * @throws Exception 抛出异常
     */
    private Node insert(int i, Object data, Node sourceNode) throws Exception {
        // p指的是要插入的位置之前的结点,s指的是要新插入的结点
        Node p, s;
        // 如果新结点要插在表头
        if (i == 1) {
            // 申请新结点
            s = new Node();
            // 设置新结点的数据
            s.setData(data);
            // 设置新节点的指针(下一个结点)的位置
            s.setNext(sourceNode);
            return s;
        }
        // 查找第(i-1)个结点,即查找要插入的位置的前一个结点
        p = findKth(i - 1, sourceNode);
        // 判断查询到的结点是否为null
        if (p == null) {
            throw new Exception("参数i错误!");
        } else {
            // 申请新结点
            s = new Node();
            // 设置新结点的数据
            s.setData(data);
            // 设置新结点的指针(下一个结点的位置)为查询到的结点的指针
            s.setNext(p.getNext());
            // 将要插入位置的前一个结点的指针指向当前要添加的新结点
            p.setNext(s);
            return sourceNode;
        }
    }

    /**
     * 删除指定位置的数据
     *
     * @param i          指定的位序
     * @param sourceNode 链表
     * @return 返回删除成功的链表
     * @throws Exception 抛出异常
     */
    private Node delete(int i, Node sourceNode) throws Exception {
        // p指的是要删除的结点之前的结点,s指的是要删除的结点
        Node p, s;
        // 如果要删除第一个结点
        if (i == 1) {
            s = sourceNode;
            if (sourceNode != null) {
                // 从链表中删除,即指针指向了第一个结点的下一个结点
                sourceNode = sourceNode.getNext();
            } else {
                return null;
            }
            return sourceNode;
        }
        // 查询要删除结点的上一个节点
        p = findKth(i - 1, sourceNode);
        if (p == null) {
            throw new Exception("第" + (i - 1) + "个结点不存在!");
        } else if (p.getNext() == null) {
            throw new Exception("第" + i + "个结点不存在!");
        } else {
            // 将s指向第i个结点,即获取要删除的节点(通过上一个节点的指针获取要删除的节点的位置)
            s = p.getNext();
            // 从链表中删除
            p.setNext(s.getNext());
            return sourceNode;
        }
    }

    /**
     * 打印该链表的所有结点数据
     *
     * @param node 链表
     */
    private void print(Node node) {
        while (node != null) {
            System.out.print(node.getData() + "\t");
            node = node.getNext();
        }
        System.out.println();
    }

    public static void main(String[] args) throws Exception {
        MyLinearList linearList = new MyLinearList();
        // 作头结点使用
        Node head = new Node("唐僧", null);
        // 插入一个结点,位序是1
        Node insert1 = linearList.insert(1, "孙悟空", head);
        linearList.print(insert1);
        // 插入一个结点,位序非1
        Node insert2 = linearList.insert(2, "猪八戒", insert1);
        linearList.print(insert2);
        // 打印链表的长度
        System.out.println(linearList.length(insert2));
        // 按序号查找
        Node kth = linearList.findKth(2, insert2);
        System.out.println(kth.getData());
        // 按值查找
        Node find = linearList.find("唐僧", insert2);
        System.out.println(find.getData());
        // 删除指定位序的结点,比如删除第二个结点
        Node delete = linearList.delete(2, insert2);
        linearList.print(delete);
    }
}

控制台打印:

数据结构之线性表的链式存储(Java表示)

把上面的代码整理了一下,代码如下:

/**
 * 线性表链式存储常用操作集实现
 *
 * @author lck100
 */
public class MyLinearList2 {
    private Node source = new Node();
    private int size = 0;// 计数器,统计链表中结点的个数

    private MyLinearList2() {
        super();
    }

    /**
     * 获取表长
     *
     * @return 返回链表长度
     */
    private int length() {
        return size;
    }

    /**
     * 按序号查找值
     *
     * @param i 查找的序号
     * @return 如果查找成功返回该结点,否则返回null
     */
    private Node findKth(int i) {
        Node node = source;
        // 计数器,统计当前是第几个结点
        int j = 1;
        // 循环的条件是结点不能为null并且j必须小于i
        while (node != null && j < i) {
            node = node.getNext();
            j++;
        }
        // 判断计数器的值是否等于要查询的位序,如果是返回结点否则返回null
        if (j == i) {
            return node;
        } else {
            return null;
        }
    }

    /**
     * 按值查找
     *
     * @param obj 要查找的值
     * @return 如果查找成功返回该值所在结点
     */
    private Node find(Object obj) {
        Node node = source;
        // 循环判断结点的值是否与要查询的值相等,相等则返回当前结点
        while (node != null && node.getData() != obj) {
            node = node.getNext();
        }
        return node;
    }

    /**
     * 在指定位置插入
     *
     * @param i    要插入的位序
     * @param data 要插入的数据
     * @return 返回插入成功的链表
     * @throws Exception 抛出异常
     */
    private Node insert(int i, Object data) throws Exception {
        // p指的是要插入的位置之前的结点,s指的是要新插入的结点
        Node p, s;
        // 如果新结点要插在表头
        if (i == 1) {
            // 申请新结点
            s = new Node();
            // 设置新结点的数据
            s.setData(data);
            // 处理第一个结点问题
            if (size == 0) {
                // 设置新节点的指针(下一个结点)的位置
                s.setNext(null);
            } else {
                // 设置新节点的指针(下一个结点)的位置
                s.setNext(source);
            }
            source = s;
            size++;
            return s;
        }
        // 查找第(i-1)个结点,即查找要插入的位置的前一个结点
        p = findKth(i - 1);
        // 判断查询到的结点是否为null
        if (p == null) {
            throw new Exception("参数i错误!");
        } else {
            // 申请新结点
            s = new Node();
            // 设置新结点的数据
            s.setData(data);
            // 设置新结点的指针(下一个结点的位置)为查询到的结点的指针
            s.setNext(p.getNext());
            // 将要插入位置的前一个结点的指针指向当前要添加的新结点
            p.setNext(s);
            size++;
            return source;
        }
    }

    /**
     * 删除指定位置的数据
     *
     * @param i 指定的位序
     * @return 返回删除成功的链表
     * @throws Exception 抛出异常
     */
    private Node delete(int i) throws Exception {
        // p指的是要删除的结点之前的结点,s指的是要删除的结点
        Node p, s;
        // 如果要删除第一个结点
        if (i == 1) {
            s = source;
            if (source != null) {
                // 从链表中删除,即指针指向了第一个结点的下一个结点
                size--;
                source = source.getNext();
            } else {
                return null;
            }
            return source;
        }
        // 查询要删除结点的上一个节点
        p = findKth(i - 1);
        if (p == null) {
            throw new Exception("第" + (i - 1) + "个结点不存在!");
        } else if (p.getNext() == null) {
            throw new Exception("第" + i + "个结点不存在!");
        } else {
            // 将s指向第i个结点,即获取要删除的节点(通过上一个节点的指针获取要删除的节点的位置)
            s = p.getNext();
            // 从链表中删除
            p.setNext(s.getNext());
            size--;
            return source;
        }
    }

    /**
     * 打印该链表的所有结点数据
     */
    private void print() {
        Node node = source;
        while (node != null) {
            System.out.print(node.getData() + "\t");
            node = node.getNext();
        }
        System.out.println();
    }

    public static void main(String[] args) throws Exception {
        MyLinearList2 linearList = new MyLinearList2();
        linearList.insert(1,"唐僧");
        linearList.print();
        System.out.println(linearList.length());
        linearList.insert(2,"孙悟空");
        linearList.insert(3,"猪八戒");
        linearList.print();
        System.out.println(linearList.length());
        linearList.insert(1,"沙僧");
        linearList.insert(2,"小白龙");
        linearList.print();
        linearList.delete(2);
        linearList.print();
        linearList.delete(4);
        linearList.print();
        Node node = linearList.find("孙悟空");
        System.out.println(node.getData());
        Node kth = linearList.findKth(2);
        System.out.println(kth.getData());
    }
}

控制台打印如下:

数据结构之线性表的链式存储(Java表示)

相关标签: 数据结构 Java