本文主要是介绍数据结构及抽象数据类型,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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不关心存储细节
例:栈的抽象数据类型ADT
- 逻辑结构:线性表
- 操作特点:限制访问端口
- 只允许在一端进行插入、删除操作
- 入栈(push)、出栈(pop)、取栈顶(top)、判栈空(isEmpty)
思考:关于抽象数据类型ADT
- 怎么体现逻辑结构?
- 抽象数据类型等价于类定义?
- 不用模板来定义可以描述ADT吗?
这篇关于数据结构及抽象数据类型的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!