数据结构数组与广义表

关于数据结构数组与广义表第一页，共四十六页，2022年，8月28日第五章数组和广义表本章前讨论的线性结构数据元素都是非结构的原子类型，元素值不可再分。本章讨论了两种数据结构—数组和广义表。作为线性表的扩展，表中的数据元素也是一种数据结构。数组这种数据结构可以看成是线性表的推广。广义表是另一种推广形式的线性表，是一种灵活的数据结构，在许多方面有广泛的应用。第二页，共四十六页，2022年，8月28日2知识结构图数组与广义表数组广义表类型定义表示方法稀疏矩阵特殊矩阵存储结构逻辑结构

应用压缩存储各种运算第三页，共四十六页，2022年，8月28日35.1数组数组是n(n＞1)个相同数据类型的数据元素a0,a1,a2,...,an-1构成的占用一块地址连续的内存单元的有限序列。数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组的下标。第四页，共四十六页，2022年，8月28日45.1.1数组的概念及其与线性表的关系由定义知，n维数组中有b1b2

…

bn个数据元素，每个数据元素都受到n维关系的约束。直观的n维数组以二维数组为例讨论。将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表。设二维数组A=(aij)mn，则

A=(α1，α2，…，αp)(p=m或n)其中每个数据元素αj是一个列向量(线性表)：

αj=(a1j，a2j，…，amj)1≦j≦n或是一个行向量：

αi=(ai1，ai2，…，ain)1≦i≦m如图5-1所示。第五页，共四十六页，2022年，8月28日5a11a12…a1na21a22…a2n……………am1am2…amnA=……………A=a11a12…a1na21a22…a2nam1am2…amna11

a21┆

am1a12

a22┆am2a1n

a2n┆amn┆┆┆A=图5-1

二维数组图例形式(a)

矩阵表示形式(b)行向量的一维数组形式(c)列向量的一维数组形式第六页，共四十六页，2022年，8月28日6n维数组的特点每个数据元素都受着n个关系的约束；在每个关系中，元素(0<=ji<=bi-2)都有一个直接后继;数据元素都必须属于同一数据类型;n=1时，退化为定长的线性表；n维数组可以看成是线性表的推广。数组一旦被定义，则维数已定，对于数组的操作只有存取元素和修改元素。(一旦建立了数组，数组中的元素个数和元素之间的关系就不再发生变动)数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次序约定）第七页，共四十六页，2022年，8月28日7

数组的顺序存储结构数组的实现机制a０的内存单元地址每个元素所需的字节个数第八页，共四十六页，2022年，8月28日8行向量下标

i

页向量下标

i列向量下标

j

行向量下标

j

列向量下标k二维数组三维数组第九页，共四十六页，2022年，8月28日9数组的顺序表示-小结n维数组的特点:数据元素同属于一种数据类型；数组一旦被定义，则维数和各维长度不能改变；数组操作只有引用型操作，没有加工型操作；数组是多维结构，但存储空间是一维结构。数组顺序表示的特点存储单元地址连续（需要一段连续空间）存储规则（以行（列）为主序）决定元素实际存储位置随机存取存储密度最大（100%）第十页，共四十六页，2022年，8月28日105.2

矩阵的压缩存储

在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编程时，通常将一个矩阵描述为一个二维数组。这样，可以对其元素进行随机存取，各种矩阵运算也非常简单。

对于高阶矩阵，若其中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储：◆多个相同的非零元素只分配一个存储空间；◆零元素不分配空间。第十一页，共四十六页，2022年，8月28日115.2.1特殊矩阵的压缩存储1.对称矩阵n阶矩阵A中元素满足性质a[i][j]=a[j][i](1≤i,j≤n)。（即aij=aji,1<=i,j<=n）a11a21a22……aij……annLTA[0..n(n+1)/2-1]k=012……n(n+1)/2-1第十二页，共四十六页，2022年，8月28日12k的含义：按行优先，是第k个（从0开始）15675289683079041526837904i=3j=2k=4公式的推导（下三角）i=3，j=2则前面有一个i-1行的完整三角形，共有元素

(1+i-1)(i-1)/2=i(i-1)/2个另外，同一行，前面还有j-1个元素所以，k=i(i-1)/2+j-1第十三页，共四十六页，2022年，8月28日132、三角矩阵

以主对角线划分，n阶三角矩阵有n阶上三角矩阵和n阶下三角矩阵两种。

n阶上三角矩阵的下三角（不包括主对角线）中的元素均为0（或常数）。n阶下三角矩阵正好相反，它的主对角线上方均为0（或常数）。

注：在大多数情况下，n阶三角矩阵常数为零。第十四页，共四十六页，2022年，8月28日14

下三角矩阵元素aij保存在向量sa中时的下标值k与（i,j）之间的对应关系是：i(i-1)/2+j当i≧j时n(n+1)/2当i<j时K=1≦i,j≦n(5-5)第十五页，共四十六页，2022年，8月28日15

稀疏矩阵的压缩存储稀疏矩阵：设m行n列的矩阵含t个非零元素，则δ=t/(m*n)称为稀疏因子，通常认为

0.05的矩阵为稀疏矩阵。(1)、稀疏矩阵矩阵中非零元素的个数远远小于矩阵元素个数。(2)

、稠密矩阵

一个不稀疏的矩阵。(3)

、稀疏矩阵压缩存储方法只存储稀疏矩阵中的非零元素，实现方法是:将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组线性表来表示。第十六页，共四十六页，2022年，8月28日161、三元组顺序表稀疏矩阵和对应的三元组线性表

若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。第十七页，共四十六页，2022年，8月28日17三元组表表示的稀疏矩阵转置18稀疏矩阵的转置Tij=Mji01290000

00000-3000014002400001800000

0-30012

0001890024000

0

00018000001400566121213931-336144324521865613-32112251831934246314第十八页，共四十六页，2022年，8月28日18稀疏矩阵用三元组表示的转置行数和列数交换i、j的值相互交换重排三元组之间的次序566121213931-336144324521865613-32112251831934246314656211231913-3631434242518第十九页，共四十六页，2022年，8月28日19用三元组表示，求稀疏矩阵M的转置矩阵TM566121213931-3361443245218T1.行数和列数交换，总个数不变:

T.m=M.n;T.n=M.m;T.t=M.t;2.让q定位T中的第一条记录:

q=1;656q第二十页，共四十六页，2022年，8月28日20M566121213931-3361443245218T3.让col取M的每一列:

for(col=1;col<=M.n;col++)

4.让p扫描三元组M的每一条记录:

for(p=1;p<=M.t;p++)656qcol=1p第二十一页，共四十六页，2022年，8月28日21M566121213931-3361443245218T656qcol=1p5.如果p指向的记录的j下标与col相等:

if(M.data[p].j==col)ije第二十二页，共四十六页，2022年，8月28日22M566121213931-3361443245218T656qcol=1p6.把M中的记录p复制到T中的记录q:T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].v=M.data[p].v;7.让q下移:q++;13-3第二十三页，共四十六页，2022年，8月28日23M566121213931-3361443245218T656qcol=2p13-321122518第二十四页，共四十六页，2022年，8月28日24M566121213931-3361443245218T656qcol=3p13-3211225183193424……第二十五页，共四十六页，2022年，8月28日25M566121213931-3361443245218T656qcol=6p13-32112251831934246314第二十六页，共四十六页，2022年，8月28日26（1）稀疏矩阵的转置：“按需查找”法简单算法的分析稀疏矩阵转置算法复杂度=O(n*t)比较一般矩阵的转置算法：其复杂度=O(m*n)如果t和m*n一个数量级，则稀疏矩阵转置算法复杂度=O(m*n2)所以此算法只适用于t<<m*n时for(col=1;col<=nu;col++)for(row=1;row<=mu;row++)T[col][row]=M[row][col];第二十七页，共四十六页，2022年，8月28日27算法的实现附设两个辅助向量num[]和cpot[]。◆

num[col]：统计A中第col列中非0元素的个数；◆

cpot[col]：指示A中第一个非0元素在b.data中的恰当位置。数组num[col]：原矩阵第col列中，非零元素的个数数组cpot[col]：原矩阵第col列中，第1个非零元素在结果三元组表中的位置显然有：cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]（2）稀疏矩阵的转置：“按位就坐”算法第二十八页，共四十六页，2022年，8月28日28ijv0566112122139331-3436145432465218ijv0656113-3221123251843195342466314col123456num[col]122001cpot[col]124666（2）稀疏矩阵的转置：“按位就坐”算法第二十九页，共四十六页，2022年，8月28日292.十字链表十字链表的定义

稀疏矩阵的每个非零元素用一个含五个域的结点表示:i:非零元素所在行;j:非零元素所在列

e:非零元素值;right域:链接同一行下一非零元素

down域:链接同一列下一非零元素；存储结构的C语言描述

typedefstructOLNode{inti,j;ElemTypee;StructOLNode*right,*down;}OLNode,*OLink;typedefstruct{OLink*rhead,*chead;intmu,nu,tu;}CrossLink;ijedownright结点结构：第三十页，共四十六页，2022年，8月28日30十字链表表示的稀疏矩阵举例ijedownright结点结构：稀疏矩阵M：M的十字链表：M.cheadM.rhead113145^^22-1^^^^312采用十字链表存储稀疏矩阵，创建稀疏矩阵、稀疏矩阵的运算见教材P104－106第三十一页，共四十六页，2022年，8月28日315.3广义表(GeneralLists)广义表(列表):n(0)个表元素组成的有限序列，记作

