当前位置:首页 >> 工学 >>

数据结构教案第一章绪论


教学主题或 课程导论 第一章 绪论(1.1 节、1.2 节) 章、节 授课类型 教学过程 教学方式 教学资源 理论课√ 实验课 实习或课程设计 练习课 其他□ 前面导论 10 分钟,新课 78 分钟,布置作业 2 分钟 讲授√ 讨论√ 阅读√ 示范操作 多媒体课件√ 演示动画√ 练习 提问√ 其他□ 音像 其他√ 相关软件

教学目的及要求(分掌握、理解、了解三个层次): 教学目的及要求(分掌握、理解、了解三个层次): 本次课程要求学生了解什么是数据结构、数据结构课程的特点、数据结构研究的内容是什么, 理解在解决问题过程中所涉及问题中数据之间的逻辑关系,掌握本课程所涉及到的基本名词、 术语和概念,特别是数据的逻辑结构和存储结构之间的关系及性质。 教学内容提要: 教学内容提要: 分钟) 第一部分 前面章节简要回顾(约 10 分钟) 介绍数据结构课程的性质、特点、课程的整体框架介绍、本课程学习过程的说明、以及最 终的考核方法。理论课和实验课的要求、所需要的参考教材和习题辅导教材、学好本课程的意 义、以及如何学好数据结构这门课程。 分钟) 第二部分 新课(约 78 分钟) 第一章 绪论 分钟) 本章内容概述(约 3 分钟) 简述本章基本要求、学习内容、重点、以及本章教学内容安排 §1.1 什么是数据结构(约 35 分钟) 分钟) 提问:什么是数据结构? 分析用计算机可以解决那些问题, 其发展的背景以及解决问题的整体过程, 引出在用计算机解 决问题的过程中,需要考虑到数据与数据之间的关系。 举例说明: (1)图书检索系统中所涉及到的数据之间的关系——线性关系 (2)人家对弈问题过程中所涉及到的棋盘与棋盘数据之间的关系——树型结构 (3)十字路口交通灯颜色设计的问题中数据之间的关系——图型结构 引出数据结构的定义、研究的内容、及其基本概念、发展史和在整个学科中的地位和作用。 §2 基本概念和术语(约 45 分钟) 分钟) 分钟) (1)通过例子引出几个基本概念(约 5 分钟) ) 数据:是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程 序识别和处理的符号的集合, 是计算机程序加工的”原料”。 数据对象:数据对象是具有相同性质的数据元素的集合。举例说明。 数据元素:数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据 元素可以由若干数据项(Data Item)组成。举例说明。 数据项:数据项是数据不可分割的最小标识单位。举例说明。 说明几者之间的关系和区别。引出数据元素之间的关系、数据结构的定义。 分钟) (2)数据之间的按照关系不同的分类(约 5 分钟) ) 集合:数据元素之间无特殊关系; 线性结构:数据元素之间存在着一个对一个的关系; 树型结构:数据元素之间存在着一个对多个的关系; 图型结构。数据元素之间存在着多对多的关系。 分钟) (3)数据结构的形式定义(二元组定义)(约 10 分钟) )数据结构的形式定义(二元组定义) Data_Structure = (D, S)其中,D 是数据元素的有限集(即一个数据对象),S 是该对象 中所有数据成员之间的关系的有限集合。 举例说明:以复数为例,说明复数类的数据结构形式定义方式。以一个事务管理的程序为例,

