严蔚敏版数据结构第五章课件.ppt

《严蔚敏版数据结构第五章课件.ppt》由会员分享，可在线阅读，更多相关《严蔚敏版数据结构第五章课件.ppt（57页珍藏版）》请在三一办公上搜索。

1、1,数据结构课程的内容,2,第5章 数组和广义表（Arrays & Lists）, 元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。 所有数据元素仍属同一数据类型。,5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的存储结构,数组和广义表的特点：一种特殊的线性表,3,5.1 数组的定义,数组： 由一组名字相同、下标不同的变量构成,注意： 本章所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。,答：对的。因为： 数组中各元素具有统一

2、的类型； 数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。,讨论：“数组的处理比其它复杂的结构要简单”，对吗？,4,一维数组存储方式,5,二维数组的特点：,2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,N维数组的特点：,n个下标，每个元素受到n个关系约束,一个n维数组可以看成是由若干个n1维数组组成的线性表。,6,N维数组的数据类型定义,n_ARRAY = (D, R),其中：,Ri = |

3、 aj1,j2,jijn , aj1,j2,ji+1jn D ,数据关系：R = R1 ,R2，. Rn ,数据对象：D = aj1,j2jn| ji为数组元素的第i 维下标 ，aj1,j2jn Elemset,数组的抽象数据类型定义略，参见教材P90,构造数组、销毁数组、读数组元素、写数组元素,基本操作：,7,5.2 数组的顺序存储表示和实现,问题： 计算机的存储结构是一维的，而数组一般是多维 的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一列序列， 然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。,注意：若规定好了次序，则数组中任意

4、一个元素的存放地址便有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。,8,补充：计算二维数组元素地址的通式设一般的二维数组是Ac1.d1, c2.d2，这里c1,c2不一定是0。,无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）：,二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L,单个元素长度,aij之前的行数,数组基址,总列数，即第2维长度,aij本行前面的元素个数,开

5、始结点的存放地址（即基地址）维数和每维的上、下界；每个数组元素所占用的单元数,则行优先存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L,9,二维数组(书上),行优先存放： 设数组开始存放位置 LOC( 0, 0 ) ，每个元素占用 l 个存储单元 LOC ( i, j ) = LOC( 0, 0 ) + ( i * m + j ) * l,10,例2：已知二维数组Am,m按行存储的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 按列存储的公式是？,Loc(aij)=Loc(a11)+(j-

6、1)*m+(i-1)*K （尽管是方阵，但公式仍不同）,例1软考题：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。,288,例3：00年计算机系考研题设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。,8950,LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950,答：请注意审题！,利用列优先通

7、式：,答： Volume=m*n*L=6*8*6=48*6=288,11,行向量 下标 i 页向量 下标 i列向量 下标 j 行向量 下标 j 列向量 下标 k,二维数组 三维数组,12,三维数组,各维元素个数为 m1, m2, m3 下标为 i1, i2, i3的数组元素的存储地址： （按页/行/列存放）,LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l,前i1页总元素个数,第i1页的前i2行总元素个数,13,n 维数组,各维元素个数为 m1, m2, m3, , mn 下标为 i1, i2, i3, , in 的数组元素的

8、存储地址：,LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l,14,Loc(j1,j2,jn)=LOC(0,0,0),若是N维数组，其中任一元素的地址该如何计算？,其中Cn=L, Ci-1=biCi， 1in,一个元素长度,数组基址,前面若干元素占用的地址字节总数,第i维长度,与所存元素个数有关的系数，可用递推法求出,教材已给出低维优先的地址计算公式，见P93（5-2）式该式称为n维数组的映像函数：,15,#define MAX_ARRAY_DIM 8 /假设最大维数为8 typedef

9、 struct ELemType *base; /数组元素基址 int dim; /数组维数 int *bound; /数组各维长度信息保存区基址 int *constants; /数组映像函数常量的基址 Array;,即Ci信息保存区,数组的基本操作函数说明（有5个）（请阅读教材P93-95）,N维数组的顺序存储表示（见教材P93）,以销毁数组函数为例,16,顺序存储方式：按低地址优先（或高地址优先）顺序存入一维数组。,行指针向量,补充：链式存储方式：用带行指针向量的单链表来表示。,注：数组的运算参见下一节实例（稀疏矩阵的转置）,（难点是多维数组与一维数组的地址映射关系）,17,5.3 矩阵

