文章目录
时间戳——2022.06.13（2.5h）
一、数据结构要研究的内容
1.计算机解决问题步骤
（1）3步骤：具体问题抽象为数学模型–>设计算法–>编程、调试、运行
（2）1实质：把具体问题抽象为数学模型的实质是：分析问题–>提取操作对象–>找出操作对象之间的关系–>用数学语言描述
（其中操作对象以及操作对象之间的关系称为数据结构）（即数据结构=操作对象+操作对象之间的关系）
2.计算机解决数值计算（略）
3.计算机解决非数值计算（重点）——线性【表】
（1）操作对象：行记录。
（2）操作对象之间的关系：线性关系。（也就是每行记录之间的关系）
4.计算机解决非数值计算（重点）——非线性【树】
（1）操作对象：棋局状态、子目录。
（2）操作对象之间的关系：(倒)树状结构。（一种当前格局派生出多种格局、一个父目录下有多个子目录）（一对多的关系）
6.计算机解决非数值计算（重点）——非线性、网状【图】
（1）操作对象：构成一条线路的各个地点的信息。
（2）操作对象之间的关系：非线性结构、网状结构。（起点和终点之间构成的多条线路，而连起来的网）
7.内容小结
（1）数据结构是一门学科。
（2）数据结构是一门研究非数值计算以及它们之间的关系和操作的学科。
（3）数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科。
（4）描述非数值计算问题的数学模型是：表、树、图。（它们都是具有逻辑关系的数据）
二、基本概念和术语1
1.数据、数据元素、数据项、数据对象
（1）数据元素是数据的基本单位。
（2）数据项是数据元素的最小单位。
（3）数据对象是数据元素的集合。
2.数据
（1）数据是：符号的集合。（可输入到计算机中）（且可被计算机识别）
3.数据元素
（1）数据的一些部分，其关系比较紧密，进行操作的时候一般作为一个整体进行操作。比如一个表数据，其中的一条记录，也就是一行记录就被多个数据项所组成。
（2）数据元素是：数据的基本单位。(也就是说：数据是数据元素的集合)(如：表数据的一条行记录)
（3）数据元素：也叫做元素、(行)记录、(树)节点、(图)顶点。
4.数据项
（1）数据项是：构成数据元素的最小单位。（比如下面学籍表，其中的一行记录中的5个具体字段都是数据项，组合后构成了数据元素）
（2）数据>数据元素>数据项
5.数据对象
（1）数据对象是：相同性质的数据元素的集合。（也是数据的一个子集）
6.数据元素和数据对象的关系（重点）
（1）数据元素是：组成数据(数据就是集合)的基本单位。
（2）数据元素是：数据(数据就是集合)的个体。
（3）数据对象是：相同性质的数据元素的集合。
（4）数据对象是：数据(数据就是集合)的子集。
7.数据结构实质（重点）
（1）数据是：数据元素的集合。(注意：别混淆，数据对象是相同性质的数据元素的集合)
（2）结构是：数据元素相互之间的关系。
（3）数据结构是：相互之间存在一种或多种特定关系的数据元素集合。(或者说，数据结构是带结构的数据元素的集合)
8.数据结构的三个方面（重点）
（1）“数据的”逻辑结构是：数据元素之间的逻辑关系。
（2）“数据的”物理结构或存储结构是：数据元素及其关系在计算机内存中的表示(又称为映像)。
（3）“数据的”运算或实现是：施加在数据元素之上的操作以及这些操作在相应存储结构上的实现。
9.数据结构的两个层次
（1）逻辑结构
（2）物理结构(存储结构)
10.逻辑结构的两个分类（重点）
（1）线性结构：有且仅有一个开始结点、一个终端结点，所有结点最多只有一个直接前趋和一个直接后继。（如：线性表、栈、队列、串）
（2）非线性结构：一个结点可能有多个直接前趋和直接后继。（如：树、图）
11.逻辑结构的四个分类（重点）
（1）集合结构：结构中的数据元素只是同属于一个集合。
（2）线性结构：结构中的数据元素一对一的线性关系。
（3）树形结构：结构中的数据元素是一对多的层次关系。
（4）图状结构或网状结构：结构中的数据元素是多对多的任意关系。
12.存储结构(物理结构)的四个分类（重点）
（1）顺序存储结构：依次存储数据单元。
（2）链接存储结构：存储自身元素的同时，存储了下一个元素的地址。
（3）索引存储结构：略。
（4）散列存储结构：略。
时间戳——2022.06.14-15（xh）
三、数据类型和抽象数据类型
1.数据类型的相关概念
（1）一些基本的数据结构：可以用数据类型来实现。
（2）而另外一些常用的数据结构：不能直接用数据类型来实现了。
2.数据类型的作用
（1）作用1：约束取值范围。
（2）作用2：约束操作。
3.数据类型的定义
（1）数据类型=值的集合+值得集合上的一组操作。
4.抽象数据类型的相关概念
（1）抽象数据类型：简称为ADT。
（3）抽象数据类型=数学模型+数学模型上的一组操作。(用户自定义的)
5.抽象数据类型的形式定义（重点）
（1）抽象数据类型可用：(D,S,P)三元组来表示。
（2）D是：数据对象。
（3）S是：数据对象上的关系集。
（4）P是：数据对象上的基本操作集。
6.抽象数据类型的定义格式（重点）
7.基本操作的定义格式
（1）参数表：提供用户输入值的同时，还可以使用&符号来返回结果。
（2）初始条件：可有可无。
（3）操作结果：返回的结果。
8.操作数据类型定义举例1-圆（重点）
9.操作数据类型定义举例2-复数（重点）
10.概念小结
四、抽象数据类型的实现
1.抽象数据类型的实现
（1）抽象数据类型的实现：变为一个能用的具体的数据类型。(在计算机上实现)
2.抽象数据类型如何实现
（1）利用已存在的数据类型来说明新的结构。
（2）利用已经存在的操作组合新的操作。
3.C语言实现抽象数据类型
（1）用已有的数据类型定义“ADT”的存储结构。
（2）用函数定义“ADT”的操作。
4.C语言实现抽象数据类型的定义举例1-复数（重点）
五、算法和算法分析
1.《数据结构与算法》
2.算法的定义
（1）算法就是：解决问题的方法和步骤。
3.算法的描述
（1）自然语言：中英文等等。
（2）流程图：传统流程图、NS流程图(盒图)。
（3）伪代码：类语言：类C语言。
（4）程序代码：C语言程序代码、JAVA语言程序代码。
4.算法与程序的关系（重点）
（1）程序=数据结构+算法。
（2）数据结构和算法是相辅相成的。
（3）数据结构通过算法来实现操作，而算法通过数据结构来设计程序。
5.算法的5特性
（1）有穷性；
（2）确定性；
（3）可行性；
（4）有0个或多个输入；
（5）有1个或多个输出。
6.算法设计的4要求
（1）正确性；
（2）可读性；
（3）健壮性；
（4）高效性。
7.算法分析的目的
（1）算法分析的目的1：看算法实际是否可行。
（2）算法分析的目的2：从多个算法中挑选出较优的算法。
8.算法效率（重点）
（1）在算法设计的时候，若满足正确性、健壮性、可读性了，就要开始考虑：算法的效率了。
（2）算法效率包括：时间效率和空间效率。
（3）时间效率：算法所耗费的时间。
（4）空间效率：算法执行过程中所耗费的存储空间。
9.算法时间效率的2种度量方法（重点）
（1）事后统计法。
（2）事前分析法。
10.事前分析法（重点）
（1）算法运行时间：一个简单操作所需的时间 X 简单操作次数。
（2）算法运行时间：每条语句的执行次数 X 该语句执行一次所需的时间。
（3）每条语句的执行次数：又称为语句频度。
（4）所有语句的执行次数：又称为语句频度之和。
（3）假设执行每条语句所需要的时间均为单位时间，则算法运行时间只需要计算所有语句的执行次数，即语句频度之和。
11.事前分析法举例1-nxn矩阵（重点）
（1）注意1：“for循环语句”执行了n+1次，是因为最后还需要判断n+1<=n不成立，因此与循环体相比多算了一次。
（2）注意2：“for循环体”执行了n次，是因为在最后判断了n+1<=n不成立之后，不再进入循环体，所以循环体执行了n次。
(注意区分：循环语句和循环体)
六、算法时间复杂度-渐进表示法
1.算法时间复杂度的基本概念（重点）
（1）为了比较时间效率，我们仅仅比较它们的“数量级”。(如：10n2优于5n3)
（2）同数量级函数：两无穷大之比为不为0的常数。(如：10n2/5n2=2，则两者之间为同数量级)
（3）同数量级函数记法：T(n)=O(f(n))，其中O是数量级的符号。
（4）O(f(n))称作：算法的渐进时间复杂度，简称为“算法时间复杂度”。
2.算法时间复杂度的求法（重点）
3.算法时间复杂度的定义
4.算法时间复杂度的定理1（重点）
（1）定理1：忽略低次幂项和最高次幂系数。
5.算法时间复杂度的计算3步骤（重点）
（1）步骤1：找到语句频度最大的那条语句作为基本语句。
（2）步骤2：计算基本语句的频度，从而得到问题规模n的某个函数f(n)。
（3）步骤3：取其数量级符号"O"表示。
（4）计算本质：算嵌套最深的语句频度。(用n的某个函数来表示次数)(然后取O)
6.算法时间复杂度的计算-4个举例
7.算法时间复杂度计算-特例
8.算法时间复杂度三个分类
9.算法时间复杂度的两个规则
（1）加的复杂度=分别复杂度，再取最大值；
（2）乘的复杂度=复杂度的乘。
10.算法时间复杂度的比较
七、算法空间复杂度-渐进表示法
1.算法空间复杂度定义
2.算法空间复杂度例1-一维数组逆序排列
3.设计好算法的过程
4.知识回顾
八、线性表
1.线性表的定义和特点
2.线性表的4个例子
3.线性表的逻辑特征
4.线性表的案例1-规律一元多项式的运算
（1）规律的一元多项式：用一维数组来表示，数组下标表示指数和系数下标，而数组值存入系数。
（2）稀疏的一元多项式：用二维数组来表示，一维存指数，二维存系数。(可以互换啊)
5.线性表的案例2-稀疏一元多项式的运算
（1）稀疏的一元多项式：用二维数组来表示，一维存系数，二维存指数。(可以互换啊)
