首页 > 其他分享 >数据结构第3节： 抽象数据类型

数据结构第3节： 抽象数据类型

时间：2024-07-03 13:01:17浏览次数：21  
标签：ADT head element 链表 next 抽象数据类型 数据结构 public

第3节：基础概念 - 抽象数据类型（ADT）

抽象数据类型（ADT）是一种逻辑上的数学模型，以及定义在此数学模型上的一组操作。ADT通常隐藏了底层实现的细节，只暴露出一个可以被外界访问和操作的接口。在Java中，ADT可以通过接口（interface）来定义，并通过类（class）来实现。

2.3.1 抽象数据类型的定义

ADT定义了数据的逻辑结构和操作，但不涉及数据的具体表示和实现。例如，一个栈的ADT可以定义为具有push、pop、peek和isEmpty等操作。

2.3.2 Java中的ADT实现

在Java中，可以使用接口来定义ADT，然后通过类来实现这些接口。

定义一个ADT接口
public interface StackADT<T> {
    void push(T element);  // 入栈操作
    T pop();               // 出栈操作
    T peek();              // 查看栈顶元素
    boolean isEmpty();     // 检查栈是否为空
}
实现ADT接口
public class ArrayStack<T> implements StackADT<T> {
    private T[] elements;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public ArrayStack() {
        elements = (T[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    @Override
    public void push(T element) {
        ensureCapacity();
        elements[size++] = element;
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        return elements[--size];
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        return elements[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private void ensureCapacity() {
        if (size == elements.length) {
            T[] newElements = (T[]) new Object[elements.length * 2];
            System.arraycopy(elements, 0, newElements, 0, size);
            elements = newElements;
        }
    }
}

2.3.3 ADT的优势

  • 封装性：ADT隐藏了数据的具体实现，只暴露操作接口，提高了代码的安全性和易用性。
  • 抽象性：ADT提供了一个高层次的操作集合，使得用户可以不必关心数据的具体存储方式。
  • 通用性：ADT的实现可以针对不同的数据存储需求进行定制，但对外提供的接口保持一致。

2.3.4 使用ADT

使用ADT可以简化编程，提高代码的可读性和可维护性。用户只需要知道如何使用ADT提供的操作，而不需要了解其内部实现。

public class Main {
    public static void main(String[] args) {
        StackADT<Integer> stack = new ArrayStack<>();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.peek());    // 输出 2
        System.out.println(stack.pop());     // 输出 2
        System.out.println(stack.isEmpty()); // 输出 false
    }
}

通过上述Java源码，我们可以看到ADT如何在Java中被定义和实现。定义一个接口作为ADT，然后通过不同的类来实现这个接口，可以提供多种数据结构的实现，同时保持对外的接口一致。这种方式使得代码更加模块化，易于理解和使用。

继续探讨抽象数据类型（ADT）的概念，我们可以再通过Java代码来展示另一个常见的ADT：队列（Queue）。

2.3.5 队列（Queue）ADT

队列是一种先进先出（FIFO）的数据结构，其ADT定义通常包括以下操作：

  • enqueue(T element): 在队列末尾添加一个元素。
  • dequeue(): 移除并返回队列头部的元素。
  • peek(): 返回队列头部的元素但不移除它。
  • isEmpty(): 检查队列是否为空。
定义队列的ADT接口
public interface QueueADT<T> {
    void enqueue(T element);  // 入队操作
    T dequeue();              // 出队操作
    T peek();                 // 查看队首元素
    boolean isEmpty();        // 检查队列是否为空
}
实现队列的ADT接口

我们可以利用链表来实现队列，以避免在数组实现中可能需要的昂贵的元素移动操作。

public class LinkedListQueue<T> implements QueueADT<T> {
    private Node<T> head; // 队首
    private Node<T> tail; // 队尾

    private static class Node<T> {
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    @Override
    public void enqueue(T element) {
        Node<T> newNode = new Node<>(element);
        if (tail != null) {
            tail.next = newNode;
        } else {
            head = newNode;
        }
        tail = newNode;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        T element = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return element;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return head.data;
    }

    @Override
    public boolean isEmpty() {
        return head == null;
    }
}

2.3.6 使用队列ADT

使用队列ADT可以简化代码，使得队列操作更加直观和安全。

public class Main {
    public static void main(String[] args) {
        QueueADT<Integer> queue = new LinkedListQueue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        System.out.println(queue.peek());    // 输出 1
        System.out.println(queue.dequeue()); // 输出 1
        System.out.println(queue.isEmpty()); // 输出 false
    }
}

2.3.7 ADT的进一步讨论

ADT不仅定义了数据的操作，还提供了一种思考问题的方式，使得程序员可以专注于如何使用数据，而不是如何实现数据结构。这种抽象层次上的分离是面向对象编程的核心概念之一。

通过这些案例，我们可以看到ADT在Java中的实现方式，以及它们如何帮助我们以一种抽象和通用的方式来处理数据结构。这些实现展示了ADT的封装性、抽象性和通用性的优势，同时也说明了为什么学习和使用ADT对于任何希望编写高效、可维护代码的程序员来说都是非常重要的。

让我们继续探讨抽象数据类型（ADT）的概念，并通过Java代码来展示另一个常见的ADT：链表（LinkedList）。

2.3.8 链表（LinkedList）ADT

链表是一种线性数据结构，其中元素以节点的形式存在，每个节点包含数据部分和指向下一个节点的链接。

定义链表的ADT接口
public interface LinkedListADT<T> {
    void addFirst(T element);  // 在链表头部添加元素
    void addLast(T element);   // 在链表尾部添加元素
    T removeFirst();           // 移除并返回链表头部的元素
    T removeLast();            // 移除并返回链表尾部的元素
    T getFirst();              // 获取链表头部的元素
    T getLast();               // 获取链表尾部的元素
    boolean isEmpty();         // 检查链表是否为空
    int size();                // 返回链表中的元素数量
}
实现链表的ADT接口
public class SinglyLinkedList<T> implements LinkedListADT<T> {
    private Node<T> head; // 链表的头节点
    private int size;     // 链表的元素数量

    private static class Node<T> {
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    @Override
    public void addFirst(T element) {
        Node<T> newNode = new Node<>(element);
        newNode.next = head;
        head = newNode;
        size++;
    }

    @Override
    public void addLast(T element) {
        Node<T> newNode = new Node<>(element);
        if (head == null) {
            head = newNode;
        } else {
            Node<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    @Override
    public T removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("Linked list is empty");
        }
        T element = head.data;
        head = head.next;
        size--;
        return element;
    }

    @Override
    public T removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("Linked list is empty");
        }
        if (head.next == null) {
            T element = head.data;
            head = null;
            size--;
            return element;
        } else {
            Node<T> current = head;
            while (current.next.next != null) {
                current = current.next;
            }
            T element = current.next.data;
            current.next = null;
            size--;
            return element;
        }
    }

    @Override
    public T getFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("Linked list is empty");
        }
        return head.data;
    }

    @Override
    public T getLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("Linked list is empty");
        }
        Node<T> current = head;
        while (current.next != null) {
            current = current.next;
        }
        return current.data;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }
}

