第1章 绪论
《数据结构》学习笔记
第1章 绪论
1.1 数据结构的研究内容
计算机计算数值时，一般经过一下步骤：
1.从具体问题抽象出数学模型（实质是分析问题）。
2.设计一个解次数学模型的算法。
3.编写程序，进行测试、调试，直到问题解决。
数据结构要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型。
1.2 基本概念和术语
1.2.1
数据项(Data Item)：是组成数据元素、有独立含义的、不可分割的最小单位。
数据元素(Data Element)：是数据的基本单位，也称为元素、记录等；用于完整地描述一个对象。
数据对象(Data Object)：是性质相同的数据元素的集合，只要集合内元素的性质均相同，都可称之为一个数据对象；是数据的一个子集。
数据(Data)：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。
（数据项<数据元素<数据对象<数据）
1.2.2 数据结构
数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合，“结构”就是指元素之间存在的关系。
-1.逻辑结构
从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
分为两个要素：
常见的四类基本结构：
图1.3
(1)集合结构：数据元素之间除了“属于同一个集合”的关系外，别无其它关系。
(2)线性结构：数据元素之间存在一对一的关系。
(3)树结构：数据元素之间存在一对多的关系。
(4)图结构或网状结构：数据元素之间存在多对多的关系。
-2. 存储结构
数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。
(1)顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助数组来描述。要求所有元素依次存放在一片连续的存储空间中。
表1.2
(2)链式存储结构：无需占用一整块存储空间。给每个结点附加指针字段，用于存放后继元素的存储地址，从而来表示结点之间的关系。
图1.5
1.2.3 数据类型和抽象数据类型
-1. 数据类型(Data Type)
是高级程序设计语言中的一个基本概念，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定来数据的取值范围，存储方式以及允许进行的运算，数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
-2. 抽象数据类型(Abstract Data Type, ADT)
一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合、数据对象的基本操作的集合。
在高级语言中，则给出更高一级的数据抽象，出现了数据类型，如整形、实型、字符型等，可以进一步利用这些类型构造出线性表、栈、队列、树、图等复杂的抽象数据类型。
1.3 抽象数据类型的表示与实现
表示和实现抽象数据类型，最好用面向对象的方法。
1.4 算法和算法分析
1.4.1 算法的定义及特性
算法(Algorithm)是为了解决某类问题而规定的一个有限长的操作序列。五个重要特征：
1.4.2 评价算法优劣的基本标准
1.4.3 算法的时间复杂度
算法效率分析的目的是看算法实际是否可行，并在同一问题存在多个算法时，可进行时间和空间性能上的比较，以便从中挑选出较优算法。
-1. 问题规模和语句频度。
问题规模：算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。n越大算法的执行时间越长。
语句频度(Frequency Count)：一条语句的重复执行次数。
算法中基本语句重复执行的次数是问题规模n度某个函数f(n)；算法的时间复杂度为：T(n)=O(f(n))
算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度(Time Complexity)。
为了方便比较不同算法的时间效率，我们仅比较它们的数量级(最高次幂)，数量级越小，算法越优。
-2. 计算时间复杂度基本方法
-3. 算法的时间复杂度分析举例
例1.
上述代码，数量级最大的为二次方，所以T(n)=O(n*2)
例2.
例3.
例4.
1.4.4 算法的空间复杂度
…持续修改完善中
总结
- 上一篇： 08-贪婪算法
- 下一篇： 第2章 数据认知与预处理