零基础学数据结构第1章概述.ppt

第1章数据结构概述 本章重点和难点 1 数据结构的基本概念2 什么是抽象数据类型3 如何计算算法的时间复杂度 1 1为什么要学习数据结构 1 数据结构的发展变迁数据结构在计算机科学与技术专业中是一门综合性的专业基础课 在国外 数据结构作为一门独立的课程是从1968年才开始设立的 1968年 美国的唐 欧 克努特教授开创了数据结构的最初体系 他所著的 计算机程序设计技巧 第一卷 基本算法 是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作 1 1为什么要学习数据结构 2 数据结构的地位在我国 数据结构已经不仅仅是计算机专业的核心课程 还是其他非计算机专业的主要选修课程之一 数据结构的研究不仅涉及到计算机硬件的研究范围 而且与计算机软件的研究有着更密切的关系 无论是编译程序还是操作系统 都涉及到数据元素在存储器中的分配问题 因此 可以认为数据结构是介于数学 计算机硬件和计算机软件三者之间的一门核心课程 1 1为什么要学习数据结构 开发所有的计算机系统软件和应用软件都要用到各种类型的数据结构 因此 要想更好地运用计算机来解决实际问题 仅掌握几种计算机程序设计语言是难以应付众多复杂问题的 要想有效地使用计算机 充分发挥计算机的性能 还必须学习和掌握好数据结构方面的有关知识 打好 数据结构 这门课程的扎实基础 对于学习计算机专业的其他课程 如操作系统 编译原理 数据库管理系统 软件工程 人工智能等都是十分有益的 1 1为什么要学习数据结构 在计算机发展的初期 人们使用计算机的目的主要是处理数值计算问题 学习数据结构的目的是为了了解计算机处理对象的特性 将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理 与此同时 通过算法训练来提高学生的思维能力 通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高 1 2基本概念和术语 1 数据 data 数据是描述客观事物的符号 能输入到计算机中并能被计算机程序处理的符号集合 它是计算机程序加工的 原料 例如 一个文字处理程序 如Microsoftword 的处理对象就是字符串 一个数值计算程序的处理对象就是整型和浮点型数据 因此 数据的含义非常广泛 如整型 浮点型等数值类型及字符 声音 图像 视频等非数值数据都属于数据范畴 1 2基本概念和术语 2 数据元素 dataelement 数据元素是数据的基本单位 在计算机程序中通常作为一个整体考虑和处理 一个数据元素可由若干个数据项 dataitem 组成 数据项是数据不可分割的最小单位 例如 一个学校的教职工基本情况表包括编号 姓名 性别 籍贯 所在院系 出生年月 职称等数据项 这里的数据元素也称为记录 教职工基本情况如表1 1所示 1 2基本概念和术语 表1 1教职工基本情况表 1 2基本概念和术语 3 数据对象 dataobject 数据对象是性质相同的数据元素的集合 是数据的一个子集 例如 正整数数据对象是集合N 1 2 3 字母字符数据对象是集合C A B C 1 2基本概念和术语 4 数据结构 datastructure 数据结构即数据的组织形式 它是数据元素之间存在的一种或多种特定关系的数据元素集合 在现实世界中 任何事物都是有内在联系的 而不是孤立存在的 同样在计算机中 数据元素不是孤立的 杂乱无序的 而是具有内在联系的数据集合 例如 表1 1的教职工基本情况表是一种表结构 学校的组织机构是一种层次结构 城市之间的交通路线属于图结构 如图1 1 图1 2所示 1 2基本概念和术语 1 2基本概念和术语 5 数据类型 datatype 数据类型是用来刻画一组性质相同的数据及其上的操作 数据类型是按照值的不同进行划分的 在C语言中 按照取值的不同 数据类型还可以分为两类 原子类型和结构类型 原子类型是不可以再分解的基本类型 包括整型 实型 字符型等 结构类型是由若干个类型组合而成 是可以再分解的 例如 整型数组是由若干整型数据组成的 结构体类型的值也是由若干个类型范围的数据构成 它们的类型都是相同的 1 3数据的逻辑结构与存储结构 1 3 1逻辑结构数据元素之间存在4种结构类型 1 集合 结构中的数据元素除了同属于一个集合外 数据元素之间没有其它关系 这就像我们数学中的自然数集合 集合中的所有元素都属于该集合 除此之外 没有其它特性 例如 数学中的正整数集合 5 67 978 20 123 18 集合中数除了属于正整数外 元素之间没有其它关系 数据结构中的集合关系就类似于数学中的集合 集合表示如图1 3所示 1 3数据的逻辑结构与存储结构 2 线性结构 结构中的数据元素之间是一对一的关系 线性结构如图1 4所示 数据元素之间有一种先后的次序关系 a b c是一个线性表 其中 a是b的前驱 b是a的后继 3 树形结构 结构中的数据元素之间存在一种一对多的层次关系 树形结构如图1 5所示 这就像学校的组织结构图 学校下面是教学的院系 行政机构的部和处及一些研究所 1 3数据的逻辑结构与存储结构 4 图结构 结构中的数据元素是多对多的关系 图1 6就是一个图结构 城市之间的交通路线图就是多对多的关系 a b c d e f g是7个城市 城市a和城市b e f都存在一条直达路线 而城市b也和a c f存在一条直达路线 1 3数据的逻辑结构与存储结构 1 3 2存储结构存储结构也称为物理结构 指的是数据的逻辑结构在计算机中存储形式 数据元素的存储结构形式通常有两种 顺序存储结构和链式存储结构 采用顺序存储的字符串 abcdef 的存储结构如图1 7所示 链式存储是把数据元素存放在任意的存储单元里 这组存储单元可以是连续的 也可以是不连续的 数据元素的存储关系并不能反映其逻辑关系 因此需要借助指针来表示数据元素之间的逻辑关系 字符串 abcdef 的链式存储结构如图1 8所示 1 3数据的逻辑结构与存储结构 数据的逻辑结构和物理结构是密切相关的 今后在学习数据结构的过程中 读者将会发现 任何一个算法的设计取决于选定的数据逻辑结构 而算法的实现依赖于所采用的存储结构 1 4抽象数据类型及其描述 1 4 1什么是抽象数据类型抽象数据类型 abstractdatatype 简称ADT 是描述具有某种逻辑关系的数学模型 并对在该数学模型上进行的一组操作 抽象数据类型描述的是一组逻辑上的特性 与在计算机内部表示无关 计算机中的整数数据类型是一个抽象数据类型 不同的处理器可能实现方法不同 但其逻辑特性相同 即加 减 乘 除等运算是一致的 1 4抽象数据类型及其描述 抽象数据类型不仅包括在计算机中已经定义了的数据类型 例如整型 浮点型等 还包括用户自己定义的数据类型 例如结构体类型 类等 一个抽象数据类型定义了一个数据对象 数据对象个数据元素之间的关系及对数据元素的操作 抽象数据类型通常是指用户定义 用来解决应用问题的数据模型 包括数据的定义和操作 例如 C 的类就是一个抽象数据类型 它包括用户类型的定义和在用户类型上的一组操作 1 4抽象数据类型及其描述 抽象数据类型体现了程序设计中的问题分解 抽象和信息隐藏特性 抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题 然后进行建立起一个计算机能处理的数据模型 并把每个功能模块的实现细节作为一个独立的单元 从而使具体实现过程隐藏起来 1 4抽象数据类型及其描述 1 4 2抽象数据类型的描述本书把抽象数据类型分为两个部分来描述 数据对象集合和基本操作集合 其中 数据对象集合包括数据对象的定义及数据对象中元素之间关系的描述 基本操作集合是对数据对象的运算的描述 数据对象和数据关系的定义可采用数学符号和自然语言描述 基本操作的定义格式为 基本操作名 参数表 初始条件和操作结果描述 1 4抽象数据类型及其描述 例如 线性表的抽象数据类型描述如下 1 数据集合线性表的数据对象集合为 a1 a2 an 每个元素的类型均为DataType 其中 除了第一个元素a1外 每一个元素有且只有一个直接前驱元素 除了最后一个元素an外 每一个元素有且只有一个直接后继元素 数据元素之间的关系是一对一的关系 1 4抽象数据类型及其描述 2 基本操作集合线性表的基本操作主要有 1 InitList L 初始化操作 建立一个空的线性表L 这就像是在日常生活中 一所院校为了方便管理 建立一个教职工基本情况表 准备登记教职工信息 2 ListEmpty L 若线性表L为空 返回1 否则返回0 这就像是刚刚建立了教职工基本情况表 还没有登记教职工信息 3 GetElem L i e 返回线性表L的第i个位置元素值给e 这就像在教职工基本情况表中 根据给定序号查找某个教师信息 4 LocateElem L e 在线性表L中查找与给定值e相等的元素 如果查找成功返回该元素在表中的序号表示成功 否则 返回0表示失败 这就像在教职工基本情况表中 根据给定的姓名查找教师信息 5 InsertList L i e 在线性表L中的第i个位置插入新元素e 这就类似于经过招聘考试 引进了一名教师 这个教师信息被登记到教职工基本情况表中 1 4抽象数据类型及其描述 可能你会在大多数教材上看到线性表的抽象数据类型用以下方式描述 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R ai 1 ai D i 2 3 n 1 4抽象数据类型及其描述 需要注意的是 在基本操作的描述过程中 参数传递有两种方式 一种是数值传递 另一种是引用传递 前者仅仅是将数值传递给形参 并不返回结果 后者其实是把实参的地址传递给形参 实参和形参其实是同一个变量 被调用函数通过修改该变量的值返回给调用函数 从而把结果带回 在描述算法时 通过在参数前加上 表示引用传递 如果参数前没有 表示是数值传递 1 5算法 1 5 1数据结构与算法的关系算法与数据结构关系密切 两者既有联系又有区别 数据结构与算法的联系可用一个公式描述 程序 算法 数据结构 数据结构是算法实现的基础 算法总是要依赖于某种数据结构来实现的 算法的操作对象是数据结构 1 5算法 数据结构与算法的区别在于 数据结构关注的是数据的逻辑结构 存储结构以及基本操作 而算法更多的是关注如何在数据结构的基础上解决实际问题 算法是编程思想 数据结构则是这些思想的逻辑基础 1 5算法 1 5 1什么是算法算法 algorithm 是解决特定问题求解步骤的描述 在计算机中表现为有限的操作序列 操作序列包括了一组操作 每一个操作都完成特定的功能 例如 求n个数中最大者的问题 其算法描述如下 1 定义一个变量max和一个数组a 分别用来存放最大数和数组的元素 并假定第一个数最大 赋给max 即 max a 0 1 5算法 2 依次把数组a中其余的n 1个数与max进行比较 遇到较大的数时 将其赋给max for i 1 i n i if max a i max a i 最后 max中的数就是n个数中的最大者 1 5算法 1 5 2算法的五大特性算法具有以下5个特性 1 有穷性 有穷性指的是算法在执行有限的步骤之后 自动结束而不会出现无限循环 并且每一个步骤在可接受的时间内完成 2 确定性 算法的每一步骤都具有确定的含义 不会出现二义性 算法在一定条件下 只有一条执行路径 也就是相同的输入只能有一个唯一的输出结果 3 可行性 算法的每一步都必须是可行的 也就是说 每一步都能够通过执行有限次数完成 4 输入 算法具有零个或多个输入 5 输出 算法至少有一个或多个输出 输出的形式可以是打印输出也可以是返回一个或多个值 1 5 3算法的描述算法的描述方式有多种 自然语言 伪代码 或称为类语言 程序流程图及程序设计语言 如C语言 例如 判断正整数m是否为质数的算法可用以下几种方式描述 1 5算法 1 5算法 1 自然语言描述法我们利用自然语言描述m是否为质数的算法如下 1 输入正整数m 令i 2 2 如果i 则令m对i求余 将余数送入中间变量r 否则 输出 m是质数 算法结束 3 判断r是否为零 如果为零 输出 m不是质数 算法结束 如果r不为零 则令i增加1 转到步骤 2 执行 1 5算法 2 程序流程图法判断m是否为质数的程序流程图如图1 9所示 我们采用类C语言描述和C语言描述如下 1 5算法 3 类语言法 voidIsPrime 判断m是否为质数 scanf m 输入正整数m for i 2 i sqrt m i r m i 求余数 if r 0 如果m能被整除 printf m不是质数 break printf m是质数 1 5算法 4 程序设计语言法 voidIsPrime 判断m是否为质数 printf 请输入一个正整数 scanf d 1 6 1算法设计的四个目标一个好的算法应该具备以下目标 1 算法的正确性算法的正确性 correctness 是指算法至少应该包括对于输入 输出和加工处理无歧义性的描述 能正确反映问题的需求 且能够得到问题的正确答案 1 6算法分析 通常算法的正确性应包括以下4个层次 a 算法对应的程序没有语法错误 b 对于几组输入数据能得到满足规格要求的结果 c 对于精心选择的典型的 苛刻的带有刁难性的几组输入数据能得到满足规格要求的结果 d 对于一切合法的输入都能得产生满足要求的结果 1 6算法分析 2 可读性算法主要是为了人们方便阅读和交流 其次才是计算机执行 可读性 readability 好有助于人们对算法的理解 晦涩难懂的程序往往隐含错误不易被发现 难以调试和修改 1 6算法分析 3 健壮性 robustness 当输入数据不合法时 算法也能做出反应或进行处理 而不会产生异常或莫名其妙的输出结果 例如 求一元二次方程根ax2 bx c 0的算法 需要考虑多种情况 先判断b2 4ac的正负 如果为正数 则该方程有两个不同的实根 如果为负 表明该方程无实根 如果为零 表明该方程只有一个实根 如果a 0 则该方程又变成了一元一次方程 此时若b 0 还要处理除数为零的情况 如果输入的a b c不是数值型 还要提示用户输入错误 1 6算法分析 4 高效率和低存储量效率指的是算法的执行时间 对于同一个问题如果有多个算法能够解决 执行时间短的算法效率高 执行时间长的效率低 存储量需求指算法在执行过程中需要的最大存储空间 效率与低存储量需求都与问题的规模有关 求100个人的平均分与求1000个人的平均分所花的执行时间和运行空间显然有一定差别 设计算法时应尽量选择高效率和低存储量需求的算法 1 6算法分析 1 6 2算法效率评价算法执行时间需通过依据该算法编制的程序在计算机上的运行时所耗费的时间来度量 而度量一个算法在计算机上的执行时间通常有两种方法 1 事后统计方法这种方法有两个缺陷 一是必须依据算法事先编制好程序 这通常需要花费大量的时间与精力 二是时间的长短依赖计算机硬件和软件等环境因素 有时会掩盖算法本身的优劣 因此 人们常常采用事前分析估算的方法评价算法的好坏 1 6算法分析 2 事前分析估算方法这主要在计算机程序编制前 对算法依据数学中的统计方法进行估算 这主要是因为算法的程序在计算机上的运行时间取决于以下因素 a 算法采用的策略 方法 b 编译产生的代码质量 c 问题的规模 d 书写的程序语言 对于同一个算法 语言级别越高 执行效率越低 e 机器执行指令的速度 1 6算法分析 例如 斐波那契数列的算法和语句的的频度如下 每一条语句的频度f0 0 1f1 1 1printf d d f0 f1 1for i 2 i n i n fn f0 f1 n 1printf d fn n 1f0 f1 n 1f1 fn n 1 每一条语句的右端是对应语句的频度 frequencycount 即语句的执行次数 上面算法总的执行次数为T n 1 1 1 n 4 n 1 5n 1 1 6算法分析 1 6 3算法的时间复杂度在进行算法分析时 语句总的执行次数T n 是关于问题规模n的函数 进而分析T n 随n的变化情况并确定T n 的数量级 算法的时间复杂度 也就是算法的时间量度 记作 T n O f n 它表示随问题规模n的增大 算法的执行时间的增长率和f n 的增长率相同 称作算法的渐进时间复杂度 asymptotictimecomplexity 简称为时间复杂度 1 6算法分析 一般情况下 随n的增大 T n 的增长较慢的算法为最优的算法 例如 在下列三段程序段中 给出原操作x x 1的时间复杂度分析 1 x x 1 2 for i 1 i n i x x 1 3 for i 1 i n i for j 1 j n j x x 1 1 6算法分析 常用的时间复杂度所耗费的时间从小到大依次是 O 1 O log2n O n O n2 O n3 O 2n O n 一些常见函数的增长率如图1 10所示 1 6算法分析 1 6 4算法的空间复杂度空间复杂度 spacecomplexity 作为为算法所需存储空间的量度 记作 S n O f n 其中 n为问题的规模 f n 为语句关于n的所占存储空间的函数 1 6算法分析 谈谈关于如何学好 数据结构 的一些粗浅认识 1 明确数据结构的重要性 树立学好数据结构的信心 2 熟练掌握程序设计语言 变腐朽为神奇3 结合生活实际 变抽象为具体4 多思考 多上机实践 1 7学好数据结构的秘诀