计算机基础综合PPT课件之数据结构-数组与广义表.ppt

《计算机基础综合PPT课件之数据结构-数组与广义表.ppt》由会员分享，可在线阅读，更多相关《计算机基础综合PPT课件之数据结构-数组与广义表.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第五章 数组与广义表 本章要点本章要点深入掌握数组的相关概念深入掌握数组的相关概念,数组元素顺序存数组元素顺序存储位置的计算方法储位置的计算方法掌握对特殊矩阵进行压缩时的下标变换公掌握对特殊矩阵进行压缩时的下标变换公式式.了解稀疏矩阵的压缩存储方法了解稀疏矩阵的压缩存储方法掌握广义表的结构特点及其存储表示方法掌握广义表的结构特点及其存储表示方法数组的定义数组的定义数组的定义方式数组的定义方式1一个一个n维数组类型可以定义为其数组元素为维数组类型可以定义为其数组元素为n-1维数组的一维数组类型维数组的一维数组类型.当当n=1时时,n维数组就退化为定长的线性表，每维数组就退化为定长的线性表

2、，每个元素不可再分解。个元素不可再分解。数组的定义（数组的定义（2）数组定义方式数组定义方式2（抽象数据类型数组）（抽象数据类型数组）ADT Array 数据对象：数据对象：ji=0,1,bi-1,i=1,2,3,n.D=aj1j2jn|n(0)称为数组维数，称为数组维数，bi是数组第是数组第i维的长度，维的长度，ji是数组元素的第是数组元素的第i维下标，维下标，aj1j1jn ElemSet 数据关系：数据关系：R=R1，R2，,Rn Ri=|0 jk bk-1,1 k n,k i,0 jji i b bi i-2,-2,aj1jijn,aj1ji+1jn D,i=2,n数组的定义（数组的定

3、义（3）基本操作基本操作:InitArray(&A,n,bound1,boundn)/构造数构造数组组A,维数维数n,各维长度各维长度bound1,boundn DestroyArray(&A)/销毁数组销毁数组A Value(A,&e,index1,indexn)/将指定的将指定的A元素赋给元素赋给e Assign(&A,e,index1,indexn)/将将e的值赋给所指定的的值赋给所指定的A的元素的元素 ADT Array数组的顺序存储数组的顺序存储二维数组二维数组Am n元素元素aij,0 i m-1,0 j n-1存储结构存储结构以行序为主序以行序为主序 Loc(i,j)=Loc(0

4、,0)+(n*i+j)L L以列序为主序以列序为主序 Loc(i,j)=Loc(0,0)+(m*j+i)L Ln n维数组的数据元素存储地址维数组的数据元素存储地址(以第一维优先存储以第一维优先存储)Loc(j Loc(j1 1,j,j2 2,j jn n)=Loc(0,0,)=Loc(0,0,)+(b)+(b2 2 b bn n j j1 1+b b3 3 b bn n j j2 2+b+bn n j jn-1n-1+j+jn n)L L 矩阵矩阵的存储矩阵的存储特殊矩阵特殊矩阵矩阵中的元素排列是有规律的矩阵中的元素排列是有规律的矩阵的非零元素很少矩阵的非零元素很少压缩存储压缩存储为多个值相

5、同的元素只分配一个存储空间为多个值相同的元素只分配一个存储空间对零元素不分配空间对零元素不分配空间对称矩阵示例对称矩阵示例对称矩阵对称矩阵性质性质:在在n阶矩阵阶矩阵A中中,aij=aji,1 i,j n压缩存储压缩存储:只存主对角线只存主对角线以上或以下以上或以下元素元素(包括主对角线包括主对角线)。可用一维数组存储。可用一维数组存储。减少存储空间减少存储空间:n2-n(n+1)/2下三角元素下三角元素aij,(i j)与一维数组与一维数组Sak(1 k n)元素的对应元素的对应关系关系 k=i(i-1)/2+j-1上三角元素上三角元素aij,(i j)与一维数组与一维数组Sak元素的对应关

6、系元素的对应关系 k=j(j-1)/2+i-1Sa下标下标 k=0 1 2 3 4 n(n+1)/2-2 n(n+1)/2-1 a00a10a11a20a21an-1,n-3an-1,n-2an-1,n-1对角矩阵对角矩阵性质性质:一个一个n阶方阵的所阶方阵的所有非零元素都集中在以有非零元素都集中在以主对角为中心的带状区主对角为中心的带状区域中域中压缩存储压缩存储:将非零元素存将非零元素存储到一维数组中储到一维数组中稀疏矩阵稀疏矩阵性质性质:矩阵中大多数元素值为矩阵中大多数元素值为0,元素分布没有一定元素分布没有一定规律规律.设在设在m n矩阵中矩阵中,有有t个元素不为零个元素不为零,稀疏因子

7、为稀疏因子为:=t/(m n)n)0.05时时,称为稀疏矩阵称为稀疏矩阵压缩存储方式压缩存储方式:三元组顺序存储三元组顺序存储链表存储链表存储稀疏矩阵示例稀疏矩阵示例三元组顺序表三元组顺序表形式描述形式描述:(i,j,aij)存储表示存储表示#define MAXSIZE 12500 typedef struct int i,j;ElemType e;Triple;三元组顺序表三元组顺序表(2)typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;/矩阵的行数矩阵的行数,列数和非零元个数列数和非零元个数 TSMatrix;存储特点存储特点:非零元在表

8、中按行序有序存储非零元在表中按行序有序存储;最后一行一个元素在最后一行一个元素在data中的序号为中的序号为tu.示例 i j e 1 1 3 1 5 7 2 3 -1 3 1 -1 3 2 -2 5 4 2 A.Data A.mu=5 A.nu=5 A.tu=6A=稀疏矩阵的转置算法稀疏矩阵的转置算法方法方法1：按列序递增转置法：按列序递增转置法 算法的基本思想是：按照被转置矩阵算法的基本思想是：按照被转置矩阵M的的“列序列序”（即转置后（即转置后T的行序）递增的顺序的行序）递增的顺序进行转置，并依次送入转置后矩阵的三元组进行转置，并依次送入转置后矩阵的三元组表中，则转置后矩阵的三元组表恰好

9、是以表中，则转置后矩阵的三元组表恰好是以“行序为主序行序为主序”Status TransposeSMaxtrix(TSMatrix M,TSMaxtrix&T)/求求M的转置矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.Tu;if(T.tu)q=1;/q为为T.data数组下标数组下标,从从1开始开始 for(col=1;col=M.nu;+col)/按按M.data的列读取的列读取 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.d

10、ataq.e=M.datap.e;+q;return OK;算法的复杂度为算法的复杂度为O(M.nuM.mu)方法方法2 2：快速转置算法：快速转置算法 需要设需要设num和和cpot两个数组。两个数组。numcol表示矩阵表示矩阵M中第中第col列的非零元素个列的非零元素个数；数；数组数组cpotcol表示矩阵表示矩阵M第第col列中第一个非列中第一个非零元素在零元素在T.data中恰当的存储位置。中恰当的存储位置。存在下列公式：存在下列公式：void FastTransposeSMatrix (TSMatrix M,TSMaxtrix&T)/求求M的转置矩阵的转置矩阵TT.mu=M.nu;

11、T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;colM.nu;+col)numcol=0;for(t=1;tM.tu;t+)numM.datat.j+;/统计统计M中每一列含非零元个数中每一列含非零元个数 cpot1=1;/求第求第col列中第一个非列中第一个非零元在零元在T.data中的序号中的序号 for(col=2;colM.nu;+col)cpotcol=cpotcol-1 +numcol-1;for(p=1;p M.tu;+p)col=M.datap.j;/取取M.data的列号存放到的列号存放到col中中 q=cpotcol;/q为为T中当前存储位置中

12、当前存储位置 T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;cpotcol=cpotcol+1;/计算第计算第col列中下一个非零元素列中下一个非零元素存储位置存储位置 /for /if时间复杂度为时间复杂度为O(M.nu+M.tu)行逻辑链接的顺序表行逻辑链接的顺序表目的目的:便于随机存储任意一行的非零元素便于随机存储任意一行的非零元素存储表示存储表示增加一个增加一个“行行”信息的辅助数组信息的辅助数组rpos typedef struct Triple dataMAXSIZE+1;/三元组表三元组表 int rpos

13、MAXRC+1;/各行第一个非零元素的位置数组各行第一个非零元素的位置数组 int mu,nu,tu;/矩阵的行数矩阵的行数,列数和非零元个数列数和非零元个数 RLSMatrix;问题问题:rposrow rposrow+1-1 分别代表什么分别代表什么?两个稀疏矩阵相乘求：求：Q=AB初始化初始化Q /Q.mu=A.mu;Q.nu=B.nu;Q.tu=0;If(A.tu*B.tu!=0)/逐行求积和逐行求积和 for(arow=1;arow=A.mu;+arow)ctemp1B.nu=0;计算计算Q中第中第arow行的积和并存入行的积和并存入ctemp 中中 将将ctemp 中非零元素压缩到

14、中非零元素压缩到Q.data中中 两个稀疏矩阵相乘两个稀疏矩阵相乘采用行逻辑连接的顺序表存储稀疏矩阵采用行逻辑连接的顺序表存储稀疏矩阵A和和B(1)对对A.data1A.tu中的每一元素中的每一元素(i,k,A(i,k)(1im1,1jn1)，找到，找到B.data中所有对应的元中所有对应的元素素(k,j,B(k,j)(1im2,1jn2)相乘并求累计和，相乘并求累计和，即关键要找到所有满足即关键要找到所有满足:A.datap.j=B.dataq.i的元素。的元素。(2)两个稀疏矩阵相乘的乘积不一定是稀疏矩阵，两个稀疏矩阵相乘的乘积不一定是稀疏矩阵，乘积矩阵乘积矩阵Q中的元素是否为非零元素，只

15、有在中的元素是否为非零元素，只有在求得其累加和后才能得到求得其累加和后才能得到。两个稀疏矩阵相乘的详细算法两个稀疏矩阵相乘的详细算法 Status MultSMatrix(RLSMatrix A,RLSMatrix B,RLSMatrix Q)/求求QAB If(A.nu!=B.mu)return ERROR;Q.mu=A.mu;Q.nu=B.nu;Q.tu=0;/初始化初始化Q if(A.tu*B.tu!=0)for(arow=1;arrow=A.mu;+arow)/处理处理A的每一行的每一行 ctemp=0;/当前行各元素累加器清零当前行各元素累加器清零 Q.rposarow=Q.tu+1

16、;/计算当前行第一个非零元素计算当前行第一个非零元素 的位置的位置 if(arowA.mu)ca=A.rposarow+1;/ca为为A的下一行第一个非的下一行第一个非 零元素的位置零元素的位置 else ca=A.tu+1;/当前行为最后一行当前行为最后一行 详细算法（详细算法（2）for(p=A.rposarow;pca;+p)/对当前行的每一非零元素对当前行的每一非零元素 brow=A.datap.j;/找到对应元素在找到对应元素在B中的行号中的行号 if(browB.mu)cb=B.rposbrow+1;/cb为为B的下一行第一个非的下一行第一个非 零元素的位置零元素的位置 else

17、cb=B.tu+1;/brow为为B的最后一行的最后一行 for(q=B.rposbrow;qcb;+q)ccol=B.dataq.j;/乘积元素在乘积元素在Q中列号中列号 ctempccol=ctempccol+A.datap.e*B.dataq.e;/for q /for p详细算法（详细算法（3）for(ccol=1;ccolMAXISIZE)return ERROR;Q.dataQ.tu=(arow,ccol,ctempccol);/if /for arow /if return OK;链式存储结构链式存储结构带行指针向量的单链表表示法带行指针向量的单链表表示法每行的非每行的非0元素链

18、成一个单链表元素链成一个单链表每行的头指针组成一个表头指针数组每行的头指针组成一个表头指针数组链式存储结构（链式存储结构（2）十字链表表示法十字链表表示法在链表中每个非在链表中每个非0元素用一个含元素用一个含5个域的结点表示个域的结点表示.每行的头指针组成一个一维数组每行的头指针组成一个一维数组每列的头指针组成一个一维数组每列的头指针组成一个一维数组十字链表的结点结构十字链表的结点结构 i j e down right1 3 2 42856-534723521-1A.cheadA.rhead 链式存储结构链式存储结构(3)十字链表存储表示十字链表存储表示 typedef struct OLNo

19、de int i,j;Elemtype e;struct OLNode*right,*down;OLNode,*Olink;typedef struct Olink*rhead,*chead;int mu,nu,tu;CrossList;稀疏矩阵十字链表的创建稀疏矩阵十字链表的创建void CreateSMatrix_OL(CrossList&A)/创建稀疏矩阵创建稀疏矩阵A if(A)free(A);scanf(&m,&n,&t);/输入输入A的行数、列数和非零元素个数的行数、列数和非零元素个数 A.mu=m;A.nu=n;A.tu=t;if(!(A.rhead=(OLink*)malloc

20、(m+1)*sizeof(OLNode)exit(OVERFLOW);if(!(A.chead=(OLink*)malloc(n+1)*sizeof(OLNode)exit(OVERFLOW);A.rhead=A.chead=NULL;/初始化行、列头指针向量初始化行、列头指针向量 for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)/按任意顺序输入非零元素，按任意顺序输入非零元素，i为零时输入结束为零时输入结束 if(!(p=(OLNode*)malloc(sizeof(OLNode)exit(OVERFLOW);p-i=i;p-j=j;p-e=e;/生成结点生成

21、结点 稀疏矩阵十字链表的创建稀疏矩阵十字链表的创建if(A.rheadi=NULL|A.rheadi-jj)p-right=A.rheadi;A.rheadi=p;else for(q=A.rheadi;(q-right)&q-right-jright);/在行表中查找插入位置在行表中查找插入位置 p-right=q-right;q-right=p;/完成行插入完成行插入 if(A.cheadj=NULL|A.cheadj-ii)p-down=A.cheadj;A.cheadj=p;else for(q=A.cheadj;(q-down)&q-down-idown);/在列表中查找插入位置在列

22、表中查找插入位置 p-down=q-down;q-down=p;/完成列插入完成列插入 广义表的定义广义表的定义LS=(a1,a2,an)其中其中:ai是单个数据元素是单个数据元素(或称为原子或称为原子)或仍然是或仍然是一个广义表一个广义表(或称子表或称子表).n是其长度是其长度.括号的层数为深度括号的层数为深度.对于非空表对于非空表,a1是表头是表头,(a2,a3an)是表尾是表尾例如例如:A=()B=(a,b)C=(a,b),c)D=(A,B,C)=(),(a,b),(a,b),c)E=(a,E)=(a,(a,(a,.)F=(A)=()广义表的抽象数据类型定义广义表的抽象数据类型定义ADT

23、 GList 数据对象：数据对象：D=ei|i=1,2,n;n0;ei AtomSet 或或ei GList,AtomSet为某个数据对象为某个数据对象 数据关系：数据关系：R=|ei-1,ei D,2in 基本操作：基本操作：InitGList(&L);/创建空的广义链表创建空的广义链表L CreateGList(&L,S);/由串由串S创建广义表创建广义表L DestroyGList(&L);/销毁广义表销毁广义表L CopyGList(&T,L);/由广义表由广义表L复制得到广义表复制得到广义表T GListLength(L);/求广义表的求广义表的L的长度，即元素个数的长度，即元素个数

24、 GListDepth(L);/求广义表求广义表L的深度的深度 广义表的抽象数据类型定义广义表的抽象数据类型定义GListEmpty(L);/判定广义表判定广义表L是否为空是否为空 GetHead(L);/取广义表取广义表L的头的头 GetTail(L);/取广义表取广义表L的尾的尾 InsertFirst_GL(&L,e);/插入元素插入元素e作为广义表作为广义表L的的 第一个元素第一个元素 DeleteFirst_GL(&L,&e);/删除广义表删除广义表L的第一个元的第一个元素素 Traverse_GL(L,Visit();/遍历广义表遍历广义表L，用，用Visit处处理理 每一个元素每

25、一个元素 ADT GList广义表常用操作广义表常用操作GLIstDepth(L):求广义表的深度求广义表的深度GetHead(L):取广义表的头取广义表的头GetTail(L):取广义表的尾取广义表的尾例例:LS=(a,(b,c),(a,(d),e)GListDepth(LS)=2+1=3 GetHead(LS)=a GetTail(LS)=(b,c),(a,(d),e)广义表的存储结构广义表的存储结构方式一方式一:Typedef enumATOM,LIST ElemTag;Typedef struct GLNode ElemTag tag;Union AtomType atom;struc

26、t struct GLNode*hp,*tp;ptr;/表头表尾指针表头表尾指针 ;*Glist;tag=1hp tp tag=0atom 表结点表结点 原子结点原子结点 例：例：A=（）表示广义表（）表示广义表A是一个空表是一个空表 B=(a，b)C=(B,c)=(a，b)，c)D=(A，B，C)=(（），（），(a，b)，(a，b)，c)E=(a，E)=(a，(a，(a，)F=(A)=(（）（）)A=NILBCDE0 a11 1 1 1 11 11 0 c0 a0 b广义表的存储结构广义表的存储结构(2)方式二方式二:Typedef enumATOM,LIST ElemTag;Typedef struct GLNode ElemTag tag;Union AtomType atom;struct GLNode*hp;/表头指针表头指针 ;struct GLNode*tp;/指向下一个元素结点指针指向下一个元素结点指针*Glist;tag=1hp tp tag=0atom tp (a)表结点表结点 (b)原子结点原子结点 作业作业5.1,5.6,5.10,5.11(2)(4)(6),5.12,5.13,5.21*