N. Wirth早在20世纪70年代就指出“程序=数据结构+算法”。数据结构主要研究数据在计算机中存储、组织、传递和转换的过程以及方法,这些也是构成与支撑算法的基础。数据结构主要讨论数据的逻辑结构、在计算机中的存储结构以及对其进行的各种处理运算的方法和算法。
如何有效地组织数据和处理数据是软件设计的基本内容,直接关系软件的运行效率和工程化程度。数据结构是软件设计的重要理论和实践基础。
早期计算机处理的对象多为简单的数值数据,而现在,随着计算机和信息技术的飞速发展,计算机应用远远超出了单纯进行数值计算的范畴。处理非数值计算性问题占用了90%以上的机器时间,设计了更为复杂的数据结构和数据元素间的互相关系。
主要有以下3个步骤:
数据是信息的载体,是计算机程序处理对象的集合,也是计算机处理信息的某种特定符号化表示形式,除了整数、实数等数值数据外,还包括字符串等非数值数据以及图形、图像、音频和视频等媒体数据。
数据项是具有独立含义、数据不可分割的最小标识单位,是数据元素的组成部分,也可称之为字段和域。
下面是小说类书籍,其中“书名”和“出版社”就是数据项(字段或域)。
书名 | 出版社 |
---|---|
此时不必问去哪里 | 山东文艺出版社 |
街头日记 | 南海出版公司 |
普通婚姻 | 上海人民出版社 |
数据元素是数据的基本单位,又可称之为元素、节点,是一个数据整体中可以表示和访问的数据单元。
"小说类书籍"就是数据元素,是数据项的集合。
数据对象是性质相同的数据元素的集合,也叫数据元素类。
比如生活类书籍、科技类书籍、小说类书籍,每一种类型的书籍的总和都是性质相同的数据元素的集合(数据对象)。
数据结构是相互之间存在着一种或者多种关系的数据元素的集合,数据结构概念包含3个方面的内容,即数据的逻辑结构、数据的存储结构和数据的操作。
数据的逻辑结构是指数据元素之间存在的逻辑关系。数据的逻辑结构与数据的存储结构无关,独立于计算机,是从具体问题抽象出来的数学模型。
集合中数据元素的关系极为松散,关系为“属于同一个集合”。
比如下图中有三个数据元素:databseTheory(数据库原理)、databaseStructure(数据结构)和wxApplets(微信小程序开发),它们的性质都是教育类的书籍,而它们之间的关系极为松散,因此属于集合类型的逻辑结构。
线性结构是数据元素中具有线性关系的数据结构,线性结构中的节点存在“一对一”的关系。开始节点和终端节点都是唯一的,除开始和终端结点外,每个节点有且仅有一个前驱节点和一个后继节点。
比如下图的字母表,a是开始节点,e是终端节点,而a与e两个节点之间都有一个前驱节点和后驱节点。对于c节点来说,b是c的前驱节点,d是c的后驱节点。并且,b与c是一对一的关系,d与c也是一对一的关系。
树形结构是数据元素之间具有层次关系的一种非线性结构,树形结构中的节点存在“一对多”的关系。除根节点外,每个节点有且仅有一个前驱节点,所有节点可以有零个或多个后驱节点。
比如下图的文件系统的组织方式,C盘是该结构的根节点,有且仅有一个根节点。文件夹1有3个后驱节点,而文件夹3没有后驱节点。
图形结构是一种非线性结构,图形结构中的节点存在“多对多”的关系,所有的节点都可以有多个前驱结点和后驱节点。
数据的逻辑结构涉及两个方面的内容,一是数据元素,二是数据元素之间的逻辑关系。
以二元组来定义数据的逻辑结构:logica structure = (D, R),D表示数据元素,R表示数据元素之间的关系
比如D={1,2,3,4,5,6,7},R={[1,2], [1,3], [3,4], [2,5], [3,6], [2,7]}
用图来表示数据元素之间的逻辑关系:
1是2的前驱元素,2是1的后继(驱)元素。
逻辑结构在计算机中的存储表示或实现叫数据的存储结构,也叫物理结构。数据的逻辑结构从逻辑关系角度观察数据,与数据的存储无关系,是独立于计算机的;而数据的存储结构是逻辑结构在计算机中的实现,依赖于计算机。
例子一:所有年级的所有班如何用表示班与班之间的关系,如:一年级一班、一年级二班、一年级三班属于一年级;二年级一班、二年级二班属于二年级。这是以逻辑层面(角度)去观察数据元素之间的关系。
例子二:分别设计班级表和学生表,两张表的逻辑结构是学生表属于班级表。数据存储在各自的表中就是存储结构。
物理位置相邻的元素在逻辑上也相邻,每个元素(数据元素)与其前驱元素和后继元素的存储位置相邻,数组就是顺序存储结构。
数据操作是指对数据结构中的数据元素进行运算或处理,每种逻辑结构都需要一组对其数据元素进行处理一实现特定功能的操作,如插入、删除、更新等。数据操作的实现依赖于数据的存储结构。
联系客服