【数据结构复习】第一章绪论

最后更新：2022-07-14 22:18:32 手机定位技术交流文章

基本概念

数据是一个可以输入到计算机并由计算机处理的符号。

2.数据分为两个主要类别:
(1)数字数据:整数、实数等。
(2)非数值数据:文本、图像、声音等。

数据要素是数据的基本单元,数据要素最小的单元是数据项。
例：

学号	姓名
001	黎明
002	李华

学校名称是一个数据项,001黎明和002李华是两个数据元素。

数据结构指有一定关系的一系列数据元素,数据元素是讨论数据结构的最小单元。

5.数据结构分为：
(一)逻辑结构元素与元素之间的逻辑关系。逻辑结构分为:

a.组装结构 b.线性结构(单一数据元素) c.树结构(多于一对) d.图形结构(多对)

(二)计算机结构数据的存储和逻辑结构的映射。存储结构分为:

a.序列存储结构:存储数据元素的连续存储单元,逻辑关系由存储位置表示。
b.Link存储结构:一套任意存储单元,存储数据元素,由指针表示逻辑关系。

算法是描述一个特定问题的解决步骤,一个有限的指令序列。

算法的基本特征是:
该算法必须在有限步骤之后结束,并在有限时间内完成.
(二)确定性:没有模糊性,相同的输入必须得到相同的输出。
(三)可行性:每个指令可以转换成特定的程序设计声明,并在计算机上执行。

3.什么是好算法：
(一)正确性:任何合法的输入都会产生任何正确的结果。
(2)鲁棒性: 对于错误输入, 算法可以进行识别处理.
(三)理解性:易于理解,易于转换成程序。
(4)抽象分类:相关操作步骤构成了一个易于理解的模块。
(5)效率: 时间效率, 空间效率, 短时间, 占用较少的空间.

注: *区分算法的特征与好的算法的特征。

算法的描述方法:
(一)自然语言(二)程序图(三)程序设计语言(四)伪码

5.求时间复杂度
（1）找出基本语句
（2）求出执行次数
以O( )为形式写的多项式的形式

常见时间复杂性
O(log2n)<O(n)<O(nlogn)<O(n²)<O(n³)<…<O(2n次方)<O(n!)

7.空间复杂度
(1)输入/输出占用空间
(二)算法本身占用的空间
(三)执行算法所需的辅助空间