数据结构第五章节数组和广义表.pptVIP

Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第五章?? 数组和广义表 ? 5. 1 数组的定义 5.2 数组的顺序存储结构 5. 3 矩阵的压缩存储 5. 4 广义表的定义 5.5 广义表的存储结构 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3 前4章介绍的数据结构共同特点： ▲ 都属于线性数据结构； ▲ 每种数据结构中的数据元素，都作为原子数据，不再进行分解； 本章讨论的两种数据结构：数组和广义表，其共同特点是： ▲ 从逻辑结构上看它们，可看成是线性结构的一种扩展； ▲ 数据元素本身也是一个数据结构； 第五章 ??? 数组和广义表 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4 一、数组的定义 (1) 数组的抽象数据类型定义 ADT Array { 数据对象： D＝{aj1,j2,…,ji,…,jn|ji=0,…,bi-1,i=1,2,…,n ( n0) 称为数组的维数,bi是数组第i维的长度，ji是数组元素的第i维下标} 5．1 数组的定义 数据关系：R＝{R1, R2,… ,Rn} Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 5 Ri＝{aj1… ji…jn, aj1… ji+1 …jn|0≤jk≤bk-1,1≤k≤n 且 k?i, 0≤ji≤bi-2, aj1… ji…jn, aj1… ji+1 …jn ∈D， i=2,… ,n } 如二维数组的定义: 数据对象: D={ aij|0≤i≤b1-1,0≤j≤b2-1 } 数据关系: R={ ROW, COL } ROW={ ai,j,ai+1,j| 0≤i≤b1-2,0≤j≤b2-1 } COL={ ai,j,ai,j+1| 0≤i≤b1-1,0≤j≤b2-2 } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 6 (2)? 二维数组的解释 二维数组中的每个元素都受两个线性关系的约束，即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。 在行关系中 aij直接前趋是 aij-1 aij直接后继是 aij+1 在列关系中 aij直接前趋是 ai-1j aij直接后继是 ai+1j Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 7 A=(?0 ,?1 ,?2 ,?3 , ?4 ,……,?p ) p = m-1 或 n-1 其中每一个数据元素 ?j 是一个列向量的线性表 ?j=（a0j , a1j ,a2j , a3j ,…… ,am-1j ) 0≤j≤n-1 二维数组也可看作这样的线性表：其每一个数据元素也是一个线性表。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 8 或 ?i 是一个行向量的线性表 ?i=（ai0 ,ai1 ,ai2 , ai3 ,…… ,ain-1