《数据结构》授课教案.doc

《《数据结构》授课教案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、授课教案　　2010～2011学年1学期开课单位：数学计算机科学学院课程名称：数据结构课程性质：专业基础课学分：3总学时：51理论学时：51实验学时：0机动学时：0授课专业：计算机科学技术/地理信息系统授课年级：2009级/2008级学生人数：80/37多媒体授课时数比例：100%主讲教师：左开中职　　称：副教授《数据结构》授课教案周次第1周第1次章节名称第一章：绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示和实现1.4算法与算法分析授课方式多媒体教室课堂讲授教具准备自制PPT电子课件教学

2、目的1．了解学习掌握数据结构的意义及数据结构的基本内容；2．掌握数据结构及数据、数据元素等相关概念；2．掌握抽象数据类型ADT的定义、表示与实现4．理解时间复杂度概念和基本的估算方法。教学重点1．数据结构的基本概念2．算法分析教学难点1．抽象数据类型ADT的定义、表示与实现2．算法时间复杂度及其计算授课要点1.1什么是数据结构用3个引例：1．图书书目自动检索2．人机对奕3．交通灯管理引出《数据结构》的研究内容1.2基本概念和术语1.数据2.数据元素、数据项3.数据对象、数据结构4.四类基本逻辑结构：集合、线性结

3、构、树形结构、图形结构或网状结构。5.数据结构一般包括三方面的内容：逻辑结构、存储结构(物理结构)和数据的运算算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。6.数据的两种存储结构：顺序存储结构和链式存储结构1.3抽象数据类型的表示与实现ADT的概念和类C语言1.4算法和算法分析1.4.1算法算法的定义算法具有五个重要特性：有穷性、确定性、可行性、输入、输出1.4.2算法设计的要求正确性，可读性，健壮性，高效率低存储1.4.3算法效率的度量时间复杂度1.4.4算法的存储空间需求空间复杂度课

4、堂讨论与练习1．什么是数据结构？数据、数据对象、数据元素、数据项等术语的关系和区别？2．数据类型和抽象数据类型是如何定义的，二者有何相同和不同之处？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？3．按照阶由低到高的顺序排列下列时间复杂度：作业1．分析并计算下面各程序段的最大语句频度和算法的时间复杂度。1）for(i=0;i

5、i=0;i

6、和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。课后记要周次第2周第1次章节名称第二章：线性表2.1线性表的类型定义2.2线性表的顺序表示与实现授课方式多媒体教室课堂讲授教具准备自制PPT电子课件教学目的1.了解线性表的结构特点；2.掌握线性表的逻辑结构；3．掌握线性表的顺序存储结构及其基本运算的实现；教学重点1．理解线性表的逻辑结构特性；2．熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；教学难点1．能

7、够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其应用场合；2．使用本章所学的基本知识设计有效算法，解决与线性表相关的应用问题。授课要点2.1线性表的类型定义1.线性表的定义（a1,…,ai-1,ai,ai+1,…an）2.定义在逻辑结构上的运算表的初始化、求表长、取表中的结点、查找结点、插入结点和删除结点等。3.抽象数据类型线性表的定义2.2线性表的顺序表示和实现1、线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素。用物理位置来表示逻辑结构。LOC(ai+1)=LOC(

8、ai)+lLOC(ai)=LOC(a1)+(i-1)*l2、顺序表的特点：随机存取3、线性表的动态分配顺序存储结构（用一维数组）#defineLIST_INIT_SIZE100#defineLISTINCREAMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;4、顺序表的运算顺序表容易实现访问操作，可随机存取