严蔚敏最新版《数据结构》电子教案

1、人民邮电出版社北京林业大学信息学院 17:29 人民邮电出版社北京林业大学信息学院 17:29 v编程基础编程基础v计算机及相关专业考研考博课程计算机及相关专业考研考博课程v计算机等级考试课程计算机等级考试课程v程序员考试课程程序员考试课程为什么要学习数据结构为什么要学习数据结构北京林业大学信息学院 17:29 课程学习指导课程学习指导 1.提前预习预习、认真听课、按时完成书面及上机作业作业 2.注意先修课程的知识准备离散数学、C C语言语言 3.注意循序渐进：基本概念概念、基本思想思想、基本步骤步骤、算法算法设计 4.注意培养算法设计的能力理解所讲算法、对此多做思考思考：若问题要求不同，应如

2、何选择数据结构，设计有效的算法课程特点：课程特点：内容抽象、概念性强、内容灵活、不易掌握内容抽象、概念性强、内容灵活、不易掌握北京林业大学信息学院 17:29 平时成绩 : 30% 作业、小测验、实验 课堂纪律无故迟到：无故旷课：上机：玩游戏、上网聊天 期末成绩 : 70%(闭卷笔试)考核方式考核方式北京林业大学信息学院 17:29 教材和参考书教材和参考书教材：教材： 数据结构数据结构978-7-115-23490严蔚敏，李冬梅，人民邮电出版社出版严蔚敏，李冬梅，人民邮电出版社出版 参考书：参考书： 数据结构数据结构C语言版语言版，严蔚敏，清华大学出，严蔚敏，清华大学出版社版社 数据结构数据

3、结构用面向对象方法与用面向对象方法与C+描述描述，殷人昆等，清华大学出版社，殷人昆等，清华大学出版社 17:29 第第1 1章章绪论绪论1. 了解数据结构研究的主要内容了解数据结构研究的主要内容2.2.掌握数据结构中涉及的基本概念掌握数据结构中涉及的基本概念3. 掌握算法、算法的时间复杂度及其分析的掌握算法、算法的时间复杂度及其分析的简易方法简易方法 教学目标教学目标北京林业大学信息学院 17:29 1.1 数据结构的研究内容数据结构的研究内容1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现 1.4 算法与算法分析算法与算法分析教学内容教学内容人民邮

4、电出版社北京林业大学信息学院 17:29 &N.N.沃思（沃思（Niklaus Wirth)Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+数据结构数据结构&电子计算机的主要用途：电子计算机的主要用途： 早期：早期： 主要用于数值计算。主要用于数值计算。 后来：后来： 处理逐渐扩大到非数值计算领域，能处理处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据多种复杂的具有一定结构关系的数据1.1 数据结构的研究内容数据结构的研究内容北京林业大学信息学院 17:29 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡

