第5章 数组

2第5章数组学习目标与要求：了解数组的概念及基本操作。掌握二维数组的行主序和列主序两种存储方式。了解特殊矩阵的特点并掌握特殊矩阵的存储形式及基本运算。了解广义表的概念及相关术语。掌握广义表的存储形式。35.1数组的定义和运算数组可以看成是一种扩展的线性数据结构，其特殊性不像栈和队列那样表现在对数据元素的操作受限制，而是反映在数据元素的构成上。从逻辑结构上看，数组可以看成是一般线性表的扩充。如图5.1所示的二维数组；图5.2行或列向量表示的数组11121j1n21222j2ni1i2ijinm1m2mjmnaaaaaaaaaaaaaaaa12jn11121j1n121222j2n2i1i2ijinjm1m2mjmnm()aaaaaaaaaaaaaaaa45.1数组的定义和运算数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识。对于数组，一般不做插入、删除操作，不移动元素，其基本操作如下。(1)Getvalue(A,e,index1,…,indexn)：若下标合法，则用e返回数组A中由index1,…,indexn下标所指定的元素的值。即给出一组下标，取相应的数据元素。(2)Setvalue(A,e,index1,…,indexn)：若下标合法，则将数组A中由index1,…,indexn所指定的元素的值置为e。即给定一组下标，修改相应数据元素中的某一个或几个数据项的值。55.2数组的顺序存储结构在计算机中，内存储器的结构是一维的。用一维的内存表示多维数组，就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列存放在存储器中。比如二维数组的顺序存储可以有两种方式：一种是按行序存储，另一种是按列序存储。在数组中若要检索某个元素，就要得到这个元素的存储位置。每个元素的存储位置可以通过数组各维的界偶、第一个元素的存放地址、元素的下标和每个元素在内存中占用的单元数计算得出。图5.3二维数组的两种存储方式……………………65.2数组的顺序存储结构下面总结一下数组中计算元素地址的方法。1.一维数组2.二维数组1)以行序为主序的存储分配2)以列序为主序的存储分配75.3矩阵的压缩存储结构二维数组可以用来存储矩阵元素。在数值分析中经常出现一些高阶矩阵，在这些高阶矩阵中有许多值相同的元素或者是零元素，为了节省存储空间，对这类矩阵采用多个值相同的元素只分配一个存储空间，有时零元素不存储的存储策略，称为矩阵的压缩存储。如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。还有一类矩阵非零的数据元素个数很少称为稀疏矩阵。下面分别讨论这两类矩阵的压缩存储。85.3.1特殊矩阵1.对称矩阵与上下三角阵对于一个n阶矩阵A来说：若当ij时，有aij等于常数C，则称此矩阵为下三角矩阵；若当ij时，有aij等于常数C，则此矩阵称为上三角矩阵；若矩阵中的所有元素均满足aij=aji，则称此矩阵为对称矩阵。图5.4对称矩阵的压缩存储saa11a21a22…aij…0123k下三角中元素存储在sa数组中的位置k=i*(i-1)/2+j95.3.1特殊矩阵2.对角矩阵在数值分析中经常出现的还有一类特殊矩阵是对角矩阵。在这种矩阵中所有非零元集中在主对角线为中心的带状区域中。图5.5所示为一个三对角矩阵，在三对角矩阵里，除了三条对角线上的元素外，其他元素都是零。图5.6所示为图5.5所示三对角矩阵的压缩存储。356000952000030717000239501234567891011121303569520307172395159105.3.2稀疏矩阵在特殊矩阵中，非零元都有明显的规律，从而都可以压缩到一维数组中。然而，实际应用中经常会遇到一类矩阵，其非零元少，且分布没有明显的规律，称之为稀疏矩阵。1.三元组表示法及转置运算图5.8(b)是N矩阵的三元组表示。0030015120001809002400N0000070000000014000000000113-3216153211242518531963424746-786314ijv115.3.2稀疏矩阵2.十字链表稀疏矩阵的十字链表(OrthogonalList)表示法是将矩阵中的每个非零元用一个结点来表示。矩阵M十字链表表示示例如图5.10所示。125.4广义表的定义广义表也是线性表的一种推广。它被广泛地应用于人工智能等领域的表处理语言LISP语言中。(1)广义表的元素可以是子表，而子表还可以是子表，由此，广义表是一个多层的结构。(2)广义表可以被其他广义表共享。如：广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。(3)广义表具有递归性。135.5广义表的存储结构5.5.1头尾表示法广义表中有两类结点，一类是单个元素结点，一类是子表结点。一个表结点可由三个域构成：标志域，指向表头的指针域，指向表尾的指针域。而元素结点只需要两个域：标志域和值域。头尾表示法的结点形式如图5.11所示。tag=1hptptag=0data(a)表结点(b)单元素结点145.5.1头尾表示法5.4节中的广义表A、B、C、D的头尾表示法存储如图5.12所示。155.5.2孩子兄弟表示法广义表的另一种表示法称为孩子兄弟表示法。在孩子兄弟表示法中，无论是单元素结点还是子表结点均由三个域构成。其结点结构如图5.13所示。165.5.2孩子兄弟表示法5.4节中的广义表A、B、C、D的孩子兄弟表示法存储如图5.14所示。175.6数组的应用【例5.2】稀疏矩阵相加。两个稀疏矩阵A和B采用十字链表方式存储，计算C=A+B，C采用十字链表方式存储。参见教材P9718本章小结(1)数组可看作线性表的推广，数组在计算机中采用顺序存储结构表示，通常有两种存储顺序：以行序为主序和以列序为主序。(2)为了节省存储空间，可以对特殊矩阵和稀疏矩阵进行压缩存储。(3)广义表是线性表的推广，有两种表示方法：头尾表示法和孩子兄弟表示法。19习题一、填空题参见教材P101二、选择题三、判断题四、应用题五、算法设计题