数据结构ppt第1章 绪论

1、数据结构数据结构b b 任课教师：徐琴 电子邮件： 课程目的课程目的 主要介绍如何合理地组织数据、有效地存 储和处理数据，正确地设计算法以及对算 法的分析和评价。通过本课程的学习，使 学生理解数据结构的逻辑结构和物理结构 的基本概念以及有关算法，培养基本的、 良好的程序设计技能，编制高效可靠的程 序，为学习后序课程奠定基础。 考试形式：闭卷考试，考试时间120分钟。 题型构成：基本概念选择题、填空题占40%， 应用题占30%，算法设计题占 30%。 成绩构成：平时成绩30%，考试成绩70%。 （一）使用教材 1 秦锋.数据结构（c语言版）.第一版.北京.清华大学 出版社.2011. 2 秦锋.

2、数据结构（c语言版）例题详解与课程设计指导. 第一版.北京.清华大学出版社.2011. （二）教学参考资料 1 严蔚敏,吴伟民.数据结构（c语言版）.第一版.北京: 清华大学出版社.2007. 2 程杰.大话数据结构.第一版.北京:清华大学出版 社.2011. 3 李春葆等.数据结构教程.第三版.北京:清华大学出版 社.2009. 4 李春葆等.数据结构教程（第三版）上机实验指导.第 一版.北京:清华大学出版社.2009. 第一章第一章 绪绪 论论 本章内容本章内容 什么是数据结构 基本概念和术语 算法 本章学习要求本章学习要求 了解：研究数据结构的目的和意义 掌握：数据结构基本概念和相关术语

3、 掌握：算法基本概念和算法评价依据 掌握：算法的时间复杂度和空间复杂度 1.1 1.1 什么是数据结构什么是数据结构 早期的计算机主要用于数值计算 现在的计算机更多地是用于非数值数据处理 （字符、表格、图像） 对非数值数据的处理：分析数据的逻辑特征 抽象出合适的数学模型合理地存储到计算机 设计出算法编写出程序 首先要构造学生信息表，表1-1表达出学生数据的 逻辑关系，它就是一个数学模型，这张表如何构造、 在计算机内如何存储将直接影响查找算法的设计以 及算法的效率。 学生基本情况 学 号姓 名性 别出生年月 . 99070101 李 军男8012 . 99070102 王颜霞女812 . 990

4、70103孙 涛男809 . 99070104单晓宏男813 . . 例例1 1 学生信息查询系统学生信息查询系统 学生信息表的特点学生信息表的特点 每个学生的信息占据一行，所有学生的信息按学 号顺序依次排列构成一张表格 表中每个学生的信息依据学号的大小存在着一种 前后关系，这就是我们所说的线性结构，现实中 这类关系的数据有很多。 通常的操作 插入某个学生的信息 删除某个学生的信息 更新某个学生的信息 按条件查找某个学生的信息 例例2 2 人机对弈人机对弈 中国象棋、国际象棋的人机大战，核心技术是人 编写的对弈程序。对弈步骤和过程可以用树型结 构表达出来（数学模型） 图图 1-1 井字棋对弈树

5、井字棋对弈树 树型结构的特点树型结构的特点 所处理的数据之间具有层次关系，这是我们 所说的树形结构,还有如：基因遗传关系等， 它是一种非线性结构。 对它的操作有：建立树形结构、存储树、访 问树中的每个结点 例例3 3 排课子系统排课子系统 排课系统中各门课程的先后关系可以用一个图 表达出来，这个图表达了数据的逻辑关系（数学模 型） 在制定教学计划时，需要考虑各门课程的开设 顺序。有些课程需要先导课程，有些课程则不需 要，而有些课程又是其他课程的先导课程。如何 安排每学期的课程？ 计算机专业课程的开设情况如下表所示： 计算机专业学生的必修课程 课程编号课程名称需要的先导课程 编号 c1 程序设计

6、基础无 c2 离散数学 c1 c3 数据结构c1 ， c2 c4 汇编语言 c1 c5 算法分析与设计c3 ， c4 c6 计算机组成原理 c11 c7 编译原理c5 ， c3 c8 操作系统c3 ， c6 c9 高等数学无 c 10 线性代数 c9 c11 普通物理 c9 c12 数值分析c9 ， c10 ， c1 课程先后关系的图型描述 图结构的特点图结构的特点 关系比较复杂，用例1和例2的结构表达不出来， 必须用图结构描述 通过实施创建图结构，存储图结构，可以对图 结构中的顶点进行线性排序，从而找出每学期 应该上的课程。 现实中，这类关系的数据非常多。如：网络规 划、交通、通讯规划等，这

