《严蔚敏最新版《数据结构》电子教案》由会员分享，可在线阅读，更多相关《严蔚敏最新版《数据结构》电子教案（55页珍藏版）》请在金锄头文库上搜索。
1、人民邮电出版社北京林业大学信息学院* 李冬梅李冬梅 数据结构数据结构人民邮电出版社北京林业大学信息学院* v编程基础v计算机及相关专业考研考博课程v计算机等级考试课程v程序员考试课程为什么要学习数据结构北京林业大学信息学院* 课程学习指导 1.提前预习、认真听课、按时完成书面及上机作业 2.注意先修课程的知识准备 离散数学、C语言 3.注意循序渐进： 基本概念、基本思想、基本步骤、算法设计 4.注意培养算法设计的能力 理解所讲算法、对此多做思考：若问题要求不同 ，应如何选择数据结构，设计有效的算法课程特点：内容抽象、概念性强、内容灵活、不易掌握北京林业大学信息学院* 平时成绩 : 30% 作业
2、、小测验、实验 课堂纪律 无故迟到： 无故旷课： 上机：玩游戏、上网聊天 期末成绩 : 70%(闭卷笔试)考核方式北京林业大学信息学院* 教材和参考书教材： 数据结构978-7-115-23490 严蔚敏，李冬梅，人民邮电出版社出版 参考书： 数据结构C语言版，严蔚敏，清华大学出 版社 数据结构用面向对象方法与C+描述 ，殷人昆等，清华大学出版社* 第1章 绪论1. 了解数据结构研究的主要内容2.掌握数据结构中涉及的基本概念 3. 掌握算法、算法的时间复杂度及其分析的 简易方法 教学目标北京林业大学信息学院* 1.1 数据结构的研究内容1.2 基本概念和术语1.3 抽象数据类型的表示与实现 1
3、.4 算法与算法分析教学内容人民邮电出版社北京林业大学信息学院* 人民邮电出版社北京林业大学信息学院* (2)数据元素被约定为ElemType 类型，用 户需要根据具体情况，自行定义该数据类型。(3)算法描述为以下的函数形式：函数类型 函数名（函数参数表）语句序列；北京林业大学信息学院* （4）内存的动态分配与释放 使用new和delete动态分配和释放内存空间 分配空间 指针变量=new数据类型; 释放空间 delete指针变量;（5）赋值语句 （6）选择语句 （7）循环语句北京林业大学信息学院* （8）使用的结束语句形式有：函数结束语句 return 循环结束语句 break; 异常结束语
4、句 exit（异常代码）；北京林业大学信息学院* （9）输入输出语句形式有：输入语句 cin (scanf( ) 输出语句 cout (printf( )（10）扩展函数有：求最大值 max 求最小值 min人民邮电出版社北京林业大学信息学院* n n算法定义：算法定义：一个有穷的指令集一个有穷的指令集，这些指令为解，这些指令为解 决某一特定任务规定了一个运算序列决某一特定任务规定了一个运算序列n n算法的描述：算法的描述：uu自然语言自然语言uu 流程图流程图uu 程序设计语言程序设计语言uu 伪码伪码1.4 算法和算法分析北京林业大学信息学院* n n算法的特性：算法的特性：uu输入输入
5、有有0 0个或多个输入个或多个输入uu 输出输出 有一个或多个输出有一个或多个输出( (处理结果处理结果) )uu 确定性确定性 每步定义都是确切、无歧义的每步定义都是确切、无歧义的uu 有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束uu 有效性有效性 每一条运算应足够基本每一条运算应足够基本人民邮电出版社北京林业大学信息学院* 算法的评价算法的评价uu正确性正确性uu可读性可读性uu健壮性健壮性uu高效性（高效性（时间代价时间代价和空间代价）和空间代价）人民邮电出版社北京林业大学信息学院* 算法效率：用依据该算法编制的程序在计算机上 执行所消耗的时间来度量算法的效率的度量算法
6、的效率的度量事后统计 事前分析估计北京林业大学信息学院* 1.事后统计：利用计算机内的计时功能，不同算法 的程序可以用一组或多组相同的统计数据区分缺点： 必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素 ，掩盖算法本身的优劣 北京林业大学信息学院* 2.事前分析估计： 一个高级语言程序在计算机上运行所消耗的时间取 决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同 的计算机上运行，效率均不同，使用绝对时 间单位衡量算法效率不合适北京林业大学信息学院* 算法中关键操作（循环和递归）重复执行的
7、次数是问题 规模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)的增长率相同，称渐近时间复杂度。北京林业大学信息学院* n * n阶矩阵加法： for( i = 0; i n; i+) for( j = 0; j n; j+) cij = aij + bij; 语句的频度（Frequency Count ): 重复执行的次数：n*n; T( n ) = O (
8、n 2) 即：矩阵加法的运算量和问题的规模n的平方是同一个量级北京林业大学信息学院* 变量计数变量计数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) = O(n2)T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) )= O(n2)北京林业大学信息学院* void exam ( float x , int m, int n ) float s
9、um ;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; /关键操作渐进时间复杂度为 O(max (m*n, m)算法的时间复杂度是由嵌套最深层语句的频度决定的北京林业大学信息学院* 例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;算法中的基本操
10、作语句为 cij=cij+aik*bkj; 北京林业大学信息学院* 例2： for( i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+)x=x+1;语句频度 =北京林业大学信息学院* 例3：分析以下程序段的时间复杂度i=1; while(i=n)i=i*2; 即f(n)log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n) =O( log2n)北京林业大学信息学院* 【例4】顺序查找，在数组ai中查找值等于e的 元素，返回其所在位置。for (i=0;i n;i+)if (ai=e) return i+1;return 0;
11、有的情况下，算法中基本操作重复执行的次数还 随问题的输入数据集不同而不同 最好情况：1次 最坏情况：n 平均时间复杂度为:O(n)北京林业大学信息学院* 时间复杂度时间复杂度T(n)T(n)按数量级递增顺序为：按数量级递增顺序为：复杂度高复杂度低指数时间的关系为：O(2n)O(n!)O(nn)当n取得很大时，指数时间 算法和多项式时间算法在 所需时间上非常悬殊北京林业大学信息学院* 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n) 其中n为问题的规模(或大小)n算法要占据的空间算法本身要占据的空间，输入/输出，指令， 常数，变量等算法要使用的辅助空间n若输入数据所占空间和算法无关，则不考虑输 入本身所占空间，否则应同时考虑。渐进空间复杂度北京林业大学信息学院* 1、数据、数据结构等基本概念2、对数据结构的两个层次的理解 逻辑结构的四种形式 线性和非线性结构的逻辑特征 存储结构的两种形式3、抽象数据类型的表示方法4、算法、算法的时间复杂度及其分析的简易 方法小结
