数据基础及结构 6

第五章数组和广义表本章目录5.0问题导入5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义和存储结构5.5广义表操作的递归算法本章学习重点：地址映像、压缩存储、递归处理5.6应用案例：深度学习模型中的张量问题导入表格与图像网页表格、本地图片、Excel工作表都具有“行×列”或“通道×高×宽”的规则形态。张量与模型深度学习中的输入、特征图与权重，本质上都是多维数组的高维扩展。表达式与JSON嵌套括号、语法树、JSON/XML结构不再“整齐划一”，更适合用广义表表达层次关系。规则数据→数组稀疏矩阵→压缩存储层次嵌套→广义表工程应用用数组解决“规则而连续”的数据组织；用压缩存储解决“稀疏而浪费空间”的矩阵；用广义表解决“层次嵌套”的表达。5.1数组的基本概念基本定义数组(array)是一种由相同类型的数据元素构成的有限序列,这些元素在内存中连续存储一维表示假设数组A包含n个相同类型的元素(n>1),其逻辑表示如下:A=(a₀,a₁,…,aₙ₋₁)，其中,ai(0≤i≤n-1)代表数组A的第i个元素。高维理解对于二维数组,可以将其视为由多个同类型一维数组组成的一维数组。具体来说,若存在:B=(b0,b1,…,bn-1)且每个bi

均为一个一维数组,则B为二维数组。更高维的数组(假设维数为d,d>2)可以看作一个线性表,其中每个元素是一个d-1维的线性表。教材强调：数组是线性表的推广，但其基本操作主要是“读/写”而不是插入/删除。5.1数组的实现ADTArray{

D={aj1,j2,…,ji,…,jn|ji=0,…,bi-1,i=1,2,…,n}其中n称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标数据关系:R={R1,R2,…,Rn}Ri={<aj1,j2,…,ji,…,jn,aj1,j2,…,ji+1,…,jn>|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,i=1,2,…,n}InitArray(n,m1,...,mn)

操作结果:若维数n和各维长度合法,则构造相应的数组ADestroyArray(A)操作结果:销毁数组AValue(A,index1,...,indexn)初始条件:A是n维数组,随后是n个下标值操作结果:若下标不越界,则返回指定的A的元素值Assign(A,e,index1,...,indexn)初始条件:A是n维数组,e为元素变量,随后是n个下标值操作结果:若下标不越界,则将e的值赋给指定的A的元素并返回OK}数组在高级语言中的4个特性固定大小数组一旦定义,其元素数量不可改变类型一致数组中的所有元素必须具有相同的数据类型。唯一索引每个元素都与一组唯一的下标相关联。随机访问数组支持随机存取，可直接访问任意位置的元素。5.2数据的顺序表示和实现存储映像一般来说，数组不涉及插入或删除操作；一旦创建，其元素数量与元素间的关系就保持固定，因此，使用顺序存储结构来表示数组是合适。数组元素存储位置的映像关系LOC(aᵢ)=LOC(a₀)+i×L(0≤i≤n-1)其中:•LOC(ai)表示元素ai的存储地址;•LOC(a0)是数组的基地址(起始存储地址)。a000a011a022a103a11…a12ia000a101a012a113a02…a12i（a）按行优先存储（b）按列优先存储二维数组的两种展开方式设A=[[a₀₀,a₀₁,a₀₂],[a₁₀,a₁₁,a₁₂]]按行优先a₀₀a₀₁a₀₂a₁₀a₁₁a₁₂a₀₀0a₀₁1a₀₂2a₁₀3a₁₁4a₁₂5按列优先a₀₀a₀₁a₀₂a₁₀a₁₁a₁₂a₀₀0a₁₀1a₀₁2a₁₁3a₀₂4a₁₂5教材图5-1的本质：多维数组最终都要线性展开到一维内存中。数组元素存储位置的映像关系二维数组A=LOC(i,j)=LOC(0,0)+(b₂×i+j)×L(0≤i≤n-1)其中,LOC(i,j)是aij的存储位置;LOC(0,0)是a00的存储位置。n维数组LOC(j1,j2,…,jn)=LOC(0,0,…,0)+(b2×…×bn×j1+b3×…×bn×j2+…+bn×jn-1+jn)×L(0≤i≤n-1)可缩写成LOC(j₁,…,jₙ)=LOC(0,…,0)+(Σcᵢjᵢ)

