数据结构-基本概念

基本术语

数据(data)

信息的载体,客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

e.g. 文本编辑器中的字符串。

数据元素(data element)、数据项(data item)

数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

一个数据元素可由若干个数据项(data item)组成,数据项是数据的不可分割的最小单位。

e.g. 学生基本信息表中,每一条学生记录是一个数据元素。学生姓名、性别、年龄等是组成学生(数据元素)的若干数据项。

数据对象(data object)

性质相同的数据元素的集合,是数据的一个子集。

e.g. 包含学生记录(数据元素)的学生基本信息表是一个数据对象。

数据结构(data structure)

是相互之间存在一种或多种特定关系的数据元素的集合(各个元素相互之间的关系)。

e.g. 张三和李四是校友

数据、数据对象、数据元素、数据项之间的关系以及数据结构研究内容,可用下图表示:

de6e00dc82d4c4eb - 数据结构-基本概念
查看大图

数据结构三要素

逻辑结构

数据元素之间的逻辑关系。根据数据元素之间的不同特性,通常有下列4类基本结构:

集合结构

结构中的数据元素之间除了“同属于一个集合”的关系外,别无其他关系。

e.g. 互不相识的软件学院的张三,和建筑学院的李四,同属东北大学,无其他关系。

线性结构

结构中的数据元素之间存在一个对一个的关系。

e.g. 将学生信息数据按照成绩进行排列,相互之间组成一个一对一的数据结构。

树形结构

结构中的数据元素之间存在一个对多个的关系。

e.g. 学校管理体系中,高三年级组组长管理多个部门,部长管理多个班级,组成一对多的树形结构。

图状结构或网状结构

结构中的数据元素之间存在多个对多个的关系。

e.g. 多位同学之间的朋友关系;微信好友关系

存储结构(物理结构)

用计算机表示数据元素的逻辑关系。

顺序存储

借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。逻辑上相邻的元素在物理位置上也相邻。

非顺序存储(离散存储)

链式存储

借助指示元素存储地址的指针(pointer)表示数据元素之间的逻辑关系。逻辑上相邻的元素在物理位置上可以不相邻。

索引存储

存储元素信息的同时,建立索引表。每一项的格式一般为:关键字,地址。

散列存储

根据关键字计算出该元素的存储地址,而非通过索引表取得存储地址,又称哈希(Hash)存储。

数据的运算

数据的逻辑结构和物理结构是密切相关的两个方面,任何一个算法的设计(运算的定义)取决于选定的数据(逻辑)结构,而算法的实现依赖于采用的存储结构。

数据结构三要素及要素内部的相关关系可总结如下:

81c160527589cc0a - 数据结构-基本概念
查看大图

数据类型(data type)

一个值的集合和定义在这个值集上的一组操作的总称。

e.g. C语言中的bool类型,取值范围true、false,可进行操作与、或、非

原子类型(atomic data type)

变量的值是不可分解的。比如bool类型、int类型。

结构类型(struct data type)

变量的值可以再分解为若干成分,如struct结构体。

抽象数据类型(Abstract Data Type,简称ADT)

一个数据模型以及定义在该模型上的一组操作,即定义了数据的逻辑结构、数据的运算,也就是定义了一个数据结构。

探讨一种数据结构时所采用的方法

定义逻辑结构(数据元素之间的关系)→定义数据的运算(对这种逻辑结构进行怎样的运算)→确定存储结构(实现定义的数据结构及基本运算)

3+


1
说点什么

avatar
250
  关注  
最新 最旧 得票最多
提醒