数据结构与算法-简介
程序员文章站
2024-01-19 10:27:46
...
本文围绕以下两个部分展开:
一、数据结构
二、算法
一、数据结构
1. 基本概念
(1)数据
是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。
数据包括数值类型(如整型、实型等)和非数值类型(如字符、声音、图形、视频等)。
(2)数据元素(记录)
是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。
(3)数据项
一个数据元素可以由若干个数据项组成。
数据项是数据不可分割的最小单位。
(4)数据对象
是性质相同的数据元素的集合,是数据的子集。
性质相同的数据元素:指数据元素具有相同数量和类型的数据项。
在实际应用中,处理的数据元素通常具有相同性质,因为数据对象是数据的子集,因此在不产生混淆的情况下,将数据对象简称为数据。
(5)数据结构
是相互之间存在一种或多种特定关系的数据元素的集合。
2. 数据结构分类:
(1)逻辑结构:
指数据对象中数据元素之间的相互关系。
分为以下4种:
1)集合结构
数据元素之间:除了同属于一个集合外,它们之间没有其他关系。
2)线性结构
数据元素之间:一对一的关系。
3)树形结构
数据元素之间:一对多的层次关系。
4)图形结构
数据元素之间:多对多的关系。
(2)物理结构(存储结构)
指数据的逻辑结构在计算机中的存储形式。
1)顺序存储结构
把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。
2)链式存储结构
把数据元素存放在任意的存储单元里,这组存储单元可以是连型的,也可以是不连续的。
需要用一个指针存放数据元素的地址,通过这个地址就可以找到相关联的数据元素的位置。
(3)二者比较
逻辑结构是面向具体问题的,是为了解决某个问题,在对问题理解的基础上,选择一个合适的数据结构来表示数据元素之间的逻辑关系。
物理结构是面向计算机的,其基本目标就是将数据及其逻辑关系存储到计算机的内存中。
3. 抽象数据类型
(1)数据类型:
指一组性质相同的值的集合,及定义在此集合上的一些操作的总称。
(2)抽象:
指抽取出事物具有的普遍性的本质。它抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。它是一种思考问题的方式,隐藏了繁杂的细节,只保留实现目标所必需的信息。
(3)抽象数据类型
Abstract Data Type,ADT。指一个数学模型,及定义在该模型上的一组操作。
它定义了:一个数据对象、数据对象中数据元素之间的关系、及对数据元素的操作。
二、算法
1. 定义
算法是解决特定问题求解步骤的描述。在计算机中表现为:指令的有限序列,并且每条指令表示一个或多个操作。
2. 五个特性
(1)输入、输出
有0个或多个输入,至少有1个或多个输出。
(2)有穷性
算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成。
(3)确定性
算法的每一个步骤都具有确定的含义,不会出现二义性。
(4)可行性
算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成。
3. 算法设计的要求
(1)正确性
指算法至少应该具有输入、输出和加工处理无歧义性,能正确反映问题的需求,能够得到问题的正确答案。
从低到高分为以下4个层次:
1)算法程序没有语法错误。
2)算法程序对于合法的输入数据能够产生满足要求的输出结果。
3)算法程序对于非法的输入数据能够得出满足规格说明的结果。
4)算法程序对于精心选择的、甚至刁难的测试数据都有满足要求的输出结果。
(2)可读性
算法要便于阅读、理解和交流。
(3)健壮性
当输入数据不合法时,算法也能作出相关处理,而不是产生异常或莫名其妙的结果。
(4)时间效率高和存储量低
4. 算法效率的度量方法:事后统计分析法(不科学、不准确)、事前分析估算法。
5. 函数的渐近增长
6. 算法的时间复杂度(最坏时间复杂度)
(1)推导大O阶的方法:
(2)常见的时间复杂度:
7. 算法的空间复杂度
整理时重点参考:《大话数据结构》程杰著
一、数据结构
二、算法
一、数据结构
1. 基本概念
(1)数据
是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。
数据包括数值类型(如整型、实型等)和非数值类型(如字符、声音、图形、视频等)。
(2)数据元素(记录)
是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。
(3)数据项
一个数据元素可以由若干个数据项组成。
数据项是数据不可分割的最小单位。
(4)数据对象
是性质相同的数据元素的集合,是数据的子集。
性质相同的数据元素:指数据元素具有相同数量和类型的数据项。
在实际应用中,处理的数据元素通常具有相同性质,因为数据对象是数据的子集,因此在不产生混淆的情况下,将数据对象简称为数据。
(5)数据结构
是相互之间存在一种或多种特定关系的数据元素的集合。
2. 数据结构分类:
(1)逻辑结构:
指数据对象中数据元素之间的相互关系。
分为以下4种:
1)集合结构
数据元素之间:除了同属于一个集合外,它们之间没有其他关系。
2)线性结构
数据元素之间:一对一的关系。
3)树形结构
数据元素之间:一对多的层次关系。
4)图形结构
数据元素之间:多对多的关系。
(2)物理结构(存储结构)
指数据的逻辑结构在计算机中的存储形式。
1)顺序存储结构
把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。
2)链式存储结构
把数据元素存放在任意的存储单元里,这组存储单元可以是连型的,也可以是不连续的。
需要用一个指针存放数据元素的地址,通过这个地址就可以找到相关联的数据元素的位置。
(3)二者比较
逻辑结构是面向具体问题的,是为了解决某个问题,在对问题理解的基础上,选择一个合适的数据结构来表示数据元素之间的逻辑关系。
物理结构是面向计算机的,其基本目标就是将数据及其逻辑关系存储到计算机的内存中。
3. 抽象数据类型
(1)数据类型:
指一组性质相同的值的集合,及定义在此集合上的一些操作的总称。
(2)抽象:
指抽取出事物具有的普遍性的本质。它抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。它是一种思考问题的方式,隐藏了繁杂的细节,只保留实现目标所必需的信息。
(3)抽象数据类型
Abstract Data Type,ADT。指一个数学模型,及定义在该模型上的一组操作。
它定义了:一个数据对象、数据对象中数据元素之间的关系、及对数据元素的操作。
二、算法
1. 定义
算法是解决特定问题求解步骤的描述。在计算机中表现为:指令的有限序列,并且每条指令表示一个或多个操作。
2. 五个特性
(1)输入、输出
有0个或多个输入,至少有1个或多个输出。
(2)有穷性
算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成。
(3)确定性
算法的每一个步骤都具有确定的含义,不会出现二义性。
(4)可行性
算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成。
3. 算法设计的要求
(1)正确性
指算法至少应该具有输入、输出和加工处理无歧义性,能正确反映问题的需求,能够得到问题的正确答案。
从低到高分为以下4个层次:
1)算法程序没有语法错误。
2)算法程序对于合法的输入数据能够产生满足要求的输出结果。
3)算法程序对于非法的输入数据能够得出满足规格说明的结果。
4)算法程序对于精心选择的、甚至刁难的测试数据都有满足要求的输出结果。
(2)可读性
算法要便于阅读、理解和交流。
(3)健壮性
当输入数据不合法时,算法也能作出相关处理,而不是产生异常或莫名其妙的结果。
(4)时间效率高和存储量低
4. 算法效率的度量方法:事后统计分析法(不科学、不准确)、事前分析估算法。
5. 函数的渐近增长
6. 算法的时间复杂度(最坏时间复杂度)
(1)推导大O阶的方法:
(2)常见的时间复杂度:
7. 算法的空间复杂度
整理时重点参考:《大话数据结构》程杰著
上一篇: Python绘制3d螺旋曲线图实例代码