第一章
教材
概述
数据结构与程序设计C语言描述，高教出版社计算机软件系列实践教程。合肥工业大学出版社
11研究内容
软件设计中常用的基本技术实际问题抽象数学模型
构造求解算法
数据结构组织
求解方法
程序设计
测试
数据结构核心课程之一
12术语
数据（data）能够输入到计算机中并能被计算机处理的符号的集合。（广义）
分解
数据元素（dataeleme
t）构成数据的基本单位（具有完整的独立意义）。描述在某些场合还被称为元素、记录、结点、顶点等。数据项（字段）元素的具体信息数据结构（datastructure）构成数据元素之间的结构关系。线性结构树形结构（树型结构）图结构（网状结构）集合数据结构示例：
编号姓名基本工资奖金……序号学号姓名成绩备注
a工资表示例
b成绩表示例
fAA1A11A12A121A2A21A3A31A32A4A311A3
A1
A2A8
A7A5A6
c家族关系示例
d群体间关系示例（连线表示相互认识关系）
逻辑结构线性、树形（树型）、图（网状）、集合存储结构数据结构在内存中的实现形式同样的逻辑结构≠同样的存储结构运算（判断存储结构的好坏）有关数据结构几个方面的联系图逻辑结构运算定义抽象算法性能数据类型存储结构运算实现（算法）算法分析（ADT）
13算法及其描述
算法特定问题的求解方法指令的有限序列满足：1输入0～
个2输出1～
个与输入有特定联系3确定性（无二义性）相同的输入只能有相同的输出4有限性执行次数有限5可行性算法可用计算机在有限时间内实现算法描述语言易懂，灵活自然语言不准确准确，严格计算机语言死板伪语言（类语言）：类pascal、类C、类C算法举例：1求最大公因子（辗转相除法）2韩信点兵问题3幻方问题（纵横图）
f14算法分析
算法的衡量指标：在正确性的前提下（1）时间性能运行算法的时间开销（2）空间性能运行算法的辅助空间规模（3）其它性能如可读性可移植性时间性能（时间复杂度）：以算法运行时间开销来度量
改进与具体机器相关
以算法中语句的执行次数来衡量
简化计算麻烦
以算法中语句的执行次数的数量级来替代数量级：如果变量
的函数f
和g
满足：limf
g
常数kk≠0，则称f
和g
是同一数量级的，并用f
Og
的形式来表示。O1Olog2
O
O
log2
O
2O
3O2
O
难以实现
例子：求解以下程序段的时间复杂度：for（i1i
i）xx1语句执行次数：1次i10
i

1次非0
次
次r