说明该程序中数据之间的关系, 分钟) (4)数据的逻辑结构定义、逻辑结构的分类(约 10 分钟) )数据的逻辑结构定义、 数据的逻辑结构从逻辑关系上描述数据, 可以看作是从具体问题抽象出来的数据模型, 与数据 的存储无关,也与数据元素本身的形式、内容、相对位置无关;举例说明; 分钟) (5)数据的物理结构定义、物理结构的分类(约 10 分钟) )数据的物理结构定义、 数据结构在计算机中的表示(或称映象)称为数据的存储结构,又称为物理结构。它包括数据 元素的表示和关系的表示。 物理结构的分类: 着重讲解顺序存储结构和链式存储结构, 并说明二者之间的不同, 举例说明。 综合比较数据逻辑结构和物理结构之间的关系,并举例说明。 分钟) (6)数据类型的定义和分类(约 5 分钟) ) 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 数据类型可分两类: 原子类 型和结构类型。 §小结(约 2 分钟) 分钟) 小结 内容回顾、重点、难点。 分钟) 第三部分 布置作业(约 2 分钟) 习题练习。 重点和难点: 重点和难点: 重点:数据结构所涉及的基本概念、数据结构的分类,数据的逻辑结构和物理结构、他们 之间的关系。 参考资料: 参考资料: 《数据结构题集》严蔚敏等编著,清华大学出版社 《数据结构学习指导与习题详解》张凤琴等编,清华大学出版社 《数据结构(C 语言篇)习题与解析》李春葆编,清华大学出版社 注意事项及心得: 注意事项及心得: 注意把握时间。 注:表中选项打“√” 【第二次(2 学时)】 教学主题或 前面章节简要回顾 1.3 抽象数据类型、1.4 算法及其分析 章、节 授课类型 教学过程 教学方式 教学资源 理论课√ 实验课 实习或课程设计 练习课 其他□ 前面章节复习 5 分钟,新课 83 分钟,布置作业 2 分钟 讲授√ 讨论√ 阅读√ 示范操作 多媒体课件√ 演示动画√ 练习 提问√ 其他□ 音像 其他√ 相关软件

教学目的及要求(分掌握、理解、了解三个层次): 教学目的及要求(分掌握、理解、了解三个层次): 了解抽象数据类型的定义、表示和实现方法。理解算法设计的五个要素和基本要求;掌握算法 效率的度量方法,着重学习算法的时间复杂度分析。 教学内容提要: 教学内容提要: 分钟) 第一部分 前面章节简要回顾(约 5 分钟) 前面第一节、第二节内容的简要回顾。 分钟) 第二部分 新课(约 83 分钟) 分钟) 本次内容概述(约 3 分钟) 简述本次课的基本要求、学习内容、重点、以及内容安排 分钟) §1.3 抽象数据类型(约 25 分钟) 由数据类型定义引入抽象数据类型的定义。

抽象数据类型:由用户定义,用以表示应用问题的数据模型,指一个数学模型以及定义在此 抽象数据类型 数学模型上的一组操作。 抽象数据类型的定义方式: 抽象数据类型的定义方式 ADT 抽象数据类型名 { 数据对象:〈数据对象的定义〉 数据关系:〈数据关系的定义〉 基本操作:〈基本操作的定义〉 } ADT 抽象数据类型名 抽象数据类型的表示与实现, 抽象数据类型的表示与实现,举例说明:三元组的表示与实现。 语言的一些共同的约定。 类 C 语言的一些共同的约定。 §1.4 算法和算法分析(约 55 分钟) 分钟) 分钟) 一、算法的基本概念(约 10 分钟) (1)算法的定义:是对特定问题求解步骤的一种描述,是一个有穷的指令集,这些指令表示一 算法的定义 算法的定义: 个或多个操作。 (2)算法的特性 要素 算法的特性(要素 算法的特性 要素) – 有穷性:算法应在执行有穷步后结束,且每一步都在有穷时间内完成 – 确定性:每步定义都是确切、无歧义的 – 可行性:算法中描述的操作应能通过执行有限次已经实现的基本运算实现 – 输入:有 0 个或多个输入 – 输出:有一个或多个输出(处理结果)。 (3)算法设计的要求 算法设计的要求 – 正确性:不含有语法错误;对于各种合法的输入数据能够得到满足规格说明要求的结果。 – 可读性:要求程序有较好的人机交互性,有助于人们对算法的理解。 – 健壮性:对输入的非法数据能作出适当的响应或处理。 – 效率与低存储需求:主要指算法的执行时间和所需的最大存储空间,这两方面主要和问 题的规模有关。 分钟) 二、算法效率的度量(约 45 分钟) 分钟) (1)衡量算法的方法(约 5 分钟) 衡量算法的方法 – 算法的后期测试:在算法中的某些部位插装时间函数 time ( )测定算法完成 某一功能所 花费时间。 – 算法的事前估计:空间复杂度、时间复杂度 (2)算法的时间效率度量方法(时间复杂度)(约 30 分钟) 算法的时间效率度量方法( 复杂度) 分钟) 算法的时间效率度量方法 时间复杂度 依据的算法选用何种策略、问题的规模、书写程序的语言、编译程序所生成目标代码的质量、 硬件的速度。 一个特定算法“运行工作量”大小,只依赖于问题的规模(通常用整数 n 表示),或者说,它是 问题规模的函数。 一个算法所耗费的时间, 应该是该算法中每条语句的执行时间之和, 而每条语句的执行时间又 是该语句的执行次数(频度)与该语句执行一次所需时间的乘积。 语句的频度指的是该语句重复执行的次数。举例说明。 语句的频度指的是该语句重复执行的次数。举例说明。 (a) {++x; s=0;} ++x 的频度为 1 (b) for (i=1; i<=n; ++i) {++x; s+=x;} ++x 的频度为 n (c) for (j=1;j<=n;++j) for (k=1;k<=n;++k) {++x; s+=x;} ++x 的频度为 n2 我们假定,每条语句一次执行的时间都是相同的,为单位时间。这样我们对时间的分析就可以

