绪论数据结构C语言第三版.ppt

第一章 绪论 1 1从问题到程序1 2有关概念和术语1 3算法及算法分析1 4关于数据结构的学习 计算机解决具体问题方法步骤 从具体问题抽象出一个适当的数学模型 设计一个解此数学模型的算法 用程序语言编写程序什么是数据结构呢 例1 图书馆信息检索系统自动化问题例2 计算机和人对弈问题例3 教学计划编排问题数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科 1 1从问题到程序 1 2有关概念和术语 1 数据 Data 数据是描述客观事物 表达信息的载体 能输入计算机并被识别 存储和处理 2 数据元素 DataElement 数据元素是组成数据的基本单位 是数据集合的个体 由若干个数据项组成 3 数据项 DataItem 数据项 DataItem 是不可分割的并且具有独立含义的最小数据单位 4 数据对象 DataObject 数据对象是性质相同的数据元素的集合 是数据的一个子集 1 2有关概念和术语 4 数据结构 DataStructure 数据结构是指相互之间存在一种或多种特定关系的数据元素集合 数据结构包括如下几个方面 1 数据元素之间的逻辑关系 即数据的逻辑结构 2 数据元素及其关系在计算机存储器中的存储方式 即数据的存储结构 也称为数据的物理结构 3 施加在该数据上的操作 即数据的运算 数据的逻辑结构 四类基本数据结构 集合结构 线性结构 树型结构 图状结构 1 集合结构 结构中的数据元素之间除了同属于一个集合的关系外 无任何其它关系 一种松散的结构 本书不做专门讨论 2 线性结构 结构中的数据元素之间存在着一对一的线性关系 结点之间关系 一对一 特点 开始结点和终端结点都是惟一的 除了开始结点和终端结点以外 其余结点都有且仅有一个前驱结点 有且仅有一个后继结点 顺序表就是典型的线性结构 3 树形结构 结构中的数据元素之间存在着一对多的层次关系 结点之间关系 一对多 特点 开始结点惟一 终端结点不惟一 除终端结点以外 每个结点有一个或多个后续结点 除开始结点外 每个结点有且仅有一个前驱结点 4 图形结构 结构中的数据元素之间存在着多对多的任意关系 结点之间关系 多对多 特点 没有开始结点和终端结点 所有结点都可能有多个前驱结点和多个后继结点 1 2有关概念和术语 线性结构 线性表 栈 队 字符串 数组 广义表非线性结构 树 图 逻辑结构 1 2有关概念和术语 数据结构的形式定义 数据结构是一个二元组Data Structure D R 其中 D是数据元素的有限集 R是D上关系的有限集 例如 学生表中共有7个结点 依次用k1 k7表示 则对应的二元组表示为B K R 其中 K k1 k2 k3 k4 k5 k6 k7 R r r 1 2有关概念和术语 又例如 有如下数据即一个矩阵 对应的二元组表示为B K R 其中 K 2 6 3 1 8 12 7 4 5 10 9 11 R r1 r2 其中 r1表示行关系 r2表示列关系r1 r2 一个二维数组 1 2有关概念和术语 1 2有关概念和术语 数据的物理结构 存储结构 数据的逻辑结构在计算机中的存储表示 映象 两种基本的存储结构 顺序存储结构 链式存储结构5 数据类型 DataType 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称 一般来说 高级语言中的数据类型可分为两类 非结构的原子类型 原子类型的值是不可分解的 C语言中的标准类型 整型 实型 字符型 枚举型 及指针和空类型 结构类型 结构类型的值是由若干成分按某种结构组成的 因此是可以分解的 并且它的成分可以是原子型或结构型 C语言中的数组 结构体 共用体 C语言的数据类型 1 2有关概念和术语 1 2有关概念和术语 6 抽象数据类型 AbstractDataType ADT 抽象数据类型是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作 抽象 的意义在于数学特性的抽象 一个ADT定义了一个数据对象 数据对象中各元素间的结构关系 以及一组处理数据的操作 ADT通常由用户定义且用以表示应用问题的数据模型 通常由基本的数据类型组成 并包括一组相关服务操作 抽象数据类型和数据类型实质上是一个概念 在算法的五大特征中 最基本的是有限性 确定性和可行性 确切的说 算法是对特定问题求解步骤的一种描述 它是指令的有限序列 其中每一条指令表示计算机的一个或多个操作 1 3 1算法的特性 1 有限 穷 性 算法必须在执行有穷步之后结束 而每一步都必须在有穷时间内完成 2 确定性 算法中每一步操作的含义都必须是确定的 不能有二义性 3 可行性 一个算法必须是可行的 即算法中每一操作都能通过已知的一组基本操作来实现 4 输入 一个算法可以有零个或多个输入 5 输出 一个算法有一个或多个输出 1 3算法及算法分析 考虑下列两段描述 1 描述一voidexam1 n 2 while n 2 0 n n 2 printf d n n 2 描述二voidexam2 y 0 x 5 y printf d d n x y 这两段描述均不能满足算法的特征 试问它们违反了哪些特征 解 1 算法是一个死循环 违反了算法的有穷性特征 2 算法包含除零错误 违反了算法的可行性特征 华中科大考研题 1 3算法及算法分析 一个好的算法一般应该具有的基本特征 算法设计的要求 1 正确性 Correctness 正确性 Correctness 的几个层次所设计的程序没有语法错误 所设计的程序对于几组输入数据能够得出满足要求的结果 所设计的程序对于精心选择的典型 苛刻而带有刁难性的几组输入数据能够得到满足要求的结果 程序对于一切合法的输入数据都能产生满足要求的结果 2 可读性 Readability 可读性 Readability 可供理解的难易程度易读性 Legibility 便于阅读的难易程度 3 健壮性 Robustness 鲁棒性 Robustness 指系统的健壮性 4 高效性 Efficiency 高效率 Timeefficiency 低耗 Spaceefficiency 1 3算法及算法分析 1 3 2算法描述 1 用自然语言表示算法 自然语言简单但易于产生二义 2 用流程图表示算法 3 用N S图表示算法 直观但不擅长表达数据的组织结构 4 用伪代码表示算法 类语言 可襒掉语言中的细节 专注算法本身的描述 5 用高级程序设计语言表示算法 较为准确但又比较严谨但细节过多 NiklausE Wirth给出的公式 算法 数据结构 程序 1 3算法及算法分析 1 3 3算法分析和算法执行时间相关的因素 1 算法选用的策略2 问题的规模3 编写程序的语言4 编译程序产生的机器代码的质量5 计算机执行指令的速度分析通常有两种衡量算法效率的方法 事后统计法 1 必须执行程序2 其它因素掩盖算法本质事前分析估算法常用分析算法 时间复杂度和空间复杂度 1 3算法及算法分析 1 时间复杂度一个特定算法的基本运算次数T n 只依赖于问题的规模 通常用整数量n表示 随问题规模n的增大 算法的执行时间的增长率和问题规模n的函数f n 的增长率相同 称作算法的渐进时间复杂度 简称时间复杂度 记作 T n O f n 一个算法的执行时间大致上等于其所有语句执行时间的总和 一个算法是由控制结构和原操作构成 则算法时间取决于两者的综合效果 算法执行时间大致为基本运算 一般是最深层循环内的语句 所需的时间与其运算次数 也称为频度 的乘积 语句频度是指该语句在一个算法中重复执行的次数 原操作是指从算法中选取一种对所研究问题是基本运算的操作 用随着问题规模增加的函数来表征 以此作为时间量度 也就是说 一个算法的时间复杂度是指该算法的基本运算次数 1 3算法及算法分析 多数情况下 求最深层循环内的简单语句 原操作 的重复执行的次数 当难以精确计算原操作的执行次数时 只需求出它关于n的增长率或阶即可 当循环次数未知 与输入数据有关 求最坏情况下的简单语句 原操作 的重复执行的次数 确定时间复杂度时 一般只求出T n 的最高阶 忽略其低阶项和常系数 本质上讲 是一种最高数量级的比较 1 3算法及算法分析 一个没有循环的算法的基本运算次数与问题规模n无关 记作O 1 也称作常数阶 一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系 记作O n 也称线性阶 常量阶 O 1 线性阶 O n 平方阶 O n2 立方阶 O n3 指数阶 O 2n 对数阶 O log2n 二维阶 O nlog2n 各种不同数量级对应的值存在着如下关系 O 1 O log2n O n O n log2n O n2 O n3 O 2n O n 1 3算法及算法分析 常用的时间复杂度 1 3算法及算法分析 常用的时间复杂度频率表一般情况下 随n的增大 T n 的增长较慢的算法为最优的算法 应尽可能选择使用多项式阶O nk 的算法 而避免使用指数阶的算法 1 3算法及算法分析 例 求两个n阶方阵的相加C A B的算法如下 分析其时间复杂度 defineMAX20 定义最大的方阶 voidmatrixadd intn intA MAX MAX intB MAX MAX intC MAX MAX inti j for i 0 i n i for j 0 j n j C i j A i j B i j 该算法中的基本运算是两重循环中最深层的语句C i j A i j B i j 分析它的频度 即 T n O n2 1 3算法及算法分析 例 分析以下算法的时间复杂度 intfun intn inti j k s s 0 for i 0 i n i for j 0 j i j for k 0 k j k s 基本语句或基本操作 return s 解 该算法的基本操作是语句s 其频度 T n O n3 则该算法的时间复杂度为O n3 1 3算法及算法分析 例 两个n n阶矩阵相乘 for i 0 i n i for j 0 j n j c i j 0 for k 0 k n k c i j c i j a i k b k j 1 3算法及算法分析 例如 下列程序段for i 1 i n i for j i j n j x 有一个二重循环 语句x 的执行频度为 n n 1 n 2 3 2 1 n n 1 2而该语句执行次数关于n的增长率为n2 即时间复杂度为O n2 1 3算法及算法分析 例 分析以下算法的时间复杂度 voidfunc intn inti 0 s 0 while s n i s s i 解 对于while循环语句 设执行的次数为m i从0开始递增1 直到m为止 有 s 0 1 2 m 1 m m 1 2 并满足s m m 1 2 n 则有m T n O 所以 该算法的时