《数据结构[Python语言描述]》教案第9课数组和广义表（5.1-5.3）.docx

课题第9课数组和广义表(5.153)课时2课时(90min)教学目标知识目标：(1)理解数组的定义及基本操作(2)掌握数组的顺序存储结构(3)掌握特殊矩阵和稀疏矩阵的压缩存储方法(4)了解广义表的定义、基本术语和基本操作(5)了解广义表的链式存储结构技能目标：(1)能独立分析问题并实现矩阵的压缩存储(2)能灵活运用数组解决较复杂的实际应用问题素质目标：培养勇于探索、知难而进的创新精神，增强民族自信心和自豪感教学重难点教学重点：数组的顺序存储结构、特殊矩阵和稀疏矩阵的压缩存储方法、广义表的基本术语和基本操作、广义表的链式存储结构教学难点：特殊矩阵和稀疏矩阵的压缩存储方法教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：如何理解数组？【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍数组的定义、基本操作和顺序存储结构，矩阵的压缩存储，广义表的定义、基本术语、基本操作和链式存储结构5.1 数组概述5.1.1 数组的定义数组是n(nNl)个具有相同数据类型的数据元素的集合。数据元素在数组中的位置称为数据元素的下标，用户可以通过数据元素的下标直接获取数据元素。数据元素的下标可以由一个或多个整数构成，其中含有的整数个数称为数组的维数。从逻辑结构上看，数组可以看作一般线性表的扩充.÷【教师】用多媒体展示“二维数组的表示形式”图，并介绍二维数组以二维数组4"(数据元素的个数为，心)为例，其表示形式如图所示.Za0.0¾la0.n-%aU%1"m-l.04hTJm-,nJ由图可以看出，二维数组中的每个数据元素均受两个关系的约束，且这两个关系都是线性关系。因此,可以将该二维数组看作一个由加个数据元素组成的线性表,表示为A=(a0tall-tal-tam)(Om-1)其中,每个数据元素a本身也是一个线性表,称为行向量,即a/=(a,；Ofa,；ia,>)同理，也可以将该二维数组看作一个由n个数据元素组成的线性表，表示为B=(%b,向,力八1)(011-l)其中，每个数据元素仇本身也是一个线性表，称为列向量，即H=(Ww,37)。【提示】数组是一组有固定个数的数据元素的集合，一旦定义了它的维数和各维的长度，数组中数据元素的个数就固定了。例如，二维数组A3×4的行长度和列长度分别为3和4,故数组中数据元素的个数为12。5.1.2数组的基本操作基本操作说明_init_0对数组进行初始化，即构造相应的存储空间destroyArray()销毁数组，释放存储空间getValue(e,index,indexn)用e返回数组中由下标indexiin加Xn所指定元素的值setValue(e,index,.,indexn)将数组中由下标index、index”所指定元素的值置为e5.1.3数组的顺序存储结构由于数组的主要操作是存取数据元素值，一般不进行插入和删除操作，因此，数组通常采用M页序存储结构。÷【教师】随机邀请学生回答以下问题数组的顺序存储与顺序表有哪些相似之处？计【学生】聆听、思考、回答一维数组的Jl质序存储与顺序表类似，可以在确定起始地址(基地址)和数组中每个数据元素所占存储单元大小的情况下，计算出一维数组中任意一个数据元素的存储地址。二维数组须按某种存放次序将数据元素排成一个线性序列，然后将这个线性序列存放在存储器中。二维数组的顺序存储方式有两种，一种是按行序存储，另一种是按列序存储。÷【教师】用多媒体展示“二维数组按行序存储"和"二维数组按列序存储”图(详见教材)，并介绍二维数组存储方式假设每个数据元素占用攵个存储单元，Loc(两)为二维数组工行的起始地址(基地址)，则二维数组按行序存储时,可以得到其中任意一个数据元素却的存储地址为1.oc(aj)=Loc(ao,o+(i×n+j)×k(0WiVm,0<?)其中，/表示数据元素即前面的行数；表示每行数据元素的个数；/表示在第/行中沏前面数据元素的个数。同理，二维数组按列序存储时，可以得到其中任意一个数据元素的的存储地址为1.oC(4j)=LoC(a()Q)+(/xi+i)x%(0<i<m,0j<n)其中.j表示数据元素®前面的列数；，表示每列数据元素的个数；i表示在第列中如前面数据元素的个数。÷【教师】随机邀请学生回答以下问题一维数组和二维数组有什么共同点？*【学生】聆听、思考、回答由上述分析可知，一维数组和二维数组均具有随机存取的特点。同理，多维数组也可以按照上述推导公式计算其数据元素的存储地址。【提示】许多高级程序设计语言都采用按行序存储二维数组，如Python.JBasic等.在Python中，一维数组通常采用a,faila,n-l的列表表示；二维数组通常采用aOQ,aO,l,.,aO,n-lLaLO,aLl,.,aLn-l,.,am-LO,am-LL,am-Ln-l的嵌套列表表示。÷【教师】讲解实例5-1（详见教材）5.2矩阵的压缩存储*【教师】随机邀请学生回答以下问题为什么要对矩阵进行压缩存储?【学生】聆听、思考、回答在高级程序设计语言中，通常采用二维数组来存储矩阵。当矩阵中有许多值相同的非零元素或零元素时，如果仍采用普通的二维数组存储矩阵，将会造成存储空间的很大浪费。为了节省存储空间，可对矩阵中值相同的元素只分配一个存储空间，或对零元素不分配存储空间，这类方法称为矩阵的压缩存储。5.2.1特殊矩阵的压缩存储如果矩阵中非零元素或零元素的分布具有一定的规律，则称这类矩阵为特殊矩阵.【提示】对于一个m行n列的矩阵而言，当m=n时称为方阵。对称矩阵、三角矩阵和对角矩阵都属于方阵。1 .对称矩阵的压缩存储若n阶矩阵A满足ai,j=aj,i（O<i<n,Oj<n）f则称矩阵A为n阶对称矩阵。÷【教师】用多媒体展示"n阶对称矩阵"和“对称矩阵的压缩存储”图（详见教材），并介绍对称矩阵压缩存储特点由于对称矩阵中的元素关于主对角线对称，所以在存储对称矩阵时，只需按行序存储对称矩阵中下三角（包括对角线）的元素，使得对称的元素共享同一存储空间。这样就可以将直接采用二维数组存储对称矩阵时占用的个元素的存储空间压缩到a。+1）2个元素的存储空间，大大节省了存储空间。若用一维数组B=W作为阶对称矩阵A的存储结构，则矩阵A中任意元素W和B中元素儿之间的关系如下./i.j下三角（包括对角线）元素k=<.&+ii<j（上三角元素）2 .三角矩阵的压缩存储若n阶矩阵A的下三角或上三角（不包括对角线）中的元素均为常数c或零，则称矩阵A为n阶上三角矩阵或n阶下三角矩阵.*【教师】用多媒体展示“n阶三角矩阵"和“下三角矩阵的压缩存储”图（详见教材），并介绍三角矩阵压缩存储特点若用一维数组8=切作为阶三角矩阵的存储结构，则矩阵A中任意元素SJ和B中元素儿之间的关系如下。（1）阶上三角矩阵：（2n-÷l）+yz.上三角（包括对角线元素（2）n阶下三角矩阵：空工+，i.j下三角（包括对角线）元素由此可知，一维数组B的最后一个元素局中存储阶上三角矩阵或阶下三角矩阵中的常数C涯3 .对角矩阵的压缩存储若n阶矩阵A的所有非零元素都集中在以对角线为中心的带状区域中,则称矩阵A为对角矩阵.对角矩阵中最常见的是三对角矩阵。【教师】用多媒体展示“n阶三对角矩阵“和“三对角矩阵的压缩存储”图（详见教材），并介绍三对角矩阵压缩存储特点三对角矩阵也可以采用一维数组寸非零元素按行序存储。在三对角矩阵中，只有第一行和最后一行有两个非零元素，其他行均有3个非零元素。因此，阶三对角矩阵需要3”-2个元素的存储空间。若用一维数组居6作为阶三对角矩阵A的存储结构，则矩阵/中三港元素沏和8中元素bk之间的关系如下。k=2i+j【提示】如果对角矩阵的主对角线上、下方各有X条次对角线，称该矩阵为（2x+l）对角矩阵,且该对角矩阵的带宽为2x+l4 .2.2稀疏矩阵的压缩存储若矩阵中非零元素的个数远远少于零元素的个数，且元素的分布没有明显的规律，则称这类矩阵为稀疏矩阵。1 .三元组表示法在存储非零元素时，除了要存储元素值，还要存储元素所在的行和列（下标从。开始）.这样，稀疏矩阵中的每个非零元素需由一个三元组（row,col,value）（row、col和value分别表示非零元素所在的行号、列号和元素值）来表示，稀疏矩阵中的所有非零元素构成了一个三元组表。稀稀矩阵的三元组中非零元素的定义如下。classTripleNode:def _init_ self. row(self, row, col,value):self. col = col#行号#列号self.value = value#元素值÷【教师】讲解实例5-2（详见教材）2 .十字链表表示法当矩阵进行某些运算时，如加法、减法和乘法等，矩阵中非零元素的个数和位置会发生很大的变化，这时可以采用矩阵的链式存储结构，即十字链表。在这种存储结构中，矩阵中的每个非零元素用一个结点表示，每个结点由5个域组成,其结构如图所示。rowcolvaluedownright÷【教师】随机邀请学生回答以下问题观察图片，思考为什么该链表被称为十字链表？【学生】聆听、思考、回答其中，row、COl和ValUe域分别存储非零元素所在的行号、列号和元素值，down域存储同一列中下一个非零元素的位置，right域存储同一行中下一个非零元素的位置。这样，同一行中的非零元素和同一列中的非零元素分别构成一个单链表，矩阵中的任意非零元素对应的结点既对应一个行链表，又对应一个列链表，故称其为十字链表。稀疏矩阵的十字链表中结点的定义如下。classCrossNode:definit(self,row,col,value):self.row=rowself.col=colself.value=valueself.down=Noneself.right=None#行号#列号#元素值#列链表指针#行链表指针(详见教材)【提示】使用十字链表压缩存储稀疏矩阵时，所有行链表的表头存储在一个数组(rhead)中，所有列链表的表头存储在另一个数组(Chead)中.【拓展阅读】据记载，矩阵概念始于19世纪50年代，是为了求解线性方程组而产生的。但其实,公元前我国就已经有了矩阵的萌芽，在九章算术一书中已经对矩阵有所描述，只是没有将它作为一个独立的概念加以研究.(详见教材)5.3广义表概述5.3.1 广义表的定义和基本术语广义表是n(n0)个娄福元M«11的有限序列，一般记作GL=(ao,a,),其中的数据元素ai(0in-l)既可以是单个元素，也可以是一个广义表。要了解广义表，须先熟悉如下基本术语.(1)原子。在广义表GL中，如果”,为单个元素，则称0为原子。(2)子表。在广义表GL中，如果“是一个广义表，则称为为广义表GL的子表。(3)深度。广义表GL中元素嵌套的最大层数称为广义表的深度.(4)长度。广义表GL中元素的个数称为广义表的长度。(5)表头。当广义表GL非空时，第一个元如称为广义表的表头。(6)表尾。在广义表GL中，除第一个元m外，其余元素组成的表称为广义表的表尾。5.3.2广义表的基本操作广义表的基本操作主要有求表长、取表头和取表尾。(1)求表长(getLeng(h()是指求广义表中元素的个数。(2)取表头(getHead()是指取非空广义表的第一个元素，它可以是一个原子，也可以是一个子表。(3)取表尾(getTail()是指取除表头外，由其余元素构成的表，它一定是一个广义表。【教师】讲解实例5-3(详见教材)5.3.3广义表的链式存储结构广义表通常采用链式存储结构，表中的每个数据元素用一个结点来表示。由于广义表中有两种数据元素(原子和子表)，因此需要两种结构的结点，一种是用于表示原子的原子结点，由标志域(lag)和值域(data)组成；另一种是用于表示子表的表结点，由标志域(tag)、指向表头结点的指针域(hp)和指向表尾结点的指针域(IP)组成，如图所示。tag=OdataIag=Ihptp(a)原子结点(b)表结点广义表的结点结构由图可以看出，广义表中通过标志域的值来区分原子结点和表结点，即tag=O表示当前结点为原子结点,tag=l表亦当前结点为表结点。广义表的链式存储结构中结点的定义如下。classGLNode:def_init_(self,tag,data,hp,tp):self.tag=tag#标志域self.data=data#元素值self.hp=h#指向表头结点的指针域self.tp=tp#指向表尾结点的指针域广义表的链式存储结构也可以称为头尾链表存储结构，即若广义表非空，则需要先将其分解为表头和表尾进行存储，如果其表头或表尾依然是广义表，重复执行上述操作。【教师】讲解实例54(详见教材)【学生】聆听、思考、理解、记录任务实施任务稀疏矩阵的转置【教师】描述问题，分析问题，安排学生扫描微课二维码观看视频“稀疏矩阵的转置”(详见教材)，要求学生设计算法【问题描述】矩阵转置就是将矩阵元素的行号与列号互换。对于一个m行n列的矩阵M,它的转置矩阵N是一个n行m列的矩阵，且Nij=Mj,i(Oi<n,Oj<m)设计T算法，实现稀磁阵的转置。【问逑分析】(1)用三元组表示稀疏矩阵。(2)将三元组中的行号和列号交换.(3)为保证转置后的矩阵仍按行序存储，需按新的行号对三元组进行排序。(4)根据新的三元组表输出转置后的稀疏矩阵。【学生】自行扫码观看配套微课，按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点数组的定义、基本操作和顺序存储结构矩阵的压缩存储：特殊矩阵的压缩存储、稀疏矩阵的压缩存储广义表的定义、基本术语、基本操作和链式存储结构【学生】总结回顾知识点作业布置【教师】布置课后作业完成iR习题。【学生】完成课后任务教学反思