作者：whisper

链接：http://proprogrammar.com:443/article/762

声明：请尊重原作者的劳动，如需转载请注明出处

1.1 数据结构的研究内容
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现

1.1 数据结构的研究内容

N.沃思（Niklaus Wirth） 教授提出：
程序=算法+数据结构
《数据结构》所处的地位：
介于数学、计算机硬件和计算机软件三者之间的 一门核心课程

1.2 基本概念和术语

（1）数据（data） —所有能输入到计算机中去的描述客观事物的符号
—数值性数据
—非数值性数据（多媒体信息处理）
（2）数据元素（data element） —数据的基本单位，也称结点（node）或记录（record）
（3）数据项（data item） —有独立含义的数据最小单位，也称域（field）
（4）数据对象（Data Object） ：相同特性数据元素的集合，是数据的一个子集整数数据对象
N = { 0， ±1， ±2， … }
学生数据对象
⑩学生记录的集合
（5）数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
数据结构 2+1（两个层次和一个操作）
逻辑结构
数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。
存储结构（物理结构）
数据元素及其关系在计算机存储器中的存储方式。
操作（运算、行为）
执行不同功能的算法

划分方法一

（1）线性结构----
有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。
例如：线性表、栈、队列、串
（2）非线性结构----
一个结点可能有多个直接前趋和直接后继。
例如：树、图

划分方法二

集合——数据元素间除“同属于一个集合”外，无其它关系
线性结构——一个对一个，如线性表、栈、队列
树形结构——一个对多个，如树
图形结构——多个对多个，如图
存储结构分为：
顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系
链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系
索引存储结构——字典中单词存储关系
散列存储结构——地址与散列函数之间建立的一种映射

数据类型

定义：在一种程序设计语言中，变量所具有的数据种类
C 语言：
基本数据类型： char int float double void
构造数据类型：数组、结构体、共用体、文件
数据类型是一组性质相同的值的集合， 以及定义于这个集合上的一组运算的总称

抽象数据类型

抽象数据类型 （ADTs: AbstractData Types）
—更高层次的数据抽象
—由用户定义，用以表示应用问题的数据模型
—由基本的数据类型组成， 并包括一组相关的操作

说明： 抽象数据类型的表示与实现

抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。
如何学习抽象数据类型？

1.3 算法和算法分析

算法定义

一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列

算法的特性

输入 有 0 个或多个输入
输出 有一个或多个输出（处理结果）
确定性 每步定义都是确切、无歧义的
有穷性 算法应在执行有穷步后结束
有效性 每一条运算应足够基本

算法设计的评价

正确性
可读性
健壮性
高效性（时间代价和空间代价）

算法效率的度量

算法效率：时间和空间来度量
时间复杂度
空间复杂度

算法效率的度量： 时间复杂度

算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量
事后统计
事前分析估计
方式 1.事后统计：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分
缺点：
①必须先运行依据算法编制的程序
②所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的劣
方式 2.事前分析估计：
一个高级语言程序在计算机上运行所消耗的时间取决于：
①依据的算法选用何种策略
②问题的规模
③程序语言
④编译程序产生机器代码质量
⑤机器执行指令速度

时间复杂度的渐进表示法

一般情况下，算法中基本操作重复执行的时间是问题规模 n 的某个函数 f（n） ，算法执行的时间的增长率和 f（n） 的增长率相同，称渐近时间复杂度。
时间复杂度的表示方法有两种：
方法 1：大 O 法 T（n） = O（f（n））
它表示随问题规模 n 的增大，算法执行时间的增长率和 f（n） 的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。
方法 2：语句频度法
计算该语句重复执行的次数，又叫频度统计法。
说明：
数学符号“O”的定义为：若 T（n） 和 f（n） 是定义在正整数集合上的两个函数，则T（n） = O（f（n）） 表示存在正的常数 C 和 n0，使得当 n≥n0 时都满足0≤T（n） ≤Cf（n） 。

分析算法时间复杂度的基本方法

找出语句频度最大的那条语句作为基本语句
计算基本语句的频度得到问题规模 n 的某个函数 f（n）
取其数量级用符号“O”表示

引例与分析

时间复杂度是由嵌套最深层语句的频度决定的

算法效率的度量： 空间复杂度

（1）定义
（2）三个组成部分
存储算法本身所占用的空间
算法的输入/输出数据占用的空间
算法在运行过程中临时占用的辅助空间
（3）原地工作：若辅助空间相对于输入数据量是常数，则称此算法是原地工作。
说明：若所占空间量依赖于特定的输入，按最坏情况来分析

算法设计的要求

（1）正确性
（2）可读性
首先是给人读，然后才是机器执行
（3）健壮性， 容错性
（4）效率与低存储量需求
重点 1：基本术语：数据结构
重点 2：抽象数据类型
重点 3：算法优劣的评价标准
重点 4：数据结构的学习方法

重点 3： 算法优劣的评价标准： 时间复杂度

（1）当 f（n） 为对数函数、幂函数、或它们的乘积时，算法的运行时间是可以接受的，称这些算法是有效算法；当 f（n） 为指数函数或阶乘函数时，算法的运行时间是不可接受的，称这些算法是无效的算法。
（2）随着 n 值的增大，增长速度各不相同， n 足够大时，存在下列关系：
对数函数<幂函数<指数函数

增长率由慢到快
尽量少用指数阶的算法

亲爱的读者：有时间可以点赞评论一下