数据结构之绪论篇 返回首页

发表于 2016-05-18

基本概念和术语

数据 (Data)
数据是信息的载体,是对信息的一种符号表示。它能够被计算机识别、存储和加工处理。
数据元素 (Data Element)
数据元素是数据的基本单位。在不同条件下,数据元素又可称为元素、结点、顶点、记录等。
数据对象 (Data Object)
数据对象是具有相同性质的数据元素的集合,是数据的一个子集。
数据类型 (Data Type)
是一组性质相同的值的集合以及定义在这个值集合上的一组操作的总称。

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。其具有以下四种基本类型:

  1. 集合结构。 结构中的数据元素之间同属于一个集合。集合是元素关系极为松散的一种结构。

  2. 线性结构。 结构中的数据元素之间存在一对一的关系。除了首尾结点,任何一个结点都有一个唯一的前驱和一个唯一的后继。

  3. 树形结构。 结构中的数据元素之间存在一对多的关系。除了树根节点,任何一个结点最多有一个前驱,可以有多个后继。是一种典型的非线性结构。

  4. 图形结构。 结构中的数据元素之间存在多对多的关系。特征是:任何一个元素可以有多个前驱,也可以有多个后继,是一种多对多的前驱后继关系。也称网状结构。

四类基本类型

数据结构包括以下三方面内容:数据的逻辑结构、存储结构和数据运算。

数据结构三方面内容

逻辑结构

从数据结构的概念可以知道,数据结构有两个要素:一个是数据元素的集合,另一个是关系的集合。在形式上,数据结构可用一个二元组来表示。

数据结构的形式定义为:Data_Structure = (D,R) 其中,D 是数据元素 (又称结点) 的有限集,R 是 D 上关系的有限集。eg:

D = (K, R)
K = {1, 2, 3, 4, 5}
R = {<1, 2>, <1, 3>, <3, 4>, <3, 5>}

其对应树形逻辑结构图:

例树形结构图

存储结构

顺序存储结构

把逻辑上相邻的结点存储在物理上相邻的存储单元里,结点之间的逻辑关系由存储单元位置的邻接关系来体现。通常借助程序语言中的数组来描述。

:+1: 优点:占用较少的存储空间。
:-1: 缺点:只能使用相邻的一整块存储单元,因此可能产生较多的碎片现象。

链式存储结构

不要求逻辑上相邻的结点在物理位置上相邻,将结点所占的存储单元分为两部分,一部分存放结点本身的信息 (数据项),另一部分存放该结点的后继结点所对应的存储单元的地址,结点间的逻辑关系由附加的指针字段表示。通常借助程序语言中的指针类型来描述。

:+1: 优点:不会出现碎片化现象,充分利用所有的存储单元。
:-1: 缺点:每个结点占用较多的存储空间。

索引存储方式

用结点的索引号来确定结点的存储地址。通常在存储结点信息的同时,还建立附加的索引表,结点间的逻辑关系由索引项来表示。

:+1: 优点:检索速度快。
:-1: 缺点:增加了附加的索引表,占用较多的存储空间,且在增加和删除数据时由于要修改索引表而花费较多时间。

散列存储方式

根据结点的关键字值直接计算出该结点的存储地址。通过散列函数把结点间的逻辑关系对应到不同的物理空间。

:+1: 优点:检索、增加和删除结点的操作都很快。
:-1: 缺点:当采用不好的散列函数时可能出现结点存储单元的冲突,为解决冲突需要附加时间和空间的开销。

这四种基本存储方式可单独使用,也可以组合使用,视情况而选取最好的方式。

数据的运算

数据的运算无非就是基本的增删查改这些操作,通过算法来实现。

算法

算法是对问题求解过程的一种描述,是为解决一个或一类问题给出的一个确定的、有限长的操作序列。

算法

算法具有以下五个特性:

  1. 有穷性。 对于任意一组合法的输入值,一个算法必须在执行有穷步之后结束,且每一步都在有穷的时间内完成。

  2. 确定性。 组成算法的每一步操作都必须是明确的、无二义性。并且在任何条件下,算法都只有一条执行路径。

  3. 可行性。 算法中所有操作都必须是足够基本的。即:序列中的每个操作都是可以简单完成的,都可以通过有限次的已经实现的基本操作运算来实现。

  4. 输入。 一个算法有 0 个或者多个输入。

  5. 输出。 一个算法有一个或多个输出。

算法设计的要求:

  1. 正确性。 算法的执行结果应当满足预先规定的功能和性能要求。

  2. 可读性。 算法应当思路清晰、层次分明、简单明了、易读易懂,有利有于阅读者对程序的理解。

  3. 健壮性。 算法应当具有容错处理。当输入非法数据时,算法应当对其作出反应并进行适当的处理,不至引起严重后果。

  4. 高效性和存储量需求。 效率指算法执行的时间。存储量需求指算法执行过程中所需要的最大存储空间。通常这二者是矛盾不可兼得的。

算法效率的度量分为:时间复杂度和空间复杂度,时间复杂度指算法运行从开始到结束所需的时间,空间复杂度指算法运行开始到结束所需的存储量 (包括输入数据所占空间、程序本身所占空间、辅助变量所占空间)。


如果你觉得本文对你有帮助,不妨请我喝瓶葡萄味芬达


显示评论