多维数组和广义表

2020/4/25,数据结构,1,第五章多维数组和广义表,第一节多维数组第二节矩阵的压缩存储一、特殊矩阵二、稀疏矩阵第三节广义表的概念第四节广义表的存储*,2020/4/25,数据结构,2,第一节多维数组,多维数组为非线性结构逻辑特征：一个元素可能有多个直接前趋和多个直接后继。,数据结构,3,一、多维数组的概念,多维数组是向量（一维数组）的扩展,1.二维数组：可以看成是m个行向量和n个列向量组成的向量,第一节多维数组,2020/4/25,数据结构,4,逻辑特征,除边界外，每个元素aij恰好有两个直接前趋和两个直接后继。,第一节多维数组,2020/4/25,2020/4/25,数据结构,5,a11:无前趋，有行列两个后继amn:无后继，有行列两个前趋a1n:只有一个列后继和一个行前趋am1:只有一个列前趋和一个行后继a1j,ai1:有两个直接后继，只有一个直接前趋amj,ain:有两个直接前趋，只有一个直接后继,第一节多维数组,2020/4/25,数据结构,6,2.三维及多维数组,实例：书三维数组Amnp:可看成p个二维数组（m*n)所组成的向量每个元素aijk同属于三个向量（二维数组）最多有3个直接前趋和直接后继（除角、边、面上的结点）,第一节多维数组,2020/4/25,数据结构,7,推广：多维数组An1n2nm可看成nm个（m-1）维数组所构成的向量任一元素ai1i2im都属于m个向量（m-1维数组），最多有m个直接前趋和m个直接后继,第一节多维数组,2020/4/25,数据结构,8,对于数组，通常只有两种操作：(1)取值：给定一组下标，存取相应的数据元素；(2)修改：给定一组下标，修改相应数据元素中的某一个或几个数据项的值。,二、多维数组的运算,重要结论：对于数组，通常只进行读、写操作，不进行元素的插入和删除操作。因此，一般采用顺序存储结构表示数组。,第一节多维数组,2020/4/25,数据结构,9,1、两种顺序存储方法：(1)行优先顺序(rowmajororder)(c,pascal语言采用）特点：按照行向量顺序排列，第i1个行向量紧接在第i个行向量后面。(以二维数组为例）,三、顺序存储方法,第一节多维数组,2020/4/25,数据结构,10,列优先顺序(columnmajororder)(Fortran语言采用）特点：按照列向量顺序排列，第i1个列向量紧接在第i个列向量后面。(以二维数组为例）,第一节多维数组,2020/4/25,数据结构,11,第一节多维数组,推广到多维的情况：先排列最右的下标，最后排最左的下标；右边下标变化快；先排列最左的下标，最后排最右的下标；左边下标变化快,2020/4/25,数据结构,12,2、特点,顺序存储的数组是一个随机存取结构，即只要知道开始元素的存储起址，维数和每一维的上、下界及单个元素所占单元数，可将数组元素的存储地址表示为其下标的线性函数。,第一节多维数组,2020/4/25,数据结构,13,(以二维数组为例,且数组采用行优先顺序）LOC(aij)=LOC(a11)+(i-1)*n+j-1*d,d为单个元素所占单元数,开始元素的存储起址,n为列数,C语言数组下标从0开始，因此上面的式子应改为：LOC(aij)=LOC(a00)+(i*n+j)*d,第一节多维数组,2020/4/25,数据结构,14,压缩存储:前提：非零元素呈某种规律分布或矩阵中有大量零元素定义：多个值相同的元素只分配一个存储空间，值为0的元素不分配空间,第二节矩阵的压缩存储,存在大量零元素或非零元素呈某种规律分布。即使存储密度为100%，造成存储空间的浪费。实例：100100的矩阵，对角线元素非零。,2020/4/25,数据结构,15,分为两类：特殊矩阵和稀疏矩阵。,5.2.1特殊矩阵,特殊矩阵：非零元素或零元素的分布有一定规律的矩阵。对特殊矩阵常采用一维数组存储。,问题：如何将二维数组元素下标转换成一维数组元素下标。,第二节矩阵的压缩存储,2020/4/25,数据结构,16,1.对称矩阵1)定义:已知n阶方阵A，其元素满足：aij=aji0=i,j=j则k=i*(i+1)/2+jb:若in=5;a-t=4;a-data16,第二节矩阵的压缩存储,2020/4/25,数据结构,29,由于A的列是B的行，因此按a-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先顺序存放的。为了找到A的每一列中的所有非零元素，需要对三元组表a-data从第一行起扫描一遍，由于a-data是按A的行优先顺序存放的，因此得到的恰是b-data应有的顺序。,第二节矩阵的压缩存储,2020/4/25,数据结构,30,spmatrix*TRANSMAT(spmatrix*a)intano,bno,col;spmatrix*b;b=(spmatrix*)malloc(sizeof(spmatrix);b-m=a-n;b-n=a-m;b-t=a-t;/*b初始化*/if(b-t0)/*有非零元素*/bno=0;for(col=0;coln;col+)/*按*a列序转置*/for(ano=0;anot;ano+)/*扫描整个三元组表*/if(a-dataano.j=col)/*列号为col则进行交换*/b-databno.i=a-dataano.j;b-databno.j=a-dataano.i;b-databno.v=a-dataano.v;/*b-data结点下标加1*/bno+;returnb;,时间复杂度：O(n*t)O(m*n),第二节矩阵的压缩存储,2020/4/25,数据结构,31,4)三元组表的特点：优点：结构简单，易于实现，存储密度高。缺点：不具有随机存储特性；矩阵中非零元素发生变化时，将会引起三元组表中大量元素的移动。,第二节矩阵的压缩存储,2020/4/25,数据结构,32,3、十字链表,1)十字链表中结点的结构：,存储行号,存储列号,存储元素值或指向下一个表头结点,列指针域，指向本列下一个非零元素,行指针域，指向本行下一个非零元素,第二节矩阵的压缩存储,2020/4/25,数据结构,33,第二节矩阵的压缩存储,2020/4/25,数据结构,34,2)十字链表存储结构描述：typedefstructlnodeinti,j;structlnode*cptr,*rptr;unionstructlnode*next;datatypev;uval;link;,第二节矩阵的压缩存储,2020/4/25,数据结构,35,算法分为两步：1.建立表头结点的循环链表行列链表共用表头结点，表头结点个数应为行列数较大者。,第二节矩阵的压缩存储,3)建立十字链表,2.依次读入非零元素的三元组，生成一个表结点，将其插入相应行、列链表中的正确位置上。,2020/4/25,数据结构,36,算法描述如下：,link*creatlinkmat()link*p,*q,*h,*cpsmax;inti,j,m,n,t,k,s;datatypev;scanf(“%d%d%d”,建立头结点循环链表,十字链表头结点,输入行、列数，非零元素个数，确定表头结点个数s,第二节矩阵的压缩存储,指针数组cp的作用是什么？,2020/4/25,数据结构,37,for(k=1;k=0)个元素a1,a2,an的有限序列，其中ai或者是原子或者是一个广义表，通常记为LS=(a1,a2,an),1)LS:广义表的名字,2)n:广义表的长度,3)如果ai是广义表，则称它为LS的子表,4)用大写字母表示广义表，小写字母表示原子,第三节广义表的概念,2020/4/25,数据结构,39,5)若LS非空(n=1)，则a1是LS的表头，（a2,a3,an)构成的表称为LS的表尾,6)表是递归定义的，一个表的深度定义为表展开后所含括号的层数,7)如果规定任何表都是有名字的，为了既表明每个表的名字，又说明它的组成，可以在每个表的前面冠以该表的名称。,第三节广义表的概念,广义表是n（n=0)个元素a1,a2,an的有限序列，其中ai或者是原子或者是一个广义表，通常记为LS=(a1,a2,an),2020/4/25,数据结构,40,A=(),A是一个空表，长度为0，深度为1,B=(b,c,d),三个元素都是原子，所以是一个线性表，长度为3，深度为1,C=(a,(b,c,d),C的两个元素一个为原子，一个为广义表，长度为2，深度为2,D=(A,B,C),D的三个元素均为广义表，长度为3，深度为3。子表值代入后，D=(),(b,c,d),(a,(b,c,d),E=(a,E),E是一个递归的表，长度为2，深度为，相当于一个无限广义表,第三节广义表的概念,A()B(b,c,d)C(a,B(b,c,d)D(A(),B(b,c,d),C(a,B(b,c,d)E(a,E(a,E(),2020/4/25,数据结构,41,2、广义表的表示方法,图示法：用分支结点表示广义表，非分支结点表示原子。特殊的，空表对应的也是非分支结点。,第三节广义表的概念,2020/4/25,数据结构,42,纯表：树对应的广义表，限制了成分的共享与递归。如：A,B,C再入表：允许结点间共享的表。如：D递归表：允许递归的表。如：E,第三节广义表的概念,线性表纯表再入表递归表,2020/4/25,数据结构,43,3、广义表的两个特殊的运算,取表头head(LS):任何一个非空广义表的表头是表中第一个元素取表尾tail(LS)：根据表尾定义，必定是子表。,第三节广义表的概念,2020/4/25,数据结构,44,A是空表。无表头，无表尾！head(B)=tail(B)=head(C)=tail(C)=head(D)=tail(D)=head()=tail()=,第三节广义表的概念,b,(c,d),a,(b,c,d),A,(B,C),(),(),表头可能不是表，表尾肯定是表！,2020/4/25,数据结构,45,1、单链表示法（模仿单链表结构）,1)结点形式,typedefstructnodeintatom;structnode*link;unionstructnode*slink;datatypedata;element;lists;,例：,E=()headE=,第四节广义表的存储,2结构描述,2020/4/25,数据结构,46,第四节广义表的存储,2020/4/25,数据结构,47,第四节广义表的存储,2020/4/25,数据结构,48,3)单链表示法的缺点,若在某个表的表头前插入或删除结点时，必须找出所有指向该结点的指针，逐一修改。如删除结点x.若删除一个子表时将该子表的所有结点空间释放，可能导致错误，如删除表A.,第四节广义表的存储,2020/4/25,数据结构,49,解决办法:,每个子表增加一个头结点,a）插入删除变为内部结点的插入删除；b）表头结点data域计数为0时，才真正删除子表。,第四节广义表的存储,2020/4/25,数据结构,50,带头结点的广义表的单链表表示：,第四节广义表的存储,2020/4/25,数据结构,51,2、双链表示法（类似于第六章的二叉链表）,1)结点形式,2)结构描述,typedefstructnodedatatypedata;structnode*link1,*link2;lists;,E=()headE=,例,第四节广义表的存储,2020/4/25,数据结构,52,第四节广义表的存储,C(A(x,L