利来w66最新 利来ag旗舰厅 利来w66国际官网 利来w66手机版
严蔚敏最新版《数据结构》电子教案
发布者:admin浏览次数:

  严蔚敏最新版《数据结构》电子教案_数学_高中教育_教育专区。人民邮电出版社 数据结构 李冬梅 北京林业大学信息学院 17:43 人民邮电出版社 为什么要学习数据结构 ?编程基础 ?计算机及相关专业考研考博课程 ?计算机等级考试课程 ?程序员考试课

  人民邮电出版社 数据结构 李冬梅 北京林业大学信息学院 17:43 人民邮电出版社 为什么要学习数据结构 ?编程基础 ?计算机及相关专业考研考博课程 ?计算机等级考试课程 ?程序员考试课程 北京林业大学信息学院 17:43 课程学习指导 课程特点:内容抽象、概念性强、内容灵活、不易掌握 ? 1.提前预习、认真听课、按时完成书面及上机作业 ? 2.注意先修课程的知识准备 ?离散数学、C语言 ? 3.注意循序渐进: ?基本概念、基本思想、基本步骤、算法设计 ? 4.注意培养算法设计的能力 ?理解所讲算法、对此多做思考:若问题要求不同, 应如何选择数据结构,设计有效的算法 北京林业大学信息学院 17:43 考核方式 ? 平时成绩 : 30% –作业、小测验、实验 –课堂纪律 –无故迟到: –无故旷课:-5 –上机:玩游戏、上网聊天 ? 期末成绩 : 70%(闭卷笔试) 北京林业大学信息学院 17:43 教材和参考书 ? 教材: ? 《数据结构》978-7-115-23490 严蔚敏,李冬梅,人民邮电出版社出版 ? 参考书: ? 《数据结构C语言版》,严蔚敏,清华大学出 版社 ? 《数据结构——用面向对象方法与C++描述》 ,殷人昆等,清华大学出版社 北京林业大学信息学院 17:43 第 1章 绪论 教学目标 1. 了解数据结构研究的主要内容 2.掌握数据结构中涉及的基本概念 3. 掌握算法、算法的时间复杂度及其分析的 简易方法 17:43 教学内容 1.1 数据结构的研究内容 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法与算法分析 北京林业大学信息学院 17:43 人民邮电出版社 1.1 数据结构的研究内容 Wirth)教授提出: 程序=算法+数据结构 ?N.沃思(Niklaus ?电子计算机的主要用途: ?早期: 主要用于数值计算。 ?后来: 处理逐渐扩大到非数值计算领域,能处理 多种复杂的具有一定结构关系的数据 北京林业大学信息学院 17:43 书目自动检索系统 线性表 书目文件 书目卡片 001 高等数学 樊映川 002 理论力学 罗远祥 登录号: 003 高等数学 华罗庚 004 书名: 线性代数 栾汝书 …… 作者名: …… …… 按书名 高等数学 理论力学 线 …… 索引表 分类号: 001,003…… 樊映川 出版单位: 002,…….. 华罗庚 出版时间: 004,…… 栾汝书 价格: …….. ……. 按作者名 001,… 002,…. 004,…. ……. 17:43 按分类号 L S …… 002,… 001,003, …… 北京林业大学信息学院 人机对奕问题 树 人民邮电出版社 …….. …….. 北京林业大学信息学院 …... …... …... 17:43 …... 文件系统的系统结构图 树 / (root) bin lib user etc math ds sw yin tao xie Queue.cpp Stack.cpp Tree.cpp 17:43 北京林业大学信息学院 人民邮电出版社 多叉路通灯管理问题 C AB BA BC AC BD E AD B 图 D DA EA EB DB EC DC ED A 北京林业大学信息学院 顶点:一条通路 连线:不能同时通行 染色:有连线的两个顶 点不能具有相同颜色 17:43 人民邮电出版社 ?求解非数值计算的问题: 设计出合适的数据结构及相应的算法 即:首先要考虑对相关的各种信息如何表示、组织 和存储? 数据结构的研究内容为: 研究非数值计算的程序设计问题中计算机的操作 对象以及它们之间的关系和操作。 北京林业大学信息学院 17:43 ?数据结构课程的形成和发展: 形成阶段: 60年代初期,“数据结构”有关的内容散见于操作系 统、编译原理和表处理语言等课程。1968年,“数据 结构”被列入美国一些大学计算机科学系的教学计划 。 发展阶段: 数据结构的概念不断扩充,包括了网络、集合代数论 、关系等“离散数学结构”的内容。 70年代后期,我国高校陆续开设该课程。 北京林业大学信息学院 17:43 ?《数据结构》所处的地位: 介于数学、计算 机硬件和计算机 软件三者之间的 一门核心课程 北京林业大学信息学院 17:43 数据结构在计算机学科中的地位 W eb概 概 概 概 算算算算算算算算算算算算 算算算算算算算算算算算 概概概 算算算算算算算算 算 算 算 B+算 算算算算算算算 概概概概 算算算算算算算算 算算算算算算 概概概概 算算算算算算算 算算算算算算算算 概概概概 算算算算算算算算算算 算算算算算算算算 概概概概 算算算算算算算算 算算算算算 算算算算算算算 数据结构与算法 概概概概概概 北京林业大学信息学院 概概概概 概概概概 概 概概概概概 17:43 课程目的 ? 能够分析研究计算机加工的对象的特性,获 得其逻辑结构,根据需求,选择合适存贮结 构及其相应的算法; ? 学习一些常用的算法; ? 复杂程序设计的训练过程,要求编写的程序 结构清楚和正确易读; ? 初步掌握算法的时间分析和空间分析技术 北京林业大学信息学院 17:43 1.2 基本概念和术语 数值性数据 非数值性数据(多媒体信息处理) ? 1、数据(data)—所有能输入到计算机中去的 描述客观事物的符号 ? ? ? 2、数据元素(data element)—数据的基本单 位,也称结点(node)或记录(record) ? 3、数据项(data item)—有独立含义的数据最 小单位,也称域(field) 三者之间的关系:数据 数据元素 数据项 例:学生表 个人记录 学号、姓名…… 北京林业大学信息学院 17:43 人民邮电出版社 4、数据对象(Data Object):相同特性数据元素 的集合,是数据的一个子集 ? ? 整数数据对象 N = { 0, ?1, ?2, … } 学生数据对象 ? 学生记录的集合 北京林业大学信息学院 17:43 5、数据结构(Data Structure)是相互之间 存在一种或多种特定关系的数据元素的集合。 数据结构是带“结构”的数据元素的集合, “结构”就是指数据元素之间存在的关系。 北京林业大学信息学院 17:43 ?数据结构的两个层次: ?逻辑结构--数据元素间抽象化的相互关系,与数据的存储无关,独 立于计算机,它是从具体问题抽象出来的数学模型。 ?存储结构(物理结构)---数据元素及其关系在计算机存储器中的存储方式。 北京林业大学信息学院 17:43 逻辑结构 划分方法一 (1)线性结构---有且仅有一个开始和一个终端结点,并且所有 结点都最多只有一个直接前趋和一个后继。 例如:线性表、栈、队列、串 (2)非线性结构---一个结点可能有多个直接前趋和直接后继。 例如:树、图 北京林业大学信息学院 17:43 逻辑结构 划分方法二 集合——数据元素间除“同属于一个集合”外,无其它关系 线性结构——一个对一个,如线性表、栈、队列 树形结构——一个对多个,如树 图形结构——多个对多个,如图 北京林业大学信息学院 17:43 存储结构 存储结构分为: 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系 北京林业大学信息学院 17:43 存储地址 存储内容 Lo 元素1 元素2 …….. Lo+m 顺序存储 Lo+(i-1)*m 元素i …….. Lo+(n-1)*m 元素n Loc(元素i)=Lo+(i-1)*m 北京林业大学信息学院 17:43 h 1345 链式存储 元素2 1536 元素3 1346 元素4 h 元素1 1400 ∧ 存储地址 1345 1346 ……. 存储内容 元素1 元素4 …….. 指针 1400 ∧ ……. 1400 ……. 元素2 …….. 1536 ……. 1346 17:43 1536 元素3 北京林业大学信息学院 数据的运算 人民邮电出版社 ? 逻辑结构和存储结构都相同, 但运算不同, 则数据结构不同. 例如, 栈与队列 ? 对于一种数据结构, 常见的运算 –插入 –删除 –修改 –查找 –排序 北京林业大学信息学院 17:43 逻辑结构 唯一 线性结构 数据的逻辑结构 存储结构 不唯一 线性表 栈、队列 串、数组 非线性结构 树形结构 图形结构 数据的存储结构 运算的实现 依赖于 存储结构 顺序存储 链式存储 数据的运算:插入、删除、修改、查找、排序 北京林业大学信息学院 17:43 数据类型 ? 人民邮电出版社 定义:在一种程序设计语言中,变量所具有 的数据种类 FORTRAN语言:整型、实型、和复数型 C语言: 基本数据类型: char int float double void 构造数据类型:数组、结构体、共用体、文件 ? 数据类型是一组性质相同的值的集合, 以及 定义于这个集合上的一组运算的总称 北京林业大学信息学院 17:43 抽象数据类型 人民邮电出版社 抽象数据类型 (ADTs: Abstract Data Types) ? ? 更高层次的数据抽象 由用户定义,用以表示应用问题的数据模型 ? 由基本的数据类型组成, 并包括一组相关的 操作 北京林业大学信息学院 17:43 抽象数据类型可以用以下的三元组来表示: ADT = (D,S,P) 数据对象 D上的关系集 ADT抽象数据类型名{ D上的操作集 ADT 常用 定义 格式 数据对象:数据对象的定义 数据关系:数据关系的定义 基本操作 :基本操作的定义 } ADT抽象数据类型名 北京林业大学信息学院 17:43 信息隐蔽和数据封装,使用与实现相分离 接口或用 户界面 查找 插入 删除 修改 数据类型 的物理实 现封装 线性表 抽 象 数 据 类 型 北京林业大学信息学院 17:43 1.3 抽象数据类型的表示与实现 抽象数据类型可以通过固有的数据类型(如整 型、实型、字符型等)来表示和实现。 它有些类似C语言中的结构(struct)类型,但增加 了相关的操作 教材中用的是类C语言(介于伪码和C语言之间)作 为描述工具 但上机时要用具体语言实现,如C或C++等 北京林业大学信息学院 17:43 人民邮电出版社 ? (1) 预定义常量及类型 ? ? ? ? ? ? //函数结果状态代码 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 // Status是函数返回值类型,其值是函数结 果状态代码。 ? typedef int Status; 北京林业大学信息学院 17:43 人民邮电出版社 ? (2)数据元素被约定为ElemType 类型,用 户需要根据具体情况,自行定义该数据类型。 (3)算法描述为以下的函数形式: 函数类型 函数名(函数参数表) { 语句序列; } 北京林业大学信息学院 17:43 (4)内存的动态分配与释放 使用new和delete动态分配和释放内存空间 分配空间 指针变量=new数据类型; 释放空间 delete指针变量; (5)赋值语句 (6)选择语句 (7)循环语句 北京林业大学信息学院 17:43 (8)使用的结束语句形式有: 函数结束语句 循环结束语句 异常结束语句 return break; exit(异常代码); 北京林业大学信息学院 17:43 (9)输入输出语句形式有: 输入语句 cin (scanf( )) 输出语句 cout (printf( )) (10)扩展函数有: 求最大值 max 求最小值 min 北京林业大学信息学院 17:43 人民邮电出版社 1.4 ? 算法和算法分析 算法定义:一个有穷的指令集,这些指令为解 决某一特定任务规定了一个运算序列 算法的描述: ? ? ? ? ? 自然语言 流程图 程序设计语言 伪码 17:43 北京林业大学信息学院 ? 算法的特性: ? ? ? ? ? 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本 北京林业大学信息学院 17:43 人民邮电出版社 算法的评价 ? ? ? ? 正确性 可读性 健壮性 高效性(时间代价和空间代价) 北京林业大学信息学院 17:43 人民邮电出版社 算法的效率的度量 ? 算法效率:用依据该算法编制的程序在计算机上 执行所消耗的时间来度量 事后统计 事前分析估计 北京林业大学信息学院 17:43 1.事后统计:利用计算机内的计时功能,不同算法 的程序可以用一组或多组相同的统计数据区分 缺点: ?必须先运行依据算法编制的程序 ?所得时间统计量依赖于硬件、软件等环境因素 ,掩盖算法本身的优劣 北京林业大学信息学院 17:43 2.事前分析估计: 一个高级语言程序在计算机上运行所消耗的时间取 决于: ?依据的算法选用何种策略 ?问题的规模 ?程序语言 ?编译程序产生机器代码质量 ?机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同 的计算机上运行,效率均不同,———使用绝对时 间单位衡量算法效率不合适 北京林业大学信息学院 17:43 时间复杂度的渐进表示法 ?算法中关键操作(循环和递归)重复执行的次数是问题 规模n的某个函数f(n),算法的时间量度记作: T(n)=O(f(n)) ?渐进符号(O)的定义:当且仅当存在一个正的常数 C和 n0 ,使得对所有的 n ? n0 ,有 T(n) ? Cf(n),则 T(n) = O(f(n)) 表示随着n的增大,算法执行的时间的增长率和 f(n)的增长率相同,称渐近时间复杂度。 北京林业大学信息学院 17:43 n * n阶矩阵加法: for( i = 0; i n; i++) for( j = 0; j n; j++) c[i][j] = a[i][j] + b[i][j]; 语句的频度(Frequency Count ): 重复执行的次数:n*n; T( n ) = O ( n 2) 即:矩阵加法的运算量和问题的规模n的平方是同一个量级 北京林业大学信息学院 17:43 变量计数 x = 0 ; y = 0; T1(n) = O(1) for ( int k = 0; k n; k ++ ) T2(n) = O(n) x ++; for ( int i = 0; i n; i++ ) T3(n) = O(n2) for ( int j = 0; j n; j++ ) y ++; T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2) 北京林业大学信息学院 17:43 void exam ( float x[ ][ ], int m, int n ) { float sum [ ]; for ( int i = 0; i m; i++ ) { //x中各行 sum[i] = 0.0; //数据累加 for ( int j = 0; j n; j++ ) sum[i] += x[i][j]; //关键操作 } for ( i = 0; i m; i++ ) //打印各行数据和 cout i “ : ” sum [i] endl; //关键操作 } 渐进时间复杂度为 O(max (m*n, m)) 算法的时间复杂度是由嵌套最深层语句的频度决定的 北京林业大学信息学院 17:43 例1:N×N矩阵相乘 for(i=1;i=n;i++) for(j=1;j=n;j++) {c[i][j]=0; for(k=1;k=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; T ? n ? ? O ? n3 ? } 算法中的基本操作语句为 c[i][j]=c[i][j]+a[i][k]*b[k][j]; T (n) ? ???1 ? ?? n ? ? n ? n ? o(n ) 2 3 3 i ?1 j ?1 k ?1 i ?1 j ?1 i ?1 n n n n n n 北京林业大学信息学院 17:43 例 2: for( i=1; i=n; i++) for (j=1; j=i; j++) for (k=1; k=j; k++) x=x+1; n 1? n 2 ? ??i ? ?i? ? i ?1 ? 2 ? i ?1 1 ? n( n ? 1)( 2n ? 1) n( n ? 1) ? ? ? ? ? 2? 6 2 ? n( n ? 1)( n ? 2) ? 17:43 北京林业大学信息学院 6 i (i ? 1) ? ?1 ? ? ? j ? ? 语句频度 = ? i ?1 j ?1 k ?1 i ?1 j ?1 i ?1 2 n i j n i n 例3:分析以下程序段的时间复杂度 i=1; while(i=n) i=i*2; ① ② 2 f (n) ?n 即f(n)≤log2n,取最大值f(n)=log2n 所以该程序段的时间复杂度T(n) =O( log2n) 北京林业大学信息学院 17:43 有的情况下,算法中基本操作重复执行的次数还 随问题的输入数据集不同而不同 【例4】顺序查找,在数组a[i]中查找值等于e的 元素,返回其所在位置。 for (i=0;i n;i++) if (a[i]==e) return i+1; return 0; ?最好情况:1次 ?最坏情况:n ?平均时间复杂度为:O(n) 北京林业大学信息学院 17:43 时间复杂度T(n)按数量级递增顺序为: 复杂度低 复杂度高 指数时间的关系为: O(2n)O(n!)O(nn) 当n取得很大时,指数时间 算法和多项式时间算法在 所需时间上非常悬殊 17:43 北京林业大学信息学院 渐进空间复杂度 ? 空间复杂度:算法所需存储空间的度量,记作: S(n)=O(f(n)) 其中n为问题的规模(或大小) ? 算法要占据的空间 算法本身要占据的空间,输入/输出,指令, 常数,变量等 ? ? 算法要使用的辅助空间 若输入数据所占空间和算法无关,则不考虑输入 本身所占空间,否则应同时考虑。 ? 北京林业大学信息学院 17:43 小结 1、数据、数据结构等基本概念 2、对数据结构的两个层次的理解 ? 逻辑结构的四种形式 ? 线性和非线性结构的逻辑特征 ? 存储结构的两种形式 3、抽象数据类型的表示方法 4、算法、算法的时间复杂度及其分析的简 易方法 北京林业大学信息学院 17:43