数据结构的基本概念
数据（Data）
是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
数据
包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。
数据元素（Data Element）
是组成数据的基本单位 ，是数据集合的个体，在
计算机中通常作为一个整体进行考虑和处理
数据对象（Data Object）
是性质相同的数据元素的集合，是数据的一个子集
什么是数据结构
是相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。
逻辑结构、存储结构和运算合
称为三要素
Data_Structure=（D, R）
其中，D—元素有限集，R—关系有限集
数据结构的研究内容
数据的逻辑结构
• 数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关
• 数据的逻辑结构可以看作是从具体问题抽象出来的数据模型
• 逻辑结构主要分为
集合 线性 树 图
数据的存储结构
• 数据的存储结构（又叫物理结构）是逻辑结构用计算机语言的实现
• 数据的存储结构依赖于计算机语言
存储方式对比
•
顺序存储
——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系
•
链式存储
——借助指示元素存储地址的指针表示数据元素间的逻辑关系
数据结构的内容
算法
算法的定义
• 算法——解决某一特定问题的具体步骤的描述，是指令的有限序列。
• 每一条指令表示一个或多个操作。
算法与程序的关系
• 算法着重体现思路和方法，程序着重体现计算机的实现;
• 程序中的指令必须是机器可执行的，算法中的指令无此限制;
• 一个算法若用计算机语言来书写，它就可以是一个程序。
算法的表示方式
• 用自然语言描述算法
• 用流程图描述算法
• 用数学语言或约定的符号语言描述算法
• 用C++的函数形式来描述算法
算法的特征
• 算法应满足具体问题的需求—
正确性
：程序中不含任何语法错误；程序对于几组输入数据能够得出满足要求的结果；程序对于精心选择的、典型的、苛刻的并带有刁难性的几组输入数据能够得出满足要求的结果；程序对于一切输入数据都能得出满足要求的结果。
• 一个算法必须由一系列具体操作组成，
具体
指的所有操作都必须经过已实现的基本操作有限次来实现，并且所有操作都是可读的、可执行的，每一操作必须在有限时间内完成。
• 算法中的所有操作都必须有
确切
的含义，不能产生歧义，算法的执行者或阅读者都能明确其含义及如何执行。
• 对于任意一组合法输入值，在执行
有限步骤
之后一定能结束，即：算法中的每个步骤都能在
有限时间
内完成
•算法应具备良好的
可读性
，一般算法的逻辑必须清楚、结构简单，所有标识符必须具有实际含义，能
见名知义
。
•当输入
数据非法时
，算法能作适当的处理并作出反应，而不应死机或输出异常结果。需
健壮
算法评价标准
•一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函
数。
•
时间复杂度 T(n)
基本操作执行次数通常是问题规模n的某个函数，记作f(n)。 •假设随着问题规模 n 的增长，算法执行时间的增长率和 f(n)
的增长率相同，可记作：
– T (n) = O(f(n))
– T (n) 为算法的(渐近)时间复杂度。
•
空间复杂度 S(n)
用空间复杂度作为算法所需存储空间的量度，记做： S(n)=O(f (n)) 。具体的为程序执行过程中由于需要所申请的内存空间。