5、片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引表线性表人民邮电出版社北京林业大学信息学院 17:29 人机对奕问题树.北京林业大学信息学院 17:29 / (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系统的系统结构图文件系统的系统结构图树人民邮电出版社北京林业大学信息学院 17:29 多叉

6、路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图顶点：顶点：一条通路连线：连线：不能同时通行染色：染色：有连线的两个顶点不能具有相同颜色人民邮电出版社北京林业大学信息学院 17:29 &求解非数值计算的问题：求解非数值计算的问题： 设计出合适的数据结构及相应的算法设计出合适的数据结构及相应的算法 即：首先要考虑即：首先要考虑对相关的各种信息如何表示、组织对相关的各种信息如何表示、组织和存储？和存储？ 数据结构的研究内容为：数据结构的研究内容为： 研究非数值计算的程序设计问题中计算机的研究非数值计算的程序设计问题中计算机的操作操作对象对象以及它们之间的以

7、及它们之间的关系和操作关系和操作。北京林业大学信息学院 17:29 &数据结构课程的形成和发展：数据结构课程的形成和发展： 形成阶段：形成阶段： 6060年代初期，年代初期，“数据结构数据结构”有关的内容散见于操作系有关的内容散见于操作系统、编译原理和表处理语言等课程。统、编译原理和表处理语言等课程。19681968年，年，“数据数据结构结构”被列入美国一些大学计算机科学系的教学计划被列入美国一些大学计算机科学系的教学计划。 发展阶段：发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论数据结构的概念不断扩充，包括了网络、集合代数论、关系等、关系等“离散数学结构离散数学结构”的内

8、容。的内容。 7070年代后期，我国高校陆续开设该课程。年代后期，我国高校陆续开设该课程。北京林业大学信息学院 17:29 &数据结构数据结构所处的地位：所处的地位：介于数学、计算介于数学、计算机硬件和计算机机硬件和计算机软件三者之间的软件三者之间的一门核心课程一门核心课程北京林业大学信息学院 17:29 北京林业大学信息学院 17:29 能够分析研究计算机加工的对象的特性，获能够分析研究计算机加工的对象的特性，获得其得其逻辑结构逻辑结构，根据需求，选择合适，根据需求，选择合适存贮结存贮结构及其相应的算法构及其相应的算法； 学习一些学习一些常用的算法常用的算法； 复杂程序设计的训练过程

9、，要求编写的程序复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读结构清楚和正确易读； 初步掌握算法的初步掌握算法的时间分析和空间分析时间分析和空间分析技术技术北京林业大学信息学院 17:29 1、数据、数据（data)所有能输入到计算机中去的描述客观事物的符号u数值性数据数值性数据u非数值性数据（多媒体信息处理）非数值性数据（多媒体信息处理）2、数据元素、数据元素（data element）数据的基本单位，也称结点（node）或记录（record）3、数据项、数据项（data item）有独立含义的数据最小单位，也称域(field)三者之间的关系：数据 数据元素 数据项例：学生表 个人

10、记录 学号、姓名1.2 基本概念和术语基本概念和术语人民邮电出版社北京林业大学信息学院 17:29 u整数数据对象整数数据对象 N = 0, N = 0, 1, 1, 2, 2, u学生数据对象学生数据对象 学生记录的集合学生记录的集合4 4、数据对象数据对象(Data Object)(Data Object)：相同特性相同特性数据元素的集合，是数据的一个子集北京林业大学信息学院 17:29 5 5、数据结构（、数据结构（Data Structure）是相互之间是相互之间存在一种或多种特定关系的数据元素的集合。存在一种或多种特定关系的数据元素的集合。数据结构是带数据结构是带“结构结构”的数据元

11、素的集合，的数据元素的集合，“结构结构”就是指数据元素之间存在的关系。就是指数据元素之间存在的关系。北京林业大学信息学院 17:29 &数据结构的两个层次：数据结构的两个层次：&逻辑结构逻辑结构- 数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。&存储结构（物理结构）存储结构（物理结构）- 数据元素及其关系在计算机存储器中的存储方式。北京林业大学信息学院 17:29 划分方法一划分方法一 （1）线性结构- 有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。 例如：线性表、栈、队列、串 （2）非线性

12、结构- 一个结点可能有多个直接前趋和直接后继。 例如：树、图逻辑结构逻辑结构北京林业大学信息学院 17:29 线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树集合数据元素间除“同属于一个集合”外，无其它关系图形结构多个对多个，如图逻辑结构逻辑结构划分方法二划分方法二北京林业大学信息学院 17:29 存储结构分为：顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系存储存储结构结构北京林业大学信息学院 17:29 元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*

13、mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储北京林业大学信息学院 17:29 1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346 链式存储链式存储 h人民邮电出版社北京林业大学信息学院 17:29 逻辑结构

14、和存储结构都相同逻辑结构和存储结构都相同, , 但运算不同但运算不同, , 则数据结构不同则数据结构不同. . 例如例如, , 栈与队列栈与队列 对于一种数据结构对于一种数据结构, , 常见的运算常见的运算 插入插入 删除删除 修改修改 查找查找 排序排序数据的运算数据的运算北京林业大学信息学院 17:29 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：插入、删除、修改、查找、排序数据的运算：插入、删除、修改、查找、排序 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表 栈、队列栈、队列 串、数组串、数组树形结构树形结构图形结构

