[工学]数据结构教案.doc

数据结构 教 案 2006～2007学年 第一学期 系 室 信管系计算机专业基础教研室 课 程 名 称 　 数 据 结 构 专业、年级、班级 　05级经济信息管理1班 主 讲 教 师 　　　　刘 玲 目 录 绪论 线性表 栈和队列 串 数组和广义表 树和二叉树 图 第九章 查找 第十章 内部排序 教材与课时安排 1、教材 严蔚敏编著. 数据结构（C语言版）. 清华大学出版社. 2、课时安排： 授 课： 44学时 上机训练： 10学时 —课程的性质和任务 ?《数据结构》是计算机科学与技术专业的核心基础课程之一。数据是计算机处理的对象，本门课程研究的数据是非数值性、结构性的数据。学习本门课程要求掌握各种主要数据结构的特点，计算机内的表示方法，处理数据的算法设计，对于算法所花费的时间和空间代价的分析也要求有一定程度的了解和掌握，以及在计算机科学中最基本的应用。通过本门课程的学习，要求学生能够组织，处理数据的理论和方法，培养训练学生选用合适的数据结构，能编写质量高，风格好的应用程序及初步评价算法程序的能力。《数据结构》的先行课程是计算机应用基础， C语言、C++语言、离散数学及概率等；后继课程有操作系统、编译原理、数据库原理、人工智能等。 学生学习时应注意本门课的特点：首先搞清楚各种数据结构的定义（逻辑结构），然后研究其可能的存储结构（物理结构），最后是一定存储结构上算法的实现。另外，配合适量的习题，辅以一定学时数的上机实践也是非常必要的，使学生在系统软件、应用软件特别是非数值软件的开发打下良好的理论基础的实践基础。 —学习要求 —课前预习，课后复习。 —上机前应设计好算法，编写好程序。 —每次作业在两周内完成，由教师检查。 第1次课 第1章 绪 论 2006-09-04 课 题 数据结构的基本概念和算法的基本概念 教案号 1 教 学 目 的 了解数据结构的基本概念，理解常用术语 课 时安 排 2 教学方法 讲授 教具 计算机、投影仪 教学的过程安排： 步骤 内容 重点 难点 要求 课堂互动 一 20分钟 1．1 什么是数据结构 通过书上的三个例子解说—— 例1－1 线性结构 例1－2 树形结构 例1－3 图形结构 数据结构的概念 数据结构的概念 完全领会 提问： (1)你认为计算机是如何实现人机对弈的？ (2)你会如何解决多叉路口交通灯的管理问题？ 二45分钟 1．2 基本概念和术语 包括：数据、数据元素、数据对象、数据结构、结构、集合、线性结构、树形结构、图形结构、逻辑结构、物理结构、顺序存储结构、链式存储结构、数据类型、原子类型、结构类型、抽象数据类型、多形数据类型 数据结构、线性结构、树形结构、图形结构、顺序存储结构、链式存储结构 抽象数据类型 完全领会、熟记 反复提问：有哪四类基本结构？ 引导提问：你知道的数据类型有哪些？ 三25分钟 1．4 算法和算法分析 包括：1个定义、5个特性、5个性能标准、2个效率的度量（时间复杂度和空间复杂度） 算法的概念、时间复杂度、空间复杂度 时间复杂度 能判断简单算法的时间复杂度 幻灯片上的题目，要求学生一起做，引导他们作答 授课内容提要： 1、数据的定义 举例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。 举例：图像、声音等。 2、数据元素、数据项3、数据对象 4、数据结构 定义二：相互之间存在特定关系的数据元素集合。 形式定义：数据结构名称=（D，S）D为数据元素的有限集，S是D上关系的有限集 一个值的集合和定义在这个值集上的一组操作的总称。 C语言中的整型，其内涵为一定范围的自然数集合，及定义在该集合上的加减乘除及取模、比较大小操作。而实型则无取模操作。当然整型也不需四舍五入。ADT） 关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。 作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。 7、算法 定义：对特定问题求解步骤的一种描述，是指令的有限序列。 特性：有穷性、确定性、可行性、输入、输出 性能标准：正确性、可读性、健壮性、快速性、节省性 效率度量标准：时间复杂度、空间复杂度 课堂小结 1. 熟悉各名词、术语的含义，掌握基本概念。 2. 理解算法五个要素的确切含义。 布置作业： 1．简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 第2次课 第2章 线性表 2006-09-11 课 题 线性表的类型定义和顺序表示 教案号 2 教 学 目 的 掌握线性表的概念和类型定义 课 时安