当前位置： 首页 > news >正文

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

news 来源：原创 2024/9/22 4:22:28

第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;}@Overridepublic void push(T element) {ensureCapacity();elements[size++] = element;}@Overridepublic T pop() {if (isEmpty()) {throw new NoSuchElementException("Stack is empty");}return elements[--size];}@Overridepublic T peek() {if (isEmpty()) {throw new NoSuchElementException("Stack is empty");}return elements[size - 1];}@Overridepublic 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());    // 输出 2System.out.println(stack.pop());     // 输出 2System.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;}}@Overridepublic void enqueue(T element) {Node<T> newNode = new Node<>(element);if (tail != null) {tail.next = newNode;} else {head = newNode;}tail = newNode;}@Overridepublic T dequeue() {if (isEmpty()) {throw new NoSuchElementException("Queue is empty");}T element = head.data;head = head.next;if (head == null) {tail = null;}return element;}@Overridepublic T peek() {if (isEmpty()) {throw new NoSuchElementException("Queue is empty");}return head.data;}@Overridepublic 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());    // 输出 1System.out.println(queue.dequeue()); // 输出 1System.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;}}@Overridepublic void addFirst(T element) {Node<T> newNode = new Node<>(element);newNode.next = head;head = newNode;size++;}@Overridepublic 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++;}@Overridepublic T removeFirst() {if (isEmpty()) {throw new NoSuchElementException("Linked list is empty");}T element = head.data;head = head.next;size--;return element;}@Overridepublic 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;}}@Overridepublic T getFirst() {if (isEmpty()) {throw new NoSuchElementException("Linked list is empty");}return head.data;}@Overridepublic 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;}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic 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());  // 输出 10System.out.println(linkedList.getLast());   // 输出 20System.out.println(linkedList.removeFirst()); // 输出 10System.out.println(linkedList.removeLast());  // 输出 20System.out.println(linkedList.isEmpty());     // 输出 true}
}

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

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

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Vue3项目给ElementPlus设置中文的两个方案
  • Python的招聘数据分析与可视化管理系统-计算机毕业设计源码55218
  • 大数据Spark 面经
  • Java中的内存数据库与缓存技术
  • Java并发编程-AQS详解及案例实战（上篇）
  • 【最新整理】全国高校本科及专科招生和毕业数据集（2008-2022年）
  • Python酷库之旅-第三方库Pandas(005)
  • mac 11 变编译安装nginx
  • Apache Seata透过源码解决SeataAT模式整合Mybatis-Plus失去MP特性的问题
  • WHAT - React useEffect 依赖的 Object.is
  • 【C语言】指针（1）：入门理解篇
  • Docker 部署 OpenVPN 与 OpenVPN 基本用法
  • CTFShow的RE题（二）
  • Gradient Descent
  • windows下编译ffmpeg 最详细教程
  • 【跃迁之路】【669天】程序员高效学习方法论探索系列（实验阶段426-2018.12.13）...
  • CentOS7简单部署NFS
  • java正则表式的使用
  • js作用域和this的理解
  • python 学习笔记 - Queue Pipes，进程间通讯
  • React组件设计模式（一）
  • Redis的resp协议
  • Spring Cloud(3) - 服务治理: Spring Cloud Eureka
  • vue从创建到完整的饿了么（11）组件的使用（svg图标及watch的简单使用）
  • 初探 Vue 生命周期和钩子函数
  • 高度不固定时垂直居中
  • 基于Vue2全家桶的移动端AppDEMO实现
  • 前嗅ForeSpider采集配置界面介绍
  • 使用Maven插件构建SpringBoot项目,生成Docker镜像push到DockerHub上
  • 小程序滚动组件，左边导航栏与右边内容联动效果实现
  • 在Docker Swarm上部署Apache Storm：第1部分
  • ［地铁译］使用SSD缓存应用数据——Moneta项目: 低成本优化的下一代EVCache ...
  • UI设计初学者应该如何入门？
  • 阿里云ACE认证学习知识点梳理
  • ​​快速排序（四）——挖坑法，前后指针法与非递归
  • ​一些不规范的GTID使用场景
  • #Linux（Source Insight安装及工程建立）
  • #职场发展#其他
  • (1) caustics\
  • （2）从源码角度聊聊Jetpack Navigator的工作流程
  • （20050108）又读《平凡的世界》
  • （BFS）hdoj2377-Bus Pass
  • （二）什么是Vite——Vite 和 Webpack 区别（冷启动）
  • （附源码）ssm考生评分系统 毕业设计 071114
  • （一）python发送HTTP 请求的两种方式(get和post )
  • （已解决）vue+element-ui实现个人中心，仿照原神
  • (转)MVC3 类型“System.Web.Mvc.ModelClientValidationRule”同时存在
  • .helper勒索病毒的最新威胁：如何恢复您的数据？
  • .java 9 找不到符号_java找不到符号
  • .net core MVC 通过 Filters 过滤器拦截请求及响应内容
  • .NET 设计一套高性能的弱事件机制
  • .net中我喜欢的两种验证码
  • .py文件应该怎样打开？
  • /etc/sudoers (root权限管理)
  • /usr/local/nginx/logs/nginx.pid failed (2: No such file or directory)