DS01课程概述.ppt

1、数据结构与算法,江汉大学数学与计算机科学学院 韩 海,概 述,2,课 程 概 况,课程名称：数据结构与算法 学时：48(讲授)+16(实验)=64 课程性质：专业基础课 先修课程：高级语言程序设计，面向对象程序设计 主要内容：主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行简单的分析和评价,3,本单元的重要概念,数据结构逻辑结构物理结构 运算算法线性表 树图检索 排序 从下面的概念开始： 数据数据元素数据对象 数据集合 注：红色要求在本次课掌握，黑色要求了解,4,一行描述一个人的各项信息，被视为一个完整的“数据元素”或者“数据对象”，每一个数据元素又是由若干个分项

2、构成。单个值(如性别)可视为数据元素但不是数据对象。,从数据(信息)开始,5,数据 百度百科：在计算机系统中，各种字母、数字符号的组合、语音、图形、图像等统称为数据 维基百科：数据指描述事物的符号记录，.，是构成信息和知识的原始材料。.如图形、声音、文字、数、字符和符号等。 信息 百度百科：信息是对客观世界中各种事物的运动状态和变化的反映，是客观事物之间相互联系和相互作用的表征，表现的是客观事物运动状态和变化的实质内容。 维基百科：信息是物质存在的一种方式、形态或运动形态，也是事物的一种普遍属性，一般指数据、消息中所包含的意义。. 信息是反映（映射）事件的内容。,“数据”与“信息”的概念,6,

3、信息是对事物、现象、联系等的反映数据是信息的描述形式，有多种类型 数据是信息的表现形式，信息是数据表示的意义 本课程后续内容在不产生歧义时通常忽略这两个概念的差异,“数据”与“信息”的关系,数据处理：对前述的人事信息，数据处理包括提取(一个人的信息)，添加(新人的信息)，删除(已有人的信息)，更新(原有人员某栏目的信息)，查找(判定某人是否存在)，排序(重新整理、排列)等,7,数据元素与数据集合,若干个同类型数据元素构成数据集合。一个人的信息是一个完整的“数据元素”，各个数据元素构成该单位的人事档案“数据集合”。 数据元素之间的逻辑关系称为“逻辑结构”，本课程只讨论同类型数据元素之间的关系，以

4、及针对这些数据元素(数据集合)可以进行什么样的处理，并探讨如何提高处理的效率。,8,常见的三种逻辑结构,前述的人事档案通常不考虑元素之间的联系，即不考虑员工之间有何种联系。但存在元素间有逻辑关系的现象，通常有以下几种情况：,集合 元素间没有联系,元素间有“前后”关系,树,图,线性表,元素间有“层次”关系,元素间“有”/“没有”联系,9,数据处理/运算,针对数据的计算和处理统称为“运算”，计算有确定的数据值作为结果，处理则没有。 与“联系”无关的运算(集合上的运算)： 查找判定集合中是否存在满足条件的元素 读取取出指定元素，包括其各个数据项 插入向集合中添加新元素 删除从集合中删除原有元素 更新

5、修改一个或者多个元素指定数据项的值 其它如“交集”、“并集”、“补集”等 与“联系”有关的运算，例如： 找出线性表的“首元素”/“尾元素” 对线性表中所有元素按指定的规则排序 求树的高度元素是层次关系，共有多少层？ 在图中求最短路径,10,数 据 存 储,人工处理时通常是为每个人建立信息卡，然后对信息卡编号、分类后放在屉、柜等之中；上述表现形式称为“机外表示”或者“人工表示” 计算机处理首先把信息存储在计算机的存储器中如何存储？比如存储“1979年10月1日”，方式之一是以4字节存储，2字节存年份，月和日各1字节；可以按字符串的形式“1979-10-01”存储；还有其它存储形式。 在存储器中组

