数据结构授课教案第章.doc

山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学 分：4.5课程类别：必修开课单位:信息科学与技术学院授课班级：授课教师：杨春花 山东轻工业学院教务处制授课时间年 月 日 星期 第 节年 月 日 星期 第 节年 月 日 星期 第 节授课内容概要第五章 数组和广义表第一节 数组的定义数组的概念、逻辑结构和基本运算。第二节 数组的顺序表示和实现数组的顺序存储表示和基本操作的实现。第三节 矩阵的压缩存储对称矩阵的定义以及压缩存储方法，稀疏矩阵的概念和三元组表的表示。第四节 广义表的定义广义表的定义；原子、子表、表头、表尾等基本概念；广义表的基本运算。第五节 广义表的存储结构广义表的头尾表示法和扩展线性链表表示。目的要求目的：理解数组和广义表的定义和存储。基本要求：了解特殊矩阵和稀疏矩阵的压缩存储方法、广义表的存储结构；理解数组的概念和数组的存储结构；掌握数组元素的存储地址的计算，掌握广义表的基本概念和操作。重 点多维数组元素在顺序存储结构中的存储地址的计算；特殊矩阵和稀疏矩阵的压缩存储方法；广义表的概念。难点多维数组元素在顺序存储结构中的存储地址的计算；特殊矩阵的压缩存储方法。作业布置习题5参考书1. 数据结构题集(C语言版), 严蔚敏，清华大学出版社，2002。3. 数据结构、算法与应用C+语言描述，(美)Sartaj Sahni著，汪诗林等译，机械工业出版社，2002。课 型理论课学时分配复 习 分钟主要教具投影、黑板讲 授 分钟教学方法讲解、提问、示例指 导 分钟教学手段板书、课件总 结 分钟备注共4学时注：课型一栏填写理论课、实验课、习题课等授 课 内 容备 注第五章 数组和广义表前4章介绍的数据结构共同特点：1）都属于线性数据结构；2）每种数据结构中的数据元素，都作为原子数据，不再进行分解；本章讨论的两种数据结构：数组和广义表，其共同特点是：1）从逻辑结构上看它们，可看成是线性结构的一种扩展；2）数据元素本身也是一个数据结构；5.1 数组的定义和运算一、数组的概念1、n维数组：n维数组是由bi个元素组成，每个元素受着n个关系的约束。在每个关系中，元素aj1,j2,jn（0jibi-2）都有一个后继。故这n个关系是线性关系。数组中的所有元素必须属于同一数据类型。每个元素都对应一组下标（j1，j2，jn），每个下标的范围0jibi-1，bi称为第i维的长度。bi为n维数组的长度。当n=1时，n维数组退化为定长的线性表。以二维数组为例：二维数组中的每个元素都受两个线性关系的约束即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。 我们可以把二维数组看成一个线性表： A=(a 1 a 2 aj an)，其中aj（1j n）本身也是一个线性表，称为列向量。还可以将数组Amn看成另外一个线性表: B=(b1，,b2,， ，bm)，其中bi（1i m）本身也是一个线性表，称为行向量，即： bI= （ai1，ai2，aij，ain）。 二、数组的基本操作1)读元素操作2)写元素操作操作方法根据其存储结构决定5.2 数组的顺序表示和实现数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就有次序约定的问题。通常有两种顺序存储方式：行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。 在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后。l 在FORTRAN语言中，数组就是按列优先顺序存储的。以行为主序：LOC(aij)=LOC(a00)+(i*n+j)*ll 以列为主序：LOC(aij)=LOC(a00)+(j*m+n)*ll 一般地，对Ac1.d1,c2.d2则：以行为主序有：LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+(j-c2)*l以列为主序： LOC(aij)=LOC(ac1c2)+(j-c2)*(d1-c1+1)+(i-c1)*ll 推广到n维数组Ab1b2.bnLOC(aj1j2.jn)=LOC(a00.0)+(j1*b2*b3*bn+j2*b3*b4*bn+jn-1*bn+jn)*ll 以列为主序：LOC(aj1j2.jn)=LOC(a00.0)+(jn*bn-1*bn-2*b1+jn-1*bn-2*bn-3*b1+j2*b1+j1)*ll 一般地，对Ac1.d1,c2.d2,cn.dn则：以行为主序有： LOC(aj1j2.jn)=LOC()+(j1-c1)*(d2-c2+1)*(d3-c3+1)*(dn-cn+1)+(j2-c2)*(d3-c3+1)*(d4-c4+1)*(dn-cn+1)+(jn-1-cn-1)*(dn-cn+1)+jn-cn*l以列为主序：LOC(aj1j2.jn)=LOC()+(jn-cn)*(dn-1-cn-1+1)*(dn-2-cn-2+1)*(d1-c1+1)+(jn-2-cn-2)*(dn-3-cn-3+1)*(dn-4-cn-4+1)*(d1-c1+1)+(j2-c2)*(d1-c1+1)+j1-c1*l例1:设二维数组A68按“行优先顺序”存储在内存中，每个元素占用6个存储单元，已知A的起始地址为1000，计算a14的地址。解：LOC(a14)=LOC(a00)+i*n+j*l =1000+1*8+4*6=1072例2:设二维数组A0.8,1.10, 每元素占6字节，已知A的起始地址为1000，求： (1)存储A共需多少字节？(2)以行序为主序存储，求a85的地址。(3)A的第8列第5行共占多少字节？解:(1)共需(d2-c2+1)*(d1-c1+1)*l=10*9*6=540字节 (2)LOC(a85)=LOC(ac1c2)+(j1-c1)*(d2-c2+1)+(j2-c2)*l=1000+8*10+4*6=1504(3)第8列共有9个元素，第5行有10个元素，第8列第5行共有9+10-1个元素，共占18*6个字节。一、数组的顺序存储表示#include #define MAX_ARRAY_DIM 8typedef structElemType *base;intdim;int*bounds;int *constants;Array;二、数组操作的实现5.3 矩阵的压缩存储对于一个矩阵结构，显然用一个二维数组来表示是非常恰当的。但有时会遇到这样一类矩阵：在这种矩阵中有许多值相同的元素或者是零元素、为了节省存储空间，可以对这类矩阵进行压缩存储。 l 压缩存储是：为多个值相同的元素只分配一个存储空间：对零元素不分配存储空间。l 特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵，反之，称为稀疏矩阵。5.3.1特殊矩阵的压缩存储1、对称矩阵 （1）在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1则称A为对称矩阵。（2）压缩存储方法：由于对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，则可将n2个元素存储到n(n-1)/2个元素空间中。不失一般性，以行序为主序存储其下三角的元素。例：5阶对称方阵及它的压缩存储 一般地，设对称矩阵A的下三角部分以行为主序顺序存储到一个向量SAn(n+1)/2中，则sak和aij之间的下标对应关系为：k=i(i-1)/2+j-1 当i=jj(j-1)/2+i-1 当ij2、三角矩阵形下图的矩阵称为三角矩阵，其中c为某个常数。其中(a)为上三角矩阵：主对角线以下均为同一个常数；(b)为下三角矩阵，主对角线以上为同一个常数；在大多数情况下，三角矩阵常数为零。下三角矩阵： 与对称矩阵类似 上三角矩阵：设存入向量：SAn*(n+1)+1中，sak 与aij 的对应关系为： k=(i-1)(2n-i+2)/2+j-i 当ij5.3.2稀疏矩阵1 什么是稀疏矩阵有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。例2 稀疏矩阵的压缩存储（只讨论有较多零元素矩阵的压缩存储）三元组表（i, j, aij )一、三元组顺序表假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表。二、行逻辑链接的三元组顺序表三、十字链表的存储结构54 广义表5.4.1 广义表的概念1 什么是广义表 广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。 记作：LS= (a1, a2, . . . . . .an)。其中ai既可以是单个元素，也可以是广义表。 说明 1）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；2）在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元素, 称为单元素(原子)，也可以是广义表，称为广义表的子表；3）n 是广义表长度；4）下面是一些广义表的例子； A = ( ) 空表，表长为0； B = (a,(b,c,d) B的表长为2，两个元素分别为 a 和子表（b,c,d)； C = (e) C中只有一个元素e，表长为1； D = (A,B,C,f ) D 的表长为4，它的前三个元素 A，B，C 广义表,第四个是单元素； E=( a ,E ) 递归表.5）若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表。对非空广义表：称第一个元素为L的表头，其余元素组成的表称为LS的表尾；例：B = (a,(b,c,d) 表头：a 表尾 (b,c,d) 即 HEAD（B）=a, TAIL(B)=(b,c,d),C = (e) 表头：e 表尾 ( )D = (A,B,C,f ) 表头：A 表尾 (B,C,f )运算可以嵌套，如：HEAD（TAIL（B）=b, TAIL(TAIL(B)=(c, d) 。2 广义表的基本操作 1） 创建广义表L； 2） 销毁广义表L； 3） 已有广义表L，由L