(1.3)--(1)《数据结构》教案.pdf

《(1.3)--(1)《数据结构》教案.pdf》由会员分享，可在线阅读，更多相关《(1.3)--(1)《数据结构》教案.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1 第第1章章 概述概述(共共 2 学时，包括实训内容学时，包括实训内容)课题课题 1.1 数据结构的发展、1.2 基本概念、1.3 算法描述与分析 理论理论课时课时 1 学时 实实训训课时课时 1 学时 教学内容教学内容 数据结构的发展、基本概念、算法描述与分析 教学目标教学目标 了解数据结构的发展；掌握数据结构的基本概念、算法描述与分析 教学重点教学重点 数据结构的基本概念、算法描述与分析 教学难点教学难点 算法描述与分析 教学教学活动及主要活动及主要内容内容 学生活动学生活动 一、创设一、创设情境情境，导入新课（，导入新课（2 分钟）（分钟）（直接导入法直接导入法）导入：1.以学生信息

2、为例，每一名学生的信息包含学号、姓名、性别、出生日期等，若想在大量的数据中进行高效的增加、删除、修改、查询操作，可以将这些数据制成表，这种表就可以称为一种数据结构。本学期同学们要学习的就是数据结构，第一节课我们首先了解一下数据结构的发展历史，然后学习数据结构的基本概念以及算法描述与分析。二、新课二、新课讲解讲解（共共计计 16 分钟）（讲解法、提问法、分钟）（讲解法、提问法、演示演示法）法）第 1 章 概述 1.1 数据结构的发展 数据结构是一门综合性的学科，它是在 20 世纪 60 年代末期开始形成和发展起来的。它是集数学、计算机硬件和软件于一身的综合学科。它以数学的方法为基础，研究如何更加

3、合理有效地组织数据，编制出高质量的程序。即 程序算法+数据结构 1.2 基本概念 1.数据 2.数据元素和数据项 3.数据对象 4.数据结构（1）逻辑结构（2）物理结构 5.数据类型 6.抽象的数据类型(1)原子类型(2)固定聚合类型(3)可变聚合类型 启 发 学 生学习 数 据 结构的兴趣。此 部 分 主要由 老 师 来讲解，同时学生也 配 合 着老师 回 答 一些常见问题。2 7多型数据类型 1.3 算法描述与分析 1算法的 5 个重要特性 (1)有穷性 (2)确定性 (3)可行性 (4)有输入 (5)有输出 2算法的评价 (1)正确性 (2)可读性 (3)健壮性 (4)高效率 (5)低存

4、储 3时间复杂性 算法的执行时间需通过依据算法所编制的程序在计算机上运行时所消耗的时间来度量。度量一个程序执行的时间通常有两种方法。(1)事后统计法 (2)事先估算法【例例 1.1】分析如下程序段的时间性能。s=0；for(i=1;i=n;i+)s=s+i;分析分析：s=0;执行 1 次 i=1；执行 1 次 i=n；执行 n+1 次 s=s+i；执行 n 次 i+；执行 n 次 总的执行次数为 3（n+1）次，因此该算法的时间复杂性为 T(n)=O(3(n+1)=O(n)。【例 1.2】分析如下程序段的时间性能。x=0;y=10;while(y100)if（x=10）x=1；x+；y+=x；

5、分析：x=0;和 y=10;各执行一次；循环部分语句的执行过程取决于 x 值和 y 值的变化，总的执行次数为 2+18+17+1+17+17=72 次。这与问题规模 n 无关，因此，该算法的时间复杂性可以写成 T(n)=O(1)。此 时 学 生应该 注 意 看PPT 的演示。教师讲解，学生 思 考 分析时 间 复 杂性的方法。3 【练习】讨论起泡排序法的时间复杂性。void bubblesort(int a,int n)/*0 单元作为临时储存空间*/int i,j,change;/*change 为交换标志*/for(i=chang=1;change∈i+)for(j=1,change

6、=0;jaj+1)a0=aj;aj=aj+1;aj+1=a0;change=1;/*有交换，则进行下一趟比较*/4空间复杂性 与时间复杂性类似，空间复杂性也是关于问题规模 n 的一个函数，当问题规模 n 趋近于无穷大时的空间量级就称为算法的渐进空间复杂性，简称空间复杂性。记作：S(n)O(f(n)【例 1.4】将一维数组中的元素逆置存放。完成这一题目可有几种方法，下面列举出 3 种实现本要求的算法，从中分析哪种更好些。方法一：RevArray1(int a,int n)int i,j,t;for(i=0,j=n-1;ij;i+,j-)t=ai;ai=aj;aj=t;分析：由于基本语句就是循环内

7、的交换语句，共执行了 n/2 次，所以 T(n)=n/2=O(n)又，算法的辅助空间只是 i、j、t 这 3 个临时变量的空间，所以 S(n)=3=O(1)三三、归纳总结，再度提升归纳总结，再度提升（1 分钟）（讲解法）分钟）（讲解法）1.数据结构的发展 2.基本概念：数据、数据元素和数据项、数据对象、数据结构、数据类型等 3.算法描述与分析：算法的 5 个重要特性、算法的评价、时间复杂性、空间复杂性 学 生 实 践练习。4 四四、作业作业，预习任务预习任务（1 分钟）（激趣法）分钟）（激趣法）p10，习题 1。预习：2.1 线性表的定义和操作、2.2 顺序表 学 生 记 录作业 和 预 习内容。5 板 书 设 计 第 1 章 概述 1.3 算法描述与分析算法描述与分析 1算法的 5 个重要特性 2算法的评价 3时间复杂性(1)事后统计法(2)事先估算法 4空间复杂性 1.1 数据结构的发展数据结构的发展 1.2 基本概念基本概念 1.数据 2.数据元素和数据项 3.数据对象 4.数据结构 5.数据类型 6.抽象的数据类型 7多型数据类型