6、织数据的方式称为数据的“物理结构”。一种逻辑结构可以对应多种不同的物理结构。物理结构与数据处理方法直接相关。,11,利用计算机求解的过程,1. 正确理解问题,2. 建立数学模型,3. 确定数据组织形式,4. 确定数据处理方法,5. 编程实现,6. 验证结果,12,什么是“数据结构”？,上一页的核心问题： 数据间有何种联系？ 数据如何存储？ 在多种方案中如何选择？ 评价方案优劣的标准？,数据的“逻辑结构”,数据的“物理结构”,数据处理是针对数据的“运算”，具体实现方案称为“算法”,+ + | 数据结构,算法的定义见后,13,知识结构(5大板块),数据结构 = 逻辑结构 + 物理结构 + 运算 本

7、课程的主要知识点：线性表树图检索排序 对数据元素可能需要进行多种运算，不同的存储结构将影响运算的效率，应选择能提高最常用的运算效率的存储结构,数据元素间三种常见关系 (逻辑结构),两种最常用的运算,是什么 有什么特点 能做什么 如何存储 怎么做(编程) 好不好,14,算法是解决问题的方案,算法(Algorithm)是针对问题而设计的一组指令操作序列作为解决方案，对于规范的输入，该操作序列能够在有限时间内获得相应的输出，即问题求解结果。 例1：大数求和问题 对问题的理解、逻辑结构、存储结构见前述。 计算方法要点： 1. 输入与存储问题； 2. 对位； 3. 循环计算； 4. 结果的存储与输出；

8、算法局限： 只针对不超过n位的计算,ci=ai+bi+第i-1位的进位,15,算 法 示 例,例2：“在人事档案中查找某个人” 输入：待查人的姓名 输出：如果找到则输出该员工的详细信息，否则提示“查无此人” 解决问题的步骤如下： 1. 打开人事档案文件，记总人数为n，以i记档案序号 令i的值为1 2. 当in时，重复执行以下步骤： (1) 取出第i份档案 (2) 比较该档案中的姓名是否与待查者姓名相同， 如果相同，则输出该档案中的信息，转4； 否则令i取下一个序号值 3. 如果在第2步骤中始终没有发现目标，输出“查无此人” 4. 关闭档案,16,描述算法的方式,自然语言前面的示例即为自然语言描

9、述 流程图以框和箭头表示，如右图即为一例，该算法仍然是“在人事档案中查找某人” 伪代码以某种形式化语言描述(类似于程序设计语言，但不能直接作为计算机某一种具体环境下的程序) 程序有不同的程序设计语言,打开人事档案，i1,取第i号档案姓名name,tar=name?,ii+1,关闭档案,Y,N,i=总人数?,N,Y,17,算法的重要特征,给定具体问题后，确定数据的存储形式，再找出一种正确的解决方案。方案具有以下特点： 输入与输出算法应有输入参数的个数及类型，各个参数的具体值给定后，针对一类问题的算法成为解决一个问题的具体实现；输出是算法处理后的结果 正确性对合适的输入可以解决问题，得到正确结果

10、有穷性算法必须能在执行有限个步骤之后终止，“有限步骤”或者“有限时间”的概念很模糊 有效性每个步骤必须有确切的操作含义，能够用已知的做法在有限时间内解决，不能有“二义性” 健壮性针对输入的限制性条件检测；当环境稍有改变时，方案能适当地应对 高效性当有多种解决问题的途径时，应采取效率较高的一种,18,评价算法的优劣,问题：某文本文件中存放了一篇英文文章，统计其中各个英文字母使用的次数。 算法： for(i=a;i=z;i+)/做26次循环s=0;读取文件中的每一个字符，如果与i对应的字母相同,则s+;输出； 算法2： 令t0至t25清0；读取文件中的每一个字符，如果该字符是第i个字母，则将ti加

