[数据结构] 01 - 数据结构绪论
参考资料:
- MyCodeSchool. (2013, March 26). Introduction to data structures [Video]. YouTube. https://youtu.be/92S4zgXN17o
- 程杰. (2011). 大话数据结构. 清华大学出版社.
1.1 - 什么是数据结构
数据结构本质上是人类处理海量信息时,摸索出的组织数据的智慧。
数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。
它经历了四个关键的阶段:
- 前计算机时期(20 世纪初期):
最早的数据组织源自于图书馆分类法、人口普查表等现实需求; - 计算机诞生初期(40 - 50 年代):
早期计算机主要做数值计算,程序的数据往往就是若干数字。冯·诺依曼体系带来了“通过偏移量访问连续数据”的概念,即内存本身就是一串连续编号的存储单元,那么把同类型数据连续存储起来是一件非常自然的事,于是数组就作为最早的数据组织方式出现了; - 数据结构真正成为科学的时期(60 年代):
1968 年,美国科学家高德纳(Donald E. Knuth)教授在《计算机程序设计艺术》第一卷《基本算法》中,较为系统地阐述了数据的逻辑结构和存储结构及其操作,将链表、栈、队列、树、图等概念理论化,开创了数据结构的课程体系,使之成为一门独立的学科; - 结构化编程诞生的时期(70 年代起):
大型程序出现、软件开始相对独立。尼克劳斯·威尔特(Niklaus Wirth)提出“程序 = 数据结构 + 算法”,即程序设计的实质是对确定的问题选择一种好的结构,加上一种好的算法。数据结构在程序设计中占据了越来越重要的地位。 - 标准化时期(90 年代起):
面向对象和泛型编程愈加成熟,数据结构开始被封装为标准库(如 C++ 的 STL),实现了“拿来即用”,使程序员可以专注于“选择哪种结构来解决哪种问题”。
1.2 - 基本概念和术语
1.2.1 - 数据
- 数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号的集合。
- Data: The set of all the symbols can be processed or stored by a computer.
- 数据不仅包括整形、实型等数值类型,还包括字符、声音、图像等非数值类型。数据其实就是符号,但必须具备两个前提:可以输入到计算机中、能被计算机程序处理。
1.2.2 - 数据元素
- 数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录。
- Data element: The term data element is an atomic unit of data that has an indentification such as a data element name;
- 例如,每一个【人类个体】都是【人类】的数据元素,每一只牛、马、鸡、狗等动物都是【畜禽类】的数据元素。
1.2.3 - 数据项
- 数据项:是组成数据元素的最小单位,一个数据元素可以由若干个数据项组成;是数据不可分割的最小单位。
- Data item: One smallest indivisible data units. One data element consists of one or many data items.
- 例如,一个【人类个体】是数据元素,他可以有眼睛、耳朵、鼻子、嘴巴等数据项,也可以有姓名、年龄、性别等数据项。一个数据元素具体有哪些数据项,要由程序应实现的功能来决定。
1.2.4 - 数据对象
- 数据对象:是性质相同的数据元素的集合,是数据的子集。
- Data object: The collection of data elements.
- 例如,【人类】由大量的【人类个体】组成,人类个体是数据元素,由这些具有相同性质的数据元素组成的【人类】就称为数据对象。
1.2.5 - 数据结构
- 结构 (Structure):不同数据元素之间不是独立的,而是存在特定的关系,我们将这些关系称为结构。
- 数据结构 (Data Structure):是相互之间存在一种或多种特定关系的数据元素的集合。
- 结构:例如分子结构就是组成分子的原子之间的排列方式;
- 数据结构:例如数组中的数据元素之间,是一前一后的关系,所以数组就是一种数据结构。研究数据结构,本质上就是研究数据元素之间的关系,以及如何有效地表示和操作这种关系。
1.3 - 逻辑结构和物理结构
-
逻辑结构是面向问题的,物理结构是面向计算机的;
-
其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。
-
Algorithm design depends on logical structure.
-
Algorithm implementation depends on how to store the DS-physical structure.
1.3.1 - 逻辑结构
逻辑结构:是指数据对象中数据元素之间的相互关系。
Logical Structure: The logical relationships between data elements.
逻辑结构分为以下的四种:
- 集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系;
- 线性结构:线性结构中的数据元素是一对一的关系;
- 树形结构:树形结构中的数据元素之间存在一种一对多的层次关系;
- 图形结构:图形结构中的数据元素是多对多的关系。
1.3.2 - 物理结构
物理(存储)结构:是指数据的逻辑结构在计算机中的存储形式。
Storage Structure: The methods of how to store Data Structure in computer memory.
*Both data elements and the relationships should be stored in memory.
数据元素的存储结构形式有两种:
- 顺序存储结构:是把数据元素存放在连续的存储单元里,其数据间的逻辑关系和物理关系是一致的;
- 链式存储结构:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。
- 数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,通过地址寻找关联数据元素的位置;
- 链式存储比顺序存储更灵活,适合时刻处于变化中的结构。
Sequential storage structure - e.g. Arrays
Linked storage structure
1.4 - 数据类型
数据类型:是指一组性质相同的值的集合,及定义在此集合上的一些操作的总称。
Data type: A data type is a collection of objects and a set of operations that act on those objects.
1.4.1 - 数据类型的定义
数据类型是根据值的不同进行划分的。在高级语言中,每个变量、常量都有各自的取值范围,类型就用来说明变量或表达式的取值范围和所能进行的操作。
在 C 语言中,按照取值的不同,数据类型可分为两类:
- 原子类型:不可再分解的基本类型,包括整型、实型、字符型等;
- 结构类型:由若干个类型组合而成,可再分解,例如整型数据。
- 例如,short 类型就比 int 类型使用更少的空间,同时取值范围也更小;变量声明
int a, b,就意味着 a 和 b 的值不能超出 int 的取值范围,a 和 b 之间的运算只能是 int 类型所允许的运算。
1.4.2 - 抽象数据类型(ADT)
抽象:是指抽取出事物具有的普遍性的本质。抽象是一种思考问题的方式,隐藏繁杂的细节,只保留实现目标所必需的信息。
我们对已有的数据类型进行抽象,就有了抽象数据类型:
抽象数据类型:一个数学模型及定义在该模型上的一组操作。
Abstract Data Type (ADT): A specification of a set of data and the set of operations that can be performed on the data.
Such a data type is abstract in the sense that it is independent of various concrete implementations.
ADT 的特性:
- 操作的灵活性:可以根据需求自己决定某种数据结构要提供哪些功能;
- ADT 并没有规定“必须提供哪些操作”,也没有规定“操作的具体行为必须完全固定”。可根据实际应用场景,自由地增删、修改或组合操作;
- 实现的独立性:无论用何种方法实现这些功能,对外部使用者来说没有任何区别;
- ADT 只定义“逻辑上能做什么”(规范),而不关心“具体怎么做”(实现细节);
- 描述抽象数据类型的标准格式:
ADT 抽象数据类型名
Data
数据元素之间逻辑关系关系的定义
Operation
操作 1
初始条件
操作结果描述
操作 2
......
操作 3
......
endADT