河池学院：《数据结构》课程电子教案（PPT教学课件）第6章 数组和稀疏矩阵

第6章数组和稀疏矩阵 6.1数组 6.2特殊矩阵的压缩存储 提纲 CONTENTS 6.3稀疏矩阵 作业 上机实验题 1/57

CONTENTS 提纲 1/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

二维数组的逻辑关系用二元组表示           9 10 11 12 5 6 7 8 1 2 3 4 B=(D，R) R={r1，r2} r1={，，，，，，， ，} //同行关系 r2={，，，，，，， } //同列关系 3/57

数组具有以下特点 （1）数组中各元素都具有统一的数据类型。 （2）d（d≥1）维数组中的非边界元素具有d个前驱元素和d个后 继元素。 （3）数组维数确定后，数据元素个数和元素之间的关系不再发 生改变，特别适合于顺序存储。 （4）每个有意义的下标都存在一个与其相对应的数组元素值。 4/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

1. 一维数组 一维数组的所有元素依逻辑次序存放在一片连续的内存存储单元中。 其起始地址为第一个元素a0的地址即LOC(a0)。 假设每个数据元素占用k个存储单元。 则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出 LOC(ai)=LOC(a0)+i×k （1≤i<n） 一维数组具有随机存储特性 6/57

2. d维数组 以m行n列的二维数组Am×n=(ai，j)为例讨论（二维数组也称为矩阵）。 7/57

按行优先存储 ai,j前面有0～i-1共i行，每行n个元素，共有i×n个元素。 在第i行中前面有a[i,0.j-1]，共j个元素。 合起来，ai,j前面有i×n+j个元素。 LOC(ai,j)=LOC(a0,0) + (i×n + j)×k 假设每个元素占k个存储单元，LOC(a0，0)表示a0，0元素的存储地址。 对于元素ai，j： 8/57

按列优先存储 ai,j前面有0～j-1共j列，每列m个元素，共有j×m个元素。 在第j列中前面有a[0.i-1,j]，共i个元素。 合起来，ai,j前面有j×m+i个元素。则： LOC(ai,j)=LOC(a0,0) + (j×m + i)×k 假设每个元素占k个存储单元，LOC(a0，0)表示a0，0元素的存储 地址。对于元素ai，j： 二维数组也具有随机存储特性，以此类推。 9/57

更一般地，数组A[c1.d1，c2.d2]，则该数组按行优先存储时有： LOC(ai，j)=LOC(ac1，c2)+[(i-c1)×(d2-c2+1)+(j-c2)]×k 按按行优先存储时有： LOC(ai，j)=LOC(ac1，c2)+[(j-c2)×(d1-c1+1)+(i-c1)]×k 10/57