Java教程

数据结构及抽象数据类型

本文主要是介绍数据结构及抽象数据类型,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.2 什么是数据结构

  • 结构:实体 + 关系
  • 数据结构:
    • 按照逻辑关系组织起来的一批数据
    • 按一定的存储方法把它存储在计算机中
    • 在这些数据上定义了一个运算的集合

数据结构三个基本面:逻辑、存储、运算

数据结构的逻辑组织

  • 线性结构
    • 线性表(表、栈、队列、串等)
  • 非线性结构
    • 树(二叉树、 Huffman树、二叉检索树等)
    • 图(有向图、无向图等)
  • 图 树 二叉树 线性表

数据的存储结构

  • 逻辑结构到物理存储空间的映射

计算机主存储器(内存)

  • 非负整数地址编码,相邻单元的集合
    • 基本单位是字节
    • 访问不同地址所需时间基本相同(即随机访问)

内存可以看做是从低到高的线性结构

  • 对逻辑结构(K,r),其他r R
    • 对结点集K建立一个从K到存储器M的单元的映射:K-->M,对于每一个结点j K都对应一个唯一的连续存储区域c M
  • 关系元组(j1,j2) r(其中j1,j2 K是结点)
    • 顺序:存储单元的顺序地址(数组)
    • 连接:指针的地址指向关系(链表)
  • 四类:顺序、链接、索引、散列(特殊的索引结构)

抽象数据类型

  • 简称ADT(Abstract Data Type)
    • 定义了一组运算的数学模型
    • 与物理存储结构无关
    • 使软件系统建立在数据之上(面向对象)
  • 模块化的思想的发展
    • 隐藏运算实现的细节和内部数据结构
    • 软件复用

ADT不关心存储细节

  • 抽象数据结构二元组
    • <数据对象D,数据操作P>
  • 先定义逻辑结构,再定义运算
    • 逻辑结构:数据对象及其关系
    • 运算:数据操作

例:栈的抽象数据类型ADT

  • 逻辑结构:线性表
  • 操作特点:限制访问端口
    • 只允许在一端进行插入、删除操作
    • 入栈(push)、出栈(pop)、取栈顶(top)、判栈空(isEmpty)

思考:关于抽象数据类型ADT

  • 怎么体现逻辑结构?
  • 抽象数据类型等价于类定义?
  • 不用模板来定义可以描述ADT吗?
这篇关于数据结构及抽象数据类型的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!