数据结构第1章概论.ppt

1 数据结构数据结构 Data StructureData Structure 计算机科学与技术系计算机科学与技术系 主讲教师：路游主讲教师：路游 2 2 学时数：学时数：6464（4444讲课讲课+20+20上机）上机） 学分：学分：4 4 教材：教材：数据结构（数据结构（C C语言版）语言版） 严蔚敏严蔚敏 吴伟民吴伟民 编著编著 清华大学出版社清华大学出版社 参考书：参考书： 数据结构题集数据结构题集 (C(C语言版语言版) ) 严蔚敏、严蔚敏、 吴伟民著吴伟民著 数据结构课程设计数据结构课程设计苏仕华等编著苏仕华等编著 机械机械 工业出版社工业出版社 数据结构题集数据结构题集(C(C语言篇语言篇) )习题与解析习题与解析 （修订版）（修订版）李春葆编著李春葆编著 清华大学出版社清华大学出版社 上机：第上机：第5-145-14周，周，星期一星期一，1-21-2节节 ，3 3教教-404-404 内容安排内容安排 章章内容内容学时学时章章内容内容学时学时 1 1 绪论绪论 2 2 7 7 图图 6 6 2 2 线性表线性表 6 6 8 8 动态存储管理动态存储管理略略 3 3 栈和队列栈和队列 6 6 9 9 查找查找 6 6 4 4 串串 4 4 1010内部排序内部排序 4 4 5 5 数组和广义表数组和广义表 4 4 1111外部排序外部排序略略 6 6 树和二叉树树和二叉树 6 6 1212文件文件略略 4 4 第第1 1章章 序序 论论 1.1 1.1 计算机基本概念计算机基本概念（复习）（复习） 1.2 1.2 数据结构基本概念数据结构基本概念 1.3 1.3 抽象数据类型概念抽象数据类型概念 1.4 1.4 算法效率的度量算法效率的度量 作业 5 5 1.1 1.1 计算机基本概念计算机基本概念 ( (复习）复习） 计算机系统计算机系统 硬件系统软件系统硬件系统软件系统 Q1 Q1 硬件系统硬件系统由哪几部分组成？由哪几部分组成？ Q2 Q2 微型微型计算机与其他计算机的区别？计算机与其他计算机的区别？ Q3 Q3 内存与外存内存与外存的不同之处是？的不同之处是？ Q4 Q4 计算机内常用到哪些计算机内常用到哪些数制数制？ Q5Q5 计算机主要计算机主要技术指标技术指标有哪些有哪些? ? 硬件硬件 概念概念 复习复习 软件软件 概念概念 复习复习 Q1 Q1 软件系统软件系统包含哪些软件？包含哪些软件？ Q2 Q2 什么是什么是系统软件和应用软件系统软件和应用软件？ Q3 Q3 机器语言、汇编语言、高级语言机器语言、汇编语言、高级语言的区别？的区别？ 6 6 Q1Q1：计算机硬件系统由哪几部分组成？：计算机硬件系统由哪几部分组成？ 答：计算机硬件系统由答：计算机硬件系统由 部分组成：部分组成： 也可浓缩也可浓缩 为为3 3部分部分 ： 存储器存储器 CPU CPU I/O I/O接口及设备接口及设备 人脑：人脑： 感受感受 判断判断 计算计算 记忆记忆 反应反应 电脑：电脑： 输入输入 控制控制 运算运算 存储存储 输出输出 控制器控制器 输 输 入入 运算器运算器 存储器 存储器 输出输出 主主 机机 5 5 7 7 Q2Q2：微型计算机与一般意义上的计算：微型计算机与一般意义上的计算 机有什么区别？机有什么区别？ 其本质特征是答 ： 运算器和控制器集成在一块IC芯片上 这种CPU简称MPU 8 8 Q3Q3：内存与外存是一回事吗？：内存与外存是一回事吗？ 能被CPU直接控制（BUS直连）的存储器称为内存 通过I/O接口才能被CPU控制的存储器称为外存 答：不是一回事。它们的区别是： I/OI/O接口接口 输 入 运算器 内存储器 控制器 输 出 BUS 外 存 储 器 CPU 9 9 Q4Q4：计算机内常用到哪些数制？计算机内常用到哪些数制？ A. A. （1101100111011001）B BB. B. （75 75 ）D D C. C. （ 37 37 ）O OD. D. （2A2A）H H 答案： C 2进制(B) 8进制(O ) 10进制( D ) 16进制(H ) 例3：下列四种不同进制的无符号数中，最小的数是 例2：下列数据中，有可能是八进制数的是 A. 238 B. 764 C. 396 D. 789 例1 ：10 (B) D 10 (O ) D 10 (H ) D 2 8 16 1010 Q5Q5： 计算机主要技术指标有哪些？计算机主要技术指标有哪些？ CPU一次能处理的二进制位数，它与数据总线 的根数有关，如8位机，16位机、32位机等等 运算器做一次“加”动作的最小可靠时间，如奔 4 机器主频2.8G（Hz） CPU每秒能执行加法指令的次数（MIPS） bit，Byte，KB，MB，GB，TB 练：微机中1K字节表示的二进制位数是： 1B=8bit 1KB= 210B 1MB= 210KB 1GB=210MB A. 1000 B. 81000 C. 1024 D. 81024 答案： D 字 长 主 频 运算速度 主存容量 1111 Q1Q1： 软件系统包含哪些软件软件系统包含哪些软件 ？ 裸机 系统软件 答： 包含系统软件和应用软件两大类 1212 Q2Q2：什么是系统软件？什么是应用软件？什么是系统软件？什么是应用软件？ 答 ： 系统软件管理计算机系统各部分，使之 高效工作，同时为上层提供服务 。 应用软件处于系统软件的上层，帮助计 算机用户完成特定领域的工作 。 系统软件中最重要的是操作系统（Operating System）， 它是一个大型的、优秀的程序，管理着计算机的全部软、 硬件资源，并提供人机交互的界面。 1313 Q3Q3：机器语言、汇编语言、高级语言的区别？机器语言、汇编语言、高级语言的区别？ 用二进制代码直接表示的语言，是计算机用二进制代码直接表示的语言，是计算机 唯一能识别、执行的语言唯一能识别、执行的语言 符号化了的机器语言（即用助记符来写程符号化了的机器语言（即用助记符来写程 序，靠汇编程序翻译成机器码才能执行序，靠汇编程序翻译成机器码才能执行 ） 接近自然英语和数学公式的语言（要通过接近自然英语和数学公式的语言（要通过 编译或解释程序翻译成机器码）编译或解释程序翻译成机器码） 答 ： 低级语言 面向机器，执行速度快，效率高； 高级语言 面向问题，易理解，易移植。 机器语言 汇编语言 高级语言 1414 1.2 1.2 数据结构基本概念数据结构基本概念 Q1 Q1 什么是数据结构？什么是数据结构？ Q2 Q2 学习数据结构有什么用？学习数据结构有什么用？ Q3 Q3 数据结构涵盖的主要内容？数据结构涵盖的主要内容？ 讨论 ： 1515 Q1Q1：什么是数据结构？：什么是数据结构？ 1616 “ “学生学生” ”表格表格 1717 “ “课程课程” ”表格表格 1818 选课单包含如下信息选课单包含如下信息 学号学号 课程编号课程编号 成绩成绩 时间时间 学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系 学生 (学号,姓名,性别,籍贯) 课程 (课程号,课程名,性别,籍贯) 选课 (学号,课程号,成绩) 1919 UNIXUNIX文件系统的系统结构图文件系统的系统结构图 / (root) binlibuseretc mathdsswyintaoxie Stack.cppQueue.cppTree.cpp 2020 术语：数据、数据元素和数据项术语：数据、数据元素和数据项 （见教材P4定义）： 数据(data)所有能被计算机识别、存储和处理的符号的集 合（包括数字、字符、声音、图像等信息 ）。 数据元素(data element)是数据的基本单位，具有完整 确定的实际意义(又称元素、结点，顶点、记录等） 。 数据项(Data item)构成数据元素的项目。是具有独立含 义的最小标识单位（又称字段、域、属性 等）。 三者之间的关系：数据 数据元素 数据项 例：班级通讯录 个人记录 姓名、年龄 2121 Q1Q1：什么是数据结构？：什么是数据结构？ 答答: : ( (见见教材教材P5P5) ) 是相互之间存在一种或多种特是相互之间存在一种或多种特 定定关系关系的的数据元素数据元素的集合，表示为：的集合，表示为： （数值或非数值） Data_Structure=（D, S） 或：是指同一数据元素类中各元素之间存在的关系。 亦可表示为：S（D, R） 或 B=（K, R ） 元素有限集关系有限集 2222 数据：数据：数据是信息的载体，是描述客观事数据是信息的载体，是描述客观事 物的数字、字符、以及所有能输入到计算物的数字、字符、以及所有能输入到计算 机中，被计算机程序识别和处理的符号的机中，被计算机程序识别和处理的符号的 集合。集合。 数值性数据数值性数据 非数值性数据非数值性数据 数据对象：数据对象：数据的子集。具有相同性质的数据的子集。具有相同性质的 数据成员（数据元素）的集合。数据成员（数据元素）的集合。 整数数据对象整数数据对象 N N = 0, = 0, 1, 1, 2, 2, 学生数据对象学生数据对象 2323 Q2Q2：学习数据结构有什么用？：学习数据结构有什么用？ 答：答：计算机内的数值运算依靠方程式，而计算机内的数值运算依靠方程式，而非数值运非数值运 算算（如表、树、图等）则要依靠数据结构。（如表、树、图等）则要依靠数据结构。 这是一门研究这是一门研究非数值计算非数值计算的程序设计问题中计算机的的程序设计问题中计算机的操操 作对象作对象以及它们之间的以及它们之间的关系和操作关系和操作等等的学科。等等的学科。 程序设计实质好算法好结构 同样的数据对象，用不同的数据结构来表示， 运算效率可能有明显的差异。 2424 逻辑结构逻辑结构 数据结构数据结构 物理（存储）结构物理（存储）结构 数据运算数据运算 Q3Q3：数据结构数据结构涵盖的内容？涵盖的内容？ 2525 解释解释1 1： 什么叫数据的逻辑结构？什么叫数据的逻辑结构？ 答：答：指数据元素之间的逻辑关系。即从逻辑关系指数据元素之间的逻辑关系。即从逻辑关系 上描述数据，它与数据的存储无关，是上描述数据，它与数据的存储无关，是独立于计独立于计 算机算机的。逻辑结构可细分为的。逻辑结构可细分为4 4类：类： 集合结构：集合结构： 仅同属一个集合仅同属一个集合 线性结构线性结构: : 一对一（一对一（1:1) 1:1) 树树 结结 构构: : 一对多（一对多（1:n)1:n) 图图 结结 构构: : 多对多多对多 (m:n)(m:n) 非线性 线 性 2626 例：用图形表示下列数据结构，并指出它例：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。们是属于线性结构还是非线性结构。 （1 1） S=(D, R)S=(D, R) D= D= a, b, c, d, e, f a, b, c, d, e, f R=( R=(a,e), (b,c), (c,a), (e,f), (f,d)a,e), (b,c), (c,a), (e,f), (f,d) 解： 上述表达式可用图形表示为： b c a e f d 此结构为线性的。 2727 （2 2） S=(D, R)S=(D, R) D= D= d d i i | 1i5 | 1i5 R=( R=(d d i i , d , d j j ), i 数据关系：数据关系： 基本操作基本操作 ： ADT ADT抽象数据类型抽象数据类型名名 ADT 常用 定义 格式 3535 例：给出自然数例：给出自然数( (NaturalNatural NumberNumber ) )的抽象数据类型定义的抽象数据类型定义 。 A ADTDT NaturalNatural_ _NumberNumber is is objectsobjects: : 一个整数的有序子集合，它开始于一个整数的有序子集合，它开始于0 0，结束于机器能，结束于机器能 表示的最大整数表示的最大整数 ( (MAX INTMAX INT ) ) functionsfunctions: : 对于所有的对于所有的 x, y x, y Natural_Number Natural_Number； TRUE, TRUE, FALSE FALSE Boolean Boolean； +,+, -, , = = ,=-, , = = ,=等都是可用等都是可用 的服务。的服务。 Zero ( )Zero ( )： NaturalNatural NumberNumber 返回返回 0 0 IsZero(x)IsZero(x)： Boolean if (x=0) Boolean if (x=0) 返回返回TRUETRUE else else 返回返回 FALSEFALSE Add(x, y)Add(x, y)： NaturalNatural NumberNumber if (x+y = MAX INT)if (x+y = MAX INT)返回返回 x+yx+y else else 返回返回MAX INTMAX INT Subtract(x,y): Subtract(x,y): NaturalNatural NumberNumber if (xy) if (xy)返回返回0 else 0 else 返回返回x-yx-y Equal(x,y): Boolean Equal(x,y): Boolean if (x= y)if (x= y)返回返回TRUE else TRUE else 返回返回FALSEFALSE Successor(x) :Successor(x) : NaturalNatural NumberNumber if (x = if (x = MAX INTMAX INT) )返回返回x else x else 返回返回x+1x+1 endend Natural_NumberNatural_Number 3636 Q3 Q3 抽象数据类型如何抽象数据类型如何表示和实现表示和实现？ 抽象数据类型可以通过固有的数据类型（如抽象数据类型可以通过固有的数据类型（如 整型、实型、字符型等）来表示和实现。整型、实型、字符型等）来表示和实现。 注1 ：它有些类似C语言中的结构（struct)类型， 但增加了相关的服务。 注2 ：教材中用的是类C语言（介于伪码和C语言之 间）作为描述工具。其描述语法见P10-11。 但上机时要用具体语言实现，如C或C+等 3737 1.4 1.4 算法效率的度量算法效率的度量 Q1. Q1. 什么是算法？什么是算法？ Q2. Q2. 如何评判一个算法的好坏？如何评判一个算法的好坏？ Q3. Q3. 算法的效率如何度量？算法的效率如何度量？ Q4. Q4. 算法的存储空间需求算法的存储空间需求 讨论： 3838 Q1. Q1. 什么是算法？什么是算法？ 答：算法是解决某一特定类型问题的有限运算序列。是一答：算法是解决某一特定类型问题的有限运算序列。是一 系列输入转换为输出的计算步骤。系列输入转换为输出的计算步骤。 算法有5个基本特性 ： 有穷性 确定性 可行性 输入 输出 对于任意一组合法输入值，在执行有穷步骤之后一定 能结束，而且每一步都能在有限时间内完成。 算法中每一条指令必须有确切的含义，不应该具有二 义性。并且在任何条件下，算法都只有唯一的一条执 行路径，即对于相同的输入只能得到相同的输出。 算法中描述的操作都可以通过已经实现的基本操作执 行有限次来实现 一个算法有0个或多个输入，这些输入都是来自某个特 定的对象的集合。 一个算法有1个或多个输出，这些输出都是与输入有着 某些特定关系的值。 3939 Q2. Q2. 如何评判一个算法的好坏？如何评判一个算法的好坏？ 正确性：算法应满足求解具体问题的需求。 对正确性的理解，有如下4种不同的程度： 1.不含语法错误； 2.对几组输入数据能够得到满足规格需求的解； 3.对精心选择的典型数据能够得到满足规格需求的解； 4.对一切合法的输入数据都能得到满足规格需求的解。 可读性：算法要便于交流，要有助于别人对算法的理解。晦涩 难读的程序往往隐藏了很多的错误。 健壮性：对于非法的输入，算法要能给出适当的反映，而不会出 现莫名其妙的错误。处理出错的方法不应是中断程序的 执行，而应是返回一个表示错误或错误性质的值。 好的时空性：算法的效率要高，同时所占的存储量要低。 通常以第3层意义 的正确性作为衡量 一个程序是否合格 的标准。 常用时间复杂度来衡量常用空间复杂度来衡量 4040 Q3. Q3. 算法的效率如何度量？算法的效率如何度量？ 通常有两种衡量算法效率的方法: 事后统计法 事前分析估算法 缺点：1必须执行程序 2其它因素可能会掩盖算法本质 效率指的是运行时间，与算法执行时间相关的因素如下： 1算法选用的策略 2问题的规模 3编写程序的语言 4编译程序产生的机器代码的质量 5计算机执行指令的速度 衡量算法的效率通常采用的方法，为此，需要引进一个 时间复杂度的概念。 4141 如何估算一个算法的时间复杂度？如何估算一个算法的时间复杂度？ 一个特定算法的“运行工作量”的大小，只依赖于问题的 规模（通常用整数 n 表示），或者说，它是问题规模的 函数。 一个算法的组成通常由控制结构（顺序、分支、循环） 与原操作（固有数据类型的操作）两部分组成，所以算 法的运行工作量也就取决于这两者的综合效果 事前分析估算方法的基本思路是：从算法中选取一种对于 所研究的问题来说是基本操作的原操作，以该基本操作在 算法中重复执行的次数作为算法运行时间的衡量准则。 由于基本操作的执行时间通常囿界于一个常数，所以 算法的执行时间 与 基本操作执行次数之和 成正比。 4242 算法的时间的渐近表示算法的时间的渐近表示 假设某算法的执行时间是T(n)，其中变量 n 可以是输入或输 出量，也可以是两者之和，还可以是它们之一的某种测度(例如， 数组的维数，图的边数等)。f(n)是在事前分析中确定的某个形式 很简单的函数，例如，nm，log2n，2n，n!等。它是独立于机器和 语言的函数，而T(n)则与机器和语言有关。 假如随着问题规模n的增长，算法执行时间T(n)的增长率和 f(n) 的增长率相同，则可记作： T (n) = O(f(n) 称f(n)为算法的渐近时间复杂度，简称时间复杂度。 大写符号给出了函数T的一个上限。大写符号的定义如下： T(n)(f(n)，当且仅当存在正的常数c和n0， 使得对于所有的nn0，有 T(n)c*f(n) 4343 3n+2=O(n) /* 3n+23n+2=O(n) /* 3n+2 4n4n for n for n 2 */2 */ 3n+3=O(n) /* 3n+33n+3=O(n) /* 3n+3 4n4n for n for n 3 */3 */ 100n+6=O(n)100n+6=O(n) /* 100n+6 /* 100n+6 101n101n for n for n 10 */10 */ 10n10n 2 2 +4n+2=O(n+4n+2=O(n 2 2 ) /* 10n) /* 10n 2 2 +4n+2+4n+2 11n11n 2 2 for n for n 5 */5 */ 6*26*2 n n +n+n 2 2 =O(2=O(2 n n ) ) /* 6*2 /* 6*2 n n +n+n 2 2 7*27*2 n n for n for n 4 */4 */ 例： 算法的时间的渐近表示（续）算法的时间的渐近表示（续） 4444 函数 名称 1 logn n nlogn n2 n3 2n n！ 常数 对数 线性 n个logn 平方 立方 指数 阶乘 常用的渐近函数 多项式关系： (1)(log2n)(n)(nlog2n)(n2)(nn) 指数关系： (2n)(n!)(nn)，且对于任意的m0，有2nnm 4545 估算一个算法的时间复杂度（示例）估算一个算法的时间复杂度（示例） 例1：两个矩阵相乘的算法 void mult(int a, int b, int i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult 基本操作: 乘法操作ai,k*bk,j 算法执行次数：是最高幂次为3的多项式 时间复杂度: O(n3) 4646 估算一个算法的时间复杂度（示例）估算一个算法的时间复杂度（示例） 例2：选择排序 void select_sort(int i n-1; +i ) j = i; / 选择第 i 个最小元素 for ( k = i+1; k n; +k ) if (ak aj ) j = k; if ( j != i ) aj ai 基本操作: 比较(数据元素)操作ak aj 算法执行次数：是最高幂次为2的多项式 时间复杂度: O(n2) 4747 例例3 3：分析以下程序段的时间复杂度。：分析