（其中：cₙ=L，cᵢ₋₁=bᵢ×cᵢ）一维数组A=(a1,a2,…,an-1)LOC(ai)=LOC(a0)+i×L(0≤i≤n-1)其中:•LOC(ai)表示元素ai的存储地址;•LOC(a0)是数组的基地址(起始存储地址)。a₀₀a₀₁a₀₂a₁₀a₁₁a₁₂数组的顺序存储实现#include<stdarg.h>#defineMAX_ARRAY_DIM8Typedefstruct{ElemType*base;//数组基址,由InitArray分配intdim;//数组维数int*bounds;//维界基址,每个维度的长度为biint*constants;//数组映像函数常量基址ci,由InitArray分配}Array;//----基本操作的算法描述----//若维数dim和随后的各维长度合法,则构造相应的数组A,并返回OK//----初始化:传入各维长度----StatusInitArray(conststd::vector<int>&dims){constintd=static_cast<int>(dims.size());if(d<1)returnStatus::ERROR;dim=d;bounds=dims;//计算元素总数并做溢出检查std::size_ttotal=1;for(inti=0;i<dim;++i){if(bounds[i]<=0)returnStatus::UNDERFLOW;//非正长度非法constautobi=static_cast<std::size_t>(bounds[i]);if(total>std::numeric_limits<std::size_t>::max()/bi){returnStatus::OVERFLOW;}total*=bi;}数组的顺序存储实现

try{base.assign(total,ElemType{});//分配并清零}catch(...){returnStatus::OVERFLOW;}//计算行主序映像常量:c[dim-1]=1;c[i]=c[i+1]*b_{i+1}c.assign(dim,0);c[dim-1]=1;for(inti=dim-2;i>=0;--i){c[i]=c[i+1]*static_cast<std::size_t>(bounds[i+1]);}returnStatus::OK;}//----下标转换为线性偏移量----StatusOffset(conststd::vector<int>&idx,std::size_t&off)const{if(static_cast<int>(idx.size())!=dim)returnStatus::ERROR;std::size_tacc=0;for(inti=0;i<dim;++i){if(idx[i]<0||idx[i]>=bounds[i])returnStatus::UNDERFLOW;

acc+=c[i]*static_cast<std::size_t>(idx[i]);}off=acc;returnStatus::OK;}//----读值----StatusValue(ElemType&e,conststd::vector<int>&idx)const//----赋值----StatusAssign(constElemType&e,conststd::vector<int>&idx)//----释放(可选)----

voidDestroyArray()5.3矩阵的压缩存储为什么要压缩？在科学和工程计算领域,矩阵运算被广泛应用。这类计算往往涉及高阶矩阵,且矩阵中常存在大量相同值或零值元素。采用压缩存储技术可以显著减少存储空间占用,同时提升计算性能。压缩的核心思想对重复出现的相同值元素,仅分配单个存储空间;对零元素不分配存储空间。进行压缩存储的矩阵类型包括特殊矩阵和稀疏矩阵两类。教材讨论的两类重点：特殊矩阵+稀疏矩阵特殊矩阵示例：对称矩阵a₀,₀a₀,₁…a₀,n-1a10a₁₁…a₁,n-1……an-1,₀an-1,1…an-1,n-1aᵢⱼ=aⱼᵢ压缩思路对角线以下的“下三角区”中的元素与“上三角区”中的元素是对称的,因此只需要存储下(上)三角区中的n(n-1)/2个元素以及对角线上的n个元素(共n(n+1)/2个),即可实现矩阵的存储.地址映像如果使用一维数组sa[n(n+1)]来存储n阶对称矩阵A,那么sa[k]和矩阵元素aij

