《数据结构[Python语言描述]》教案第3课线性表（2.1-2.2）.docx

课题第3课线性表(2.12.2)课时2课时(90min)教学目标知识目标：(1)理解线性表的定义和特点(2)掌握线性表的基本操作(3)掌握JII页序表的存储结构及其基本操作的实现技能目标：能根据线性表数据的特点选择合适的存储结构素质目标：通过了解"二十四节气”的起源，坚定文化自信教学重难点教学重点：线性表的基本操作、顺序表的存储结构及其基本操作教学睚点：顺序表的基本操作教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：什么是线性表？【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍线性表概述、顺序表存储结构和基本操作2.1 线性表概述线性表是最简单、最常用的数据结构，可以将其简单理解为"线性结构的表".【教师】随机邀请学生回答以下问即日常生活中，线性表的例子有哪些？*【学生】聆听、思考、回答26个英文字母、24个节气等排列规律的有限序列。【拓展阅读】”春雨惊春清谷天，夏满芒夏暑相连。秋处露秋寒霜降，冬雪雪冬小大寒这首仅28个字的“二十四节气歌”蕴含了中华民族千百年来的智慧浓缩。2016年，"二十四节气"入选联合国教科文组织非物质文化遗产名录。在国际气象界，这一已有千年历史的时间认知体系被誉为“中国第五大发明"。(详见教材)2.1.1线性表的定义和特点÷【教师】用多媒体展示“线性表的逻辑结构”图(详见教材)，介绍线性表的逻辑结构线性表是由11(110)个特性相同的数据元素组成的有限序列，数据元素之间是一对一的关系。线性表可以表示为Oi-l,4i,4+l,线性表中的每个数据元素都有一个确定的位置，劭为首元素，4为第/(0<<P-I)个元素，力为尾元素。相邻数据元素之间存在着序偶关系,a-1称为a的前驱元素，3+1称为a的后继元素。诩没有前驱元素，没有后继元素。除此之外，每个数据元素有且仅有一个前驱元素和一个后继元素。通常情况下，用线性表中数据元素的个数表示线性表的长度。当=0时，线性表为空表。2.1.2线性表的基本操作÷【教师】用多媒体展示“线性表基本操作的定义”表(详见教材)，介绍线性表的基本操作2.2线性表的顺序存储顺序表线性表的JI项序存储是指，在内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素。采用顺序存储结构的线性表称为顺序表。2.2.1 顺序表的存储结构假设顺序表中有n(nO)个数据元素,每个数据元素占用k个存储单元，且以顺序表中第一个数据元素的存储地址LOC(ao)作为顺序表的起始地址或基地址(用d表示)，则可以得到顺序表中第i个数据元素4的存储地址为1.oc(ai)=d+i×k(0in-l)相邻两个数据元素ai和密+1的存储地址之间的关系为1.oc(ai+)=Loc(ai)+k(0i<n-1)÷【教师】用多媒体展示“顺序表存储结构”图片(详见教材)，随机邀请学生回答以下问题观察该图片，思考顺序表的存储结构具有什么特点？÷【学生】聆听、观察、思考、回答在顺序表中,逻辑结构相邻的数据元素在物理存储单元中也是相邻的。只要确定顺序表的起始地址(基地址)和表中每个数据元素所占存储单元的大小，就可以计算出顺序表中任意一个数据元素的存储地址。也就是说，顺序表中任一数据元素都是可以随机存取的，这种存取元素的方法称为随机存取法。因此，线性表的顺序存储结构是一种随机存取的存储结构。2.2.2 顺序表中基本操作的实现1.初始化JI质序表初始化顺序表是为顺序表动态分配存储空间，并将其长度设置为0,其具体步骤如下。(I)设置JI质序表的最大容量。(2)设置Jl质序表的存储空间。(3)将顺序表的长度设置为0.【算法描述】classSqList:#定义顺序表类definit(self,max):#构造方法，定义变量并赋初值self.max=max#设置顺序表的最大容量self.data=None*self.max#设置顺序表的存储空间self.length=0#设置顺序表的长度为02.在JI圆字表中插入数据元素顺序表的插入操作是指在长度为n的顺序表的第i(0in)个位置之前插入一个数据元素e÷【教师】用多媒体展示“在顺序表中插入数据元素”图(详见教材)，并介绍顺序表的插入操作在顺序表中插入数据元素的具体步骤如下.(1)判断顺序表的存储空间是否已满，若已满，则抛出异常。(2)判断插入数据元素的位置i是否满足条件()4in,若不满足，则抛出异常。(3)将插入位置及其之后的所有数据元素依次向后移动一个位置，空出存放新数据元素的位置。(4)将新的数据元素插入到第i个位置。(5)顺序表的表长加Ie【算法描述】【算法分析】详见教材假设在顺序表任意位置插入数据元素的概率都是相同的，即/乙=一，则在长度为"的顺序表中w+1插入一个数据元素时，需要移动其他数据元素的平均次数为Stn0=因此，该算法的平均时间复杂度为0(加.【提示】最坏时间复杂度是算法在最坏情况下的时间复杂度，表示算法的计算量可能达到的最大值。最好时间复杂度是算法在最好情况下的时间复杂度，表示算法的计算量可能达到的最小值。平均时间复杂度是算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值，一股用于表示该算法的时间复杂度。3.在顺序表中删除数据元素顺序表的删除操作是指将顺序表中第/(O<<rl)个数据元素从顺序表中删除。÷【教师】用多媒体展示“在顺序表中删除数据元素”图(详见教材)，并介绍顺序表的删除操作在顺序表中删除数据元素的具体步骤如下.(1)判断删除数据元素的位置i是否满足条件OWSn-I,若不满足,则抛出异常。(2)将第i个数据元素之后的数据元素都向前移动一个位置。(3)顺序表的表长减1.【算法描述】【算法分析】详见教材假设在顺序表的任意位置删除数据元素的概率都是相同的，即Pj=-,则在长度为n的顺序表中n删除一个数据元素时，需要移动其他数据元素的平均次数为n/=O2因此，该算法的时间复杂度为0(加【高手点拨】在顺序表中插入和删除一个数据元素时，需要移动大量的数据元素，时间效率较低。4.在Jl质序表中杳找数据元素在顺序表中杳找数据元素的过程是从第一个数据元素(a)开始，依次将表中的数据元素与要查找的数据元素进行比较，若相等，则返回该数据元素在表中的位置；否则，查找失败。÷【教师】用多媒体展示“在顺序表中查找数据元素”图(详见教材)，并介绍在顺序表中查找数据元素操作在顺序表中查找数据元素的具体步骤如下。(1)从顺序表中第一个数据元素(a)开始，依次和要查找的数据元素e比较，若找到与e相等的数据元素ai,则查找成功，并返回该数据元素的位置i。(2)若顺序表查找完成后依然没有找到数据元素e,则查找失败，返回L【算法描述】【算法分析】详见教材假设在顺序表中每个数据元素的杳找概率都是相同的，即Pi=L,则在长度为n的顺序表中查找n数据元素时，需要查找数据元素的平均次数为因此，该算法的时间复杂度为Om5 .在顺序表中取指定数据元素【教师】用多媒体展示“在顺序表中取指定数据元素”图(详见教材)，并介绍在顺序表中取指定数据元素操作在顺序表中取指定数据元素的具体步骤如下。(1)判断指定的位置i是否满足条件OSSn-I,若不满足，则返回-1。(2)若i满足条件，将直接返回第/个数据元素。【算法描述】defgetElem(self,i):ifi<0ori>self.length-1:return-1returnself.datai【算法分析】该算法的时间复杂度为O(I)e6 .求酬表的长度求Il页序表的长度就是返回JI项序表中数据元素的个数。【算法描述】defgetLength(self):returnself.length【算法分析】该算法的时间复杂度为O(I)e7 .遍历Jl质序表遍历JI质序表就是依次访问JI顺序表中的各个数据元素。【算法描述】deftraversal(self):foriinrange(self.length):returnself.datai【算法分析】该算法的时间复杂度为08)。【高手点拨】当线性表的长度变化不大,且易于事先确定其大小时，为了节省存储空间，应使用顺序存储结构。此外，若线性表的主要操作是查找数据元素，且很少插入或删除数据元素，也应使用顺序存储结构。【教师】讲解实例2-1,2-2（详见教材），并要求学生完成实例2-3（详见教材）【学生】聆听、思考、理解、记录任务实施任务一利用顺序表存储学生成绩【教师】描述问题，分析问题，要求学生完成任务【问题描述】设计算法创建一个学生成绩表（其中每个学生的成绩信息包括学号、姓名、语文成绩、数学成绩、英语成绩、总成绩），实现学生成绩的录入、总成绩的计算，以及学生成绩的查询和删除。【问题分析】创建一个顺序表存储学生的成绩信息，首先输入学生人数确定要创建的JI砺表长度，然后依次录入每个学生的成绩信息并提示"成绩录入成功！"，最后计算学生个人总成绩。（详见教材）【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点线性表的定义、特点和基本操作顺序表的存储结构顺序表中基本操作的实现【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习。【学生】完成课后任务教学反思