2.3.9 使用链表ADT

使用链表ADT可以简化链表操作，使得链表的使用更加直观和安全。

public class Main {
    public static void main(String[] args) {
        LinkedListADT<Integer> linkedList = new SinglyLinkedList<>();
        linkedList.addFirst(10);
        linkedList.addLast(20);
        System.out.println(linkedList.getFirst());  // 输出 10
        System.out.println(linkedList.getLast());   // 输出 20
        System.out.println(linkedList.removeFirst()); // 输出 10
        System.out.println(linkedList.removeLast());  // 输出 20
        System.out.println(linkedList.isEmpty());     // 输出 true
    }
}

通过上述Java源码，我们可以看到链表ADT如何在Java中被定义和实现。定义一个接口作为ADT，然后通过类来实现这个接口，可以提供多种链表的实现，同时保持对外的接口一致。这种方式使得代码更加模块化，易于理解和使用。

ADT的使用提高了代码的可维护性和可扩展性，因为具体的实现可以被替换或修改，而不影响使用这些数据结构的客户端代码。这种抽象层次上的分离是面向对象编程的核心概念之一，有助于创建清晰、可重用和易于测试的代码。

标签：ADT,head,element,链表,next,抽象数据类型,数据结构,public
From： https://blog.csdn.net/hummhumm/article/details/140120642

