《01-概述》由会员分享，可在线阅读，更多相关《01-概述（11页珍藏版）》请在金锄头文库上搜索。
1、1,数据结构Data Structure,2,第一章 概 述,第一章 概 述1.1 研究内容 1.2 术语 1.3 算法及其描述 1.4 算法分析,3,1.1 研究内容,软件设计中常用的基本技术,实际问题,抽象,实际问题,实际问题,构造求解算法,测试,程序设计,数据结构组织,数据结构,4,1.2 术语,数据（data） 能够输入到计算机中并能被计算机处理的符号分解 的集合.（广义） 数据元素（data element） 构成数据的基本单元（具有完整的独描叙 立意义）。在场合还被称为元素、记录、结点、顶点等。 数据项（字段） 元素的具体信息 数据结构（data structure）构成数据元素之
2、间的结构关系。线性结构 树形结构（树型结构）图结构（网状结构）集合,5,1.2 术语,数据结构示例：,(a) 工资表示例,(b) 成绩表示例,6,1.2 术语,A,A2,A1,A11,A3,A12,A311,A21,A32,A31,A121,A1,A2,A3,A5,A4,A6,A8,A7,(c) 家族关系示例,(d) 群体间关系示例 （连线表示相互认识关系）,7,1.2 术语,逻辑结构 线性、树形（树型）、图（网状）、集合 存储结构 数据结构在内存中的实现形式 同样的逻辑结构同样的存储结构 运算（判断存储结构的好坏）有关数据结构几个方面的联系图,逻辑结构,逻辑结构,运算实现（算法）,存储结构,
3、运算定义,抽象 数据 类型 （ADT）,8,1.3 算法及其描述,算法 特定问题的求解方法指令的有限序列 满足：(1) 输入 0n个(2) 输出 1n 个 与输入有特定联系(3) 确定性（无二义性） 相同的输入只能有相同的输出(4) 有限性 执行次数有限(5) 可行性 算法可用计算机在有限时间内实现,9,1.3 算法及其描述,算法描述语言易懂，灵活 自然语言 不准确 准确，严格 计算机语言 死板伪语言（类语言）：类pascal、类C、类C+算法举例：1.求最大公因子（辗转相除法）2.韩信点兵问题3.幻方问题（纵横图）,10,1.4 算法分析,算法的衡量指标：在正确性的前提下（1）时间性能运行算
4、法的时间开销（2）空间性能运行算法的辅助空间规模（3）其它性能如可读性/可移植性时间性能（时间复杂度）：以算法运行时间开销来度量 改进 与具体机器相关 以算法中语句的执行次数来衡量简化 计算麻烦 以算法中语句的执行次数的数量级来替代数量级：如果变量n的函数f(n)和g(n)满足：lim f(n)/g(n)=常数 k (k,0)，则称f(n)和g(n) 是同一数量级的，并用f(n)=O(g(n)的形式来表示。O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)| O(2n) O(n!)难以实现,11,1.4 算法分析,例子：求解以下程序段的时间复杂度： for（i=1; i=n; i+）x=x+1; 数量级为：lim f(n)/g(n)= lim (3n+2)/n = 3，则时间复杂度为为O (n) 练习：(1) for (i=1; in; i+) for (j=1; j= i; j+) x+; (2) i = 1; while (in) i = i*2;,语句执行次数,1次,n+1次,n次,n次,共：3n+2次,