7、里典型的非线性关 系。 操作对象的关系复杂多样 操作不再是单纯的数值计算，更多的是非数值 问题求解，需要对数据（不是数值）进行分析、 组织及管理。 必须对数据进行有效的组织、存储，才能对数 据进行有效的操作 结论结论 1.2 基本概念和术语 数据(data):是对信息的一种符号表示。在计算机科 学中是指所有能输入到计算机中并被计算机程序处理 的符号的总称。 数据元素(data element):是数据的基本单位，在计 算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项 是数据的不可分割的最小单位。 数据结构(data structure)：是相互之间存在一种或

8、 多种特定关系的数据元素的集合。 数据结构的定义 逻辑结构 指数据元素之间的逻辑关系，又称此为逻辑结构。指数据元素之间的逻辑关系，又称此为逻辑结构。独独 立于计算机，是数据本身所固有的。立于计算机，是数据本身所固有的。 存储结构（物理结构） 数据元素及逻辑关系在计算机存储器内的表示方式。数据元素及逻辑关系在计算机存储器内的表示方式。 是逻辑结构在计算机存储器中的映射，必须依赖于计是逻辑结构在计算机存储器中的映射，必须依赖于计 算机。算机。 数据运算 对数据施加的操作。对数据施加的操作。运算的定义依赖于逻辑结构，但运算的定义依赖于逻辑结构，但 运算的实现必依赖于存储结构。运算的实现必依赖于存储结

9、构。 数据元素之间的相互关系称为逻辑结构 通常分为四类基本结构： 一、集合 结构中的数据元素除了同属于一种 类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一 的关系。 三、树型结构 结构中的数据元素之间存在一对多 的关系。 四、图状结构或网状结构 结构中的数据元素之间存在多对多 的关系。 数据元素及逻辑关系在计算机内的表示方法称为存储结构 4种基本方式： 顺序存储结构:用数据元素在存储器中的相对位置来表 示数据元素之间的逻辑关系。 链式存储结构：在每一个数据元素中增加一个存放地址 的指针，用此指针来表示数据元素之间的逻辑关系。 索引存储：在存储数据元素的同时还建立附加的索引

10、表。 散列存储：依据数据元素的关键字，用一个事先设计好 的函数（称为散列函数）计算出该数据元素的存储地 址，然后把它存入该地址中。 1.3 什么是算法 算法具有五大特性： 1）有穷性： 一个算法必须在执行有穷步之后结束，且每步 都可在有限时间内完成。 2）确定性： 算法中的每一步，必须有确切的含义，不能有二 义性 3）可行性： 算法中描述的每一步操作都可以通过已有的基本 操作执行有限次实现 4）输入： 一个算法应该有零个或多个输入 5）输出： 一个算法应该有一个或多个输出 思考：烹调过程、程序、操作系统等是不是算法？ 如何描述算法 使用自然语言。 优点是简单且便于人们对算法的阅读,缺点是不够严

11、谨， 容易产生二义性。 可以使用程序流程图、n-s图等算法描述工具。 其特点是描述过程简洁、明了。 用一种伪语言（类pascal、类c ） 比程序设计语言更容易描述更容易理解，比自然语言更 接近程序设计语言。 用c、c+ 等标准的程序设计语言 如何评价算法 正确性： 要求算法能够正确地执行预先规定的功能，并达到所 期望的性能要求（有四个层次的正确） 可读性： 为了便于理解、测试和修改算法，算法应该具有良好 的可读性（注意程序设计风格，如：空行、注释、命 名、对齐等） 健壮性： 当输入数据非法运行环境改变时，算法能恰当地作出 反应或进行处理，不会产生莫名其妙的输出结果 时间与空间效率： 要求算法

12、的执行时间尽可能地短，占用的存储空间尽 可能地少。 影响算法运行所需时间的因素 硬件的速度硬件的速度 例如使用486机还是使用双核机。 书写程序的语言书写程序的语言 实现语言的级别越高，其执行效率就越低 编译程序所生成目标代码的质量。编译程序所生成目标代码的质量。 对于代码优化较好的编译程序其所生成的程序质量较 高 问题的规模问题的规模 例如，求100以内的素数与求1000以内的素数其执行的 时间必然是不同的 算法设计的好坏算法设计的好坏 结论：不能用实际的时间来考量、应该用时间复杂度与 空间复杂度来评价算法的优劣。 时间复杂度 时间复杂度是指，算法运行从开始到结束所需要的时 间。 算法所需的

