数组和广义表

《数组和广义表》由会员分享，可在线阅读，更多相关《数组和广义表（32页珍藏版）》请在金锄头文库上搜索。

1、第五章 数组和广义表,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 5.1 数组的定义和特点 定义,数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值,5.2 数组的顺序存储结构 次序约定 以行序为主序 以列序为主序,5.3 矩阵的压缩存储 对称矩阵,三角矩阵,对角矩阵,Loc(aij)=Loc(a11)+2(i-1)+(j-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）

2、唯一确定,稀疏矩阵 定义：非零元较零元少，且分布没有一定规律的矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,稀疏矩阵的压缩存储方法 顺序存储结构 三元组表,#define M 20 typedef struct node int i,j;int v; JD; JD maM;,三元组表所需存储单元个数为3(t+1) 其中t为非零元个数,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,ma0.i,ma0.j,ma0.v分别存放 矩阵行列维数和非零元个数,带辅助行向量的二元组表,增加一个辅助数组NRAm+

3、1,其物理意义是第i行第一个非零元 在二元组表中的起始地址（m为行数） 显然有：,6,NRA0不用或 存矩阵行数,二元组表需存储单元个数为2(t+1)+m+1,伪地址表示法,伪地址：本元素在矩阵中（包括零元素再内）按行优先顺序的相对位置,伪地址表示法需存储单元个数 为2(t+1),求转置矩阵 问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表 问题分析 一般矩阵转置算法：,for(col=0;coln;col+)for(row=0;rowp-col时，p和q右移 （2）插入： a、若p=NULL且q=NULL，即本行空，则rhr-1=s; b、若p=NULL,q!=NULL，即走

4、到行末，则q-right=s c、若c=p-col，则修改p-val d、若ccol且q=NULL，则在p之前插入s，即s是行链表中第一个结点，令rhr-1=s; s-right=p; e、若ccol且q!=NULL，则在p之前插入s，即 s-right=p; q-right=s;,m=4,n=3 1,1,3 2,2,5 2,3,4 4,1,8 2,1,7,5.4 广义表的定义,广义表是线性表的推广。是表中含有表的一种列表，广泛地应用于人工智能等领域的表处理语言LISP语言。 一般表示为：LS = (a1,a2, a3. an) 其中LS是广义表(a1,a2,a3an)的名字，n是它的长度。

5、ai(1 i n) 是表中任意元素。在线性表中它只能是单元素，但在广义表中它可以是单元素，也可以是一个广义表（称为子表）。 习惯上广义表的名字用大写字母表示，单元素用小写字母表示。,例子（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 ) E是是含有一个单元素和一个表元素的表，长度为2。(6) F = ( ) F是

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

7、(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(C)

8、 = ( 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 ：存放表

9、尾元素结点地址。 原子结点中P -atom ：存放元素值。 Typedef enum ATOM , LIST ElemTag; Typedef struct GLNode ElemTag tag; / 共用，区分表结点和原子结点union / 表结点和原子结点的联合部分AtomType atom;struct struct GLNode *hp,*tp; ptr; myuu; *Glist;,表元素结点,单元素结点,P,Tag=1,hp,tp,Tag=0,atom,A =NULL,B 1 C 1 1 ,0 e 0 a 1 1 1,D 1 1 1,E 1 1,0 a,0 b 0 c 0 d,特点

10、： 1）除空表外，其表头指针均指向一个表结点。 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,表结点 原子结点,ACB DE,1 ,1 ,1 ,1,1 ,1 ,0 a 1 ,0 b 0 c 0 d ,0 e 0 a 1 ,