数据结构与算法笔记（王卓⽹课+教材+⼤话数据结构）
数据结构与算法笔记（王卓⽹课+教材+⼤话数据结构）
##最新整理
绪论、算法（P1-P9）1.4数据起源结构
数据结构是⼀门研究⾮数值计算之间的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科
学习进程：
1.4.1基本概念和术语
数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输⼊给计算机处理的符号合集。⽽这些符号必须包括两个前提：
（1） 可以输⼊到计算机中
（2） 能被计算机程序处理
像声⾳，图像，视频等是可以通过编码的⼿段变成字符数据来处理
1.4.2 数据元素
数据元素：是组成数据的、有⼀定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。Eg：在⼈类中，数据元素就是⼈！
数据项：⼀个数据项可以有若⼲个数据项组成。 Eg：⼈的眼、⽿、⿐
注：数据项是数据不可分割的最⼩单位。
真正让讨论问题时，数据元素才是数据结构中间⾥数据模型的着眼点。
1.4.4数据对象
数据对象：是性质相同的数据元素的⼏何，是数据的⼦集。
1.4.5数据结构
数据结构：相互之间存在⼀种或多种特定关系的数据元素的集合。
研究数局结构的意义：为编写出⼀个“好”程序，必须分析待处理对象的特性及各处理对选哪个之间存在的关系。
1.5逻辑结构与物理结构
1.5.1逻辑结构
逻辑结构：指数据对象中数据元素之间的相互关系。
1. 集合结构：集合结构中的数据元素除了同属于⼀个集合外，它们之间没有其他关系。
2. 线性结构：线性结构中的数据之间是⼀对⼀的关系。
3. 树形结构：⼀对多的层次关系
4. 图形结构：多对多的关系
在⽤⽰意图表⽰数据的逻辑结构时，要注意两点
5. 将每⼀个数据元素看做⼀个结点，⽤圆圈表⽰
6. 元素指甲的逻辑关系⽤节点之间的连线表⽰，如果这个关系是有⽅向的。那么⽤有箭头的连线表⽰1.5.2物理结构
定义：指数据的逻辑结构在计算机中的存储形式
数据元素的存储结构形式：顺序存储、链式存储
1. 顺序存储结构：是把数据元素存放在地址连续的存储单元⾥，其数据间的逻辑关系和物理关系是⼀致的。
2. 链式存储结构：当整个结构时刻处于变化中，顺序存储是不科学的。
则引出链式存储结构是把数据元素存放在任意的存储单元⾥，这组存储单元可以是连续的也可以是不连续的。
注：
1.存储器主要是针对内存⽽⾔，像硬盘，软盘等外部存储器的数据结构组织通常⽤⽂件结构来描述。
2.如何存储数据元素之间的逻辑关系，是实现物理结构的重难点。
1.6抽象数据类型
1.6.1数据类型
：是指⼀组性质相同的值的集合及定义在此集合上的⼀些操作的总称
在c语⾔中数据类型分为两类：
原⼦类型：是不可以再分解的基本类型，包括整形、实型、字符型
结构类型：由若⼲个类型组合⽽成，是可以再分解的。
Eg：整形数组由若⼲个整形组成
数据类型的作⽤：
1.约束变量或常量的取值范围
2.约束变量或常量的操作
1.6.2抽象数据类型（ADT）
：
是指⼀个数学模型及定义在该模型上的⼀组操作
1.从问题中抽象出数据模型（逻辑结构）
2.定义在数据模型上的⼀组抽象运算
3.不考虑计算机内的存储结构与运算的具体实现算法
定义抽象数据类型格式：
体现了程序设计中间问题分解、抽象和信息隐藏的特性。
##第⼆章 算法 第⼆章 算法
2.4算法定义
算法是解决待定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表⽰⼀个或多个操作。
简⽽⾔之：算法就是解决问题的⽅法和步骤
算法与程序
算法是解决问题的⼀个⽅法或⼀个过程，考虑如何将输⼊转换成输出，⼀个问题可以有多种算法。程序使⽤某种程序设计语⾔对算法的具体实现 程序 = 数据结构 + 算法 数据结构通过算法实现操作
算法根据数据结构设计程序ADT 抽象数据名{ 数据对象<；数据对象的定义> 数据关系<；数据关系的定义> 基本操作<；基本操作的定义>}ADT 抽象数据名
1
2
3
4
5基本操作定义格式： 基本操作名（参数表） 初始条件（初始条件描述） 操作结果（操作结构描述）
1
2
3
4
2.5算法特性
算法具有五个基本特性：输⼊、输出、有穷性、确定性、可⾏性
2.5.1输⼊输出
⼀个算法有0个输⼊或多个输⼊
算法⾄少有⼀个或多个输出
2.5.2有穷性
指算法在执⾏有限的步骤之后，⾃动结束⽽不会出现⽆限循环，并且每⼀个步骤在可接受的时间完成
2.5.3确定性
算法的每⼀步骤都具有确定的含义，不会出现⼆义性
2.5.4可⾏性
2.6算法设计的要求
2.6.1正确性 有没有语法错误 对于合法的输⼊数据能够产⽣满⾜要求的输出结果 对于⾮法的输⼊数据能够得出满⾜规格说明的结果
对于精⼼选择的，甚⾄刁难的测试数据都有满⾜要求的输出结果
通常第三层意义上的作为衡量⼀个算法是否合格的标准
2.6.2可读性
算法设计的另⼀⽬的为了便于阅读、理解和交流
2.6.3健壮性
当输⼊数据不合法时。算法也能做出相关处理，⽽不是产⽣异常或莫名其妙的结果
算法分析
⼀个好的算法⾸先具备正确性，然后是健壮性可读性，在⼏个⽅⾯都满⾜的情况下主要考虑算法的效率，算法的效率主要通过以下两个⽅⾯来考虑： 时间效率：算法所消耗的时间 空间效率：算法执⾏过程中所耗费的存储空间
c语言好的网课时间效率和空间效率有时是冲突的
算法时间效率的度量 算法的每⼀步都必须是可⾏的，也就是说，每⼀步都能够通过执⾏有限次数完成
1算法⾄少应该具有输⼊输出和加⼯处理⽆歧义性、能正确反映问题的需求，能够得到问题的正确答案。
算法的正确通常在⽤法上有很⼤的差别，⼤体为以下四个层次
1
2 **两种度量⽅法：**
1
事后统计 将算法实现测算其时间和空间的开销。
缺点：编写程序实现算法将花费较多的时间和精⼒；所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本⾝的优劣。
事前分析
对算法所消耗资源的⼀种估算⽅法。 
发表评论