13、时间=每条语句的执行时间之和。 每条语句的执行时间=语句执行次数（也称为频度）*执 行一次该语句所需时间 假设执行每条语句一次所需的时间均为单位时间 算法所需的时间=算法中语句的频度之和 例1： 求两个n阶方阵的乘积c=a*b的算法 #define n 100 void matrixmultiply(int a nn，int bnn，int cnn) for(i=0;in; i+) n+1 for(j=0; jn;j+) n(n+1) cij=0; n2 for(k=0;kn;k+) n2(n+1) cij=cij+aik*bkj; n3 上述算法的执行时间（即语句的频度之和） 是 t(n)=

14、2n3+3n2+2n+1；它是方阵阶数n 立方的函数。 例1的时间复杂度分析 语句1是循环控制语句，它的循环次数决定，故 是n+1，但是它的循环体却只执行n次 语句2作为语句1的循环体内的语句应执行n次， 但每次执行时它本身又要执行n+1次， 故语句2 的频度为n(n+1)。 3、4、5语句的频度可类似得到。 例1的时间复杂度分析 算法的执行时间是求解问题的规模n（如矩阵的 阶数，线性表的长度）的函数，我们考察它的 数量级量度，即它与什么简单函数f(n)是同一 数量级的，即t(n)=o(f(n)。 对于前例，当n时 t(n)/n3 = (2n3+3n2+2n+1)/ n32 按“o”的定义我们

15、可知t(n)=o(n3) 另一方法： 基本运算：一般指最深层循环内的语句 时间复杂度=基本运算在算法中重复执行的次数。 例1中，基本运算是三重循环中最深层的语句，分 析它的频度，即： t(n)=n3=o(n3) 例 +x; s=0; 将x自增看成是基本操作，则语句频度为1，即时 间复杂度为o(1) 如果将s=0也看成是基本操作，则语句频度为2， 其时间复杂度仍为o(1)，即常量阶。 例 for(i=1;i =n;+i) +x;s+=x; 基本运算频度为：n其时间复杂度为： o(n) 即时间复杂度为线性阶。 例 for(i=1;i=n;+i) for(j=1;j=n;+j) +x;s+=x; 基

16、本运算频度为：n2 其时间复杂度为：o(n2) 即时间复杂度为平方阶。 例 for(i=2;i=n;+i) for(j=2;j1 -i) change=false; for(j=0;jaj+1) aj aj+1; change=ture； 最好情况：0次 最坏情况：1+2+3+n-1 =n(n-1)/2 最坏时间复杂度为:o(n2) 常见的时间复杂度，其关系为： o(1)o(logn)o(n)o(nlogn) o(n2)o(n3) 指数时间的关系为： o(2n)o(n!)o(nn) 当n取得很大时，指数时间算法和多项式时间算法在 所需时间上非常悬殊。 空间复杂度 空间复杂度:算法所需存储空间的

17、度量，记作: s(n)=o(f(n) 其中n为问题的规模(或大小) 特别说明：算法的空间复杂度定义和时间复 杂度一样，不过一个算法的空间复杂度是 对算法运行中所需的辅助空间的度量，操 作对象所占的空间不计入空间复杂度的度 量之中。具体可见例6 例6 n矩阵amxn中存在某个元素aij满足：aij是第i行中 最小值且是第j列中的最大值，则称该元素为矩阵a 的一个鞍点，试编写算法找出a中的所有鞍点。 算法一：穷举法 算法思想： 对每一个元素aij进行判别 n若aij是第i行的最小数，则继续判别，看它是否 也是第j列的最大数，如果成立则是鞍点。 n当aij不是第i行的最小数或者不是第j列的最大数 则

18、选择下一个元素继续。 算算 法法 的的 c c 语语 言言 描描 述述 #define m 10 #define n 10 void saddle ( int amn) /*求求m行行n列矩阵的鞍点列矩阵的鞍点*/ int i,j,k，smin,smax；/* smin 为为true时表示时表示aij是第是第i行最小数，行最小数， smax 为为true时表示时表示aij是第是第j列的最大数列的最大数 */ for (i=0；im；i+ ) /* 用枚举法对矩阵的每个元素进行判断用枚举法对矩阵的每个元素进行判断*/ for (j=0；jn；j+ ) k=0； while ( k= aij )

19、/*是否是第是否是第i行最小数行最小数*/ k+; if (kn) smin=false; else smin=true; if ( smin =true) /*是第是第i行最小数时继续判断行最小数时继续判断*/ k=0； while (km) if (km) smax=false; else smax=true; if ( smin=true /* a i j 是鞍点。是鞍点。*/ /end for j 复杂度分析 时间复杂度 双重循环体内有两个并列的while循环语言。第 一个while循环执行o (n )次，第二个while循 环最多执行o（m）次。所以总的时间复杂度应 该是o (m*n*( m+n) 空间复杂度 除矩阵a用二维数组存储外，用了几个辅助