Chapter05——数组和广义表

ai,1 ai,2 … ai,j … ai,n an,1 an,2… an,j … an,n
i(i-1)/2+j-1 (i≥j) k= 第五章数j组(j和-1广)义/2表+i-1 (i＜j)
第五章数组和广义表
5.1 数组的类型定义 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储 5.4 广义表
第五章数组和广义表
5.1 数组的定义和运算
数组是一种数据类型。从逻辑结构上看，数 组可以看成是一般线性表的扩充。二维数组可 以看成是线性表的线性表。例如：
Am×n=
a11 a12 … a1j ……
LO(0C ,0,..0.) , ci ji (Cn=L,ci-1=bi*ci,1<i≤n) i1
数组元素的存储位置是其下标的线性函数，由于计算各 个元素存储位置的时间相等，所以存储数组中任一元素的 时间也相等，称具有这一第五特章数点组和的广义存表 储结构为随机存储结构。
N维数组数据元素存储地址计算
i= （ai1，ai2， …，aij ，…，ain）。
B
‖
a11 a12 … a1j … a1n
1
……
…
Am×n= ai1 ai2 … aij … ain
i
……
…
am1 am2 … amj … amn
m
第五章数组和广义表
看一个二维数组的简单情况。
D={aij|0≤i≤b1-1,0≤j≤b2-1, aij∈ ElemType}
}
第五章数组和广义表
5.3 矩阵的压缩存储
• 压缩存储：为多个值相同的元素只分配一个存 储空间，对零元素不分配空间。
• 目的：节省存储空间 • 任务：压缩存储矩阵并使矩阵的运算有效进行。 • 矩阵的存储：二维数组 • 可压缩存储的矩阵有两类:

第五章数组和广义表一．选择题1．在二维数组A 中引用A[i,j]的时间_________。

A．与i、j的大小有关B．与i、j的大小无关C．与i的大小有关，与j的大小无关D．与i的大小无关，与j的大小有关2．在稀疏矩阵的带行指针向量的链接存储中，每一行单链表中的结点都具有相同的________。

A．行号 B．列号 C．元素值 D.地址3．二维数组A 按行顺序存储，其中每个元素占1个存储单元。

若 A[1][1]的存储地址为420， A[3][3]的存储地址为446，则A[5][5]的存储地址为_______。

A．470 B．471 C．472 D. 4734．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。

A．行号 B．列号 C．元素值 D.地址5．下面的说法中，不正确的是________。

A．对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可B．对角矩阵中只须存放的非零元素即可C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储6．对一些特殊矩阵采用压缩存储的目的主要是为了________。

A．表达变得简单 B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销7．若将n 阶对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组 B 中，则该对称矩阵在 B 中占用了________个数组元素。

A．n2 B．n*(n-1) C．n*(n+1)／2 D．n*(n-1)8. 稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。

A. 行号B.列号C.元素值D.元素总数9．稀疏矩阵一般的压缩存储方法有两种，即________。

A．二维数组和三维数组 B．三元组和散列C. 三元组和十字链表 D．散列和十字链表10．有一个 10 阶对称矩阵 A，采用压缩存储方式(以行序为主存储，且A[0 Ⅱ0]=1)，则A[8][5]的地址是________。

5.2 数组的顺序表示和实现

特点：用一组地址连续的存储单元按照某种规则存放数组 中的数据元素。 两种规则（顺序存储方式）：


以行序为主（低下标优先）—将数组元素按行排列，第 i+1个行向量紧接在第i个行向量后。如：PASCAL、C。 以列序为主（高下标优先）—将数组元素按列排列，第 j+1个列向量紧接在第j个列向量后。如：FORTRAN。
am-1,0 a01 a11 …… am-1,1
……
按 列 序 为 主 序
a0,n-1 a1,n-1
……
am-1,n-1 am-1,n-1 ?A[2][3][2]以行序为主存储，写出其元素存放的先后顺序
5.2 数组的顺序表示和实现


计算数组任一元素(a j1 j2 ... jn )的地址需要的三要素： ①数组的起始地址（即基地址） ②数组维数和各维的长度； ③数组中每个元素所占的存储单元 已知二维数组Ab1*b2，每个元素占L个存储单元， LOC(0,0)是 数组第一个元素的起始地址，以行序为主存储，求LOC(i,j)。
N维数组数据元素存储地址计算
1、数组M[1..10][-1..6][[0..3]，起始地址是1000,每个元素占3个 存储单元,数组元素个数是 ，M[2][4][2]的地址是 。 2、数组A[0 .. 8][1 .. 10]的成员由6个字节组成，存放a要 个字 节，a的第8行第5列占 个字节。按行序a[8][5]与按列序 起始地址相同。 （10-1+1）*（6-（-1）+1）*（3-0+1）=320 LOC（M[2][4][2]）=1000+[（i-1）*b2*b3+(j-(-1))*b3+k]*l =1000+[32*(2-1)+4*(4+1)+2]*3=1162 LOC（a[8][5]）=a（起始地址）+（i*n+(j-1)）*l =a+(8*10+4)*6=a+504， LOC(a[3][10])=a(起始地址)+((j-1)*m+i)*l =a+(9*9+3)*6=a+504。

M
1 1 2 3 3 4
1 5 3 1 2 4
3 7 -1 -1 -2 2
N
1 1 2 3 4 5
1 3 3 2 4 1
3 -1 -2 -1 2 7
行列下 标调换
1 5 3 1 2 4
1 1 2 3 3 4
3 7 -1 -1 -2 2
按行下 标排序
法1：
按照矩阵M的列序进行转置，即按三元组A的 第二个字段值（列下标）由小到大的顺序进行转置。 为了找到M中每一列中所有的非零元素，需要对其 三元组表a.data从第一行起整个扫描一遍，由于 a.data是以M的行序为主序来存放每个非零元素 的，对于M中具有相同列下标的非零元来讲，先扫 描到的非零元的行下标一定小于后扫描到的非零元 的行下标，由此得到的恰是b.data应有的顺序。
• 压缩的含义
– 为多个值相同的元素只分配一个存贮空间； – 零元素不分配或少分配存贮空间。
• 特殊矩阵：元素值相同或零元素分布有 一定规律的矩阵。 • 稀疏矩阵：元素值相同或零元素分布没 有规律的矩阵。 • 特殊矩阵的压缩存贮实际是将二维数组 的数据元素压缩到一维数组上。
特殊矩阵的压缩存储
特殊矩阵: 非零元在矩阵中的分布有一定规则
常用的稀疏矩阵的存储方法
三元组表示法 顺序存储 行逻辑联接的顺序表 带辅助行向量的二元组表示法 伪地址表示法 带行指针向量的单链表示法 链接存储 散列存储 行列表示法（十字链表） 多链表示法（正交表）
顺序存储
1、三元组表示法 用一个线性表来表示稀疏矩阵，线性表的每个 结点对应稀疏矩阵的一个非零元素。其中包括三个 域，分别为该元素的行下标、列下标和值。结点间 的先后顺序按矩阵的行优先顺序排列（跳过零元 素），将线性表用顺序的方法存储在连续的存储区 里。