数组和广义表

关于数组和广义表第一页，共三十页，2022年，8月28日本章学习要求1.了解数组的逻辑结构和基本运算；2.熟练掌握数组的两种存储表示方式，并掌握数组在以行为主存储的地址计算方法；3.掌握对特殊矩阵进行压缩存储时的下标变换公式；4.掌握特殊矩阵和稀疏矩阵的定义及其压缩存储原理、特点、适用范围，了解以三元组表示稀疏矩阵时进行矩阵运算的方法；5．掌握广义表的结构特点及存储表示方法。第二页，共三十页，2022年，8月28日5.1数组的定义数组由一组名字相同、下标不同的同类型的元素组成，它有两个特点：（1）表长固定（2）数据元素类型统一

数组的分类：（1）一维数组，即向量；（2）二维数组；（3）多维数组。第三页，共三十页，2022年，8月28日5.1数组的定义

数组结构不存在插入、删除运算。常见的操作：

值检索：给定一组下标，查取相应的数组元素的值。

值存储：给定一组下标和值，存入或修改相应数组元素的值。第四页，共三十页，2022年，8月28日5.2数组的顺序存贮结构理论上，数组可以用两种存储结构，即顺序存储结构和链式存储结构。实际：顺序存储结构更为适宜。m行n列的二维数组按行优先顺序(以行为主序

)存储：数组元素aij的存储位置由下式决定：

LOC（A[i,j]）=LOC（A[0,0]）+（i*n+j）*L每个元素占L个存贮单元

第五页，共三十页，2022年，8月28日5.2数组的顺序存贮结构m行n列的二维数组按列优先顺序(以列为主序

)存储：数组元素aij的存储位置由下式决定：

LOC（A[i,j]）=LOC（A[0,0]）+（j*m+i）*L每个元素占L个存贮单元

第六页，共三十页，2022年，8月28日5.2数组的顺序存贮结构练习：1、二维数组A[20][10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10][5]的存储地址是1000，则A[18][9]的存储地址是＿＿＿＿。A．1208B．1212C．1368 D．13362、二维数组A中，每个数据元素占4个字节，行下标从0到4，列下标从0到5，按行优先存储时元素A[3][5]的地址域同按列优先存储时元素＿＿＿＿的地址相同。A．A[2][4]B．A[3][4]C．A[3][5]D．A[4][4]第七页，共三十页，2022年，8月28日5.3矩阵的压缩存储特殊矩阵:值相同的元素或零元素在矩阵中的分布有一定的规律。稀疏矩阵:矩阵中只有少量的非零值元，并且这些非零值元在矩阵中的分布没有一定规律。压缩存储原理：为相等的多个非零元只分配一个存储空间，零元不分配空间。第八页，共三十页，2022年，8月28日5.3.1特殊矩阵的压缩存储特殊矩阵常见的特殊矩阵有对称矩阵、下（上）三角矩阵、对角矩阵等等。1.对称矩阵若一个n阶矩阵A中的元素满足aij=aji（1≤i，j≤n），则称为n阶对称矩阵。压缩存储原理：为每一对对称元素分配一个存储空间，则可将原本需要n×n个元素空间压缩为n(n+1)/2个元素空间中。第九页，共三十页，2022年，8月28日

假设以一维数组s[1：n(n+1)/2]作为n阶对称矩阵A的存储结构，则s[k]和矩阵元素aij之间存在一一对应关系，矩阵下标(i,j)与k的关系如下：第十页，共三十页，2022年，8月28日2.三角矩阵下（上）三角矩阵的特点是以主对角线为界的上（下）半部分所有元素的值都相同，而下（上）半部分的元素值则没有任何规律。将上半部分的常量值存储在0单元，下半部分和主对角上的元素从1号单元开始存放对于任意的（i,j），在一维数组中的存放位置可利用下列公式求得：第十一页，共三十页，2022年，8月28日3.对角矩阵若n阶方阵中的非零值元都集中在以主对角线为中心的(由k条对角线组成的)带状区域中，则称为k阶对角矩阵。非零元素以行为主序，从下标为1的位置开始依次存放在一维数组中，而位置1存放数值0