LS=(a1,a2,…,an)表头(head):n>0时,表的第一个表元素表尾(tail):其它表元素组成的表空表:n=0的广义表。广义表的特性：有长度：n有深度：广义表中括号的重数可递归可共享表名表元素

表长非空列表表头可是原子或列表,表尾必定是列表第三十二页，共四十六页，2022年，8月28日32广义表的图形表示1、A=(/)2、B=(e)3、C=(a,(b,c,d))4、D=(A，B，C)注：○：表□：原子第三十三页，共四十六页，2022年，8月28日33广义表的定义GetHead(L):在广义表L存在的条件下，取L的表头。GetTail(L):在广义表L存在的条件下，取L的表尾。举例：1A=()

GetHead(A)=NULL,GetTail(A)=NULL2B=(e)

GetHead(B)=e,GetTail(B)=()3C=(a,(b,c,d))GetHead(C)=a,GetTail(C)=(b,c,d)

GetHead((b,c,d))=b,GetTail((b,c,d))=(c,d)

GetHead((c,d))=c,GetTail((c,d))=(d)4D=(A,B,C)GetHead(D)=A,GetTail(D)=(B,C)

GetHead((B,C))=B,GetTail((B,C))=(C)5E=(())

GetHead(B)=(),GetTail(B)=()第三十四页，共四十六页，2022年，8月28日345.3.2广义表的存储结构采用链式存储结构，元素包括原子和子表，结点结构：表结点：表示列表原子结点：表示原子1、广义表的头尾链表存储表示：

typedefenum{ATOM,LIST}ElemTag;//ATOM=0:原子,LIST=1:子表

typedefstructGLNode{ElemTagtag;//公共部分，用来区分原子结点和表结点

Union{//原子结点和表结点的联合部分

AtomTypeatom;Struct{structGLNode*hp,*tp;}ptr;//hp指向表头,tp指向表尾

};}*Glist;tag=1hptptag=0atom第三十五页，共四十六页，2022年，8月28日35A=(/)B=(e)C=(a,(b,c,d))D=(A，B，C)E=(a，E)5.5广义表的存储结构示例B0e1^C11^0a111^0b0d0cD1^11^E11^0aA=NIL表结点：原子结点：tag=1hptptag=0atom第三十六页，共四十六页，2022年，8月28日365.5广义表的存储结构示例对广义表：C=(a,(b,c,d))，其头尾链表为：1C0a1^10b10c1^0d第三十七页，共四十六页，2022年，8月28日372、广义表的扩展线性链表存储表示：

typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子，LIST==1：子表

typedefstructGLNode{ElemTagtag;//公共部分，用来区分原子结点和表结点

Union{//原子结点和表结点的联合部分

AtomTypeatom;//原子结点的值域

StructGLNode*hp//表结点的头指针

};GLNode*tp;//指向下一个结点

}*Glist;第三十八页，共四十六页，2022年，8月28日38广义表的另一种存储结构示例A=(/)B=(e)C=(a,(b,c,d))D=(A，B，C)E=(a，E)CABD0e1^1^1^0a0b0c0d^1^1^^^E11^0a1^11^tag=1hptptag=0atomtp表结点：原子结点：第三十九页，共四十六页，2022年，8月28日395.3.3广义表的基本操作与实现

下面讨论头链和尾链存储结构下和原子和子表存储结构下一些典型操作的算法实现。//---广义表的头尾链表存储表示typedefenum{ATOM,LIST}ElemTag;//ATOM==0原子，LIST==1子表typedefstructGLNode{ElemTagtag;//公共部分，用于区分原子结点和表结点

union{AtomTypeatom;//atom是原子结点的值域

struct{structGLNode*hp,*tp;}ptr;//ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾

};}*GList;//广义表类型第四十页，共四十六页，2022年，8月28日40第五章数组和广义表1、求广义表深度算法

广义表的深度是广义表中所有原子数据元素到达根结点的最大值。intGListDepth(GListLS){//采用头尾链表存储结构，求广义表L的深度

if(!L)return1;//空表深度为1if(L->tag==ATOM)return0;//原子深度为0for(max=0,pp=L;pp;pp=pp->ptr.tp){//求以pp->ptr.hp为头指针的子表深度

dep=GListDepth(pp->ptr.hp);if(dep>max)max=dep;}returnmax+1;}//GListDepth第四十一页，共四十六页，2022年，8月28日41第五章数组和广义表2