之间存在一一对应的关系:当i≥j：k=i(i-1)/2+j-1当i<j：k=j(j-1)/2+i-1……a110a211a222a313…an，1n(n-1)/2an,nn(n+1)/2-1K=对称矩阵的压缩存储稀疏矩阵稀疏矩阵稀疏矩阵就是矩阵中零元素占比较大的矩阵。稀疏因子假设在m×n的矩阵中,有t个元素不为零,令δ=t/(m×n),称δ为矩阵的稀疏因子。一般来说,当δ≤0.05时称矩阵为稀疏矩阵。稀疏矩阵定义ADTSparseMatrix{数据对象:D={aij|i=1,2,…,m;j=1,2,…,n;aij

∈ElemSet,m和n分别为矩阵的行数和列数}数据关系:R={Row,Col}Row={<ai,j,ai,j+1>|1≤i≤m,1≤j≤n-1}Col={<ai,j,ai+1,j>|1≤i≤m-1,1≤j≤n}基本操作:CreateSMatrix(M);操作结果:创建稀疏矩阵MDestroySMatrix(M);初始条件:稀疏矩阵M存在操作结果:销毁稀疏矩阵MPrintSMatrix(M);初始条件:稀疏矩阵M存在操作结果:输出稀疏矩阵MCopySMatrix(M);初始条件:稀疏矩阵M存在操作结果:由稀疏矩阵M复制得到TAddSMatrix(M);初始条件:稀疏矩阵M与N的行数和列数对应相等操作结果:求稀疏矩阵的和Q=M+NSubtSMatrix(M);初始条件:稀疏矩阵M与N的行数和列数对应相等操作结果:求稀疏矩阵的差Q=M-NMultSMatrix(M);初始条件:稀疏矩阵M的列数等于N的行数操作结果:求稀疏矩阵的积Q=M*NTransposeSMatrix(M);初始条件:稀疏矩阵M存在操作结果:求稀疏矩阵M的转置矩阵T}ADTSparseMatrix稀疏矩阵的三元组表示012900000000000-3000014000240000018000001500-7000稀疏矩阵M三元组含义(1,2,12)第1行第2列=12(1,3,9)第1行第3列=9(3,1,-3)第3行第1列=-3(3,6,14)第3行第6列=14（4,3,24）第4行第3列=2400-3001512000180900240000000-70000000014000转置矩阵T000000（5,2,18）第5行第2列=18（6,1,15）第6行第1列=15（6,4，-7）第6行第4列=-7三元组顺序表存储稀疏矩阵//-----稀疏矩阵的三元组顺序表存储表示-----#defineMAXSIZE12500typedefstruct{inti,j;

//该非零元素的行下标和列下标ElemTypee;

//该非零元素的值}Triple;

//三元组类型typedefunion{Tripledata[MAXSIZE+1];intmu,nu,tu;//矩阵的行数、列数和非零元素个数}TSMatrix;

//稀疏矩阵类型若采用顺序存储结构来表示三元组表,通过这种方式压缩存储稀疏矩阵的方式称为三元组顺序表。矩阵转置二维数组给定一个m×n的矩阵M,其转置矩阵T是一个n×m的矩阵,满足T(i,j)=m(j,i),1≤i≤n,1≤j≤m(即把矩阵的第i行转为第i列)。时间复杂度O(mu×nu)。for(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];三元组顺序表按照矩阵M的列序进行转置。对矩阵的三元组表a.data从第一行开始整个扫描一遍后,即可找到M每一列中所有的非零元素。因为a.data以M的行序为主序来存放非零元素,由此得到的恰好是b.data应有的顺序。时间复杂度O(nu×tu)。StatusTransposeSMatrix(TSMatrixM,TSMatrixT){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;++col){for(p=1;p<=M.tu;++p){//找每个元素if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}//if}//for}//for}ifreturnOK;}//TransposeSMatrix快速转置法矩阵M的向量cpot的值col1234567num[col]2221010cpot[col]1357889复杂度O(nu+tu)StatusFastTransposeSMatrix(TSMatrixM,TSMatrixT){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;//初始化for(t=1;t<=M.tu;++t)++num[M.data[t].j];//计算每列元素个数cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];//计算转置后每列位置这是教材中“把重复扫描变成一次定位”的经典优化思路。for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[a].i=M.data[p].j;T.data[q].j=M.data[P].i;T.data[q].e=M.data[p].e;++cpot[col];}//for}//ifreturnOK;}//FastTransposeSMatrix行逻辑链接的顺序表存储稀疏矩阵for(i=1;i<=m1;++i)for(j=1;j<=m2;++j){Q[i][j]=0;for(k=1;k<=n1;++k)Q[i][j]+=M[i][k]×N[k][j];}设Q=M×N,M是m1×n1矩阵,N是m2×n2矩阵。若采用二维数组存储矩阵,那么当n1=m2时有：复杂度O(m1×n1×n2)显然,传统矩阵乘法算法的时间复杂度相对较高。行逻辑链接的顺序表存储稀疏矩阵#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];

//非零元素三元组表intrpos[MAXRC+1];

//各行第一个非零元素的位置表intmu,nu,tu;

//矩阵的行数、列数和非零元素个数}RLSMatrix;

