数据结构知识详解 第一章 绪论思维导图,数据结构知识详解 第一章 绪论总结
Yyds干货库存
知识框架
1.数据结构的基本概念1.1基本概念和术语1.1.1数据定义：它是信息的载体，是能够输入计算机并被计算机程序识别和处理的数字、字符和所有符号的集合。
数据的组成：
整数、实数等数字字符和声音、图像、视频等非数字类型1.1.2数据元素的定义：数据元素是数据的基本单位，通常作为一个整体来考虑和处理。具有一定意义的基本单位，在计算机中通常作为一个整体来处理，也称为元素和记录。
数据元素的组成：
几个数据项的例子：
个人信息表的每一行都是一个数据元素。
1.1.3数据项的定义：构成数据元素的最小单位，几个数据项可以构成一个数据元素。
注：数据项是数据的最小单位。
1.1.4数据对象的定义：具有相同性质的数据元素的组合，是数据的子集。
例子
1.1.5抽象数据类型的定义：抽象数据组织及相关操作。
构成：
对象数据关系基本操作集中抽象数据类型的标准格式；
1.1.6数据类型定义：在这个集合上定义的一组值和一组操作。
角色：
用于描述变量或表达式的取值范围，并描述可以执行的运算类型：
原子类型定义：其值不可分离的数据类型示例：int integer结构类型定义：其值可细分为若干组件的数据类型示例：int integer抽象数据类型定义：其值可细分为若干组件的数据类型示例：int integer 1.1.7数据结构定义：彼此具有一个或多个特定关系的数据元素的集合
数据结构的三个要素：
逻辑结构把问题抽象出来，然后研究存储结构，研究具体细节。数据的操作1.2数据结构的三要素1.2.1数据的逻辑结构。逻辑结构是指数据对象中数据元素之间的逻辑关系，即从逻辑关系上描述数据。
1.线性结构：
定义：结构中的数据元素之间只有一对一的关系。
例子
2.非线性结构：
定义：结构中的数据元素之间不是一对一的关系。
树形结构
一对多关系
图形结构
多对多关系
聚集
除了属于同一个集合，没有其他关系。
1.2.2数据存储结构的定义：数据对象在计算机中的存储表示，也称为物理结构。
数据字段：当一个数据元素由几个数据项组成时，数据项的表示称为数据字段。
数据结构的存储方法：1。顺序存储方法
定义：逻辑上相邻的节点存储在物理上相邻的存储单元中，节点之间的关系通过存储单元的相邻性来体现。
优势：
可以实现随机存取(或顺序存取)。每个元素占用空间最少的缺点：
只能使用一个相邻的存储单元块，这可能导致更多的外部分段访问结构。
随机存取：存取第N个数据时，可以不存取第(N-1)个数据而直接存取第N个数据(也叫顺序存取):存取第N个数据时，必须先存取第(N-1)个数据。2链存储方法：
定义：逻辑上相邻的节点不要求物理上相邻，节点之间的逻辑关系用指示节点存储地址的指针来表示。
优势：
不会出现碎片，所有存储单元都可以得到充分利用。缺点：
每个元素都占用额外的存储空间来存储指针，并且只能顺序访问。注意：
节点中存储单元的地址：相邻节点的某个连续存储空间：不一定连续。3.索引存储方法
定义：存储元素信息时，建立一个附加的索引表。
优势：
检索速度快的缺点：
额外的索引表会占用额外的空间。添加或删除数据时，修改索引表会花费更多时间。注意：
索引表的每一项称为一个索引项，索引项的一般形式是关键字，地址关键字：标识唯一节点地址：指向上述节点4的指针。哈希存储方法。
定义：根据节点的关键字直接计算出节点的存储地址，比如location=Hash(key)
优势：
检索、添加和删除节点的快速操作的缺点：
如果哈希函数不好，就会出现元素存储单元冲突。解决冲突会增加时间和空间开销注意：
这种方法本质上是顺序存储方法的扩展。key:关键字hash():计算地址的方法，Hash函数位置：存储本节点地址1.2.3数据的操作定义：对数据施加的操作，包括操作的定义和实现。
注意：
运算的定义：对于逻辑结构，指出运算的作用。操作的实现：对于存储结构，指出操作的具体操作步骤。2算法和算法的评价。2.1算法的基本概念定义：算法是对具体问题求解步骤的描述。它是一个有限的指令序列，其中每个指令代表一个或多个操作。
2.1.1指令可由计算设备执行，如人或机器。它们可以是计算机指令，也可以是我们常用的语言。
1.算法
为了解决某一个问题或某一类问题，需要将指令表达为一定的操作序列，它包括一组操作，每个操作执行一个特定的功能。
2.算法的例子
把大象放在冰箱里：
1.打开冰箱门。2.把大象塞进去。3.关上冰箱门。2.1.2算法的五个特点。1.有限的。
一个算法必须总是在执行有限步后结束，并且每一步都必须在有限时间内完成。
示例：
经常写无限循环代码，对有限性不满足。
2.确实的事情
每一条指令都要有确切的含义，同样的输入只能产生同样的输出，读者在理解上不会有歧义。
3.可行性
算法中描述的所有操作都可以通过执行已经实现了有限次的基本操作来实现。
4.投入
有零个或多个输入，这些输入来自一组特定的对象。
5.输出
输出的算法是信息处理的结果，没有输出的算法是没有意义的。
2.1.3算法的评价(四个方面)1。正确性
该算法能正确解决问题。
右水平：
程序中没有语法错误。对于合法的输入数据，该程序可以产生令人满意的输出结果。对于非法输入的数据，该程序可以产生令人满意的结果。该程序对精心选择的甚至是困难的测试数据都有令人满意的输出结果。一级要求最低，色谱四级最难。我们几乎不可能逐一验证所有输入是否正确。一般以3级作为算法正确性的标准。
2.可读性
帮助人们阅读、理解和交流。
3.稳健性
当输入非法数据时，算法可以适当的响应或处理，而不是出现莫名其妙的错误。
4.高效率和低存储要求
效率：指的是时间。效率越高越好。该算法时间短，效率高。
储物：指空间。存储越低越好。是指算法在执行过程中需要的最大存储空间。
2.2算法效率的度量2.2.1标准时间复杂度和空间复杂度的度量2.2.2度量方法1。事后统计法
主要是通过设计的测试程序和数据，用计算机定时器来比较不同算法编译的程序的运行时间，从而确定算法的效率。
缺乏
需要根据算法预先编译一个程序，这通常需要花费大量的时间和精力。时间的比较取决于计算机软硬件等环境因素，有时会掩盖算法本身的优劣。操作系统、编译器、运行框架和其他软件的差异也会影响它们的结果。程序的运行时间往往和测试数据的规模有很大关系，在小测试数据面前往往体验不到高效的算法。2.事前分析和估计方法。
在计算机程序编译之前，根据统计方法对算法进行估计。
在计算机上运行程序所花费的时间取决于以下因素：
方法——所采用的策略和方法好坏算法3354的基本翻译所生成的代码的质量是由软件对问题的输入所支持的。定标器执行指令的速度2.2.3时间复杂度1。频率
定义：
N:表示算法问题的规模T(n)是算法问题规模N的函数分析的时间复杂度，主要分析T(n)的数量级。3.算法的基本操作。
定义：最深循环中的语句
该算法基本运算的频率与T(n)在同一数量级
4.算法的时间复杂度
定义：用算法基本运算的频率f(n)来分析。
算法的时间复杂度标记：T(n)=O(f(n))
O: T (n)的数量级称为O:T(n ^ 1):常数级；O(2):线性序；O(logn):对数阶；O (n):常见的平方阶T(n)O(1)O(log(n))O(n . log(n))O(n)O(n)O(n)O(2)O(n！) O (n)复杂度计算规则加法规则T(n)=T1(n)T2(n)=O(f(n))O(g (n))=O(max(f(n)，g(n)))
乘法法则t(n)=t1(n)* T2(n)=o(f(n))* o(g(n))=o(f(n)* g(n))
影响时间复杂度的因素问题规模n输入数据的性质(输入数据的初始状态)最坏情况和平均情况最坏情况时间复杂度的定义：最坏情况时间复杂度
平均时间复杂度定义：当所有输入概率相等时，算法的期望运行时间。
最佳时间复杂度的定义：最佳情况下的时间复杂度。
2.2.4空间复杂度算法的空间复杂度：记为S(n)，表示算法消耗的空间，是问题规模n的函数。
渐进空间复杂度：简称空间复杂度，记为S(n)=O(g(n))
分析空间复杂度，只需要分析除输入和程序之外的额外空间。
2.2.5时空复杂度分析方法1。观察方法(循环主题中的变量与循环条件无关)
(1)计算方法：列举归纳得出。
(2)分类：
递归类：递归程序一般使用递归T (n)=1t (n-1)=11t (n-2)=n-1t (1)的公式，即T(n)=O(n)
非递归直接计数
(3)例子
递归类
时间复杂度为O(n)
非递归类
时间复杂度为o (n)
2.设置循环次数T方法(循环主题中的变量与循环条件相关)
(1)计算方法：假设t次结束。
(2)例子
时间复杂度为O (log (n))
不太好做。如果有帮助，希望大家给我一键三通的支持。谢谢你。
程序员技术栈原创作品，博客作者。如需转载，请联系作者，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。