10、的压缩存储,讨论：1. 什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2. 所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。3. 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。4. 什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）,重点介绍稀疏矩阵的压缩和相应的操作。,18,特殊矩阵的压缩存储,特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩阵三对角矩

11、阵,19,对称矩阵的压缩存储,设有一个 nn 的对称矩阵 A。,在矩阵中，aij = aji,20,为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。数组 B 共有 n + ( n - 1 ) + + 1 = n*(n+1)/2 个元素。,21,上三角矩阵,下三角矩阵,22,下三角矩阵,B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1,0 1 2 3 4 5 6 7 8 n(n+1)/2-1,若 i j, 数组

12、元素Aij在数组B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j,前i行元素总数 第i行第j个元素前元素个数,23,若 i j，数组元素 Aij 在矩阵的上三角部分, 在数组 B 中没有存放，可以找它的对称元素Aji：= j *(j +1) / 2 + i,24,上三角矩阵,B a00 a01 a02 a03 a11 a12 a13 a22 a23 a33,0 1 2 3 4 5 6 7 8 9,若i j，数组元素Aij在数组B中的存放位置为n + (n-1) + (n-2) + + (n-i+1) + j-i,前i行元素总数 第i行第j个元素前元素个

13、数,n = 4,25,若 i j，数组元素Aij在数组B中的存放位置为 n + (n-1) + (n-2) + + (n-i+1) + j-i = = (2*n-i+1) * i / 2 + j-i = = (2*n-i-1) * i / 2 + j 若i j，数组元素Aij在矩阵的下三角部分，在数组 B 中没有存放。因此，找它的对称元素Aji。 Aji在数组 B 的第 (2*n-j-1) * j / 2 + i 的位置中找到。,26,三、对角矩阵的压缩存储,B a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1,0 1 2 3 4 5 6 7 8

14、9 10,27,三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组 B 中，且a00存放于B0。在三条对角线上的元素aij 满足 0 i n-1, i-1 j i+1在一维数组 B 中 Aij 在第 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 j-i+1 个，所以元素 Aij 在 B 中位置为 k = 2*i + j。,28,一、稀疏矩阵的压缩存储,问题：如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？解决思路：对每个非零元素增开若干存

15、储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。实现方法：将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组表来表示。,二、稀疏矩阵的操作,29,例1 ：,三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。,行下标,列下标,元素值,例2：写出右图所示稀疏矩阵的压缩存储形式。,( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7),法1：用线性表表示：,30,法2：用三元组矩阵表示：,注意：为更可靠描

