【★★★★★ 第1章 绪论总结笔记 2022 9.10】

1.数据结构的基本概念

1. 数据： 数据是信息的载，是描述客观事物属性的数、字符及所有能输入到计算机并被计算机程序识别和处理的符号集合。 数据是计算机程序加工的原料。
2. 数据元素： 数据元素是数据的基本单位，数据元素可由若干 “数据项”组成；
3. 数据项：数据项是构成数据元素的不可分割的最小单位；
4. 数据对象： 数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
5. 数据类型：数据类型是一个值的集合和定义在这个集合上的一组操作的总称；
   • 原子类型： 其值不可再分的数据类型
   • 结构类型： 其值可以再分解为若干成分的数据类型
   • 抽象数据类型：抽象数据组织及与之相关的操作
6. 数据结构：数据结构是互相之间存在一种或多种特定关系的数据元素的集合；数据元素相互之间的关系称为结构；
   7.== 数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法实现依赖所采用的存储结构==；

2.数据结构三要素

逻辑结构、存储结构、数据的运算

数据的逻辑结构

元素之间的逻辑关系，从逻辑上描述数据，与数据的存储无关，是独立于计算机的。逻辑结构分线性结构和非线性结构
线性结构有：单链表、栈、队列、字符串
非线性结构有：图、树、集合

集合：结构中的数据元素之间除了同在一个集合外，没有其他关系
线性结构：结构中数据元素之间只存在一对一的关系
树形结构：结构中的数据元素之间存在一对多的关系
图状结构或网状结构： 结构中的数据元素之间存在多对多的关系

数据的存储结构

存储结构是数据结构在计算机中的表示，也称为物理结构。他包含数据元素的表示和关系的表示；
存储结构可分为：

1. 顺序存储
   把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现；优点：可实现随机存储，每个元素占用最少的存储空间；缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片
2. 链式存储
   不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系；优点：不会出现碎片现象，可以充分利用所有存储单元； 缺点：每个元素因为存储指针而需要额外的存储空间，且只能顺序存储
3. 索引存储
   在存储元素信息的同时，还建立附加的索引表。索引表的每项称为索引项，索引项一般形式为(关键字，地址)‘== 优点：检索速度快 缺点：符加索引表额外占用存储空间，增加和删除需要修改索引表，需要花费过多的时间==
4. 散列存储
   根据元素关键字直接计算出元素的存储地址。又称为哈希存储。 优点：检索、增加、删除结点操作很快； 缺点：若散列函数不好，则会出现元素存储单元的冲突，而解决冲突会增加时间和空间的开销

数据的运算

施加在数据上的运算包括运算的定义和实现。 运算的定义是针对逻辑结构的，指出运算的功能； 运算的实现是针对存储结构的，指出运算的具体操作步骤

常见的数据运算：

• 搜索运算
• 插入运算
• 删除运算
• 更新运算

做题总结：

1. 可以用抽象数据类型来定义一个完整的数据结构
2. 有序表说的是逻辑结构
3. 循环队列(顺序表)，链表，哈希表 都说的是存储结构； 栈是逻辑结构
4. 数据的逻辑结构独立于其存储结构
5. 链式存储时，各个不同结点的存储空间可以不连续，但是结点内的存储单元地址必须连续

3.算法和算法的评价

算法的概念

算法是 对特定问题的求解步骤的一种描述，它的指令是有限序列，期中每条指令表示一个或多个操作；
算法的5个特性：

1. 有穷性 一个算法必须在有穷步之后结束，每一步都可在有穷时间内完成
2. 确定性 算法的每条指令必须是有确切的含义，对于相同的输入应该有相同的输出
3. 可行性 算法中描述的操作都可以通过已经实现的基本运算进行有限次来实现
4. 输入 一个算法有0个或多个输入
5. 输出 一个算法有一个或多个输出

程序步

程序步： 一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关，问题实例的特征： 与问题的具体实例有关的量 eg：对一组特定个数的元素进行排序，对该数组元素的排序是排序问题的一个实例。元素的个数可视为该实例的特征。 程序步数就是程序步的执行次数！

