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

数据结构教案第一章绪论


教学主题或 课程导论 第一章 绪论(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 语言篇)习题与解析》李春葆编,清华大学出版社 注意事项及心得: 注意事项及心得: 抽象数据类型要简略讲,注意把握时间


相关文章:
数据结构 第1章 绪论
数据结构 第1章 绪论_理学_高等教育_教育专区。第1章 绪论一、选择题 1. 算法的计算量的大小称为计算的(B)。 A.效率 B. 复杂性 C. 现实性 D. 难度 2...
数据结构习题第1章 绪论答案
数据结构习题第1章 绪论答案_理学_高等教育_教育专区。第 1 章绪论 一、单项选择题 1.①B②D。 2.C。 3.A。 4.B 5.C 6.A。 7.C A 8.C。 9....
第一章绪论习题解析
第一章 绪论一,选择题 1.组成数据的基本单位是( ) A.数据项 B.数据类型 ...A.理想结构,物理结构 B.理想结构,抽象结构 C.物理结构,逻辑结构 D.抽象结构,...
数据结构 第1章 绪论
数据结构 第1章 绪论_理学_高等教育_教育专区。帮助大家更好的理解1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的① 、数据信息...
数据结构练习 第一章 绪论
数据结构练习 第一章 绪论 - 数据结构练习 第一章 绪论 一、选择题 1.以下数据结构中哪一个是非线性结构?( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 2...
数据结构第1章绪论习题答案
数据结构第1章绪论习题答案_工学_高等教育_教育专区。习题及详细答案Ch1 绪论 1.下列与数据元素有关的叙述中,哪一个是不正确的( B )。 A.数据元素是数据的基...
数据结构第1章 绪论 答案
数据结构第1章 绪论 答案数据结构第1章 绪论 答案隐藏>> 第一章 概论 一、填空题 测试题 答案 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操...
数据结构绪论基础
数据结构绪论基础 - 一、单项选择题: 1、从逻辑上可以把数据结构分为集合结构、线性结构、 ( 种结构。 A、 动态结构 B、静态结构 C、树形结构 D、链式结构 ...
《数据结构》习题集:第1章 绪论
数据结构课后练习题第一章 绪论一、 1. 选择题 数据结构被形式定义为(D,S),其中 D 是(B)的有限集合,S 是 D 上的(H )有限集合。 A、算法 B、数据元素...
1数据结构实验1绪论
与技术 学号 姓名 课程名称:数据结构 实验室 计算机号 成绩评定 教师签名 日期: 实验 1 绪论 (复习 C 语言) VC 1.熟练掌握 C 语言中数组,指针和结构体的...
更多相关标签: