第6章数组和稀疏矩阵 6.1数组 6.2特殊矩阵的压缩存储 提纲 CONTENTS 6.3稀疏矩阵 作业 上机实验题 1/57
CONTENTS 提纲 1/57
数组6.16.1.1数组的基本概念数组是一个二元组（idx，value）的集合，对每个idx，都有一个value值与之对应。idx称为下标，可以由一个整数、两个整数或多个整数构成，下标含有d（d≥1）个整数称为维数是d。数组按维数分为一维、二维和多维数组。一维数组A是n（n>1）个相同类型元素ag，a1，，an-构成的有限序列，其逻辑表示为A=（ao，a1，，an-1），其中，A是数组名，ai（0≤i≤n-1)是数组A中序号为的元素。一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。以此类推。2/57
数组是一个二元组（idx，value）的集合，对每个idx，都有一个value值 与之对应。idx称为下标，可以由一个整数、两个整数或多个整数构成，下 标含有d（d≥1）个整数称为维数是d。 数组按维数分为一维、二维和多维数组。 一维数组A是n（n>1）个相同类型元素a0，a1，.，an-1构成的有限序列，其 逻辑表示为A=（a0，a1，.，an-1），其中，A是数组名，ai（0≤i≤n-1） 是数组A中序号为i的元素。 一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。 以此类推。 2/57
二维数组的逻辑关系用二元组表示23A68759121011B=(D, R)R=(r1, r2]r1=(<1, 2>,<2,3>,<3, 4>, <5, 6>, <6, 7>, <7,8>,<9, 10>,1/同行关系<10,11>，<11，12>)r2=[<1, 5>,<5,9>, <2, 6>,<6, 10>, <3, 7>, <7,11>,<4, 8>,//同列关系<8,12>)3/57
二维数组的逻辑关系用二元组表示 9 10 11 12 5 6 7 8 1 2 3 4 B=(D，R) R={r1，r2} r1={<1，2>，<2，3>，<3，4>，<5，6>，<6，7>，<7，8>，<9，10>， <10，11>，<11，12>} //同行关系 r2={<1，5>，<5，9>，<2，6>，<6，10>，<3，7>，<7，11>，<4，8>， <8，12>} //同列关系 3/57
数组具有以下特点（1）数组中各元素都具有统一的数据类型。（2）d（d≥1）维数组中的非边界元素具有d个前驱元素和d个后继元素。（3）数组维数确定后，数据元素个数和元素之间的关系不再发生改变，特别适合于顺序存储。（4）每个有意义的下标都存在一个与其相对应的数组元素值。4/57
数组具有以下特点 （1）数组中各元素都具有统一的数据类型。 （2）d（d≥1）维数组中的非边界元素具有d个前驱元素和d个后 继元素。 （3）数组维数确定后，数据元素个数和元素之间的关系不再发 生改变，特别适合于顺序存储。 （4）每个有意义的下标都存在一个与其相对应的数组元素值。 4/57
d维数组抽象数据类型ADT Arrayt数据对象：D= 数组中所有元素}数据关系：R=(r1, r2, ", ra}ri={元素之间第i维的线性关系丨i=1，…，d)基本运算：Value(A，ii，i2，，ia)：A是已存在的d维数组，其运算结果是返回A[ii,.,i.]值。Assign(A，e，i1，i2，…，i.)：A是已存在的d维数组，其运算结果是置A[ii,iz,",ia]=e。5/57
d维数组抽象数据类型 ADT Array { 数据对象： D={ 数组中所有元素 } 数据关系： R={r1，r2，.，rd} ri={ 元素之间第i维的线性关系 | i=1，.，d} 基本运算： Value(A，i1，i2，.，id)：A是已存在的d维数组，其运算结果是返回 A[i1，i2，.，id]值。 Assign(A，e，i1，i2，.，id)：A是已存在的d维数组，其运算结果是 置A[i1，i2，.，id]=e。 . } 5/57