当前位置:首页 » 数据结构精品文章 » 正文

数据结构之绪论-基本概念和术语汇总

957 人参与  2018年08月18日 09:00  分类 : 数据结构精品文章  评论

1、顺序存储方法

把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构(Sequential Storage Structure)。

2、链接存储方法

不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构(Linked Storage Structure)。

3、索引存储方法

通常在储存结点信息的同时,还建立附加的索引表。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项,则该索引表称之为稠密索引Dense Index)。

4、原子类型

其值不可分解。通常是由语言直接提供。

5、结构类型

其值可分解为若干个成分(或称为分量)。

6、抽象数据类型(Abstract Data Type

指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。

7、时间复杂度

度量算法执行的时间长短。

一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))

分析:随着模块n的增大,算法执行的时间的增长率和fn)的增长率成正比,所以fn)越小,算法的时间复杂度越低,算法的效率越高。

8、空间复杂度

    度量算法所需存储空间的大小。是程序运行所以需要的额外消耗存储空间,也用o()来表示。比如插入排序的时间复杂度是o(n2),空间复杂度是o(1)

9、数据

指所有能输入到计算机中并被计算机程序处理的符号集合。

10、数据元素

数据的基本单位。

11、数据项

具有独立含义的最小标识单位。

12、逻辑结构

数据之间的逻辑关系的描述。

13、算法定义

算法是有限指令的集合,遵循着它可以完成一项特定的任务。

14、频度

算法执行一次,某一语句实际被执行的次数,叫该语句在此算法中的频度。

15、大O定义(形式化的描述时间复杂度)

当且仅当两个常数cn0对所有nn0使得T(n)cf(n)时,则 T(n)O(f(n))

16、数据结构

指的是数据之间的相互关系,即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

17、输入

一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供,也可以使用赋值语句在算法内给定。

18、输出

一个算法应有一个或多个输出,输出的量是算法计算的结果。

19、确定性

算法的每一步都应确切地、无歧义地定义。对于每一种情况,需要执行的动作都应严格地、清晰地规定。

20、有穷性

一个算法无论在什么情况下都应在执行有穷步后结束。

21、可行性

算法中有待实现的运算都是相当基本的,每种运算原则上都能精确地由人用纸和笔用有限的运算即可完成。

22、逻辑结构

指数据元素之间的逻辑关系。

23、存储结构

数据元素及其关系在计算机存储器内的表示,称为数据的存储结构。

24、线性结构

数据逻辑结构中的一类。它的特征是若结构为非空集,则该结构有且只有一个开始结点和一个终端结点,并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。

25、非线性结构

数据逻辑结构中的另一大类,它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。

26、物理结构

逻辑结构在计算机存储器里的实现。

27、数据类型

是一个值的集合以及在这些值上定义的一组操作的集合的总称。

28、抽象数据类型

由一组数据结构和在该组数据结构上的一组操作所组成。

image.png

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=11

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!