数据结构课件(第5章)数组和广义表.ppt

1、第五章 数组和广义表,信阳师范学院 计算机与信息技术学院,2020/7/28,数据结构 page 2,信阳师范学院计算机与信息技术学院,主要内容,2020/7/28,数据结构 page 3,信阳师范学院计算机与信息技术学院,基本内容： 数组的定义和顺序存储； 矩阵的压缩存储； 广义表。 学习要点： 了解数组的逻辑结构； 掌握以行或列序为主序的方式存储时，数组元素地址的计算方法； 掌握特殊矩阵的压缩存储； 了解广义表。,2020/7/28,数据结构 page 4,信阳师范学院计算机与信息技术学院,（2）每种数据结构中的数据元素，都是原子数据，不再进行分解；,本章讨论三个方面的内容：数组、 矩阵的

2、压缩存储、广义表,本章讨论的两种数据结构：数组和广义表，其共同特点是：1）从逻辑结构上看它们，可看成是线性结构的一种扩展； 2）数据元素本身也是一个数据结构。,前4章介绍的数据结构共同特点：,（1）都属于线性结构；,引言,2020/7/28,数据结构 page 5,信阳师范学院计算机与信息技术学院,数组是由一组个数固定，类型相同的数据元素组成的阵列。,Amn=,在行关系中 aij直接前趋是 aij-1 aij直接后继是 aij+1 在列关系中 aij直接前趋是 ai-1j aij直接后继是 ai+1j,5.1 数组的定义,一维数组的特点：,1个下标，ai的直接前驱是ai-1 ，直接后继是ai+

3、1。,二维数组的特点：,2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：,2020/7/28,数据结构 page 6,信阳师范学院计算机与信息技术学院,N维数组的数据类型定义,ADT ARRAY,Ri = | 0jkbk-1, 1kn 且k i, 0jibi-2, aj1,j2,jijn , aj1,j2,ji+1jn D ,数据关系：R = R1 ,R2，. Rn ,D = aj1,j2jn| n(0)称为数组的维数，bi是数组第i维的长度，ji为数组元素的第i 维下标 ，aj1,j2jn Elemset,构造数组、销毁数组、读数组元素、写数组元素,基本操作：,数据对象：,j

4、i=0, . ,bi-1, i=1,2, . n,2020/7/28,数据结构 page 7,信阳师范学院计算机与信息技术学院,初始化操作 InitArray( Typedef Array1 Array2m;,Typedef elemtype Arraymn;,2020/7/28,数据结构 page 12,信阳师范学院计算机与信息技术学院,用一组连续的存储单元存放数组的数据元素。,二维数组的两种顺序存储方式： （1）行序为主序 （2）列序为主序,例：,5.2 数组的顺序表示和实现,2020/7/28,数据结构 page 13,信阳师范学院计算机与信息技术学院,行序为主序：,数据元素的存储位置：

5、 loc(i,j)=loc(0,0)+aij之前的元素个数L,(i*n+j),2020/7/28,数据结构 page 14,信阳师范学院计算机与信息技术学院,列序为主序：,数据元素的存储位置： loc(i,j)=loc(0,0)+aij之前的元素个数L,j*m+i,2020/7/28,数据结构 page 15,信阳师范学院计算机与信息技术学院,例2：已知二维数组Am,m按行存储的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 请问按列存储的公式相同吗？,答：尽管是方阵，但公式仍不同。应为： Loc(aij)=Loc(a11)+(j-1)*m+(i-1

6、)*K,例1软考题：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。这个数组的体积是 个字节。,288,答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288,2020/7/28,数据结构 page 16,信阳师范学院计算机与信息技术学院,例3 ：设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。,解：根据列优先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K 得：LOC(a32,58)=2048+

7、(58-1)*60+(32-1)*28950,想一想：若数组是a059, 069，结果是否仍为8950？,8950,维界虽未变，但此时的a32,58不再是原来的a32,58,2020/7/28,数据结构 page 17,信阳师范学院计算机与信息技术学院,基本内容 特殊矩阵的压缩存储 ； 稀疏矩阵的压缩存储； 稀疏矩阵在三元组顺序表存储方式下，矩阵的运算的实现。 学习要点 了解矩阵的两种压缩存储方法及适用范围； 了解在三元组顺序表存储方式下，实现矩阵运算的方法。,5.3 矩阵的压缩存储,2020/7/28,数据结构 page 18,信阳师范学院计算机与信息技术学院,对称矩阵是满足下面条件的n 阶

8、矩阵 aij= aji 1 i,j n,1. 特殊矩阵,值相同元素或者零元素分布有一定规律的矩阵称特殊矩阵,例 对称矩阵、 上（下）三角矩阵都是特殊矩阵,2020/7/28,数据结构 page 19,信阳师范学院计算机与信息技术学院,对称矩阵,若ij，则aij在下三角形中。 aij之前的i-1行（从第1行到第i-1） 一共有1+2+i-1=i(i-1)/2个元素，在第i行上， ai j之前恰有j-1个元素（即ai1,ai2,aij-1），因此有： k=i*(i-1)/2+j-1,若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j-

9、1)/2+i-1,2020/7/28,数据结构 page 20,信阳师范学院计算机与信息技术学院,三角矩阵,2020/7/28,数据结构 page 21,信阳师范学院计算机与信息技术学院,对角矩阵,Loc(aij)=Loc(a11)+2(i-1)+(j-1),2020/7/28,数据结构 page 22,信阳师范学院计算机与信息技术学院,M有42（67）个元素 有8个非零元素,2. 稀疏矩阵,例,有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。,2020/7/28,数据结构 page 23,信阳师范学院计算机与信息技术学院,稀疏矩阵可由非零元的三元组表及

