《数据结构[Python语言描述]》教案第1课绪论（1.1-1.3）.docx

数据结构教案课时分配表章序课程内容课时备注1绪论42线性表43栈和队列64串25数组和广义表26树和二叉树67图48直找49排序4酎36课即绪论(1.1-13)课时2课时(90min)教学目标知识目标：(1)熟悉数据结构的基本概念和术语(2)理解数据的逻辑结构、存储结构和抽象类型等概念技能目标：能针对实际问题设计出较高质量的算法，并使用多种方法进行描述素质目标：学习楷模事迹，汲取开拓创新、无私奉献的榜样力量教学重难点教学重点：数据结构的基本概念和术语、数据的逻辑结构和存储结构教学难点：数据的逻辑结构和存储结构、抽象数据类型教学方法问答法、讨论法、讲授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用文旌课堂APP进行签到【学生】班干部报请假人员及原因新课预热【教师】自我介绍，与学生简单互动，介绍课程内容、考核标准等【学生】聆听、互动【教师】讲一些数据结构发展历程、主要研究内容及本课程概述早期的计算机主要用于数值计算，到20世纪中叶后，逐渐扩展到对非数值的计算，它所处理的对象越来越多，包括图像、视频、表格等具有一定结构的数据。如何合理地组织这些数据，并对它们进行高效的处理，就是“数据结构”主要研究的内容。【学生】聆听、记录、理解问题导入【教师】提出以下问题数据是什么?谈谈你对数据的理解。【学生】思考、举手回答【教师】通过学生的回答引入要讲的知识传授新知【教师】介绍数据的基本概念和术语、逻辑结构和存储结构、抽象数据类型1 .1基本概念和数据2 .数据数据(data)是客观事物的符号表示，在计算机科学中，是指所有能被计算机程序识别、存储、加工和处理的符号的总称，它是计算机程序加工的"原料"。对计算机科学而言，的含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。3 .数据元素数据元素(dataelement)是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。数据元素又称为元素或记录。÷【教师】通过多媒体展示表1(详见教材)，介绍数据元素如表1-1所示的学生基本信息表中，每个学生的信息就是一例据元素。3 .数据项*【教师】随机邀请学生回答以下问题什么是数据项？【学生】聆听、思考、回答数据项(dataitem)是组成数据元素的、有独立含义的、不可再分的最小单位，如学生基本信息表中的学号、姓名等.4 .又揄数据对象(dataobject)是性质相同的有限个数据元素的集合，是数据的一个子集。*【教师】通过多媒体展示“数据元素、数据项及数据对象之间的关系”图片(详见教材)，并介绍三者之间的关系5 .数据结构数据结构(datastructure)是相互之间存在一种或多种关系的数据元素的集合。结构就是指数据元素之间的相互关系，因此，可以将数据结构看作带结构的数据元素的集合.1.2逻辑结构和存储结构数据结构包含3个方面，即数据的逻辑结构、数据的存储结构和数据的基本操作及其实现。其中，数据的基本操作及其实现定义在数据的逻辑结构和存储结构之上。1.2.1 逻辑结构数据的逻辑结构是指数据元素之间逻辑关系的描述，它与数据的存储无关,独立于计算机，是从具体问题抽象出来的数学模型.根据数据元素之间关系的不同，可分为4种不同的逻辑结构。*【教师】通过多媒体展示逻辑结构图(详见教材)，并介绍各自的特点(1)集合结构的数据元素之间只有属于同一个集合的关系。例如，判断一个数字是否为整数，可以将所有整数看作一个集合结构。(2)线性结构的数据元素之间是一对一的关系。此时每个数据元素都有唯一的前驱元素(第一个元素除外)和唯一的后继元素(最后一个元素除外)。例如，由多节车厢组成的列车、排队买票人员、一叠盘子等都可以看作线性结构。(3)树形结构的数据元素之间是一对多的关系。例如，学校的组织结构、家族关系等都可以看作树形结构。(4)图形结构(也称网状结构)的数据元素之间是多对多的关系。此时每个数据元素都可以有多个前驱元素或后继元素。例如，城市公共交通网、计算机网络等都可以看作图形结构。【知识库】集合结构、树形结构和图形结构均属于非线性结构。1.2.2存储结构数据的存储结构(也称物理结构)是指数据元素在计算机中的存储表示,是逻辑结构在计算机中的实现。将数据元素存储到计算机时，通常既要存储各数据元素的数据项，又要存储数据元素之间的逻辑关系。根据数据元素之间的逻辑关系在计算机中的不同表示，可分为两种不同的存储结构，分别是顺序存储结构和链式存储结构。*【教师】随机邀请学生回答以下问题试分析顺序存储结构和链式存储结构的区别。【学生】聆听、思考、回答三三l勾顺序存储结构是指逻辑上相邻的数据元素，其物理位置(内存中的位置)也相邻，数据元素间的逻辑关系由存储单元的邻接关系体现。顺序存储结构是一种最基本的存储方法，通常借助程序设计语言中的数组来实现。【教师】通过多媒体展示顺序存储的学生基本信息，井介绍顺序存储特点2.链式存储结构链式存储结构是指在计算机中用一组任意的存储单元存储数据元素，然后再通过地址链接的形式将全部数据元素组织到一起。这组任意的存储单元既可以是连续的，也可以是不连续的。链式存储结构通常借助程序设计语言中的指针来实现,在这种存储结构中,逻辑上相邻的数据元素，其物理位置不一定相邻。【教师】通过多媒体展示链式存储的学生基本信息，并介绍链式存储特点1.3抽象数据类型数据类型(datatype)是一组性质相同的值的集合和定义在该集合上的一组操作的总称，它最早出现在高级程序设计语言中用于描述操作对象的特性(如取值范围、允许执行的操作等)。抽象数据类型(abstractdatatype,ADT)是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。抽象数据类型和数据类型实质上可看作一个概念。"抽象”的意义在于辘类型的数学抽象特性。【高手点拨】抽象数据类型含义更广，不仅包括各种不同的计算机处理器中已定义并实现的数据类型(又称固有数据类型)，还包括设计软件系统时用户自己定义的复杂数据类型，且所定义的数据类型的抽象层次越高，含有该数据类型的软件复用程度就越高。抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一个最基本的原则，即通过封装和信息隐蔽，使对象操作的具体实现方法和外部引用相分离。÷【教师】通过多媒体展示三元组来描述抽象数据类型，介绍三元组含义及抽象数据类型的格式用三元组(D,S,P)来描述抽象数据类型。其中，D是数据对象，S是D上的关系集，P是对D的操作集，因此抽象数据类型的格式定义如下。ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT抽象数据类型名【学生】聆听、思考、理解、记录任务实施【教师】要求学生构造整数集合SET,基本操作包括求集合的长度、判断元素是否在集合中ADTSET(数据对象：D=diO<=i<=size-l雌关系：无基本操作：getSize()#求集合的长度get(i)#求集合的第i个元素isln(e)#判断元素e是否在集合中add(e)#将元素e添加到集合中delete(e)#从集合中删除元素edisplay()#输出集合中的元素ADTSET【学生】按照要求完成任务,如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点数据结构的基本概念和术语逻辑结构和存储结构抽象数据类型【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习.【学生】完成课后任务教学反思