相关文章

  • 【408考点之数据结构】B树和B+树
    B树和B+树在大规模数据存储和检索中，B树和B+树是两种广泛使用的数据结构。它们被设计用来高效地管理数据，使得插入、删除和查找操作都能在对数时间内完成。以下是对这两种数据结构的详细介绍。1.B树（B-Tree）定义：B树是一种自平衡的多路查找树，通常用于数据库和文件系统中。B树......
  • [JLU] 数据结构与算法上机题解思路分享-第三次上机
    前言首先，请务必自己尽全力尝试实现题目，直接看成品代码，思维就被拘束了，也很容易被查重。这里只是思路解析的博客，代码仓库在JLU_Data_Structures_Record希望你能在这里找到你想要的:)正文A图的创建分数10作者朱允刚单位吉林大学请编写程序创建一个有向图。有向图中包含......
  • 数据结构小学期第2天
    今日完成了小组分发的剩下两个题目其一，老板的作息表新浪微博上有人发了某老板的作息时间表，表示其每天4:30就起床了。但立刻有眼尖的网友问：这时间表不完整啊，早上九点到下午一点干啥了？本题就请你编写程序，检查任意一张时间表，找出其中没写出来的时间段。输入格式：输入第一行给出......
  • PART1-Oracle关系数据结构
    2.Oracle关系数据结构2.1.表和表簇2.1.1.模式对象简介数据库模式是数据结构的逻辑容器，这些数据结构称为模式对象。模式对象的例子有表和索引。模式对象是通过SQL创建和操作的。一个数据库用户拥有密码和各种数据库权限。每个用户拥有一个与其同名的模式。模式包含了属于......
  • [JLU] 数据结构与算法上机题解思路分享-第二次上机
    前言首先，请务必自己尽全力尝试实现题目，直接看成品代码，思维就被拘束了，也很容易被查重。这里只是思路解析的博客，代码仓库在JLU_Data_Structures_Record希望你能在这里找到你想要的:)正文A二叉树的创建与遍历分数10作者朱允刚单位吉林大学通过带空指针信息的先根序列（......
  • 数据结构：期末考 第六次测试（总复习）
    一、单选题（共50题，100分）1、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（D）.（2.0）A、（n−1）/2B、nC、n+1D、n/22、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后......
  • 【数据结构】常见的几种数据结构
    常见的数据结构：数组、链表、队列、栈、、堆、二叉树、B树、哈希表、图数组因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来。根据索引查找元素，时间复杂度是\(O(1)\)。动态数组动态数组具体代码实现importjava.util.Arrays;importjava.util.Ite......
  • 数据结构 —— Trie 树
    一个笔记需要一张头图：Trie树是一种维护（广义）字符串（我们认为广义字符串是一切可以被线性描述的类型，例如，我们认为整数（无论是哪种进制下）是一种广义字符串；有理数也是一种广义字符串（使用无限循环小数方式表述，可能需要一些特殊处理。））的数据结构，其特征为适于处理前缀类型或寻找类型（i.e.......
  • 探索数据结构：队列的的实现与应用
     ......
  • 堆数据结构
    堆（Heap）是一种特殊的树形数据结构，通常被实现为一个完全二叉树，以数组的形式存储。堆主要用于实现优先队列，它有两种基本形式：最大堆（MaxHeap）和最小堆（MinHeap）。特点完全二叉树：堆在逻辑上是一个完全二叉树，这意味着除了最后一层外，每一层的节点都是满的，并且最后一层的节点都靠左排列。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99