第五章数组和广义表.ppt

《第五章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《第五章数组和广义表.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章 数组和广义表数组和广义表数组可以看成是一种特殊的线性表，即线性表中数数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表据元素本身也是一个线性表n5.1 数组的定义和特点数组的定义和特点定义定义数组特点数组特点n数组结构固定数组结构固定n数据元素同构数据元素同构数组运算数组运算n给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素n给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值()()()()()()()()()n5.2 数组的顺序存储结构次序约定n以行序为主序n以列序为主序a11a12.a1na21a22.a2nam1am2.amn.L

2、oc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为主序存放 amn .am2 am1 .a2n .a22 a21 a1n .a12 a1101n-1m*n-1n按列序为主序存放按列序为主序存放01m-1m*n-1m amn .a2n a1n .am2 .a22 a12 am1 .a21 a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)m+(i-1)*ln5.3 矩阵的压缩存储对称矩阵a11a12.a1na21a22.a2nan1an2.ann.a11 a21 a22 a31 a32 an1 a

3、nn.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：三角矩阵a1100.0a21a220.0an1an2an3.ann.0Loc(aij)=Loc(a11)+(+(j-1)*li(i-1)2a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：对角矩阵a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1ann.0a32a33a3400Loc(aij)=Loc(a11)+2(i-1)+(j-1)a11 a12 a21 a22 a23

4、ann-1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：M由(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵维数（6,7）唯一确定稀疏矩阵n定义：非零元较零元少，且分布没有一定规律的矩阵n压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值n稀疏矩阵的压缩存储方法顺序存储结构三元组表#define M 20typedef struct node int i,j;int v;JD;JD maM;三元组表所需存储单元个数为3(t+1)其中t为非零元个数

5、6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 mai j v0 1 2 3 4 5 6 7 8ma0.i,ma0.j,ma0.v分别存放矩阵行列维数和非零元个数行列下标非零元值带辅助行向量的二元组表增加一个辅助数组NRAm+1,其物理意义是第i行第一个非零元在二元组表中的起始地址（m为行数）显然有：NRA1=1NRAi=NRAi-1+第i-1行非零元个数(i2)0 1 2 3 4 5 6 NRA1335676 7 8 2 12 3 9 1 -3 6 14 3 24 2 18 1 15 4 -7 maj v0 1 2 3

6、 4 5 6 7 8矩阵列数和非零元个数列下标和非零元值NRA0不用或存矩阵行数二元组表需存储单元个数为2(t+1)+m+1伪地址表示法伪地址：本元素在矩阵中（包括零元素再内）按行优先顺序的相对位置 6 7 2 12 3 9 15 -3 20 14 24 24 30 18 36 15 39 -7 maaddr v伪地址非零元值矩阵行列维数0 1 2 3 4 5 6 7 8伪地址表示法需存储单元个数为2(t+1)求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表Y问题分析一般矩阵转置算法：for(col=0;coln;col+)for(row=0;rowp-col时，p

7、和q右移（2）插入：a、若p=NULL且q=NULL，即本行空，则rhr-1=s;b、若p=NULL,q!=NULL，即走到行末，则q-right=sc、若c=p-col，则修改p-vald、若ccol且q=NULL，则在p之前插入s，即s是行链表中 第一个结点，令rhr-1=s;s-right=p;e、若ccol且q!=NULL，则在p之前插入s，即 s-right=p;q-right=s;418234m=4,n=31,1,32,2,52,3,44,1,82,1,71132172255.45.4广义表的定义广义表的定义n广义表是线性表的推广。是表中含有表的一种列表，广泛地应用于人工智能等领域

8、的表处理语言LISP语言。l一般表示为：LS=(a1,a2,a3.an)其中LS是广义表(a1,a2,a3.an)的名字，n是它的长度。lai(1 i n)是表中任意元素。在线性表中它只能是单元素，但在广义表中它可以是单元素，也可以是一个广义表（称为子表）。l习惯上广义表的名字用大写字母表示，单元素用小写字母表示。例子（1）A=（）A是一个空表，长度为零。（2）B=（e）B是含有一个单元素的表，长度为1。(3)C=(a,(b,c,d,)C是含有一个单元素和一个表元素的表，长度为2。(4)D=(A,B,C)D是含有三个表元素的表，长度为3。=(),(e),(a,(b,c,d)(5)E=(a,E)

9、E是是含有一个单元素和一个表元素的表，长度为2。(6)F=()F是含有一个表元素的表，长度为1。从上述的定义和例子可推出广义表的三个重要结论：1）广义表的元素可以是子表，而子表的元素还可以是子表。2）广义表可以为其他列表所共享。例如上述的表D中A，B，C为D的子表。3）广义表可以是一个递归的表，即广义表也可以是其本身的子表。如E表。广义表的图形表示n圆圈表示子表；n方块表示原子；n例子：D=（），（e），（a，（b，c，d）eabcdD广义表的表头、表尾广义表的表头、表尾 1）广义表的表头表尾 广义表的表头可以是单元素，也可以是表元素来充当。但是广义表的表尾，只能是表元素来充当。例如：GetH

10、ead(B)=e;GetTail(B)=().GetHrad(D)=A;GetTail(D)=(B,C);由于（B，C）为非空列表，还可以继续分解得到：Get Head（B，C）=B;GetTail（B，C）=（C）;GetHead(C)=C.注意表()与表()不同，()表不能分解为表头与表尾，而()表则是表头表为都是空表()。如广义表C（a,（b，c，d）可以分解为：GetHead(C)=a;GetTail(C)=(b,c,d);Get Head(GetTail(C)=(b,c,d);GetHead(Get Head(GetTail(C)=b;GetTail(Get Head(GetTail

11、(C)=(c,d);GetHead(GetTail(Get Head(GetTail(C)=c;GetTail(GetTail(Get Head(GetTail(C)=(d);GetHead(GetTail(GetTail(Get Head(GetTail(C)=d.5.5广义表的存储 从广义表中可以知道其数据元素有单元素和表元素，而两种元素的结构不同，所以很难用顺序存储结构，通常都采用链式存储，每一种数据元素使用一种结点。因为广义表的数据元素有单元素和表元素，所以结点就有表结点与单元素结点（原子结点）。其中表元素P-hp：存放表的头元素结点地址；P-tp：存放表尾元素结点地址。原子结点中P-

12、atom：存放元素值。Typedef enum ATOM,LIST ElemTag;Typedef struct GLNode ElemTag tag;/共用，区分表结点和原子结点 union /表结点和原子结点的联合部分 AtomType atom;struct struct GLNode*hp,*tp;ptr;myuu;*Glist;表元素结点单元素结点PTag=1hptpTag=0atomA=NULLB 1 C 1 1 0 e 0 a 1 1 1D 1 1 1 E 1 10 a0 b 0 c 0 d特点：特点：1）除空表外，其表头指针均指向一个表结点。）除空表外，其表头指针均指向一个表结

13、点。2）容易分清表中原子和子表所在层次。）容易分清表中原子和子表所在层次。3）最高层的表结点个数即为该表的长度。）最高层的表结点个数即为该表的长度。另一种链式存储结构另一种链式存储结构Typedef enumATOM,LIST ElemTag;Typedef struct GLNode ElemTag tag;union AtomType atom;struct GLNode*hp;myuu;struct GLNode*tp；*Glist;其两种结点的结构如下图所示：P tag=1 hp tp tag=0 atom tp表结点 原子结点 A C B D E1 1 1 11 1 0 a 1 0 b 0 c 0 d 0 e 0 a 1 1 1 广义表的深度n深度：广义表的括弧的重数。n原子的深度为0；n例如：1、（）的深度为1；2、（a,b,c）的深度为1；3、（），（a）的深度为3；练习1、写出head(tail(head(a,b),c,d)和tail(head(tail(a,(b,c,d)各自的运算结果。2、广义表A=(a),b,(d,(f),c),(e),g,(h),求A的长度与深度；3、画出广义表A的图形表示及一种存储结构图；4、写出用求头、尾元素的方式求出单元素h的过程。