第五章数组2009.ppt

1、第五章 数组和广义表,数组和广义表可看成是一种特殊的线性表，其特殊在于表中的数据元素本身也是一种线性表。,2020/9/13,zhengzhihua,2,第五章 数组和广义表,5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构,2020/9/13,zhengzhihua,3,5.1 数组的定义,2020/9/13,zhengzhihua,4,ADT Array 数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系： RR1, R

2、2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array,基本操作:,1. 数组的抽象数据类型定义,2020/9/13,zhengzhihua,5,基本操作：,InitArray( /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型,typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型,2.三元组表示的数据类型,data,2020/9/13,zhengzhihua,34,3.

3、运算（三元组）,定义 TsMatrix A 创建一个三元组M 存取运算，找一个元素aij 元素改值运算 稀疏矩阵的转置 两个稀疏矩阵相加,2020/9/13,zhengzhihua,35,元素改值运算 首先要查找 aij的存储地址，分情况讨论,查找不成功。即原aij=0，修改后aij 0;则应在A中插入(i,j,aij);,2020/9/13,zhengzhihua,36,元素改值运算 首先要查找 aij的存储地址，分情况讨论,查找不成功。即原aij=0，修改后aij 0;则应在A中插入(i,j,aij); 若查找成功。即原aij 0，修改后aij=0 ;则应在A中删除(i,j,aij)；,2

4、020/9/13,zhengzhihua,37,元素改值运算 首先要查找 aij的存储地址，分情况讨论,查找不成功。即原aij=0，修改后aij 0;则应在A中插入(i,j,aij); 若查找成功。即原aij 0，修改后aij=0 ;则应在A中删除(i,j,aij)； 若查找成功。即原aij 0，修改后aij 0 ;只要修改aij的值；,转置运算算法,一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。 将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得

5、到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。,2020/9/13,zhengzhihua,39,如何求转置矩阵？,2020/9/13,zhengzhihua,40,用“三元组”表示时如何实现？,1 2 14,1 5 -5,2 2 -7,3 1 36,3 4 28,2 1 14,5 1 -5,2 2 -7,1 3 36,4 3 28,i j e,i j e,Void transmatrix(tripletable M , tripletable T) int p, q ,col; T.mu=M.nu; T.nu=M.mu

6、; T.tu=M.tu; ,q=1; /计算转置非零元个数 for(col=1; col=T.nu; col+) for(p=1; p=M.tu;p+) if(M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; q+; ,M,T,它的主要工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=1;col=n;+col) for(row=1;row=m;+row) tcolrow=mrowco

7、l; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。,算法分析,2020/9/13,zhengzhihua,43,对M扫描一次，按M第二列提供的列号一次确定位置装入T的一个三元组。 具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。,算法思想：,快速转置的算法,2020/9/13,zhengzhihua,44,为了预先确定矩阵M中的每一列的第一个非零元素在数组T中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组T

8、中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组 num0.n 和 cpot0.n 其中：num0.n：统计M中每列非零元素的个数； numcol的值可以由A的第二列求得。,0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 M= 0 0 24 0 0 0 0 T=MT= 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 0 0 0 0 15 0 0 7 0 0 0 0 0 14 0 0 0,例,例,例,M,T,例,M

9、,T,关键：需先求出M中每一列的非零元个数num(y)，从而确定M中每一列的第一个非零元在T.data中的位置。,例,M,T,关键：需先求出M中每一列的非零元个数num(y)，从而确定M中每一列的第一个非零元在T.data中的位置。,例,M,T,关键：需先求出M中每一列的非零元个数num(y)，从而确定M中每一列的第一个非零元在T.data中的位置。,1,3,5,7,8,8,9,例,M,T,公式：cpot1 = 1 cpoty =cpot y-1 + numy-1,1,3,5,7,8,8,9,公式：cpot1 = 1 cpoty =cpot y-1 + numy-1 2 y M.nu (M的列

10、数),快速转置算法要点： 求,快速转置算法 void FastTranstri(Tritupletable M,Tritupletable T) int p,q, y, k; /k为M中的非零元个数 int num0.M.nu,copt0.M.nu; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;,if(T.tu != 0 ) for( y =1; y=M.nu; +y ) /num(y)初始化 numy= 0; for(k=1;k=M.tu;+k) / M中每列的 +numM.datak.j; /非零元个数,cpot1=1; for( y =2; y=M.nu; +y) c

11、poty=cpoty-1+numy-1;,/利用公式求出第一个非零元在T中的位置,公式：cpot1 = 1 cpoty =cpot y-1 + numy-1,/转置 for (p=1;p=M.tu;+p) y =M.datap.j; /确定第一个结点是M的第几列 q =cpoty; /确定在T.data中的哪个位置, T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=a.datap.e; cpoty= cpoty+1;, ,2020/9/13,zhengzhihua,56,分析算法FastTransposeSMatrix的时间复杂度：,时间

12、复杂度为: O(M.nu+M.tu),for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) ,2020/9/13,zhengzhihua,57,二、链式存储,带行指针向量的单链表表示法 十字链表表示法 循环十字链表表示法,2020/9/13,zhengzhihua,58,1.带行指针向量的单链表,指向该行的下一个非零元,2020/9/13,zhengzhihua,59,2. 十字链表表示,2020/9/13,zhengzhihua,60,2. 十字链