15、图形结构逻辑结构逻辑结构唯一唯一存储结构存储结构不唯一不唯一运算的实现运算的实现依赖于依赖于存储结构存储结构人民邮电出版社北京林业大学信息学院 17:29 n定义：定义：在一种程序设计语言中，变量所具有在一种程序设计语言中，变量所具有的数据种类的数据种类数据类型数据类型FORTRAN语言：语言：整型、实型、和复数型整型、实型、和复数型 C语言语言：基本数据类型：基本数据类型： char int float double void构造数据类型：构造数据类型：数组、结构体、共用体、文件数组、结构体、共用体、文件 数据类型是一组性质相同的值的集合数据类型是一组性质相同的值的集合, , 以及以及定义于

16、这个集合上的一组运算的总称定义于这个集合上的一组运算的总称人民邮电出版社北京林业大学信息学院 17:29 抽象数据类型 (ADTs: Abstract Data Types)u更高层次的数据抽象更高层次的数据抽象u由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数据模型数据模型u由由基本的数据类型基本的数据类型组成组成, , 并包括并包括一组相关的一组相关的操作操作抽象数据类型抽象数据类型北京林业大学信息学院 17:29 抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示： ADT = （D，S，P） 数据对象数据对象 D上的关系集上的关系集 D上的操作集上

17、的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象： 数据数据关系关系： 基本基本操作操作 ： ADT ADT抽象数据类型抽象数据类型名名ADT常用常用定义定义格式格式北京林业大学信息学院 17:29 抽抽象象数数据据类类型型查找插入查找插入 删除删除 修改修改 线性表线性表接口或用户界面数据类型的物理实现封装信息隐蔽信息隐蔽和和数据封装数据封装，使用与实现相分离，使用与实现相分离北京林业大学信息学院 17:29 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现抽象数据类型可以通过抽象数据类型可以通过固有的固有的数据类型（如整数据类型（如整型、实型、字符型等）来表示和

18、实现。型、实型、字符型等）来表示和实现。它有些类似它有些类似C C语言中的语言中的结构（结构（struct)struct)类型类型，但增加，但增加了相关的了相关的操作操作教材中用的是教材中用的是类类C C语言（介于伪码和语言（介于伪码和C C语言之间）作语言之间）作为描述工具为描述工具但上机时要用具体语言实现，如但上机时要用具体语言实现，如C C或或C+C+等等人民邮电出版社北京林业大学信息学院 17:29 (1) (1) 预定义常量及类型预定义常量及类型 /函数结果状态代码函数结果状态代码 #define OK 1 #define OK 1 #define ERROR 0 #define E

19、RROR 0 #define INFEASIBLE -1 #define INFEASIBLE -1 #define OVERFLOW -2 #define OVERFLOW -2 / Status/ Status是函数返回值类型，其值是函数结是函数返回值类型，其值是函数结果状态代码。果状态代码。 typedef int Status; typedef int Status; 人民邮电出版社北京林业大学信息学院 17:29 (2)(2)数据元素被约定为数据元素被约定为ElemType ElemType 类型，类型，用用户需要根据具体情况，自行定义该数据类型。户需要根据具体情况，自行定义该数据类

20、型。(3)(3)算法描述为以下的函数形式：算法描述为以下的函数形式： 函数类型函数类型 函数名（函数参数表）函数名（函数参数表） 语句序列；语句序列； 北京林业大学信息学院 17:29 （4 4）内存的动态分配与释放）内存的动态分配与释放使用使用new和和delete动态分配和释放内存空动态分配和释放内存空间间分配空间指针变量分配空间指针变量=new数据类型数据类型;释放空间释放空间delete指针变量指针变量;（5 5）赋值语句）赋值语句（6 6）选择语句）选择语句（7 7）循环语句）循环语句北京林业大学信息学院 17:29 （8）使用的结束语句形式有：使用的结束语句形式有：函数结束语句函数

