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

《《数据结构[Python语言描述]》教案第4课线性表（2.3）.docx》由会员分享，可在线阅读，更多相关《《数据结构[Python语言描述]》教案第4课线性表（2.3）.docx（7页珍藏版）》请在优知文库上搜索。

1、课题第4课线性表（23）课时2课时(90min)教学目标知识目标：（1）掌握单链表和双链表的结构特点及其基本操作的实现（2）理解循环链表的特点技能目标：能使用线性表解决实际问题素质目标：增强主动思考、积极寻求问题解决方法的意识教学重难点教学重点：单链表和双链表的结构特点及其基本操作、循环链表的特点教学难点：单链表和双链表的结构特点及其基本操作教学方法问答法、讨论法、讲授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入（5min）【教师】提出以下问题：如你螂链式存储?【蚂思考、传授新知【教师】通过学生的

2、回答引入要讲的知识，介绍单链表和双链G的特点2.3线性表的链式存储一链表线性表的链式存储是指，用一组地址任意的存储单元依次存f单元可以是连续的，也可以是不连续的。采用链式存储结构的线t链表又可以分为单链表、双链表和循环链表等。2.3.1 单链表1.单链表的结构特点在线性表的链式存储结构中,为了表示每个元素与其后继元彳本身的数据信息外，还要存储一个指示其后继元素地址的信息，1的存储结构，称为结点（node）。莅的结构特点及其基本操作、循环链表谱线性表中的各个数据元素，这些存储生表称为链表。黄之间的逻辑关系，除了需要存储元素区两部分信息共同构成了一个数据元素datanext其中，存储元素本身?域（

3、next）单链表（也称线性链其中每个结点只包含一个象据信息的部分称为数据域（data）,存储其后继元素地址信息的部分称为指针麦）是指将n个数据元素通过其对应结点的指针域按其逻辑关系链接成的链表，数据域和一个指针域.“014.On-head.F其中,head称为头指针,用于指向单链表的第一个结点（也称首元结点）。由于单链表的最后一个结点没有后继元素，所以其指针域为空（None）,用符号人表示。【提示】在Python中并不存在指针的概念，此处的指针属性实际上存放的是后继结点的引用，但为了表述datanext方便仍然采用指针一词。【教师】讲解实例2-4(详见教材)在单链表中，逻辑上相邻的两个数据元素

4、，其存储的物理位置不一定相邻，每个数据元素的存储地址都存放在其前驱结点的指针域中。要想取得第/个结点，必须从头指针出发按照顺序依次在单链表中寻找，因此，线性表的链式存储结构是一种顺序存取的存储结构。为了操作方便,通常在单链表的第一个结点之前增加一个头结点。单链表的头指针指向头结点，头结点的数据域可以不存储任何数据信息，也可以存储与线性表中瘫元素类型相同的其他附加信息。头结点的指针域存储第一个结点的地址信息。.(详见教材)【高手点拨】为避免读者对首元结点、头结点和头指针的概念产生混淆，下面分别对其进行解释说明。(1)首元结点是指链表中存储第一个数据元素的结点。(2)头结点是在首元结点之前增加的一

5、个结点，其指针域指向首元结点。.(详见教材)2.单链表中基本操作的实现1 )初始化单链表初始化单链表就是构造一个空表。步点head【算法描述】classSLinkList:def_init_(self):self.head=Node(None)self.head.next=None2)建立单链表建立单链表是在一个空表中一次性创建多个结点。建立单链表的常用方法有头插法和尾插法两种。(1)头插法是通过将新结点逐个插入单链表中的头结点之后来建立单链表。【教师】用多媒体展示“使用头插法建立单链表”图(详见教材)，并介绍算法描述使用头插法建立单链表可分为如下6步。建立艮有头结点的空表。生成第一个结点s.