独立于软硬件系统。时间复杂度是问题规模的函数——T( n )。 设解决一个问题的规模为 n ,基本操作被重复执行的次数是 n 的一个函数 f(n),假如,随 着问题规模 n 的增长,算法执行时间的增长率和 f(n)的增长率相同,则可记作: T (n) = O(f(n)) 其中 T(n)叫算法的渐进时间复杂度,简称时间复杂度, O 是 Order(数量级)的首字母, ( )叫算法的渐进时间复杂度, 意思是 T(n)与 f(n)只差一个常数倍。 举例说明时间复杂度的计算方法: 例对 n 个整数的序列进行选择排序。其中序列的“长度” n 为问题的规模。 void selectSort ( int a[ ], int n ) { //对 n 个整数 a[0],a[1],…,a[n-1]按递增顺序排序 for ( int i = 0; i < n-1; i++ ) { int k = i; //从 a[i]查到 a[n-1], 找最小整数, 在 a[k] for ( int j = i+1; j < n; j++ ) if ( a[j] < a[k] ) k = j; int temp = a[i]; a[i] = a[k]; a[k] = temp; } } (3)算法的空间效率度量方法(空间复杂度)(约 5 分钟) 算法的空间效率度量方法( 分钟) 算法的空间效率度量方法 空间复杂度) 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量,记作: 空间复杂度 S(n) = O(g(n)) 表示随着问题规模 n 的增大,算法运行所需存储量的增长率与 g(n)的增长率相同。 算法的存储量包括: – 输入数据所占空间; – 程序本身所占空间; – 辅助变量所占空间 §小结(约 3 分钟) 分钟) 小结 内容回顾、重点、难点。 分钟) 第三部分 布置作业(约 2 分钟) 书面作业:阅读教材程序段、分析其时间复杂度。并思考下列问题。 1 为什么要学习《数据结构》? 2 学习《数据结构》什么内容? 3 如何学习《数据结构》? 重点和难点: 重点和难点: 重点:掌握时间复杂度的概念、会计算问题的时间复杂度,了解空间复杂度。 难点:抽象数据类型概念的理解、问题时间复杂度的计算。 参考资料: 参考资料: 《数据结构题集》严蔚敏等编著,清华大学出版社 《数据结构学习指导与习题详解》张凤琴等编,清华大学出版社 《数据结构(C 语言篇)习题与解析》李春葆编,清华大学出版社 注意事项及心得: 注意事项及心得: 抽象数据类型要简略讲,注意把握时间


相关文章:
《数据结构》教案.doc
数据结构教案 - 教学单元(章节) : 第一章:绪论 1.1 数据结构概念 教学目的: 理解学习数据结构的重要意义 掌握数据结构的基本概念 知识要点: 数据结构、...
数据结构教案第一章绪论_图文.doc
数据结构教案第一章绪论 - 教学主题或 课程导论 第一章 绪论(1.1 节、1.
数据结构第一章绪论._图文.ppt
数据结构第一章绪论. - 数据结构 C语言描述 授课教师:岳静 电话:13551817786 E-mail: qiuqiuyj@163.com 教学网站: desktop.swpu.edu...
第一章_数据结构---绪论.pdf
第一章_数据结构---绪论_教育学_高等教育_教育专区。数学与软件科学学院信息与...数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构教案...
数据结构第一章绪论PPT_图文.ppt
数据结构第一章绪论PPT - 10 100 865 说在课程学习之前 ?为什么学习数据结构与算法? ?课程基本信息 ?学习目的与考核形式 为什么学习数据结构与算法? ? 算法:...
数据结构ppt第一章绪论_图文.ppt
数据结构ppt第一章绪论 - 数据结构》 主讲教师 陈明 ?教材 数据结构教程 李春葆等 清华大学出版社 数据结构 ( C语言版) 严蔚敏 吴伟民 清华大学出版社 ? 参考...
第1章 绪论-2013数据结构电子教案 c语言版本_图文.ppt
第 1章 绪论 第一章 绪论一、教学内容: 1、数据结构基本概念 数据、数据元素、数据对象、数据结构和数据类型等概念 2、算法及算法分析 性能分析与度量:算法的...
数据结构详细教案数据结构绪论.doc
7 数据结构教案 第 1 章 绪论 第1章 绪论 1.1 什么是数据结构 1.2
数据结构第一章绪论.ppt
数据结构第一章绪论_工学_高等教育_教育专区。数据结构C语言描述授课教师:岳静 电话:13551817786 E-mail: qiuqiuyj@163.com 教学网站: desktop.swpu.edu.cn...
数据结构 第一章 绪论_图文.ppt
数据结构 第一章 绪论 - ? 软件工程专业必修课程 数据结构 Data Structures 课程简介 教学目标: 了解数据的特性,学会数据的组织 及其在计算机内部的表示方法 ? ?...
数据结构教案第1章 绪论_图文.pdf
数据结构教案第1章 绪论 - 第一章 绪论 计算机是一门研究用计算机进行信息表示
第一章 数据结构---绪论.doc
第一章 数据结构---绪论 - 数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构教案-详案-2004 级 6 班 课程导入 课程性质:专业必修...
数据结构第1章 绪论教案.doc
数据结构第1章 绪论教案 - 第1章 本章主要介绍以下内容 绪论 1、数据结构的概念及其研究的主要内容 2、基本概念和术语 3、算法的概念、特点以及效率评价方法 本...
数据结构第一章 绪论_图文.ppt
数据结构第一章 绪论 - 莫尚丰 教材: 《数据结构》(C语言版) 严蔚敏 吴伟
第1章 绪论-2013数据结构电子教案 c语言版本分析_图文.ppt
第 1章 绪论 第一章 绪论一、教学内容: 1、数据结构基本概念 数据、数据元素、数据对象、数据结构和数据类型等概念 2、算法及算法分析 性能分析与度量:算法的...
数据结构第一章绪论_图文.ppt
数据结构第一章绪论 - 课程内容: ?计算机软件的基础知识数据结构 课时安排: ?数据结构64学时 ?上机16学时 ?4,5,6,7,10,11,12,13周,周一...
数据结构教案C语言版.pdf
三、课程教学内容第一章 绪论 教学内容: 1) 什么是数据结构 2) 抽象数据类型概念;数据类型;数据抽象与抽象数据类型;用于描述数据结构的 语言 3) 数据结构的抽象...
数据结构 第一章 绪论_图文.ppt
数据结构 第一章 绪论 - 数据结构 遥感信息工程学院 邬建伟 关于数据结构课程 数据结构, 数据结构,起源于程序设计需求: 是讨论“描述现实世界实体的数学模型 非...
1第一章 数据结构绪论_图文.ppt
1第一章 数据结构绪论 - 数据结构 (Data structure) 刘金定
考研 期末 数据结构 第一章 绪论_1.doc
第一章 绪论 1.1 什么是数据结构 一般来讲,用计算机解决一个具体问题时,大致
更多相关标签: