《数组和广义表培训课件》由会员分享，可在线阅读，更多相关《数组和广义表培训课件（61页珍藏版）》请在金锄头文库上搜索。
1、数据结构第五章数组与广义表,本章内容 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构,5-3,通过本章学习，要求掌握如下内容： 1多维数组的定义及在计算机中的存储表示； 2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式； 3稀疏矩阵的三元组表示及转置算法实现； 4稀疏矩阵的十字链表表示及相加算法实现； 5广义表存储结构表示及基本运算。,重点难点,5-4,数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定
2、的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：,5.1 数组的定义,( ),( ),( ),( ),( ),( ),( ),( ),( ),二维数组同样满足数组的定义。二维数组可以看成一个特殊的一维数组，其中的每个元素又是一个一维数组。,5.1 数组的定义,5-7,数组的特点：,数组中的数据元素数目固定(结构固定)；,数组中的数据元素具有相同的数据类型(元素同构)；,数组中的每个数据元素都与一组唯一的下标值相对应；,数组是一种随机存取结构。,5.1 数组的定义,5.1 数组的抽象数据类型ADT,5-8,一维数组存储结构示意图,地址映像的计算公式：
3、假设线性表中每个元素占L个单元，第一个元素的地址为loc(a1)，则第i个元素的地址为： loc(ai) =loc(a1)+(i-1)L,5.2 数组的顺序表示和实现,问 题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？ 解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。 注意： 用一组连续的存储单元来表示数组； 若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式； 约定的次序不同，则计算元素地址的公式也有所不同； C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先,5-10,5-11,5.2 数组的顺序表示
4、和实现,设一3维数组A423，存贮在一个顺序线性表S中，结构如下所示：,5.2 数组的顺序表示和实现,以行为主:对二维数组进行“按行切分”，即将数组中的数据元素“按行依次排放”在存储器中； 以列为主：对二维数组进行“按列切分”，即将数组中的数据元素“按列依次排放”在存储器中。,5-12,按行序为主序存放,LOC(i,j)=LOC(0,0)+(i*n+j)*L,按列序为主序存放,LOC(i,j)=LOC(0,0)+(j*m+i)*L,例题,无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址： 开始结点的存放地址（即基地址） 维数和每维的上、下界； 每个数组元素所占用的单元数,5
5、-15,例题,【例5-1】对于给定的二维数组float a34，计算： (1) 数组a中的数组元素上界、下界、元素数目； (2) 若数组a的起始地址为1000，且每个数组元素长度为32位(即4个字节)，数组元素a23的内存地址。 【解】(1)由于C语言中数组的行、列下标值的下界均为0，该数组行上界为3-1=2，列上界为4-1=3，所以该数组的元素数目共有3*4=12个。 (2)由于C语言采用行序为主序的存储方式，有： LOC(a2,3)=LOC(a0,0)+(i*n+j)*L =1000+(2*4+3)*4 =1044,5-16,例题,【例5-2】一个二维数组A，行下标的范围是1到6，列下标的
6、范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。 【解】 Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288 【例5-3】 设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。,5-17,根据列优先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*L 得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950,想一想：若数组是a059, 069，结果是否仍为8950？,5-18,5.3 矩阵的压缩
7、存储,在高级语言编制程序时，将一个矩阵描述为一个二维数组。 矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费.,5.3 矩阵的压缩存储,5-19,压缩存储,为多个值相同的矩阵只分配一个存储空间； 对零元不分配空间。,5-20,5.3 矩阵的压缩存储,5.3.1 特殊矩阵,值相同的元素或者0元素在矩阵中的分布有一定规律。,5-21,5.3 矩阵的压缩存储,对称矩阵,仅存储下三角,下
8、三角矩阵,5.3 矩阵的压缩存储,5.3 矩阵的压缩存储,对角矩阵,5-24,5.3 矩阵的压缩存储,5.3.2 稀疏矩阵 定义：设矩阵A中有t个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。 设在的矩阵A中，有t个非零元素。令 e=t/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵。 以常规方法，即以二维数组表示的高阶的稀疏矩阵时产生的问题： 1.零值元素占的空间很大； 2.计算中进行了很多和零值的运算；,5.3 矩阵的压缩存储,解决问题的原则 1. 尽量少存或不存0元； 2. 尽量减少没有意义的运算； 3. 运算要方便。 能尽可能快地找到与下标值
9、（i，j）对应的运算； 能尽可能快地找到同一行或同一列的非0值元。 压缩存储方法：三元组顺序表、行逻辑连接和十字链表。,5-25,存储特点,三元组顺序表,对于矩阵中每个非0元素，用它的行号、列号、元素值，即（i, j, aij）表示。 将表示稀疏矩阵的所有非0元素的三元组按行优先顺序排列，则可得到一个其结点均是三元组的线性表，称为三元组表。 以顺序存储结构来表示三元组。 要唯一确定一个稀疏矩阵，还必须存储该矩阵的行数和列数。,5-27,三元组法存储,（( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6
10、,4,-7) 6行6列，8个非零元,三元组顺序表,三元组法存储,5-28,三元组顺序表,数据类型定义,# define MAXSIZE 12500 三元组结点： typedef struct int i, j; /行号，列号 ElemType e; Triple; 稀疏矩阵： typedef struct Triple dataMAXSIZE+1 ; int mu, nu, tu; /*行、列、非零元素个数*/ TSMatrix ;,三元组顺序表,5-30,例子：三元组法表示的矩阵转置 M T,已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。,常规算法： for(col=1;col=n
11、u;col+) for(row=1;row=mu;row+) Tcolrow=Mrowcol;,时间复杂度： O(munu),三元组顺序表,5-31,解决思路：,将矩阵行、列维数互换； 将每个三元组中的i和j相互调换； 重排三元组次序；,三元组顺序表,5-32,2 1 3,5 1 -5,2 2 -1,1 3 6,4 3 8,1 4 -4,5 4 7,2 1 3,5 1 -5,2 2 -1,5 1 -5,三元组顺序表,5-33,2 1 3,5 1 -5,2 2 -1,1 3 6,4 3 8,1 4 -4,5 4 7,三元组顺序表,5-34,2 1 3,5 1 -5,2 2 -1,1 3 6,4
12、3 8,1 4 -4,5 4 7,0,0,0,0,0,+1,+1,+1,+1,+1,+1,+1,三元组顺序表,5-35,2 1 3,5 1 -5,2 2 -1,1 3 6,4 3 8,1 4 -4,5 4 7,1,2,3,4,5,5,6,7,三元组顺序表,5-36,三元组顺序表,优点：,非零元在表中按行序有序存储，便于进行依行序处理的矩阵运算。,缺点：,若需按行号存取某一行的非零元，则需从头开始查找。,三元组顺序表,为了便于随机存储任意一行的非零元，需要知道每一行的第一个非零元在三元组表中的位置。,3.行逻辑连接的顺序表,# define MAXSIZE 12500 三元组结点： typede
13、f struct int i, j; ElemType e; Triple; 稀疏矩阵： typedef struct Triple dataMAXSIZE+1 ; int rposMAXRC+1; /*各行第一个非零元的位置表 int mu, nu, tu; /*行、列、非零元素个数*/ TSMatrix ;,5-39,3.行逻辑连接的顺序表,带行向量的三元组法的矩阵乘法,5-40,3.行逻辑连接的顺序表,=,问题描述：,已知两个稀疏矩阵M和N的三元组表，求两个矩阵相乘的结果矩阵Q。,常规算法： for(i=1;i=m1;i+) for(j=1;j=n2;j+) Qij=0; for(k=1
14、;k=n1;k+) Qij += Mik* Nkj;,1、只对M和N的非零元进行计算；,2、M中列号与N中行号相等的非零元相乘即可；,3、Q与M的行号对齐的，且Qij是累加的结果。,3.行逻辑连接的顺序表,3.行逻辑连接的顺序表,Q初始化； if （Q是非零矩阵） for(arrow=1;arrow=M.mu;arrow+) ctemp=0; 计算Q中第arrow行的积并存入ctemp中； 将ctemp中非零元压缩存储到Q.data； ,5-42,处理M的每一行,分析上述算法的时间复杂度,例子:求矩阵乘法,1、累加器ctemp初始化的时间复杂度为O(M.muN.nu) 2、求Q的所有非零元的时
15、间复杂度为O(M.tuN.tu/N.mu) 3、进行压缩存储的时间复杂度为O(M.muN.nu),总的时间复杂度O(M.muN.nu+M.tuN.tu/N.mu),若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则： M中非零元的个数：M.tu=M mn N中非零元的个数： M.tu=N np 相乘算法的时间复杂度就是O(mn(1+nMN)，当： M 1000时， 算法的时间复杂度相当于O(mp)。,引入原因,十字链表,当矩阵的非零元的个数发生变化时，不宜采用三元组表。如A=A+B，非零元的插入或删除将会引起A.data中的数据移动，这是顺序结构三元组的弱势。,数据类型定义,结点： typedef struct OLNode int i, j; ElemType e; struct OLNode *right， *down；/*该非零元所在行的后继链域*/ OLNode; *OLink； 稀疏矩阵： typedef struct OLink *rhead，*chead； int mu，nu，tu； Crosslist;,down,right,5-46,4.
