概念

相互之间存在一种或多种特定关系的数据元素的集合 逻辑结构，存储结构，运算合称为三要素

数据结构形式定义

数据结构是一个二元组 Data_Structure = (D,S) D是数据元素的有限集，S是D上关系的有限集

基本术语

数据

所有能被计算机识别，存储和处理的符号的集合

数据元素

是数据的基本单位，具有完整的实际意义。一个数据元素可由若干个数据项组成

数据项

构成数据元素的项目。是数据不可分割的最小单位

数据类型

指一个类型和定义在这个类型上的操作集合。

抽象数据元素

抽象定义的，没有实际含义的数据元素

抽象数据类型

用户自己定义的数据类型

数据结构涵盖的内客

逻辑结构

线性结构

线性表，栈，队，串，数组

非线性结构

树结构，图结构，集合结构

物理结构(存储结构)

是数据的逻辑结构在计算机存储器内的表示(或映像)。它依赖于计算机

分类

顺序结构，链式结构，索引结构，散列结构

数据运算

在数据的逻辑结构上定义的操作算法

分类

插入运算，删除运算，修改运算，查找运算，排序运算

数据类型与抽象数据类型的区别

数据类型

是一个值的集合和定义在该值上的一组操作的总称

抽象数据类型

由用户定义，用以表示应用问题的数据类型。它由基本的数据类型构成，并包括一组相关的服务(或称操作) 它与数据类犁实质上是一个概念，但其特征是使用与实现相分离，实行数据封装和信息隐蔽(独立于计算机)

抽象数据类型用三元组表示

ADT = (D,S,P) D:数据对象 S:D上的关系集 P:D上的操作集

ADT常用定义格式

算法和算法分析

算法

是对特定问题求解步骤的一种描述，是指令的有限序列，输入转换输出的计算步骤 好的程序设计：好算法+好结构

基本特性

有穷性，确定性，可行性，必有输出

评价指标

正确性，可读性，健状性，高效率(常用时间复杂度衡量)与低存储量(常用空间复杂度衡量)需求

算法描述方式

自然语言，程序设计语言，流程图，类高级语言(类C语言，类Pascal语言等)

类C语言描述语法

类C语言精选了C语言的一个核心子集，也做了若干扩充，以利于描述

时间复杂度

若存在两个正常数c,n0，对于所有的$n>=n_0$，有| f(n) |<= c| g(n) |， 则记作f(n)=O(g(n))

频度：是指该语句重复执行的次数

定理：若$$A(n)=a_mn^m+a_{m-1}n^{m-1}+…+a_1n+a_0是一个m次多项式，则A(n)=0(n^m)$$

空间复杂度

算法所需存储空间的量度

记作：S(n)=O(f(n))

其中n为问题的规模(或大小)