13、表,稀疏矩阵的每一行用一个单链表表示 稀疏矩阵的每一列用一个单链表表示,非零元结点,2020/9/13,zhengzhihua,61,2. 十字链表,2020/9/13,zhengzhihua,62,2. 十字链表,1 1 5,2 -3 ,4 9 ,1 4 ,3 4,2 2 -3 ,1 1 5,4 1 4 ,1 4 7 ,head,1,2020/9/13,zhengzhihua,64,十字链表的结点结构,typedef struct OLNode int i, j; elemtype e; struct OLNode *ringht, *down; OLNode, *OLink;,typede

14、f struct OLink *chead, *rhead; int mu, nu, tu ; Crosslist;,1,3 4,2 2 -3 ,1 1 5,1 4 7 ,head,2,typedef struct OLnode int i, j; struct OLnode *right,*down; union int e ; struct OLnode *next; tag; OLnode, *Olink;,十字链表的结点结构,2,3 4,2 2 -3 ,1 1 5,1 4 7 ,head,3,3.循环十字链表,稀疏矩阵的十字链表,十字链表的创建,CreatSNatrix-OL( Cro

15、sslist ,3 4,2 2 -3 ,1 1 5,4 1 4 ,1 4 7 ,head,1,2020/9/13,zhengzhihua,71,2020/9/13,zhengzhihua,72,scanf( ,在行中插入结点,2020/9/13,zhengzhihua,73,5.4 广义表的定义,广义表是线性表的推广。 它是n(n0 )个数据元素d1，d2，dn的有限序列。其中di(1in)可以是单个数据元素(原子)，也可以是一个广义表（子表）。 记为 LS=(d1,d2,dn)， 其中 LS为广义表的名字 ， n为广义表的长度，,2020/9/13,zhengzhihua,74,1. 定义,

16、一个长度为 n (n0 )的广义表定义为 Lists = ( D, R ) D =di | i=1,2n , n0 且diD0或dilists R= LR LR=| di-1, di D0 , 2in,若di 是单个数据元素，则称为是广义表LS的单元素（原子)，若di 是一个广义表，则称为是广义表LS的子表。 当广义表LS非空时，称第一个元素为表头（head）,称其余元素组成的表（ d2，d3，dn ）为表尾（Tail）。,注,2020/9/13,zhengzhihua,75,2. 广义表的表示,广义表通常用（）括起来，用“，”分割其元素；规定用小写字母表示原子,用大写字母表示广义表。,202

17、0/9/13,zhengzhihua,76,举例,（1）A=( )，A为空表，长度为0。 （2）B=(a,（b,c）)，B是长度为2,第一项为原子, 第二项为子表。 （3）C=(x,y,z)，C是长度为3，每一项都是原子。 （4）D=(B,C)，D是长度为2，每一项都是子表。 （5）E=(a,E)，是长度为2的广义表，第一项为原子，第二项为它本身。 注（）和 （）不同,2020/9/13,zhengzhihua,77,广义表的深度,一个广义表的深度是指该广义表展开后所含括号的层数。 举例 （1）A=( )，n=0 ， GetHead(A)=()为空表 ,深度为1。 （2）B=(e) n=1 ，

18、 GetHead(B)=e为原子,GetTail(B)=()为空表, 深度为1。 （3）C=(a,(b,c,d)，长度为2，深度为2 GetHead(C)=a为原子，GetTail(C)=(b,c,d), （4）D=(A,B,C)， D是长度为3，深度为3 GetHead(D)=A为子表, GetTail(D)=(B,C) , D=( ), (e), (a,(b,c,d),2020/9/13,zhengzhihua,78,5.5 广义表的存储结构,方法1. 原子和子表结点表示 方法2. 共享结构表示,2020/9/13,zhengzhihua,79,通常采用头、尾指针的链表结构,表结点: 原子

19、结点：,方法1. 原子和子表结点表示,tag是标志域，tag=0，则表示为原子, tag=1，则表示为子表，,2020/9/13,zhengzhihua,80,type struct GLnode int tag ; union char data ; struct struct GLnode *ht , *tp ; prt; ; *GList;,结点结构,2020/9/13,zhengzhihua,81,表头、表尾分析法：,构造存储结构的两种分析方法:,若表头为原子，则为,空表 ls=NIL,非空表 ls,tag=1,指向表头的指针,指向表尾的指针,tag=0 data,否则，依次类推。,2

20、020/9/13,zhengzhihua,82,2020/9/13,zhengzhihua,83,L = ( a, ( x, y ), ( ( x ) ) ),a,( x, y ),( ),1,L,L = ( ),1,1,1,1,0 x,( ),x,2020/9/13,zhengzhihua,84,例如:,a (x, y) (x),LS=( a, (x,y), (x) ),ls,2020/9/13,zhengzhihua,85,例如，设L=(a,b) A=(x,L)=(x,(a,b) B=(A,y)=(x,(a,b),y) C=(A,B)=(x,(a,b),(x,(a,b),y),2020/9

21、/13,zhengzhihua,86,结点结构,方法2. 共享结构表示,原子结点 表结点，,typedef struct GLnode int tag ; struct GLnode *next ; union char data ; struct GLnode *sublist; val ; GLnode, *GList;,2020/9/13,zhengzhihua,87,L = ( a, ( x, y ), ( ( x ) ) ),a,( x, y ),( ),0 a,L,L = ( ),1,1,1,0 x,( ),x,1,2020/9/13,zhengzhihua,88,5.6 广义表的

22、运算,创建广义表 根据字符串S建立相应的广义表 递归定义如下： 基本项 置空广义表 当S为空表时 建原子结点的子表 当S为单字符串时,typedef struct GLnode int tag ; struct GLnode *next ; union char data ; struct GLnode *sublist; val ; GLnode, *GList;,2020/9/13,zhengzhihua,89,算法,S= () 表空 S=(a1,a2,an) 有n个子表 每个ai由三种情况 带括号的空串（）-置空广义表Null 长度为1的原子 e -建立原子结点的子表 长度1的字串S 设

23、sub为脱去S 中最外层括号的子串，设为s1,s2,sn,其中si为非空字串，对每一个si建立一个表结点，并令其hp域的指针为由si建立的子表的头指针，除最后建立的表结点的尾指针为null外，其余表结点的尾指针均指向在它之后建立的表结点。,GCreat(GLnode *gh) ch=getchar( ); if ( ch!= ) gh=(GLnode*)malloc(sizeof(GLnode); if (ch=( ) gh-tag=1; GCreat(gh-val.sublist); else gh-tag=0; gh-val.data=ch; else gh=null; ch=getcha

24、r(); if (gh!=null) if (ch=,) GCreat(gh-next) else gh-next=null; ,A= ( (a,b), c),2求广义表的深度depth(LS) 假设广义表以刚才的单链表表示法作存储结构，则它的深度可以递归求出。即广义表的深度等于它的所有子表的最大深度加1，设dep表示任一子表的深度，max表示所有子表中表的最大深度，则广义表的深度为：depth=max+1，算法描述如下： int depth(struct node1 *LS) int max=0,dep; while(LS!=NULL) if(LS-atom=0) /有子表 dep=dept

25、h(LS-ds.slink); if(depmax) max=dep; LS=LS-link; return max+1; 该算法的时间复杂度为O(n)。,本章小结 1多维数组在计算机中有两种存放形式：行优先和列优先。 2行优先规则是左边下标变化最慢，右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。 3列优先规则是右边下标变化最慢，左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。 4对称矩阵关于主对角线对称。为节省存储单元，可以进行压缩存储，对角线以上的元素和对角线以下的元素可以共用存储单元，故nn的对称矩阵只需 个存储单元即可。 5三角矩阵有上三角矩阵和下三角矩阵之分，为节省内存单元，可以采用压缩存储，nn的三角矩阵进行压缩存储时，只需+1个存储单元即可。 6稀疏矩阵的非零元排列无任何规律，为节省内存单元，进行压缩存储时，可以采用三元组表示方法，即存储非零元素的行号、列号和值。若干个非零元有若干个三元组，若干个三元组称为三元组表。 7广义表为线性表的推广，里面的元素可以为原子，也可以为子表，故广义表的存储采用动态链表较方便。,1按行优先存储方式，写出三维数组A324在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内