16、述，通常再加一行“总体”信息：即总行数、总列数、非零元素总个数,稀疏矩阵压缩存储的缺点：将失去随机存取功能 :-(,31,法三：用带辅助向量的三元组表示。,方法： 增加2个辅助向量： 记录每行非0元素个数，用NUM（i）表示； 记录稀疏矩阵中每行第一个非0元素在三元组中的行号，用POS（i）表示。,7,6,5,3,1,3,用途：通过三元组高效访问稀疏矩阵中任一非零元素。,规律：POS(1)1 POS(i)POS(i-1)+NUM(i-1),32,法四：用十字链表表示,用途：方便稀疏矩阵的加减运算；方法：每个非0元素占用5个域。,同一列中下一非零元素的指针,同一行中下一非零元素的指针,十字链表的

17、特点：每行非零元素链接成带表头结点的循环链表；每列非零元素也链接成带表头结点的循环链表。则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即呈十字链状。,以刚才的稀疏矩阵为例：,33,#define MAXSIZE 125000 /设非零元素最大个数125000 typedef struct int i; /元素行号 int j; /元素列号 ElemType e; /元素值Triple; typedef struct Triple dataMAXSIZE+1; /三元组表，以行为主序存入一维向量 data 中 int mu; /矩阵总行数 int nu; /矩阵总列数 i

18、nt tu; /矩阵中非零元素总个数TsMatrix;,三元组表的顺序存储表示（见教材P98）：,/一个结点的结构定义,/整个三元组表的定义,34,二、稀疏矩阵的操作,三元组表a.data,三元组表b.data,M,T,（以转置运算为例）,目的：,35,答：肯定不正确！除了： （1）每个元素的行下标和列下标互换（即三元组中的i和j互换）；还应该：（2）T的总行数mu和总列数nu与M值不同（互换）； （3）重排三元组内元素顺序，使转置后的三元组也按行（或列）为主序有规律的排列。,上述（1）和（2）容易实现，难点在（3）。,若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完

19、成了对该矩阵的转置运算，这种说法正确吗？,有两种实现方法,压缩转置(压缩)快速转置,提问：,36,方法1：压缩转置,思路：反复扫描a.data中的列序，从小到大依次进行转置。,三元组表a.data,三元组表b.data,1,1,2,2,col,q,1,2,3,4,37,Status TransPoseSMatrix(TSMatrix M, TSMatrix ,压缩转置算法描述：（见教材P99）,/用三元组表存放稀疏矩阵M，求M的转置矩阵T,/q是转置矩阵T的结点编号,/col是扫描M三元表列序的变量,/p是M三元表中结点编号,38,1、主要时间消耗在查找M.datap.j=col的元素，由两重

20、循环完成: for(col=1; col=M.nu; col+) 循环次数nu for(p=1; p=M.tu; p+) 循环次数tu所以该算法的时间复杂度为O(nu*tu) -即M的列数与M中非零元素的个数之积最恶劣情况：M中全是非零元素，此时tu=mu*nu， 时间复杂度为 O(nu2*mu )注：若M中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是O(nu*mu) （程序见教材P99）结论：压缩转置算法不能滥用。前提：仅适用于非零元素个数很少（即tumu*nu）的情况。,压缩转置算法的效率分析：,39,方法2 快速转置,三元组表a.data,三元组表b.data,思路：

21、依次把a.data中的元素直接送入b.data的恰当位置上（即M三元组的p指针不回溯）。,关键：怎样寻找b.data的“恰当”位置？,q,3,5,40,如果能预知M矩阵每一列(即T的每一行)的非零元素个数，又能预知第一个非零元素在b.data中的位置,则扫描a.data时便可以将每个元素准确定位（因为已知若干参考点）。,技巧：利用带辅助向量的三元组表，它正好携带每行（或列）的非零元素个数 NUM(i)以及每行（或列）的第一个非零元素在三元组表中的位置POS(i) 等信息。,设计思路：,不过我们需要的是按列生成的M矩阵的辅助向量。,规律：POS(1)1POS(i)POS(i-1)+NUM(i-1

22、),请回忆：,请注意a.data特征：每列首个非零元素必定先被扫描到。,41,令：M中的列变量用col表示； num col ：存放M中第col 列中非0元素个数， cpot col ：存放M中第col列的第一个非0元素的位置， （即b.data中待计算的“恰当”位置所需参考点）,讨论：按列优先的辅助向量求出后，下一步该如何操作？由a.data中每个元素的列信息，即可直接查出b.data中的重要参考点之位置，进而可确定当前元素之位置！,规律： cpot(1)1cpotcol cpotcol-1 + numcol-1,M,3 5 7 8 8,col 1 2 3 4 5 6,42,Status F

23、astTransposeSMatrix（TSMatirx M, TSMatirx ,快速转置算法描述：,/M用顺序存储表示，求M的转置矩阵T,/先统计每列非零元素个数,/再生成每列首元位置辅助向量表,/p指向a.data，循环次数为非0元素总个数tu,/查辅助向量表得q，即T中位置,/重要语句！修改向量表中列坐标值，供同一列下一非零元素定位之用！,43,1. 与常规算法相比，附加了生成辅助向量表的工作。增开了2个长度为列长的数组(num 和cpos ）。,传统转置：O(mu*nu) 压缩转置：O(mu*tu) 压缩快速转置：O(nu+tu)牺牲空间效率换时间效率。,快速转置算法的效率分析：,2

24、. 从时间上，此算法用了4个并列的单循环，而且其中前3个单循环都是用来产生辅助向量表的。 for(col = 1; col =M.nu; col+) 循环次数nu; for( i = 1; i =M.tu; i +) 循环次数tu; for(col = 2; col =M.nu; col+) 循环次数nu; for( p =1; p =M.tu ; p + ) 循环次数tu; 该算法的时间复杂度(nu*2)+(tu*2)=O(nu+tu）,讨论：最恶劣情况是tu=nu*mu(即矩阵中全部是非零元素），而此时的时间复杂度也只是O(mu*nu)，并未超过传统转置算法的时间复杂度。,小结：,稀疏矩阵

25、相乘的算法见教材P101-103,44,5.4 广义表的定义,广义表是线性表的推广，也称为列表（lists）记为： LS = ( a1 , a2 , ， an ),广义表名 表头(Head） 表尾 (Tail),1、定义：, 第一个元素是表头，而其余元素组成的表称为表尾； 用小写字母表示原子类型，用大写字母表示列表。,n是表长,在广义表中约定：,讨论：广义表与线性表的区别和联系？ 广义表中元素既可以是原子类型，也可以是列表； 当每个元素都为原子且类型相同时，就是线性表。,45,2、特点：,有次序性有长度有深度可递归可共享,一个直接前驱和一个直接后继表中元素个数表中括号的重数自己可以作为自己的子

26、表可以为其他广义表所共享,特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。,46,E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表,1）A =( )2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(a, E),例1：求下列广义表的长度。,n=0，因为A是空表n=1，表中元素e是原子n=2，a 为原子，(b,c,d)为子表n=3，3个元素都是子表n=2，a 为原子，E为子表,D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表,47, A=( a , (b, A) ),

27、例2：试用图形表示下列广义表.（设 代表原子， 代表子表）,e, D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) ),的长度为3，深度为3,的长度为2，深度为,48,介绍两种特殊的基本操作：GetHead( L) 取表头(可能是原子或列表);GetTail(L ) 取表尾(一定是列表) 。,广义表的抽象数据类型定义见教材P107-108,49,1. GetTail【(b, k, p, h)】 ; 2. GetHead【( (a,b), (c,d) )】 ; 3. GetTail【( (a,b), (c,d) )】 ; 4. GetTail【 GetHead【(a,b),(

28、c,d)】 ;,例：求下列广义表操作的结果（严题集5.10）,(k, p, h),（b）,(a,b),5. GetTail【（e）】 ; 6. GetHead 【 ( ( ) )】 .7. GetTail【 ( ( ) ) 】 .,( ),(a,b),( ),( ),(c,d),50,5.5 广义表的存储结构,由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示 ，通常用链式结构，每个元素用一个结点表示。,1.原子结点：表示原子，可设2个域或3个域，依习惯而选。,注意：列表的“元素”还可以是列表，所以结点可能有两种形式,法2：标志域、值域、表尾指针,指向下一结点,法1：标志域，

29、数值域,51,2.表结点：表示列表，若表不空，则可分解为表头和表尾，用3个域表示：标志域，表头指针，表尾指针。, A =( ), C =( a ,( b , c , d ) ),例：, B=( e ),A=NULL,指向表头,指向表尾,52, E=(a, E), D=( A , B ,C )( ),(e),(a,(b,c,d),本章结束,（参见教材P109图）,53,1. 数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是( A )。【南京理工大学 2001 一、13 （1.5分）】 A. 1175 B. 1180 C. 12

30、05 D. 12102、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标k的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素 M43 的起始地址相同。 3 、数组A中，每个元素的长度是3个字节，行下标k的范围从1到8，列下标j的范围从1到10，从首地址SA开始连续存放在存储器中，该数组按行存放时，元素A85的起始地址为 SA+74 。,54,4. 设数组a1.50,1.80的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a45,68的存储地址为_（1）_;若以列序为主序顺序存储，则元素a45,68的存储地址为

31、_（2）_。 5、二维数组A1020510采用行序为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000，则A189的地址是 。6、有一个10阶对称矩阵A,采用压缩存储方式存储(上三角)，（按行为主序，并且A00=1）,则A85的地址为 42 。,55,8、一个稀疏矩阵如图,则对应的三元组为：,0 0 2 03 0 0 00 0 -1 50 0 0 0,56,9 、一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ )【西安交通大学 1996 二、8 (3分)】10. 二维以上的数组其实是一种特

32、殊的广义表。（ ） 【北京邮电大学 2002 一、5 （1分）】11. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）12、广义表（a,b,c,d）的表头是 ，表尾是 。13、广义表（a,b,c,d）的表头是 ，表尾是 。14、广义表（a,（b,c,d）的表头是 ，表尾是 。15、广义表（a,（b,(c,(d)）的表头是 ，表尾是 ,长度是 ，深度是 。16、广义表（a,(（b, (c）,f）,e）, d）的表头是 ，表尾是 ,长度是 ，深度是 。,57,17、HEADTAIL(a,b,c)的结果是 ； TAILHEAD(a,b),(c,d) 的结果是 ； HEADHEAD(a,b),(c,d) 的结果是 ；18. 已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是( )。A. head(tail(LS) B. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(head(LS) 【西安电子科技大学 2001应用一、3（2分）】 19. 广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为（ ）。【北京邮电大学1999一、2（2分）】Head(Tail(Head(Tail(Tail(A)A. (g) B. (d) C. c D. d,