10、其行数、列数唯一确定。,三元组表A= ( (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,三元组表,2020/7/28,数据结构 page 24,信阳师范学院计算机与信息技术学院,#define MAXSIZE 12500 /假设非零元个数的最大值为12500 Typrdef struct int i, j; / 非零元的行下标和列下标 ElemType e; /非零元 Triple; Typedef struct Triple dataMAXSIZE+1; /存储

11、非零元三元组表, data0未用 int mu, nu, tu; /矩阵的行数、列数和非零元个数 TSMatrix;,三元组顺序表,2020/7/28,数据结构 page 25,信阳师范学院计算机与信息技术学院,三元组顺序表图示,设M是TSMatrix 类型的结构变量，则M有四个域，其中M.data用于存储矩阵M的三元组表，如右图所示,2020/7/28,数据结构 page 26,信阳师范学院计算机与信息技术学院,转置运算是一种最简单的矩阵运算。对于一个m行 n列的矩阵M，它的转置矩阵T是一个n行m列的矩阵。,矩阵的转置,2020/7/28,数据结构 page 28,信阳师范学院计算机与信息技

12、术学院,解决思路： 将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使T.data中元素以N的行(M的列)为主序,方法一：按M的列序转置 即按T.data中三元组次序依次在M.data中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表M.data从第一行起扫描一遍。由于M.data中以M行序为主序，所以由此得到的恰是T.data中应有的顺序。,2020/7/28,数据结构 page 29,信阳师范学院计算机与信息技术学院,7 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,col=

13、1,col=2,2020/7/28,数据结构 page 30,信阳师范学院计算机与信息技术学院,/采用三元组表存储表示，求稀疏矩阵M的转置矩阵T T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; / q为当前三元组在T.data 存储位置(下标) for (col=1; col=M.nu; +col) for (p=1; p=M.tu; +p) /p为扫描M.data 的“指示器” /p“指向”三元组称为当前三元组 if (M.datap.j= =col) T.dataq.i =M.datap.j; T.dataq.j=M.datap.i; T.d

14、ataq.e=M.datap.e; +q; return OK; / TransposeSMtrix 算法5.1,算法分析：T(n)=O(nutu) 若 tu 与munu同数量级，则,Status TransposeSMatrix(TSMatrix M, TSMatrix 2. 求M中各列第一个非零元在T.data中的下标cpot ; 3. 对M.data进行一次扫描， 遇到col列的第一个非零元三元组时，按cpotcol 的位置，将其放至T.data中，当再次遇到col列的非零元三元组时，只须顺序放到col列元素的后面;,快速转置算法主要步骤：,2020/7/28,数据结构 page 35,

15、信阳师范学院计算机与信息技术学院,/采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵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; /求M中每一列非零元个数 /求第 col列中第一个非零元在T.data中的序号 cpot1=1; for(col=2; col=M.nu; +col) cpotcol=cpotcol-1+numcol-1; /FastTransposeSMatrix,Status Fast

16、TransposeSMatrix(TSMatrix M, TSMatrix 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;/FastTransposeSMatrix,2020/7/28,数据结构 page 37,信阳师范学院计算机与信息技术学院,该算法利用两个辅助向量num 、cpot ，实现了对M.data一次扫描完成M到T 的转置。 从时间上看，算法中有四个并列的单循环，循环次数

17、分别为nu、tu、nu和tu，因而总的时间复杂度为O（nu+tu)，在M的非零元个数tu和munu 同等数量级时，其时间复杂度为O( munu) 。由此可见，只有当tu munu时，使用快速转置算法才有意义。,时间复杂度分析,2020/7/28,数据结构 page 38,信阳师范学院计算机与信息技术学院,为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。可在稀疏矩阵的存储结构中增加一个指示“行”信息的辅助数组, 就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。,类型描述： Typedef struct Triple dataMAXSIZE+1; int

18、rposMAXRC+1； /各行第一个非零元的位置表 int mu，nu，tu； RLSMatrix；,行逻辑链接的顺序表,2020/7/28,数据结构 page 39,信阳师范学院计算机与信息技术学院,tpedef struct node int row,col,val; struct node *down, *right; JD; tpedef struct node *la,*lo;,十字链表,2020/7/28,数据结构 page 40,信阳师范学院计算机与信息技术学院,小结,特殊矩阵的压缩存储是根据元素的分布规律，确定元素的存储位置与元素在矩阵中的位置的对应关系；,矩阵压缩存储是指为

19、多个值相同的元素分配一个存储空间， 对零元素不分配存储空间；,；,稀疏矩阵的压缩存储除了要保存非零元素的值外，还要保存非零元素在矩阵中的位置；,2020/7/28,数据结构 page 41,信阳师范学院计算机与信息技术学院,基本内容 1 广义表的概念； 2 广义表的基本操作； 3 广义表的存储结构； 学习要点 了解广义表的结构特征及存储方法；,5.4 广义表,2020/7/28,数据结构 page 42,信阳师范学院计算机与信息技术学院,广义表也称为列表，是线性表的一种扩展，也是数据元素 的有限序列。 记作：LS= (1, 2。n)。其中i可以是单个 元素，也可以是广义表。,说明 1）广义表的

20、定义是一个递归定义，因为在描述广义表时又用到了广义表； 2）在线性表中数据元素是单个元素，而在广义表中， 元素可是以单个元素称为原子，也可以是广义表，称为广义表的子表； 3）n 是广义表长度；,广义表的概念,2020/7/28,数据结构 page 43,信阳师范学院计算机与信息技术学院,4）下面是一些广义表的例子； A = ( ) 空表，表长为0； B = (e) B中只有一个元素e，表长为1； C = (a,(b,c,d) C的表长为2，两个元素分别为 a 和子表（b,c,d)； D = (A,B,C) D 的表长为3，它的三个元素 A，B，C 广义表； E=(a,E) 这是一个递归的表,它

21、的长度为2。E相当于一个无限的列表：E=（a,(a,(a,)） 5） 对非空广义表：称第一个元素为L的表头，其余元素组成的表称为LS的表尾； B = (e) 表头：e 表尾 ( ) C = (a,(b,c,d) 表头：a 表尾 (b,c,d) D = (A,B,C) 表头：A 表尾 (B,C),2020/7/28,数据结构 page 44,信阳师范学院计算机与信息技术学院,若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表。,注意： ( ) 和( )不同！ （）是空表，长度为零； ( ) 长度为1，可分解为表头：( )和表尾： ( ),2020/7/28,数据结构 page 45,信阳师范学院计算机与信息技术学院,1） 创建空的广义表L； 2） 销毁广义表L； 3） 已有广义表L，由L复制得到广义表T； 4） 求广义表L的长度； 5） 求广义表L的深度； 6） 判广义表L是否为空； 7） 取广义表L的表头； 8） 取广义表L的表尾； 9） 在L中插入元素作为L的第一个元素； 10）删除广义表L的第一个元素，并e用返回其值； 11）遍历广义表L，用函数visit( )处理每个元素；,广义表的基本操作,2020/7/28,数据结构 page 46,信阳师范学院计算机与信息技术学院,Typedef enum ATOM,LISTElemTag; /ATOM=0:原