//行逻辑链接顺序表类型为了优化稀疏矩阵乘法的计算效率,可以在稀疏矩阵的存储结构中保留快速转置算法生成的“行”信息辅助数组cpot,从而形成一种改进的三元组表———即行逻辑链接顺序表。该存储结构的类型定义如下:稀疏矩阵相乘工程启示：不要让“注定为0的运算”参与计算。//求矩阵乘积Q=M×N,采用行逻辑链接存储表示StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrixQ){if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.tu×N.tu!=0){//MN是非零矩阵for(arow=1;arow<=M.mu;++arow){//处理M的每一行ctemp[]=0;//当前行各元素累加器清零Q.rpos[arow]=Q.tu+1;//记录当前行首个元素位置if(arow<M.mu)tp=M.rpos[arow+1];else{tp=M.tu+1;}for(p=M.rpos[arow];M.data[p].i==arow;++p){//对M的当前行中每一个非零元素brow=M.data[p].j;if(brow<N.nu)t=N.rpos[brow+1];elset=N.tu+1;for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j;//乘积元素在Q中的列号ctemp[ccol]+=M.data[p].e*N.data[q].e;}//forq}//求得Q中第crow(=arow)行的非零元素for(ccol=1;ccol<=Q.nu;++ccol)if(ctemp[ccol]){if(++Q.tu>MAXSIZE)returnERROR;Q.data[Q.tu]=(arow,ccol,ctemp[ccol]);}//if}//forarow}//ifreturnOK;}//MultSMatrix十字链表存储稀疏矩阵当矩阵的非零元素分布和数量在运算过程中频繁变动时,顺序存储结构的三元组表就不再适用.针对这种情况,采用链式存储结构来组织三元组数据更为合适。十字链表采用包含5个数据域的结点来存储每个非零元素:(1)i、j和e这3个域分别表示该非零元素所在的行、列和元素的值;(2)向右域right用来链接同一行中下一个非零元素;(3)向下域down用来链接同一列中下一个非零元素。ijvdownright^0-1002000稀疏矩阵M113312^^22-1^^145^^M.cheadM.rhead稀疏矩阵M的十字链表5.4广义表的定义和存储结构广义表的定义广义表是线性表的推广,也可称为列表(lists),它本质上是一个由有限数量元素组成的有序序列。记作：LS=(α₁,α₂,…,αₙ)表头/表尾当广义表LS非空时,称第一个元素α1

为LS的表头(head),其余元素组成的表(α2,α3,…,αn)为LS的表尾(tail)。原子/子表在广义表的定义中,αi

可以是单个元素(即广义表LS的原子),也可以同样是一个广义表(即广义表LS的子表)。示例C=(a,(b,c,d))headtaila(b,c,d)广义表的抽象类型数据定义ADTGlist{数据对象:D={ei|i=1,2,…,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet为某个数据对象}数据关系:LR={<ei-1,ei>|ei-1,ei∈D,2≤i≤n}基本操作:InitGList(L);操作结果:创建空的广义表LCreateGList(L,S);初始条件:S是广义表的书写形式串操作结果:由S创建广义表LDestroyGList(L);初始条件:广义表L存在操作结果:销毁广义表L

CopyGList(T,L);初始条件:广义表L存在操作结果:由广义表L复制得到广义表T

广义表的抽象类型数据定义基本操作:GListLength(L);初始条件:广义表L存在操作结果:求广义表L的长度,即元素个数GListDepth(L);初始条件:广义表L存在操作结果:求广义表L的深度GListEmpty(L);初始条件:广义表L存在操作结果:判定广义表L是否为空GListHead(L);初始条件:广义表L存在操作结果:取广义表L的头GListTail(L);初始条件:广义表L存在操作结果:取广义表L的尾

广义表的抽象类型数据定义基本操作:InsertFirst_GL(L,e);初始条件:广义表L存在操作结果:插入元素e作为广义表L的第一元素DeleteFirst_GL(L,e);初始条件:广义表L存在操作结果:删除广义表L的第一元素,并用e返回其值Traverse_GL(L,Visit());初始条件:广义表L存在操作结果:遍历广义表L,用Visit()函数处理每个元素}ADTGlist广义表的3个关键特性(1)广义表的元素可以是子表,且子表本身也可以包含子表,从而形成多层次嵌套结构。以列表D为例,其结构清晰地展示了这种层次关系。(2)广义表支持子表共享机制。如在示例中,列表D可以包含列表A、B、C作为其子表,此时D不需要重复存储这些子表的具体内容,只需通过子表名称引用即可。(3)广义表允许递归定义,即一个列表可以将其自身作为子表。列表E就是这种递归结构的典型示例。表头表尾存储结构//----广义表的头尾链表存储表示----typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;struct{structGLNode*hp,*tp;}ptr;};}

