数据结构与操作系统.pptVIP

第1章 绪论 要求： 了解数据、数据元素、数据对象、数据结构、数据的逻辑结构和物理结构等概念； 了解抽象数据类型的定义和表示； 掌握类C和C之间的差异； 重点掌握算法效率的度量方法，学会分析简单算法的性能。（了解常见函数的增长率） 第1章 绪论 科学计算 非数值计算 处理对象 数值--字符、表格、图像等 1.1 什么是数据结构 数学模型—算法—程序—解答 方程 非数值计算 非数学方程 例2 下棋 井子棋 格局-结点 结局-叶子 倒长树 非线性数据结构 BCW3.1 数据结构是一门研究非数值计算的程序问题中计算机的操作对象以及它们之间的关系和操作等等的学科 逻辑结构+存储结构+算法 唐.欧.克努特 专业基础课 程序设计 编译程序 OS DBases 1.2 基本概念和术语 数据Data 符号表示 数据元素 Data Element 数据基本单位 数据项 Data Item 最小单位 数据对象 Data Object 元素集合 数据结构 Data Structure 关系、元素集合 关系 集合 线性 树形 结构 图（网状） 形式定义：二元组 Data_Structure= (D,S) D 元素有限集 S D关系有限集 例4 复数 实数集合有序对 C1,C2 例5 事务管理 Group = (P, R) P {T, G1…Gn, S11…Snm} R {R1, R2} R1 T, Gi R2 Gi, Sij 1= i =3, 1= j =2 逻辑结构 抽象 高级 数据项 数据元素 物理结构 存储结构 位（串）元素 结点node 算法实现 顺序 － 相对位置 非顺序映象结构 － 指针 数据类型 集合＋操作 原子 结构—数据结构 低级 高级 抽象数据类型 定义、表示、实现 面向对象 C＋＋等 （D，S，P） 数据对象 D上的关系集 D上的操作集 原子，固定，可变聚合 指针 （VAR pascal） 例6 三元组定义 1.3 抽象数据类型的表示与实现 类C 简明、清晰，易转换成程序 例7 三元组的类C表示及实现 1.4 算法和算法分析 1.4.1 算法 步骤 特性：有穷性，确定性，可行性，输入输出 1.4.2 算法设计的要求 正确性，可读性，健壮性，效率（时空） 1.4.3 算法效率的度量 事后统计（程序，硬件） 事前分析 不考虑语言，硬件 规模，策略 1 算法的时间复杂度 Time Complexity 基本操作重复执行的次数 T（n）= O（f（n）） n 问题的规模 例 矩阵乘法 T（n）= O（n3） 频度 语句重复执行的次数 可变 时间复杂度 （输入有关）最坏，最好，平均 排序 2 空间复杂度 Space Complexity S（n）= O（f（n）） 原地操作，不需额外空间 作业： * * 例1 查书 索引表文件的检索 记录 线性的数据结构 例3 交叉口交通灯颜色数 顶点-通路 连线边-顶点间矛盾关系 图1.3 图—非线性 例 分析以下程序段的时间复杂度 for (i=1;in;i++) { y=y+1; /* 1 * / for (j=0; j=(2*n); j++) x++; /* 2 * / } 语句1的频度是：n-1 语句2的频度是： 则该程序段的时间复杂度： T(n)= 常见函数的时间复杂度按数量递增排列及增长率: 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) …… k次方阶O(nk) 指数阶O(2n)