对于任意的（i,j），可按以下公式求得矩阵元素在一维数组中的存储位置k：第十二页，共三十页，2022年，8月28日假设在m×n的矩阵中，有t个元素不为零。令δ=t/m×n,称δ为矩阵的稀疏因子。通常认为δ≤0.05的矩阵为稀疏矩阵。三元组顺序表将三元组按行优先顺序排列，同一行中按列号从小到大的顺序排列，组成一个线性表，称为三元组表，再采用顺序存储方法存储该表，称为三元组顺序表。5.3.2稀疏矩阵第十三页，共三十页，2022年，8月28日三元组顺序表的结构定义如下：DefineSMAX1024typedefstruct{inti,j;/*非零元素的行下标、列下标*/datatypev;/*非零元素值*/}triple;/*三元组类型*/typedefstruct{intmu,nu,tu;/*矩阵的行数、列数及非零元素的个数*/tripledata[SMAX];//三元组表}TSMatrix;/*三元组表的存储类型*/第十四页，共三十页，2022年，8月28日矩阵转置运算的实现：对于一个m×n的矩阵M，它的转置矩阵N是一个n×m的矩阵，且N（i,j）=M（j,i），0≤i≤n，0≤j≤m。

假设a和b都是TSMatrix型变量，分别表示矩阵M、N。从a得到b转置的实现步骤：①将矩阵的行列值互换；②将每个三元组中的i和j相互调换；③重排三元组之间的次序。第十五页，共三十页，2022年，8月28日

1、按矩阵M的列序进行转置【算法思想】对矩阵M中每一列col（0≤col≤n-1），通过从头至尾扫描三元组表a.data，找出所有列号等于col的那些三元组，将它们的行号、列号互换后依次放入b.data，即可得到N的按行优先的压缩存储表示。具体实现如下：第十六页，共三十页，2022年，8月28日0002800000009100000000-60000003110-150220015A=j==3时j==1时ijv13456782ijv111514221665191632813456782j==2时方法1：按照原矩阵的列号的顺序对三元组扫描111515910000060222800030000011009100015B=22113233628j==4时4122第十七页，共三十页，2022年，8月28日Statustransmatrix(TSMatrixa,TSMatrix&b){intp,q,col;b.mu=a.nu;b.nu=a.mu;b.tu=a.tuif(b.tu){q=0;for(col=0;col<a.nu;col++)for(p=0;p<a.tu;p++)if(a.data[p].j==col){b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;q++;}}return(ok);}第十八页，共三十页，2022年，8月28日2、快速转置【算法思想】建立两个辅助向量分别记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中的开始存放位置；扫描三元组表，根据某项的列号，确定它转置后的行号，查第二个辅助向量表，按查到的位置直接将该项存入转置三元组表中。第十九页，共三十页，2022年，8月28日方法2（对号入座）ijv13456782ijv1115142216651916328134567821115关键：确定原矩阵的三元组表中每个三元组在新表中的位置41226161591第二十页，共三十页，2022年，8月28日512346？15loc(1,1)0002800000009100000000-60000003110-150220015A=0000060222800030000011009100015B=11loc(2,1)=loc(1,1)+2loc(3,1)=loc(2,1)+13loc(4,1)=loc(3,1)+2

22寻址公式：A中第i列的第一个非零元在TB中的位置=(A中第i-1列的第一个非零元在TB的位置)+(A中第i-1列的非零元的个数)第二十一页，共三十页，2022年，8月28日if(b.tu){for(col=0;col<a.nu;++col)num[col]=0;/*初始化*/for(k=0;k<a.tu;++k)++num[a.data[k].j];/*求M的每一列含非零元素个数*/cpot[0]=0;for(col=1;col<a.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=0;p<a.tu;++p)//转置

{col=a.data[p].j;q=cpot[col];b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;++cpot[col];}}return(ok);}算法实现如下：Statusfast_transpos(TSMatrixa,TSMatrix&b)/*将三元组表a表示的稀疏矩阵转置为三元组表b表示的稀疏矩阵*/{intp,q,col,k;intnum[0..a.nu],cpot[0..a.nu];b.mu=a.nu;

b.nu=a.mu;

b.tu=a.tu;第二十二页，共三十页，2022年，8月28日5.4广义表5.4.1广义表的定义和性质

广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。

广义表中的元素区分为区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表LS非空（n>=1)，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。广义表所含括号的重数即为广义表的深度。第二十三页，共三十页，2022年，8月28日5.4广义表5.4.1广义表的定义和性质一、广义表的定义1、定义也称列表（lists），n0个元素的集合。一般记为：LS=(a1,a2,…an)其中：元素允许为单元素或子表。习惯上：单元素用小写字母子表用大写字母2、广义表的例子如下：（1）A=（）——A是一个空表，其长度为零。（2）B=（e）——表B只有一个原子e，B的长度为1。（3）C=（a,(b,c,d))——表C的长度为2，两个元素分别为原子a和子表(b,c,d)。第二十四页，共三十页，2022年，8月28日5.4广义表（4）D=（A，B，C）——表D的长度为3，三个元素都是广义表。显然，将子表的值代入后，则有D=((),(e),(a,(b,c,d)))。（5）E=（E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…))))。（6）F=（（））——长度为1的非空表，该表中唯一的一个元素是空表。3、广义表的三个重要结论：（1）多层次的结构。（2）共享性。（3）递归性。第二十五页，共三十页，2022年，8月28日5.4广义表

二、广义表有两个特殊的基本运算：取表头head(LS)：取表中的第一个数据元素，不能对空表操作。取表尾tail(LS)；取除表头外，其余数据元素构成的子表，不能对空表操作。第二十六页，共三十页，2022年，8月28日5.4广义表5.4.2广义表的存储结构

由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。对于广义表：F=（e,C,（）），其中C=（a,（b,c,（d））），采用头尾表示法的存储结构如图

头尾表示法实现广义表的链式存储结构。第二十七页，共三十页，2022年，8月28日5.5数组应用举例

例5-1已知一个函数声明为“intFINDMAX(inta[][],intm,intn);”，编写出此函数定义，求出并返回矩阵An×m