多维数组和广义表

1、多维数组和广义表第1页，共28页，2022年，5月20日，14点15分，星期二二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱和两个后继。也可看作是以线性表为数据元素的线性表。n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。因此，多维数组是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。5.1 多维数组第2页，共28页，2022年，5月20日，14点15分，星期二多维数组用一维的存储单元存放，需约定次序。C语言是行优先顺序。二维数组中任一元素aij的存储地

2、址:n维数组Loc(aij)=Loc(a00)+(n*i+j)*d第3页，共28页，2022年，5月20日，14点15分，星期二5.2 矩阵的压缩存储 压缩存储 使用一维数组存储矩阵，并且在一维数组中为多个值相同的元素只分配一个存储空间，对零元不分配空间。第4页，共28页，2022年，5月20日，14点15分，星期二5.2.1 特殊矩阵对称矩阵： aij=aji 0i,jn-1压缩存储方法：为每一对对称元分配一个存储空间将下三角的元素，按行存储到一维数组sa中,共有n(n+1)/2个存储单元，aij在一维数组中的位置k为： i(i1)/2+j 当i=j； j(j1)/2+i 否则 第5页，共2

3、8页，2022年，5月20日，14点15分，星期二特殊矩阵三角矩阵：上（下）三角中的元素均为常数c或0压缩存储方法：只存储上（下）三角元素。下三角：k=i*(i1)/2+j (i=j); k=n*(n+1)/2 (ij)上三角：k=(i/2)*(2n-i+1)+j-i (ij)注意：k, i,j从零开始第6页，共28页，2022年，5月20日，14点15分，星期二特殊矩阵对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中压缩方法：压缩存储到一维数组sa 中，三对角矩阵有3n-2个元素。 第7页，共28页，2022年，5月20日，14点15分，星期二5.2.2 稀疏矩阵 已知矩阵Amn，t

4、为非零元个数，若tm=a-n;b-n=a-m;b-t=a-t; if(b-t0) bno=0; for(col=0;coln;col+) for(ano=0;anot;ano+) if(a-dataano.j=col) b-databno.i= a-dataano.j; b-databno.j= a-dataano.i; b-databno.v= a-dataano.v; bno+; return b;第12页，共28页，2022年，5月20日，14点15分，星期二2.十字链表当矩阵中非零元素的个数和位置经过运算后变化较大时，就不宜采用顺序存储结构，而应采用链式存储结构来表示三元组。行链表与列

5、链表都是带表头结点的循环链表。第13页，共28页，2022年，5月20日，14点15分，星期二元素结点rptr指向同一行中下一个非零元素的指针（向右域）cptr指向同一列中下一个非零元素的指针（向下域）ijVcptrrptr00nextrptr00nextcptr表头结点行表头结点列表头结点next用于表示头结点的链接第14页，共28页，2022年，5月20日，14点15分，星期二1396457稀疏矩阵的十字链表表示的示例第15页，共28页，2022年，5月20日，14点15分，星期二十字链表结构定义：typedef struct lnode int i,j; /非零元的行下标和列下标 str

6、uct lnode *cptr,*rptr; union struct lnode *next; datatype v; uval;Link;Link *l；ijVcptrrptr第16页，共28页，2022年，5月20日，14点15分，星期二需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。分别用两个一维数组存储行链表的头指针和列链表的头指针，可加快访问速度。第17页，共28页，2022年，5月20日，14点15分，星期二 5.3 广义表 5.3.1 广义表的概念 5.3.2 广义表的存储结构第18页，共28页，2022年，5月20日

7、，14点15分，星期二 什么是广义表 广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。 记作：LS=(1,2,，n)。其中i可以是单个元素，也可以是广义表。5.3.1 广义表的概念 说明 1）在广义表中，元素可以是单个元素，称为原子；也可以是广 义表，称为广义表的子表； 3）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；2）n 是广义表长度；第19页，共28页，2022年，5月20日，14点15分，星期二A=( )6）对非空广义表L,称第一个元素为L的表头，其余元素组成的广义表称为L的表尾； B=(e) C=(a,(b,c,d) D=(A,B,C) E=(a,E)

8、 例：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页，2022年，5月20日，14点15分，星期二广义表的图形表示LabL=（a，b）AxLA=（x，L）abAxLabyBB=（A，y）AxLayBCbC=（A，B）

9、aDD=（a，D）第21页，共28页，2022年，5月20日，14点15分，星期二 广义表的基本运算 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页，2022年，5月20日，14点15分，星期二5.3.2 广义表的存储结构 由于广义表中的数据元素可以具有不同的类型，（或是原子，或是广义表）因此难以用顺序存储结构表示，通常采用链式存储结构，书上介绍了两种链式存储结构，一种是单链表示法，另一种是

10、双链表示法。 第23页，共28页，2022年，5月20日，14点15分，星期二单链表示法 atomData/slinklinkatom=本结点为子表本结点为原子第24页，共28页，2022年，5月20日，14点15分，星期二示例A=NuLL A = ( ) B1e B = (e) C = (a,(b,c,d)C1a111bcd0第25页，共28页，2022年，5月20日，14点15分，星期二1E0aE（a,E）D = (B,C)0D0B1eC1a111bcd0第26页，共28页，2022年，5月20日，14点15分，星期二双链表示法 Link1Datalink2CabcdC = (a,(b,c,d)指向该结点的子表指向该结点的后继第27页，共28页，2022年，5月20日，14点15分，星期二 小 结 1 广义表是数据