21、结束语句 return return 循环结束语句循环结束语句 break;break;异常结束语句异常结束语句 exitexit（异常代码）；（异常代码）；北京林业大学信息学院 17:29 （9）输入输出语句形式有：输入输出语句形式有：输入语句 cin (scanf( )输出语句 cout (printf( )（10）扩展函数有：扩展函数有：求最大值 max求最小值 min人民邮电出版社北京林业大学信息学院 17:29 1.4 算法和算法分析算法和算法分析北京林业大学信息学院 17:29 人民邮电出版社北京林业大学信息学院 17:29 人民邮电出版社北京林业大学信息学院 17:29 算法效率

22、：用依据该算法编制的程序在计算机上算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量执行所消耗的时间来度量事后统计事后统计事前分析估计事前分析估计北京林业大学信息学院 17:29 1.1.事后统计：事后统计：利用计算机内的计时功能，不同算法利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分的程序可以用一组或多组相同的统计数据区分 缺点：缺点：必须先运行依据算法编制的程序必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣，掩盖算法本身的优劣 北京林业大学信息学院 17:29 2.2.

23、事前分析估计：事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取一个高级语言程序在计算机上运行所消耗的时间取决于：决于： 依据的算法选用何种策略依据的算法选用何种策略 问题的规模问题的规模 程序语言程序语言 编译程序产生机器代码质量编译程序产生机器代码质量 机器执行指令速度机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，的计算机上运行，效率均不同，使用使用绝对时绝对时间单位间单位衡量算法效率不合适衡量算法效率不合适北京林业大学信息学院 17:29 算法中关键操作关键操作（循环和递归）（循环和递归）

24、重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：T(n)=T(n)=O(f(n)(f(n) 时间复杂度的渐进表示法时间复杂度的渐进表示法渐进符号（渐进符号（O）的定义：当且仅当存在一个正的常数）的定义：当且仅当存在一个正的常数 C C和和n0 ，使得对所有的，使得对所有的 n n0 ，有，有 T(n) T(n) Cf(n) Cf(n)，则，则T(n) = O(f(n)表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度渐近时间复杂度。北京林业大学信息学院 17:29 n * n阶矩阵加法：阶矩阵加法：for( i = 0; i n; i+)for(

25、 j = 0; j n; j+)cij = aij + bij;语句的频度语句的频度（Frequency Count ): 重复执行的次数：重复执行的次数：n*n;T( n ) = O ( n 2)即：矩阵加法的运算量和问题的规模即：矩阵加法的运算量和问题的规模n的平方是同一个量级的平方是同一个量级北京林业大学信息学院 17:29 x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1(n) = O(1)T2(n) = O(n)T3(n)

26、= O(n2)T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)北京林业大学信息学院 17:29 void exam ( float x , int m, int n ) float sum ; for ( int i = 0; i m; i+ ) /x中各行 sumi = 0.0; /数据累加 for ( int j = 0; j n; j+ ) sumi += xij; /关键操作关键操作 for ( i = 0; i m; i+ ) /打印各行数据和 cout i “ : ” sum i endl; /关键操作关键操作 渐进时间

27、复杂度为 O(max (m*n, m)算法的时间复杂度是由算法的时间复杂度是由嵌套最深层嵌套最深层语句的频度决定的语句的频度决定的北京林业大学信息学院 17:29 例1：NN矩阵相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; 算法中的基本操作语句为算法中的基本操作语句为cij=cij+aikcij=cij+aik* *bkj;bkj; 233111111( )1()nnnnnnijkijiT nnnno n 3T nO n北京林业大学信息学院 17:29 例例2：for( i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+)x=x+1;niniijniijjkiij1111112)1(16)2)(1(2)1(6)12)(1(2121112nnnnnnnniinini