11、1；输出t0至t25 试比较上述两个算法的优劣,19,评价算法优劣的标准,解决一类问题可以有多种不同的方案，可以从以下几个方面评价算法的优劣： 正确性是一个方案可行的必要条件 易读性算法要易于理解、易于编程 健壮性算法要有广泛的适用性 时间复杂度针对一类问题设计的算法，随着问题中数据量的增加，算法在计算机上实现时所需要的时间会如何增加，这是算法的计算量问题 空间复杂度用计算机解决问题时，除了数据本身需要一定的存储空间之外，通常还需要一些临时用的存储空间。随着问题中数据量的增加，这些临时用的存储空间需要如何增加 1是必要条件，2、3不很在意，现在一般认为：4是最重要的评价标准，5是评价时的参考。

12、 如何描述一个算法的“时间复杂度”或者“空间复杂度”,20,评价算法的相关参数,问题尺寸描述问题所涉及的数据元素多少的量。通常以代表元素数量的n表示，比如“在人事档案中查找某个人”，则问题的尺寸就是档案中的员工总数。问题尺寸可以有其它表现形式。比如“在长方形的迷宫中寻找路径”，问题尺寸是迷宫的大小，表示这个数据往往用迷宫的行数和列数，即mn 算法中的基本操作指算法中的各种操作步骤，能在计算机上较容易地实现，并且与问题尺寸无关。比如“在人事档案中查找某个人”的算法，基本操作包括：打开档案、读取一份档案、比较两个姓名等等认为“基本操作”在计算机上完成所需要的时间是大致相同的，均为1个时间单位，这显

13、然是一种很不精确的假设。,21,时间复杂度函数,时间复杂度函数以1个单位时间完成一次“基本操作”，则完成算法的总时间可以表示成一个计算式，该计算式通常是关于问题尺寸的函数，即：T = f(n)该函数通常是多项式的形式，但也有其它形式，例如：T1 = n2 + 2n +1T2 = 3nlog2 n + 4n + 7 （从时间上如何评价这两个算法？见后） 有时不容易确定一个算法的时间复杂度函数，比如“在人事档案中查找某个人”的算法，尽管已经认为处理每个框的时间相同，但仍然需要至少区分以下两种情况： “最好情况”。最好情况下，只需要翻阅一份档案就可以解决“在人事档案中查找某个人”的问题。 “最坏情况

14、”。最坏情况下，需要翻阅所有档案才能解决“在人事档案中查找某个人”的问题。 考察时间复杂度时，往往需要第三种情况平均情况。,22,等概率下的平均时间复杂度函数,设：共有n份档案，查阅一份档案的时间为固定值t；在第i份档案上找到目标的可能性记作pi，且p1=p2=pn；查遍所有档案还没找到才能确定“查无此人”，“查无此人”的可能性记作p；显然： (p1+p2+pn)+p=1，pi=(1-p)/n，i=1,2,n 则，平均时间复杂度函数T可以表示成下面的形式：T = tp1 + 2tp2 + + ntpn + ntp = t(p1+2p2+npn) + ntp = t(1+2+n)(1-p)/n)

15、 + ntp 其中t,p为常量，T是n的一次函数，考虑p=0和p=1。,= t( (1-p) + ntp,= n+,23,时间与问题尺寸的关系,两个算法的时间复杂度函数如下，如何评价算法在时间上的好坏：T1 = n2 + 2n +1T2 = 3nlog2 n + 4n + 7 参照如下的对比表： n T1 T2 1 4 11 10 121 147 100约104约103 1000约106约104 . . . 随着n的增长，T1明显比T2增长得快，因此T2对应的算法在时间上优于T1对应的算法。,24,时间复杂度函数的级别,时间复杂度级别简称“时间复杂度”，把时间复杂度函数取最高次的项并去掉系数，写成O(.)的形式，比如，如上的T1=O(n2) ，T2=O(nlog2 n) 前述档案查找问题的平均时间复杂度为O(n) 常见的时间复杂度：O(2n),O(n3