多维数组和广义表精选PPT.ppt

多维数组和广义多维数组和广义表表第1页，此课件共28页哦n n二维数组中，每个数据元素对应一对数组下标，在二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在行方向上和列方向上都存在一个线性关系，即存在两个前驱和两个后继。也可看作是以线性表为数据两个前驱和两个后继。也可看作是以线性表为数据元素的线性表。元素的线性表。n nn n n n维数组中，每个数据元素对应维数组中，每个数据元素对应维数组中，每个数据元素对应维数组中，每个数据元素对应n n n n个下标，受个下标，受个下标，受个下标，受n n n n个关系个关系个关系个关系的制约，其中任一个关系都是线性关系。可看作是的制约，其中任一个关系都是线性关系。可看作是的制约，其中任一个关系都是线性关系。可看作是的制约，其中任一个关系都是线性关系。可看作是数据元素为数据元素为数据元素为数据元素为n-1n-1n-1n-1维数组的一维数组。维数组的一维数组。维数组的一维数组。维数组的一维数组。n n因此，多维数组是对线性表的扩展：线性表中的数因此，多维数组是对线性表的扩展：线性表中的数因此，多维数组是对线性表的扩展：线性表中的数因此，多维数组是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。据元素本身又是一个多层次的线性表。据元素本身又是一个多层次的线性表。据元素本身又是一个多层次的线性表。5.1 5.1 多维数组多维数组第2页，此课件共28页哦n n多维数组用一维的存储单元存放，需约定次序。多维数组用一维的存储单元存放，需约定次序。C C语言是行优先顺序。语言是行优先顺序。n n二维数组中任一元素二维数组中任一元素二维数组中任一元素二维数组中任一元素a a a aijijijij的存储地址的存储地址的存储地址的存储地址:n nn n n n维数组维数组维数组维数组Loc(Loc(Loc(Loc(a a a aijijijij)=Loc()=Loc()=Loc()=Loc(a a a a00000000)+(n*i+j)*d)+(n*i+j)*d)+(n*i+j)*d)+(n*i+j)*d第3页，此课件共28页哦5.2 5.2 矩阵的压缩存储矩阵的压缩存储 压缩存储压缩存储 使用一维数组存储矩阵，并且在一维数组使用一维数组存储矩阵，并且在一维数组中为多个值相同的元素只分配一个存储空间，中为多个值相同的元素只分配一个存储空间，对零元不分配空间。对零元不分配空间。第4页，此课件共28页哦5.2.1 5.2.1 特殊矩阵特殊矩阵n对称矩阵：对称矩阵：a aijij=a=ajiji 0i,jn-1 0i,jn-1u压缩存储方法：为每一对对称元分配一个存储空间压缩存储方法：为每一对对称元分配一个存储空间将下三角的元素，按行存储到一维数组将下三角的元素，按行存储到一维数组sasa中中,共有共有n(n+1)/2n(n+1)/2个存储单元，个存储单元，a aijij在一维数组中的位置在一维数组中的位置k k为：为：i(ii(i1)/2+j 1)/2+j 当当i=ji=j；j(jj(j1)/2+i 1)/2+i 否则否则 第5页，此课件共28页哦特殊矩阵特殊矩阵n三角矩阵三角矩阵：上（下）三角中的元素均为常数：上（下）三角中的元素均为常数c c或或0 0u压缩存储方法：只存储上（下）三角元素。压缩存储方法：只存储上（下）三角元素。u下三角：下三角：k=i*(ik=i*(i1)/2+j(i=j);1)/2+j(i=j);k=n*(n+1)/2 (ij)k=n*(n+1)/2 (ij)u上三角：上三角：k=(i/2)*(2n-i+1)+j-i(i=j);k=(i/2)*(2n-i+1)+j-i(ij)k=n*(n+1)/2 (ij)注意：注意：k,i,jk,i,j从零开始从零开始第6页，此课件共28页哦特殊矩阵特殊矩阵n n对角矩阵：所有非零元都集中在以主对角线对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中为中心的带状区域中n n压缩方法：压缩存储到一维数组压缩方法：压缩存储到一维数组sa sa 中，三对角中，三对角矩阵有矩阵有3n-23n-2个元素。个元素。第7页，此课件共28页哦5.2.2 5.2.2 稀疏矩阵稀疏矩阵 已知矩阵已知矩阵已知矩阵已知矩阵A A A Am m m m n n n n，t t t t为非零元个数，若为非零元个数，若为非零元个数，若为非零元个数，若t(mt(mt(mtm=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页哦2.2.十字链表十字链表n n当矩阵中非零元素的个数和位置经过运算后变化较大时，就不宜采用顺序存储结构，而应采用链式存储结构来表示三元组。n n行链表与列链表都是带表头结点的循环链表。第13页，此课件共28页哦n n元素结点元素结点urptrrptr指向同一行中下一指向同一行中下一个非零元素的指针（向右域）个非零元素的指针（向右域）ucptrcptr指向同一列中下一指向同一列中下一个非零元素的指针（向下域）个非零元素的指针（向下域）ijVcptrrptr00nextrptr00nextcptrn n表头结点表头结点u行表头结点行表头结点u列表头结点列表头结点unextnext用于表示头结点的链接用于表示头结点的链接第14页，此课件共28页哦1396457稀疏矩阵的十字链表表示的示例稀疏矩阵的十字链表表示的示例第15页，此课件共28页哦十字链表结构定义：十字链表结构定义：typedef struct lnodetypedef struct lnodetypedef struct lnodetypedef struct lnode int i,j;/int i,j;/int i,j;/int i,j;/非零元的行下标和列下标非零元的行下标和列下标非零元的行下标和列下标非零元的行下标和列下标 struct lnode*cptr,*rptr;struct lnode*cptr,*rptr;struct lnode*cptr,*rptr;struct lnode*cptr,*rptr;union union union union struct lnode*next;struct lnode*next;struct lnode*next;struct lnode*next;datatype v;datatype v;datatype v;datatype v;uval;uval;uval;uval;Link;Link;Link;Link;Link *lLink *lLink *lLink *l；ijVcptrrptr第16页，此课件共28页哦n n需要辅助结点作链表的表头，同时每个结点要增加需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀疏时才能两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。起到节省空间的效果。n n分别用两个一维数组存储行链表的头指针和列链表分别用两个一维数组存储行链表的头指针和列链表的头指针，可加快访问速度。的头指针，可加快访问速度。第17页，此课件共28页哦 5.3 5.3 广义表广义表 5.3.1 5.3.1 广义表的概念广义表的概念 5.3.2 5.3.2 广义表的存储结构广义表的存储结构第18页，此课件共28页哦 什么是广义表什么是广义表 广义表也称为列表，是广义表也称为列表，是线性表的一种扩展线性表的一种扩展，也是数据元素的有限序列。，也是数据元素的有限序列。记作：记作：LS=(LS=(1 1,2 2,，n n)。其中。其中i i可以是单个元素，也可以是可以是单个元素，也可以是广义表。广义表。5.3.1 5.3.1 广义表的概念广义表的概念 说明 1 1）在广义表中，元素可以是单个元素，称为）在广义表中，元素可以是单个元素，称为原子原子；也可以是广；也可以是广 义表，称为广义表的义表，称为广义表的子表子表；3 3）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；表；2 2）n n 是广义表长度；是广义表长度；第19页，此课件共28页哦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页哦广义表的图形表示广义表的图形表示LabL=（a，b）AxLA=（x，L）abAxLabyBB=（A，y）AxLayBCbC=（A，B）aDD=（a，D）第21页，此课件共28页哦 广义表的基本运算广义表的基本运算 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页哦5.3.2 5.3.2 广义表的存储结构广义表的存储结构 由于广义表中的数据元素可以具有不同的类型，（或是原子，或是广义表）因此难以用顺序存储结构表示，通常采用链式存储结构，书上介绍了两种链式存储结构，一种是单链表示法，另一种是双链表示法。第23页，此课件共28页哦单链表示法单链表示法 atomData/slinklinkatom=本结点为子表本结点为子表本结点为原子本结点为原子第24页，此课件共28页哦示例A=NuLLA=NuLL A=()A=()B B1e B=(e)B=(e)C=(a,(b,c,d)C=(a,(b,c,d)C1 a111bcd 0第25页，此课件共28页哦1E E0aE E（a,Ea,E）D=(B,C)D=(B,C)0D D0B B1eC1 a111bcd 0第26页，此课件共28页哦双链表示法双链表示法 Link1Datalink2Cabcd C=(a,(b,c,d)C=(a,(b,c,d)指向该结点的子表指向该结点的子表指向该结点的后继指向该结点的后继第27页，此课件共28页哦 小 结 1 广义表是数据元素的有限序列。其数据元素可以单个 元素，也可以是广义表；2 若广义表不空，则可分成表头和表尾，反之，一对表头 和表尾可唯一确定广义表；3 广义表通常采用链式存储结构。链表中有两种的结点：一种是表结点，用以表示广义表；一种是原子结点，用以表示原子；第28页，此课件共28页哦