float sum(float list [],const int n){
       float sum=0;               //程序步  1
       for(int i=0;i<n;i++){     //程序步  n+1
       sum+=list[i];             //程序步n
       return sum;              //程序步 1
         }                     //总程序步 2n+3
}
1
2
3
4
5
6
7

算法指标

好的算法应该具有的指标

• 正确性 算法应该能够正确的解决求解问题
• 可读性 算法应具有良好的可读性
• 健壮性 输入非法数据时，算法能做出反应或进行处理，而不会产生莫名其妙的输出结果。
• 效率与低存储量需求 效率指的是算法执行的实际按，存储需求是指算法执行过程中所需要的最大存储空间，两者都与问题的规模有关
  算法的度量：
  算法的度量通过实际按复杂度和空间复杂度

时间复杂度

时间复杂度： 一个语句的频度是指该语句在算法中被重复执行的次数。 算法中所有语句的频度之记为T(n) 算法时间复杂度记为T(n)=O(f(n))
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中f(n)是问题规模n的某个函数。

渐近时间复杂度为
O(1)2)3)n)n)

空间复杂度

算法的空间复杂度S(n)定义为该算法所耗费的存储空间，是问题规模n的函数。记为S(n)=O(g(n))
一个程序在执行时需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现算法所需要的辅助空间。 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。
算法原地工作时指 算法所需要的辅助空间为常量
== O(1) 耗时空复杂度与输入数据大小无关 ==

4.抽象数据类型ADT

ADT 抽象数据类型名
{
数据： 数据元素及其之间关系的定义
运算：
运算1：运算功能的描述
…
运算n：运算功能的描述
}

做题总结：

1. 一个算法应该是问题求解步骤的描述
2. 算法时间复杂度O(n²)表明 算法执行时间与n²成正比
3. ==一个算法中的语句执行次数称为语句的频度。

王海艳课后练习题

王海艳课后练习题：
一、基础题

1. 健壮的算法不会因非法输入数据而出现莫名其妙的状态； 算法的优劣与算法描述的语言有关 ； 数据的逻辑结构独立于数据的存储结构；
2. 逻辑上可以把数据结构分为：线性结构、非线性结构
3. 数据采用链式存储时，存储单元的地址不一定连续
4. 算法的时间复杂度取决于问题的规模
5. 双重for 1-n 的时间复杂度为 O(n²)
   二、简答题

• 数据：计算机加工和处理的对象
• 数据元素：数据的基本单位
• 数据项：组成数据元素的不可分割最小单位
• 数据结构：按某种逻辑关系组织起来的数据元素的集合
• 线性结构(一对一关系)、图形结构(多对多关系)、树形结构(一对多关系)、集合结构（没有关系）；
• 常见的存储结构：顺序存储、链式存储、散列存储、索引存储
• 算法是对特定问题的求解步骤的描述，指令是有限序列；算法的特性：有穷性(算法必须总能在执行有限步后停止)，确定性(算法每一条指令都有确切的含义，没有二义性)，可行性(可以通过已经实现的基本运算执行有限次来实现)，输入(0个或者多个输入)，输出(至少一个输出)；
• 算法和程序的区别和联系： 区别：在语音描述上不同，程序必须是规定的程序设计语言，算法的描述形态有自然语言，伪代码，流程图，程序语言等；算法所描述的步骤必须是有限的，而程序可以无限的执行下去，比如一个死循环可以被称为程序，但是不能是算法 联系：程序是计算机指令的有序集合，是算法用某种程序设计语言的表述，是算法在计算机中的具体实现
• 衡量算法的指标：健壮性(输入不合法可以适当处理)、正确性(无语法功能错误)、可读性(== 算法应具有良好的可读性==)、效率(有效使用存储空间和有高的时间效率)，最优性(选择最佳算法)，可使用性(用户友好性)
• 

(1)执行次数 n ； 复杂度O(n)
(2)执行次数log3ⁿ； 复杂度O(logⁿ)
(3)执行次数n²；复杂度O(n²)
(4)执行次数：|n^1/2|+1; 复杂度：O(n^1/2)