程序数据结构算法程序设计方法和工具语言.ppt

《程序数据结构算法程序设计方法和工具语言.ppt》由会员分享，可在线阅读，更多相关《程序数据结构算法程序设计方法和工具语言.ppt（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 绪论程序程序=数据结构数据结构+算法算法+程序设计方法和工具程序设计方法和工具+语言语言什么是数据结构 数据结构是一门研究非数值计算的程序设计问题中计算机数据结构是一门研究非数值计算的程序设计问题中计算机数据结构是一门研究非数值计算的程序设计问题中计算机数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科的操作对象以及它们之间的关系和操作等的学科的操作对象以及它们之间的关系和操作等的学科的操作对象以及它们之间的关系和操作等的学科v背景：应用领域非数值计算 对 象具有一定结构的数据 主要问题对象的特性及对象之间的关系v计算机解决问题的步骤：分析（对

2、象间关系，数学语言描述）数学模型算法编程解答v实例 （1）图书馆书目检索系统自动化问题线性表 （2）计算机和人对弈问题树 （3）多叉路口交通灯的管理问题图v地位：综合性的专业基础课第一章 绪论基本概念和术语v数据所有能输入到计算机中并被计算机程序处理的符号的总称。例：图象、声音等。v数据元素数据的基本单位，程序中通常作为一个整体考虑。它可包括若干个数据项。v数据项数据想4是数据不可分割的最小单位。v数据对象性质相同的数据元素的集合。v数据结构相互之间存在一种或多种特定关系（1:1，1:n，m:n)的数据元素的集合。v逻辑结构 Data_Structure=(D,S)二元组 D是数据元素的有限集

3、，S是D上关系的有限集。第一章 绪论1.物理结构(存储结构)数据结构在计算机中的表示。包括数据元素的表示和关系的表示。1.数据元素：位串。2.数据元素之间的关系：顺序映象顺序存储结构：元素在存储器中的 相对位置非顺序映象链式存储结构：指示元素存储地址的指针v数据类型是一个值的集合和定义在这个值集上的一组操作的总称。引入数据类型，对用户来说，实现了信息隐蔽。v抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示无关。vADT和数据类型实质上是一个概念，但其范畴更广，包括用户在设计软件系统时自己定义的数据类型。第一章

4、绪论一个含抽象数据类型的软件模块通常应包含定义定义、表表示示和实现实现三个部分。ADT=（D，S，P）P表示对D的基本操作集。ADT按其值特性可分为原子类型、固定聚合类型和可变聚合类型。ADT 抽象数据类型名数据对象：数据关系：伪码基本操作：ADT 抽象数据类型名 基本操作定义格式：基本操作名（参数表）初始条件：操作结果：参数分赋值参数和引用参数（&开头）抽象数据类型的表示与实现第一章 绪论算法和算法分析v算法：对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。算法具有五个重要特性：有穷性、确定性、可行性、输入和输出。v算法设计的要求：正确性、可读性、健壮性、效率。v时间复杂度q事后统计的方法q事前分析估算方法 算法时间依赖函数的规模，取决于控制结构和原操作的综合效果，以原操作重复执行的次数(频度)作为算法的时间度量。q平均时间复杂度、最坏时间复杂度v空间复杂度