*GList;Tag=1原子结点表结点hptpTag=0atom列表的链表节点结构子表存储结构//---广义表的扩展线性链表存储表示---typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;union{AtomTypeatom;structGLNode*hp;};structGLNode*tp;//相当于next}*GList;Tag=1hptpTag=0原子结点表结点atomtp列表的另一种节点结构1^^1^0e^1^1^1^0a11^1^0a1^1^0b0c0d^ABDEC5.5广义表操作的递归算法为什么广义表适合递归？当问题分解后产生的子问题与原问题性质相同时,递归算法往往比基于栈的非递归实现更符合直觉思维,也更易于理解。分治法的设计思想对于一个输入规模为n的函数或问题,将其划分为k(1≤k≤n)个子问题,分别求解后再合并结果。设计要点1明确定义函数首部和规格说明,包括功能描述和接口规范设计要点2将每个递归调用视为简单操作,只需确保接口一致即可实现预定功能,避免过度深究调用细节。求广义表深度基本项DEPTH(LS)=1，当LS为空表时；DEPTH(LS)=0，当LS为原子时。归纳项DEPTH(LS)=1+Max{DEPTH(αᵢ)}

1≤i≤n且n≥1intGListDepth(GListL){if(!L)return1;

//空表深度为1if(L->tag==ATOM)return0;

//原子深度为0for(intmax=0,pp=L;pp;pp=pp->ptr.tp){dep=GlistDepth(pp->ptr.hp);//递归求解子表深度if(dep>max)max=dep;}returnmax+1;

//返回本层最深深度}深度示例：D=(A,B,C)=((),(e),(a,(b,c,d)))最终结果DEPTH(D)=1+Max{DEPTH(A),DEPTH(B),DEPTH(C)}=1+Max{1,1,2}=3DEPTH(D)=1-+Max{DEPTH(A),DEPTH(B),DEPTH(C)}DEPTH(A)=1;DEPTH(B)=1-+Max{DEPTH(e)}=1+0=1;DEPTH(C)=1+Max{DEPTH(a),DEPTH((b,c,d))}=2DEPTH(a)=0DEPTH((b,c,d))=1+Max{DEPTH(a),DEPTH(b),DEPTH(c)}=1+0=1复制广义表StatusCopyGList(GlistT,GlistL){if(!L)T=NULL;//复制空表else{if(!(T=(Glist)malloc(sizeof(GLNode))))exit(OVERFLOW);//建表结点T->tag=L->tag;if(L->tag==ATOM)T->atom=L->atom;//复制单原子结点else{CopyGList(T->ptr.hp,L->ptr.hp);//复制求得表头L->ptr.hp的一个副本T->ptr.hpCopyGList(T->ptr.tp,L->ptr.tp);//复制求得表尾L->ptr.tp的一个副本T->ptr.tp}//else}//elsereturnOK;}//CopyGList设LS为原表,NEWLS为复制表,其递归定义如下:基本项:InitGList(NEWLS){置空表},当LS为空表时。归纳项:COPY(GetHead(LS)->GetHead(NEWLS)){复制表头}COPY(GetTail(LS)->GetTail(NEWLS)){复制表尾}建立广义表存储结构广义表字符串S有两种可能情况:(1)S=‘()’(带括号的空白串);(2)S=(α1,α2,…,αn),其中αi(i=1,2,…,n)是S的子串。αi

可能有如下3种情况:(1)带括号的空白串;(2)长度为1的单字符串;(3)长度>1的字符串。建立广义表存储结构//采用头尾链表存储结构,由广义表的书写形式串S创建广义表L。设emp="()"StatusCreateGList(GListL,SStringS){if(StrCompare(S,emp))L=NULL;//创建空表else{GListL=newGLnode;//建表结点if(!L){exit(OVERFLOW);}if(StrLength(S)==1){L->tag=ATOM;L->atom=S}//创建单原子广义表else{L->tah=LIST;p=L;SubString(sub,S,2,StrLength(S)-2);do{//重复建n个子表server(sub,hsub);//从sub中分离出表头串hsubCreateGList(p->ptr.hp,hsub);q=p;if(!StrEmpty(sub)){//表尾不空GLNode*p=newGLNode;if(!p){exit(OVERFLOW);}p->tag=