6、其中，新结点的数据域存储数据元素的数据信息，指针域为None将第一个结点插入头结点之后.生成新结点%将新结点的指针指向第一个结点(s,nexl=head,nex(),然后将头结点的指针指向新结点S(head.nex(=s)0重复步骤和,直到单链表生成完毕.【算法描述】详见教材【提示】上述算法中的语句==S的顺序不能颠倒。若先执行语句head.next=S,再执彳谴句=head.next,会找不到结点a,此时相当于执行语句s.next=s,插入操作将出现错误.（2）尾插法是通过将新结点逐个插入单链表的尾部来建立单链表。*【教师】用多媒体展示“使用尾插法建立单链表”图（详见教材），并介绍算法描述使

7、用尾插法建立单链表可分为如下3步。建立只有头结点的空表，并增加指针t,使其指向头结点。从线性表的第一个数据元素开始依次获取表中数据元素，并生成一个新结点S0其中，新结点的数据域存储数据元素的数据信息，指针域为Nonee将新结点插入当前链表的表尾，并使指针t始终指向当前链表的尾结点。【算法描述】详见教材【教师】讲解实例2-5（详见教材）3）在单链表中取指定结点的值若要在单链表中取指定结点的值，须从单链表的首元结点出发，然后顺着指针域向后依次访问各个结点.【教师】讲解具体步骤，并介绍算法描述（详见教材）4）在单链表中插入结点单链表的插入操作是指在长度为n的单链表的第i（0in）个位置插入一个值为e

8、的结点，因此，须首先找到插入位置的前驱结点，然后修改该结点的指针域。*【教师】讲解具体步骤，并介绍算法描述（详见教材）5）在单链表中删除结点删除单链表中的结点与插入结点类似，也须首先找到删除结点的前驱结点，然后修改该结点的指针域。【教师】讲解具体步骤，并介绍算法描述（详见教材）6）在单链表中查找结点要查找单链表中值为e的结点，需从单链表的首元结点开始，逐个将结点的值与e进行比较。当两者相等时，则当前指针指向的就是要查找的结点，其具体步骤如下。（1）使用指针P指向首元结点.（2）从首元结点开始顺看指针域依次向后查找，只要当前结点的指针p不为空，且P所指结点的数据域与要查找的值e不相等，就循环执行

9、p指向下一个结点的操作。（3）直找成功后，返回p【算法描述】defIistLocate（self,e）:=self.head.next#P指向首元名吉点#查找值为e的结点并由P指向该结点whilepisnotNoneandp.data!=e:=.nextreturnp【算法分析】该算法的时间复杂度为0（n）.7）遍历单链表遍历单链表就是依次访问单链表中的各个结点，并输出各个结点的值.【算法描述】deftraversal（self）:P=self.head,next#P指向首元结点whilepisnotNone:#判断当前指针是否指向尾结点print（p.data,end=,1）p=p.next

10、【算法分析】该算法的时间复杂度为08）。【教师】讲解实例2-6（详见教材）2.3.2双链表1 .双链表的结构特点在单链表中，每个结点只设置了一个指针域用于指示该结点的后继结点。因此，从单链表的任意结点出发，都只能顿着指针方向向后杳找其他结点。若要杳找其前驱结点，必须从单链表的头结点出发，从前向后依次杳找.为此，在单链表的每个结点中增加一个指向其前驱结点的指针域，这样的链表称为双链表。【教师】随机邀请学生回答以下问翘试分析双链表的结构特点。计【学生】聆听、思考、回答双链表中的每个结点有一个数据域（data）和两个指针域（prior和next）,一个指针域（prior）指向该结点的前驱结点，另一个

11、指针域（next）指向该结点的后继结点。priordatanext双链表的一般形式：（详见教材）2 .双链表中基本操作的实现1 ）初始化双链表初始化双链表就是构造一个空表。【算法描述】classDLinkList:definit（self）:self.head=DNode（None）self.head.next=Noneself.head.prior=None2）在双链表中插入结点在长度为n的双链表的第i（0in）个位置插入一个值为e的结点，首先需要找到第i-1个结点，然后修改4个指针属性。【教师】用多媒体展示“在双链表中插入结点”图，并介绍详细步骤和算法描述（详见教材）【提示】以上算法是在双

12、链表中先找到第i-1个结点，然后在该结点之后插入新结点，还可以在双链表中先找到第i个结点，然后在该结点之前插入新结点。3）在双链表中删除结点删除长度为n的双链表的第i（0in-1）个结点，首先需要找到该结点，然后修改其前驱结点和后继结点的指针属性.【教师】用多媒体展示“在双链表中删除结点”图，并介绍详细步骤和算法描述（详见教材）【提示】以上算法是在双链表中先找到第i个结点，然后通过其前驱结点和后继结点删除该结点，还可以在双链表中先找到第i-1个结点，然后再删除其后继结点。【教师】讲解实例2-7（详见教材）2.3.3循环链表*【教师】随机邀请学生回答以下问题什么是循环链表？【学生】聆听、思考、回

13、答将链表中最后一个结点的指针域指向头结点，从而形成一个首尾相接的链表，这样的链表称为循环链表。在循环链表中，所有结点链接在环上，从循环链表中任一结点出发均可找到其他结点。循环链表又可以分为循环单链表和循环双链表。【教师】用多媒体展示“带头结点的循环单链表”“带头结点的循环双鞋表”图片（详见教材），并介绍这两种循环链表循环链表的操作与普通链表基本一致，不同的是，在循环链表中判断某个结点为尾结点的条件不是其后继结点为空，而是其后继结点为头结点.（详见教材）【高手点拨】当线性表的长度变化较大，难以事先确定其大小时，应使用链式存储结构。此外，若线性表的主要操作是插入或删除，也应使用链式存储结构。【学生

14、】聆听、思考、理解、记录任务实施任务利用单链表实现多项式相加【教师】描述问题，分析问题，要求学生完成任务【问题描述】已知有两个-元n阶多项式a（x）=a+alx+a2x2+a3x3+.+anxn和b（x）=b+b1x+b2x2+b3x3+.+bnxn,设计算法求它们的和C（X）。【问题分析】多项式中的每一项由其系数和指数来确定，如a2x2中的a2是系数，x2中的2是指数.多项式相加的规则是指数相同的项，指数不变，系数相加；指数不同的项，指数小的项在前，指数大的项在后，最后合并两项即可。（详见教材）【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问眶任务二一利用循环链表解决约瑟夫问题【教师】描述问题,分析问题,安排学生扫描微课二维码观看视频“利用循环链表解决约瑟夫问题“（详见教材），要求学生完成任务【问题描述】设编号为1、2、n的n个人按既定方向围坐一圈，从第一个人开始报数，数到m的人出列，下一个人继续从I开始报数,数到m的人出列。依此规则重复下去，直到最后一个人出列，这就是著名的约瑟夫问题.当任意给定n和m后，设计算法求这n个人的出列顺序。例如，当n=