《第五章数组和广义表优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第五章数组和广义表优秀PPT.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章数组和广义表第一页，本课件共有57页学习提要：学习提要：1.了了解解数数组组的的两两种种存存储储表表示示方方法法，并并掌掌握握数数组组在以行为主的存储结构中的地址计算方法。在以行为主的存储结构中的地址计算方法。2.掌掌握握对对特特殊殊矩矩阵阵进进行行压压缩缩存存储储时时的的下下标标变变换公式。换公式。3.了了解解稀稀疏疏矩矩阵阵的的两两种种压压缩缩存存储储方方法法的的特特点点和和适适用用范范围围，领领会会以以三三元元组组表表示示稀稀疏疏矩矩阵阵时时进进行行矩阵运算采用的处理方法。矩阵运算采用的处理方法。4.掌握广义表的结构特点及其存储表示方法。掌握广义表的结构特点及其存储表示方法。第二页
2、，本课件共有57页ADTArray 数据对象数据对象：Daj1,j2,.,ji,jn|ji=0,.,bi-1,i=1,2,.,n 数据关系数据关系：RR1,R2,.,Rn Ri|0 jk bk-1,1 k n 且k i,0 ji bi-2,i=2,.,n ADT Array 基本操作基本操作:5.1数组的类型定义数组的类型定义第三页，本课件共有57页基本操作基本操作：InitArray(&A,n,bound1,.,boundn)DestroyArray(&A)Value(A,&e,index1,.,indexn)Assign(&A,e,index1,.,indexn)第四页，本课件共有57页I
3、nitArray(&A,n,bound1,.,boundn)操作结果：操作结果：若维数若维数n和各维长度合法，和各维长度合法，则构造相应的数组则构造相应的数组A，并，并返回返回OK。DestroyArray(&A)操作结果：操作结果：销毁数组销毁数组A。第五页，本课件共有57页Value(A,&e,index1,.,indexn)初始条件：初始条件：A是是n维数组，维数组，e为元素变量，为元素变量，随后是随后是n个下标值。个下标值。操作结果：操作结果：若各下标不超界，则若各下标不超界，则e赋值为赋值为所指定的所指定的A的元素值，并返的元素值，并返回回OK。第六页，本课件共有57页Assign(
4、&A,e,index1,.,indexn)初始条件：初始条件：A是是n维数组，维数组，e为元素为元素变量，随后是变量，随后是n个下标值。个下标值。操作结果：操作结果：若下标不超界，则将若下标不超界，则将e的的值赋给所指定的值赋给所指定的A的元的元素，并返素，并返OK。第七页，本课件共有57页二维数组的定义二维数组的定义:数据对象数据对象:D=aij|0ib1-1,0 jb2-1数据关系数据关系:R=ROW,COL ROW=|0ib1-2,0jb2-1 COL=|0ib1-1,0 jb2-2第八页，本课件共有57页二维数组的定义二维数组的定义:第九页，本课件共有57页5.2数组的顺序表示和实现数
5、组的顺序表示和实现类型特点类型特点:（1）只有引用型操作，没有加工型操作；只有引用型操作，没有加工型操作；（2）数组是多维的结构，而存储空间是数组是多维的结构，而存储空间是一个一维的结构。一个一维的结构。有两种顺序映象的方式有两种顺序映象的方式:（1）以行序为主序以行序为主序（2）以列序为主序以列序为主序第十页，本课件共有57页a00a01a0n-1a10a11a1n-1am-10am-11am-1n-1.按行序为主序存放按行序为主序存放 am-1n-1 .am-11 am-10 .a1n-1 .a11 a10 a0n-1 .a01 a0001n-1m*n-1nLOC(i,j)=LOC(0,0
6、)+(nij)L第十一页，本课件共有57页按列序为主序存放按列序为主序存放01m-1m*n-1m am-1n-1 .a1n-1 a0n-1 .am-11 .a11 a01 am-10 .a10 a00a00a01.a0n-1a10a11.a1n-1am-10am-11am-1n-1.LOC(i,j)=LOC(0,0)+(mji)L第十二页，本课件共有57页称为基地址基地址或基址以以“行序为主序行序为主序”的存储映象的存储映象:二维数组二维数组A中任一元素中任一元素ai,j的存储位置的存储位置LOC(i,j)=LOC(0,0)+(nij)L以以“列序为主序列序为主序”的存储映象的存储映象:二维数
7、组二维数组A中任一元素中任一元素ai,j的存储位置的存储位置LOC(i,j)=LOC(0,0)+(mji)L第十三页，本课件共有57页推广到一般情况，可得到推广到一般情况，可得到n维数组维数组数据数据元素存储位置的映象关系元素存储位置的映象关系称为称为n维数组的映象函数。维数组的映象函数。数组元素数组元素的存储位置是其下标的线性函数的存储位置是其下标的线性函数。其中其中cn=L，ci-1=bici,1i n。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+ci ji i=1n第十四页，本课件共有57页5.3.1特殊矩阵特殊矩阵5.3矩阵的压缩存储矩阵的压缩存储5.3.2稀疏矩阵稀疏矩
8、阵第十五页，本课件共有57页第十六页，本课件共有57页以常规方法，即以二维数组表示以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的高阶的稀疏矩阵时产生的问题问题:(1)零值元素占了很大空间零值元素占了很大空间;(2)计算中进行了很多和零值的运算。计算中进行了很多和零值的运算。第十七页，本课件共有57页(1)尽可能少存或不存零值元素；尽可能少存或不存零值元素；解决问题的原则解决问题的原则:(2)尽可能减少没有实际意义的运算；尽可能减少没有实际意义的运算；(3)操作方便。操作方便。即：即：能尽可能快地找到与下标值能尽可能快地找到与下标值(i，j)对应对应的元素，的元素，能尽可能快地找到同一行或同
9、一列的能尽可能快地找到同一行或同一列的非零值元。非零值元。第十八页，本课件共有57页5.3.1特殊矩阵特殊矩阵 特殊矩阵是指非零元素或零元素的分特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。布有一定规律的矩阵。对称矩阵对称矩阵元素满足条件元素满足条件aij=aji1=i,j=n的的n阶矩阵。阶矩阵。第十九页，本课件共有57页按行序为主序：按行序为主序：a11a12.a1na21a22.a2nan1an2.ann.a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 第二十页，本课件共有57页三角矩阵三角矩阵按行序为主序：按
10、行序为主序：Loc(aij)=Loc(a11)+i*(i-1)/2+(j-1)*La1100.0a21a220.0an1an2an3.ann.0a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 第二十一页，本课件共有57页v对角矩阵对角矩阵a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1ann0a32a33a3400Loc(aij)=Loc(a11)+2(i-1)+(j-1)按行序为主序：按行序为主序：a11 a12 a21 a22 a23 ann-1 ann.k=0
11、1 2 3 4 n(n+1)/2-1 第二十二页，本课件共有57页5.3.2稀疏矩阵稀疏矩阵假设假设m行行n列列的矩阵含的矩阵含t个非零个非零元素元素，则称，则称为为稀疏因子稀疏因子。通常认为通常认为 0.05的矩阵为稀的矩阵为稀疏矩阵。疏矩阵。第二十三页，本课件共有57页稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑链接的顺序表二、行逻辑链接的顺序表三、三、十字链表十字链表第二十四页，本课件共有57页#define MAXSIZE 12500 typedefstructint i,j;/该非零元的行下标和列下标 ElemType e;/该非零元的值
12、Triple;/三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedefunion Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;/稀疏矩阵类型稀疏矩阵类型第二十五页，本课件共有57页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 i j e0 1 2 3 4 5 6 7 8第二十六页，本课件共有57页T如如何何求求转转置置矩矩阵阵？第二十七页，本课件共有57页用常规的二维数组表示时的算法其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+co
13、l)for(row=1;row=mu;+row)Tcolrow=Mrowcol;第二十八页，本课件共有57页678121213931-3361443245218611564-7ije0 1 2 3 4 5 6 7 8ije76813-3161521122518319342446-763140 1 2 3 4 5 6 7 8?M.dataT.data第二十九页，本课件共有57页解决思路：解决思路：只要做到只要做到将矩阵行、列值互换；将矩阵行、列值互换；将每个三元组中的将每个三元组中的i和和j相互调换；相互调换；重排三元组次序，使重排三元组次序，使T.data中元中元素以素以N的行的行(M的列的列
14、)为主序为主序第三十页，本课件共有57页方法一：按方法一：按M的列序转置的列序转置按按T.data中三元组次序依次在中三元组次序依次在M.data中找到相应的三元组进行转置，中找到相应的三元组进行转置，即按照矩阵即按照矩阵M的列序的列序来进行置换。来进行置换。为找到为找到M中每一列所有非零元素，中每一列所有非零元素，需对其三元组表需对其三元组表M.data从第一行起扫描从第一行起扫描一遍。由于一遍。由于M.data中以中以M行序为主序，行序为主序，所以由此得到的恰是所以由此得到的恰是T.data中应有的顺中应有的顺序序。第三十一页，本课件共有57页678121213931-3361443245
15、218611564-7i j e0 1 2 3 4 5 6 7 8M.data76813-3161521122518319342446-76314ije0 1 2 3 4 5 6 7 8T.dataqppppppppqqqqppppppppcol=1col=2第三十二页，本课件共有57页StatusTransposeSMatix(TSMatrixM,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵采用三元组表存储表示，求稀疏矩阵M的转置矩阵的转置矩阵T。T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;If(T.tu)q=1;for(col=1;col=M.nu;+col)f
16、or(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;returnOK;/TransposeSMatrixT(n)=O(nu*tu)第三十三页，本课件共有57页方法二：快速转置方法二：快速转置按按M.data中三元组次序转置，转置结果放中三元组次序转置，转置结果放入入T.data中恰当位置。中恰当位置。此法关键是要预先确定此法关键是要预先确定M中每一列第一个中每一列第一个非零元在非零元在T.data中位置，为确定这些位置，转中位置，为确定这些位置，转置前应
17、先求得置前应先求得M的每一列中非零元个数。的每一列中非零元个数。实现：实现：设两个数组设两个数组numcol：表示矩阵：表示矩阵M中第中第col列中非零元个数列中非零元个数cpotcol：指示指示M中第中第col列第一个非零元在列第一个非零元在T.data中位置中位置显然有：显然有：cpot1=1;cpotcol=cpotcol-1+numcol-1;(2 col M.nu)第三十四页，本课件共有57页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 i j e0 1 2 3 4 5 6 7 8M.datai j e0 1
18、 2 3 4 5 6 7 8T.datacolnumcolcpotcol1122323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753第三十五页，本课件共有57页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 i j e0 1 2 3 4 5 6 7 8for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1
19、=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1 +numcol-1;Col1234567Numcolcpotcolt1t1t1t1t2t2t2t10 01357889第三十六页，本课件共有57页Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+c
20、ol)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)/转置矩阵元素 col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;/for /if return OK;/FastTransposeSMatrixT(n)=O(nu+tu)T(n)=O(mu*nu)第三十七页，本课件共有57页三元组顺序表又称三元组顺序表又称有序的双下有序的双下标法标法，它的特点是，非零元在表中，它的特点是，非零元在表中按行序有序存储，因此按行序有序
21、存储，因此便于进行依便于进行依行顺序处理的矩阵运算行顺序处理的矩阵运算。然而，若。然而，若需需随机随机存取某一行中的非零元，则存取某一行中的非零元，则需从头开始进行查找。需从头开始进行查找。第三十八页，本课件共有57页#define MAXMN 500 typedefstruct Triple dataMAXSIZE+1;/非零元三元组表 intrposMAXMN+1;/各行第一个非零元的位置表各行第一个非零元的位置表 int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型二、行逻辑链接的顺序表二、行逻辑链接的顺序表第三十九页，本课件共有57页M=N=Q=Q=MN第四十页，本课件
22、共有57页113145 i j e1 2 3 4 31222-1M.data122211 i j e1 2 3 4 32431-2N.data21-1 i j e1 2 3 4 Q.dataparow 1 2 3 ropsarow 134brow 1 2 3 4ropsbrow 1235ccol 1 2ctempt1tpq6p126tpp2tq-1tp=5p1tq4324第四十一页，本课件共有57页三、三、十字链表十字链表3 0 0 50-1 0 02 0 0 011314522-1312 第四十二页，本课件共有57页Type struct OLNodeType struct OLNode i
23、nt i,j;int i,j;int e;int e;struct OLNode*right,*down;struct OLNode*right,*down;OLNode;*OLink;OLNode;*OLink;Type struct Type struct OLink *rhead,*chead;OLink *rhead,*chead;int mu,nu,tu;int mu,nu,tu;CrossList;CrossList;第四十三页，本课件共有57页5.4广义表的类型定义广义表的类型定义ADTGlist 数据对象数据对象：Dei|i=1,2,.,n;n0;eiAtomSet 或 eiG
24、List,AtomSet为某个数据对象 数据关系：数据关系：LR|ei-1,eiD,2inADT Glist基本操作基本操作:第四十四页，本课件共有57页广义表是广义表是递归递归定义的定义的线性结构线性结构，LS=(1,2,n)其中：其中：i或为原子或为原子或为广义表或为广义表例如例如:A=()F=(d,(e)D=(a,(b,c),F)C=(A,D,F)B=(a,B)=(a,(a,(a,)第四十五页，本课件共有57页广义表是一个多层次多层次的线性结构线性结构例如：例如：D=(E,F)其中:E=(a,(b,c)F=(d,(e)DEFa()d()bce第四十六页，本课件共有57页广义表广义表LS=
25、(1,2,n)的的结构特点结构特点:1)广义表中的数据元素有相对广义表中的数据元素有相对次序次序；2)广义表的广义表的长度长度定义为最外层包含元素个数；定义为最外层包含元素个数；3)广义表的广义表的深度深度定义为所含括弧的重数；定义为所含括弧的重数；注意：注意：“原子原子”的深度为的深度为0“空表空表”的深度为的深度为14)广义表可以广义表可以共享共享；5)广义表可以是一个广义表可以是一个递归递归的表。的表。递归表的深度是无穷值，长度是有限值递归表的深度是无穷值，长度是有限值。第四十七页，本课件共有57页6)任何一个非空广义表任何一个非空广义表LS=(1,2,n)均可分解为均可分解为表头表头H
26、ead(LS)=1和和表尾表尾Tail(LS)=(2,n)两部分。两部分。例如例如:D=(E,F)=(a,(b,c)，F)Head(D)=E Tail(D)=(F)Head(E)=a Tail(E)=(b,c)Head(b,c)=(b,c)Tail(b,c)=()Head(b,c)=b Tail(b,c)=(c)Head(c)=c Tail(c)=()第四十八页，本课件共有57页 结构的创建和销毁结构的创建和销毁 InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);基基本本操操作作 状态函数状态函数 GListLen
27、gth(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);插入和删除操作插入和删除操作 InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);遍历遍历 Traverse_GL(L,Visit();第四十九页，本课件共有57页5.5 广义表的表示方法广义表的表示方法通常采用头、尾指针的链表结构通常采用头、尾指针的链表结构表结点表结点:原子结点：原子结点：tag=1hptptag=0data第五十页，本课件共有57页（1）表头、表尾分析法：表头、表尾分析法：构造存储结构的两种分析方法构造存储结构的两种分析方法:
28、若表头为原子，则为若表头为原子，则为空表空表 ls=NIL非空表非空表lstag=1指向表头的指针指向表尾的指针tag=0data否则，依次类推。否则，依次类推。第五十一页，本课件共有57页第五十二页，本课件共有57页L=(a,(x,y),(x)a(x,y)()1LL=()0a111110 x ()x第五十三页，本课件共有57页（2）子表分析法：子表分析法：若子表为原子，则为若子表为原子，则为空表空表 ls=NIL非空表非空表指向子表1 的指针tag=0atom否则，依次类推。否则，依次类推。指向子表2 的指针指向子表n 的指针111ls 1 tag=1hptp第五十四页，本课件共有57页例如
29、例如:LS=(a,(x,y),(x)0a11ls10 x0b10 x第五十五页，本课件共有57页第五章 作 业5.1假设有二维数组假设有二维数组A68，每个元素用相邻的，每个元素用相邻的6个字节个字节存储，存储器按字节编址。已知存储，存储器按字节编址。已知A的起始存储位置的起始存储位置（基地址）为（基地址）为1000，计算：，计算：（1）数组）数组A的体积（即存储量）；的体积（即存储量）；（2）数组）数组A的最后一个元素的最后一个元素a57的第一个字节的地址；的第一个字节的地址；（3）按行存储时，元素）按行存储时，元素a14的第一个字节的地址；的第一个字节的地址；（4）按列存储时，元素）按列存储时，元素a47的第一个字节的地址。的第一个字节的地址。第五十六页，本课件共有57页第五章 作 业5.10求下列广义表操作的结果：求下列广义表操作的结果：（1）GetHead(p,h,w);（4）GetTail(a,b),(c,d);（5）GetHead(GetTail(a,b),(c,d)。5.12按教科书按教科书5.5节中图节中图5.8所示结点结构，画出下列广义所示结点结构，画出下列广义表的存储结构图，并求它的深度。表的存储结构图，并求它的深度。（1）(),a,(b,c),(),d),(e)（2(a),b),(),d),(e,f)第五十七页，本课件共有57页