多维数组和广义表

多维数组和广义表第1页，共28页，2023年，2月20日，星期一二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱和两个后继。也可看作是以线性表为数据元素的线性表。n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。因此，多维数组是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。5.1多维数组第2页，共28页，2023年，2月20日，星期一多维数组用一维的存储单元存放，需约定次序。C语言是行优先顺序。二维数组中任一元素aij的存储地址:n维数组Loc(aij)=Loc(a00)+(n*i+j)*d第3页，共28页，2023年，2月20日，星期一5.2矩阵的压缩存储

压缩存储使用一维数组存储矩阵，并且在一维数组中为多个值相同的元素只分配一个存储空间，对零元不分配空间。第4页，共28页，2023年，2月20日，星期一5.2.1特殊矩阵对称矩阵：aij=aji0≤i,j≤n-1压缩存储方法：为每一对对称元分配一个存储空间将下三角的元素，按行存储到一维数组sa中,共有n(n+1)/2个存储单元，aij在一维数组中的位置k为：

i(i＋1)/2+j当i>=j；

j(j＋1)/2+i否则第5页，共28页，2023年，2月20日，星期一特殊矩阵三角矩阵：上（下）三角中的元素均为常数c或0压缩存储方法：只存储上（下）三角元素。下三角：k=i*(i＋1)/2+j(i>=j);k=n*(n+1)/2(i<j)上三角：k=(i/2)*(2n-i+1)+j-i(i<=j);k=n*(n+1)/2(i>j)注意：k,i,j从零开始第6页，共28页，2023年，2月20日，星期一特殊矩阵对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中压缩方法：压缩存储到一维数组sa[]中，三对角矩阵有3n-2个元素。

第7页，共28页，2023年，2月20日，星期一5.2.2稀疏矩阵

已知矩阵Am×n，t为非零元个数，若t<<(m×n)，则称Am×n为稀疏矩阵。 用三元组(i,j,v)存储行和列的位置及非零元值。第8页，共28页，2023年，2月20日，星期一1.三元组表顺序存储方式存储稀疏矩阵的三元组.第9页，共28页，2023年，2月20日，星期一

三元组表结构定义#definesmax16//非零元个数最大值Typedefintdatatypetypedefstruct{inti，j;//行下标和列下标

datatypev;}node;typedefstruct{nodedata[smax];//非零元三元组表

intm,n,t;//行数、列数、非零元个数

}SpMatrix;SPMatrix*a,*b;第10页，共28页，2023年，2月20日，星期一三元组表稀疏矩阵的转置运算第11页，共28页，2023年，2月20日，星期一稀疏矩阵的转置

Spmatrix*transmat(a)Spmatrix*a;{intano,bno,col;Spmatrix*b;b=malloc(sizeof(Spmatrix));b->m=a->n;b->n=a->m;b->t=a->t;if(b->t>0){bno=0;for(col=0;col<a->n;col++)for(ano=0;ano<a->t;ano++)if(a->data[ano].j==col){b->data[bno].i=a->data[ano].j;b->data[bno].j=a->data[ano].i;b->data[bno].v=a->data[ano].v;bno++;}}returnb;}第12页，共28页，2023年，2月20日，星期一2.十字链表当矩阵中非零元素的个数和位置经过运算后变化较大时，就不宜采用顺序存储结构，而应采用链式存储结构来表示三元组。行链表与列链表都是带表头结点的循环链表。第13页，共28页，2023年，2月20日，星期一元素结点rptr——指向同一行中下一个非零元素的指针（向右域）cptr——指向同一列中下一个非零元素的指针（向下域）ijVcptrrptr00nextrptr00nextcptr表头结点行表头结点列表头结点next用于表示头结点的链接第14页，共28页，2023年，2月20日，星期一1396457稀疏矩阵的十字链表表示的示例第15页，共28页，2023年，2月20日，星期一十字链表结构定义：typedefstructlnode{inti,j;//非零元的行下标和列下标

structlnode*cptr,*rptr;union{structlnode*next;datatypev;}uval;} Link;Link*l；ijVcptrrptr第16页，共28页，2023年，2月20日，星期一需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。分别用两个一维数组存储行链表的头指针和列链表的头指针，可加快访问速度。第17页，共28页，2023年，2月20日，星期一

5.3广义表

5.3.1广义表的概念

5.3.2广义表的存储结构第18页，共28页，2023年，2月20日，星期一

什么是广义表广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。记作：LS=(α1,α2,…，αn)。其中αi可以是单个元素，也可以是广义表。5.3.1广义表的概念

说明

1）在广义表中，元素可以是单个元素，称为原子；也可以是广义表，称为广义表的子表；

3）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；2）n是广义表长度；第19页，共28页，2023年，2月20日，星期一A=()6）对非空广义表L,称第一个元素为L的表头，其余元素组成的广义表称为L的表尾；

B=(e)

C=(a,(b,c,d))

D=(A,B,C)

E=(a,E)例：B=(e)

C=(a,(b,c,d))D=(A,B,C)表头：e；表尾()表头：a；表尾((b,c,d))表头：A；表尾(B,C)空表，表长为0；4）下面是一些广义表的例子；B中只有一个元素e，表长为1；两个元素分别为a和子表（b,c,d)；表长为2。它的三个元素A，B，C广义表；表长为3。E的表长为25）广义表的深度：表展开后所含括号的层数。设一个原子的深度是0。深度＝max｛各元素的深度｝＋1第20页，共28页，2023年，2月20日，星期一广义表的图形表示LabL=（a，b）AxLA=（x，L）abAxLabyBB=（A，y）AxLayBCbC=（A，B）aDD=（a，D）第21页，共28页，2023年，2月20日，星期一广义表的基本运算

1）取广义表L的表头；head（）

2）取广义表L的表尾；tail（）

例如：head(L)=a,tail(L)=(b),head(tail(L))=b,tail(tail(L))=()head(B)=A,tail(B)=(y)第22页，共28页，2023年，2月20日，星期一5.3.2广义表的存储结构由于广义表中的数据元素可以具有不同的类型，（或是原子，或是广义表）因此难以用顺序存储结构表示，通常采用链式存储结构，书上介绍了两种链式存储结构，一种是单链表示法，另一种是双链表示法。

第23页，共28页，2023年，2月20日，星期一单链表示法

atomData/slinklinkatom=本结点为子表本结点为原子第24页，共28页，2023年，2月20日，星期一示例A=NuLL

A=()B1∧e

B=(e)C=(a,(b,c,d))C1a∧111bcd∧0第25页，共28页，2023年，2月20日，星期一1E0∧aE＝（a,E）D=(B,C)0D0∧B1∧eC1a∧111bcd∧0第26页，共28页，2023年，2月20日，星期一双链表示法

Link1Datalink2C∧a∧∧∧∧bcd∧C=(a,(b,c,d))指向该结点的子表指向该结点的后继第27页，共28页，2