基本概念和术语
- 数据
- 数据元素
数据元素是数据的基本单位。
数据项是构成数据元素的不可分割的最小单位。
- 数据对象
数据对象是具有相同性质的数据元素的集合,是数据的一个子集。
- 数据类型
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
- 抽象数据类型(ADT)
抽象数据类型描述了数据的逻辑结构和抽象运算,通常用(数据对象,数据关系,基本操作集)这样的三元组来表示,从而构成一个完整的数据结构定义。
- 数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容:逻辑结构、存储结构和数据的运算。
数据结构的三要素
-
数据的逻辑结构
数据的逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。它与数据的存储无关,是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构。
线性结构:结构中的数据元素之间只存在一对一的关系。
-
数据的存储结构
存储结构是指数据结构在计算机中的表示,也称物理结构。数据的存储结构是逻辑结构在计算机上的映射,它不能独立于逻辑结构而存在。
数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储。
- 顺序存储:逻辑上相邻的元素物理位置上也相邻。
优点是可以实现随机存取,,每个元素占用最少的存储空间;缺点是只能使用相邻的一整块存储单元,可能产生较多的外部碎片。
- 链式存储:不要求逻辑上相邻的元素在物理位置上也相邻,借助指针来表示元素之间的逻辑关系。
优点是不会出现碎片现象,能充分利用所有存储单元;缺点是每个元素因存储指针而占用额外的存储空间,且只能实现顺序存取。
- 索引存储:在存储元素信息的同时,建立附加的索引表。
优点是检索速度快;缺点是增加附加的索引表后会占用较多的存储空间。在增加和删除数据时要修改索引表,会花费较多的时间。
- 散列存储:根据元素的关键字直接计算出该元素的存储地址,又称Hash存储。
优点是检索、增加和删除结点的操作都很快;缺点是若散列函数不好,则可能出现元素存储单元的冲突,解决冲突会增加时间和空间开销。
-
数据的运算
运算的定义是针对逻辑结构的,指出运算的功能;运算的实现是针对存储结构的,指出运算的具体操作步骤。
链式存储设计时,各个不同结点的存储空间可以不连续,但结点内的存储单元地址必须连续。
- 对于两种不同的数据结构,它们的逻辑结构和物理结构有可能完全相同。例如二叉树和二叉排序树,二叉排序树可以采用二叉树的逻辑表示和存储方式,但它们的运算定义不同,以查找结点为例:二叉树的时间复杂度为O(n),二叉排序树的时间复杂度为O(log2n).
- 线性表既可以用顺序存储的方式实现,也可以用链式存储的方式实现。在顺序存储的方式下,在线性表中插入和删除元素,平均要移动近一半的元素,时间复杂度为O(n);而在链式存储方式下,插入和删除的时间复杂度都是O(1)。
算法的基本概念
算法是对特定问题求解步骤的一种描述,是指令的有限序列,其中每个指令表示一个或多个操作。具有以下五个特性:
- 有穷性
- 确定性
- 可行性
- 输入
- 输出
通常设计一个“好”的的算法应达到以下目标:
- 正确性
- 可读性
- 健壮性
- 效率与低存储量需求
算法效率的度量是通过时间复杂度和空间复杂度来描述的。
某算法的时间复杂度为O(n2),表明该算法的执行时间与n2成正比,问题规模仍是n
版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/qq_38929220/article/details/101941986
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。