2009-7-30 软件基础教案（第五章 数组）
第五章 数组
Chapter 5 Array
5.1 数组定义及基本操作
5.2 数组的存储结构
5.3 特殊矩阵的压缩存储
5.4 稀疏矩阵的压缩存储
2009-7-30 软件基础教案（第五章 数组）
数组是我们最常用的一种数据结构，各种计算机语言均有此类型 。
例如：顺序表 顺序栈 循环队列
5.1 数组的定义及操作一、数组的定义数组是 n(n?1)个相同数据类型数据元素的 a0，
a1…an-1构成的有限序列，且该有限序列存储在一块 地址连续 的内存单元中。
二、数组的实现机制
1.一维数组 （ a0,a1,a2,a3,…an ）满足 线性关系；
Loc(ai)=Loc(a0)+i× k (0?i<n)
2009-7-30 软件基础教案（第五章 数组）
2.二维或二维以上数组：（以二维为例）
Amn=
看元素 a11有两个直接前趋 a01和 a10两个直接后继 a21和 a12
3.三维数组,每个元素有三个直接前趋和三个直接后继,( 略 )
a a ….,a
a00 a01 ……,a0n-1
10 11 0n-1… …,..
a a am-10 m-11 m-1n-1
Loc(aij)=Loc(a00)+(i× n+j)× k (0?i < m,0?j <n)
但是,
1)可将 Amn看成由 m个行向量组成的向量,即
Amn={ (a11,a12,…… a1n),(a21,a22,…… a2n),……( am1,
am2,…… amn) }
2)将 Amn看成由 n个列向量组成的向量,即
Amn=( (a11,a21,……am1),(a12,a22,……am2)……
(a1n,a2n,……amn) )
列向量为线性,
元素 1 元素 2
元素 m
看 (ai1,ai2,….,ain),除 ai1,ain 外只有一个直接前趋和一个直接后继,
元素 1 元素 2
元素 n
据此 数组可看成是线性表的扩展,即线性表中的数据元素本身也是一个数据结构,
数组和线性表的相同之处,都是有若干个相同数据类型的数据元素构成的有限序列 ;
数组和线性表的不同之处,
1.数组要求其元素占用一块地址连续的内存单元空间,而线性表无此要求 ;
2,线性表的元素是逻辑意义上不可再分的元素,而数组中的每个元素还可以是个数组。
3.数组的操作主要是向某个下标的数组元素中存数据和取某个下标的数组元素,这与线性表的插入、删除操作不同。
2009-7-30 软件基础教案（第五章 数组）
数组的特性数组中的数据元素数目固定；
数组中的数据元素具有相同的数据类型；
数组中的每个数据元素都和一组唯一的下标值对应；
数组是一种 随机存储结构,可随机存取数组中的任意数据元素。
2009-7-30 软件基础教案（第五章 数组）
三、数组的基本操作
int a,b[2][2];
1.随机存。
b[1][1]=5;
2.随机取。
a=b[1][1];
3.数组列表
4.矩阵运算
2009-7-30 软件基础教案（第五章 数组）
通常采用 顺序存储结构以二维数组 Amn为例
5.2 数组的存储结构假设,Am× n=
a00 a01 a02 a03 … a0n-1
a10 a11 a12 a13 … a1n-1
…
am-10 am-11 am-12 am-13 … am-1n-1
即 a00,a01,a02……a 0n-1,a10,a11,…...a 1n-1……
am-1,0
2009-7-30 软件基础教案（第五章 数组）
a00 …a01 a0n-1 a10 a11 a1n-1… … am-10 …am-11 am-1n-1
a00 …a10 am-10 a01 …a11 am-11 a0n-1 …a1n-1 am-1n-1…
行优先列优先
Loc(aij)=Loc(a00)+(i× n+j)× k
Loc(aij)=Loc(a00)+(j× m+i)× k
K:为每个元素所占存储单元,
Pascal和 C语言中数组存储为此方式,
Fortran语言采用此方法,
2009-7-30 软件基础教案（第五章 数组）
例题对于二维数组 float a[5][4]，每个数据元素占据 4个存储单元，试计算：
（ 1）数组 a中的数组元素数目；
（ 2）若数组 a的起始地址为 2000，数组元素
a[3][2]的内存地址。
解：（ 1） 5× 4＝ 20个；
（ 2） Loc(a32)=Loc(a00)+(i× n+j)× k
=2000+(3 × 4+2) × 4
=2056
2009-7-30 软件基础教案（第五章 数组）
5.3 特殊矩阵的压缩存储特殊矩阵压缩存储方法,只存数值不同的元素,节省空间。
读压缩掉矩阵元素方法,利用特殊矩阵压缩存储的数学映射公式。
特殊矩阵,指许多值相同的元素或有许多零元素、
且值相同的元素或零元素的分布有一定的规律的矩阵。
2009-7-30 软件基础教案（第五章 数组）
1.N阶对称矩阵的压缩存储对称矩阵,n阶方阵 A中的元素满足：
aij = aji 0≤ i,j≤ n-1
存储：可只存储上三角矩阵或下三角矩阵将 n*n个元素压缩存储到 n(n+1)/2个元素空间中
（ sa数组）。
以按行优先存储为例。
A矩阵与 sa[k]关系：
i(i+1)/2+ j i≥j
j(j+1)/2+i i<jk=
1 5 1 3 7
5 0 8 0 0
1 8 9 2 6
3 0 2 5 1
7 0 6 1 3
2009-7-30 软件基础教案（第五章 数组）
K 0 1 2 3 … n(n-1)/2 … n(n+1)/2-1
sa[k] a11 a21 a22 a31 … an1 … ann
隐含 a12 a13 … a1n
N阶对称矩阵的压缩存储对应关系一维数组实现了对 n阶对称矩阵的压缩存储，其压缩存储空间效率将近一倍。
2009-7-30 软件基础教案（第五章 数组）
2.N阶下三角矩阵压缩存储
(1)上三角元素 (不包括对角线元素 )的数据元素都为 0
(2)上三角元素 (不包括对角线元素 )的数据元素都为常数
(
K=
当 i?j时当 i?j时
2
1 j)ii ++
空
K=
当 i?j时当 i?j时2
1
2
1
)n(n
j)i(i
+
++
a11 0 0……..0
a21 a22 0 …….0
……………….
an1 an2 ….,a nn
Ann =
a11 c c…….,c
a21 a22 c ……,c
……………….
an1 an2 ….,a nn
Ann =
2009-7-30 软件基础教案（第五章 数组）
存放形式,
{a00,a10,a11,a20,a21,…a n-10,an-11,… a n-1n-1}
非零元素 aij存储地址,
Loc(aij)=Loc(a00)+[i*(i+1)/2+j]*k
（ 0≤j ≤i ≤ n-1）
a00 0 0……..0
a10 a11 0 …….0
……………….
an-10 an-11 ….,a n-1n-1
Ann =
上三角矩阵的存储类似下三角矩阵，自推
2009-7-30 软件基础教案（第五章 数组）
K=i=j
设以行序为主，存储在一维数组 sa[n]中，则 aij与
sa[k]的对应关系为当 i=j时
3.对角矩阵的压缩存储 (略 )
定义,矩阵中数据元素除了主对角线上的其他为零 aij = 0 i≠j ;1≤ i ≤n,1≤j≤ m
2009-7-30 软件基础教案（第五章 数组）
1.以上数组存储方式与顺序存储线性表类似。
2.数组元素的存储位置是其下标的线性函数。
总之：
特殊矩阵的压缩存储方法：
找出特殊矩阵的非零元素的分布规律，将其存储到一个存储空间，只需在算法中按公式计算即可实现矩阵元素的随机存取。
5.4 稀疏矩阵,
含有大量零元素的矩阵,且无规律。仅存非零元素,可省空间,
避免大量无意义运算,提高运算效率,
例,A=
3 0 0 0 7
0 0 -1 0 0
-1 -2 0 0 0
0 0 0 0 0
0 0 0 2 0
1.顺序存储,按行优先顺序排列,
(1).三元组表,
0 21 3 4
0
1
2
3
4
每个结点由三个域组成
a.非零元素行下 标 ;
b.非零元素列下标 ;
c.非零元素值,
2009-7-30 软件基础教案（第五章 数组）
A的三元组表表示,
(0,0,3) (0,4,7) (1,2,-1) (2,0,-1) (2,1,-2) (4,3,2)
行 列 值
0 0 3
0 4 7
1 2 -1
2 0 -1
2 1 -2
4 3 2
若有 N个非零元素则需要 3N个存储单元
3 0 0 0 7
0 0 -1 0 0
-1 -2 0 0 0
0 0 0 0 0
0 0 0 2 0
0 21 3 4
0
1
2
3
4
A=
2009-7-30 软件基础教案（第五章 数组）
#define maxsize 10000
typedef int elemtype;
typedef struct{
int i,j;
elemtype d;
}Datatype;
typedef struct{
Datatype data[maxsize];
int m,n,t;
}triType;
设 A为 triType型
/*m行数值,n列数值,t非零元素个数 */
/*i 行号,j 列号 */
/*元素值 */
三元组表的 C语言描述
2009-7-30 软件基础教案（第五章 数组）
*(2).带辅助行向量的二元组表,
希望省略三元组表中相同的行下标增加 (m+1)个元素的辅助行向量 NRA
定义,NRA[0]=0;
NRA[i]=NRA[i-1]+第 i-1行非零元素个数,
例,A=
3 0 0 0 7
0 0 -1 0 0
-1 -2 0 0 0
0 0 0 0 0
0 0 0 2 0
以上例中 A为例,列 值二元组表,NRA[0]=0 0 3
NRA[1]=2 4 7
NRA[2]=3 2 -1
NRA[3]=5 0 -1
NRA[4]=5 1 -2
NRA[5]=6 3 2
存储,一维数组,NRA[0]~NRA[5]
二维数组,(0,3) (4,7) (2,-1)……(3,2)
N个非零元素,则需 2N+m+1个存储单元比三元表节省单元,
查找速度快 。
A=
3 0 0 0 7
0 0 -1 0 0
-1 -2 0 0 0
0 0 0 0 0
0 0 0 2 0
2.链接存储结构,
(1)三元组单链表,
三元组线性表采用链接存储结构。
300 740 -121 -102
-212 2 ∧34
h (0,0,3) (0,4,7) (1,2,-1) (2,0,-1) (2,1,-2) (4,3,2)
缺点：算法事件复杂度高 3 0 0 0 7
0 0 -1 0 0
-1 -2 0 0 0
0 0 0 0 0
0 0 0 2 0
0 21 3 4
0
1
2
3
4
A=
2009-7-30 软件基础教案（第五章 数组）
(2)带行指针向量的单链表,
设置一个行指针向量,向量中每个元素为指针类型,它指向本行矩阵的第一个非零元素,如果都是零元素，则指针为空,
以 A为例,行指针向量
/\
0 3 4 7 /\
2 -1 /\
0 -1 1 -2 /\
3 2 /\
0
1
2
3
4
A=
3 0 0 0 7
0 0 -1 0 0
-1 -2 0 0 0
0 0 0 0 0
0 0 0 2 0
2009-7-30 软件基础教案（第五章 数组）
为了方便算法中对矩阵的行方向和列方向的搜索。
采用动态存储结构,每个非零元素用一个结点由五个数据域组成,三个数值,两个指针,
三个数值,i,j,value.表示非零元素的行号、列号和元素值。
两个指针,Down：向下指针
Right：向右指针
i j Value
Down Right
十字链表设置：行头结点、列头结点和链表头结点,
(3).十字链表,
2009-7-30 软件基础教案（第五章 数组）
链表头结点 m n link
3 0 0 7
0 0 -1 0
-1 -2 0 0
0 0 0 0
例 1,A4× 4=
行链表的头结点与列链表的头结点共用一个结点,
link
Down Right
行头结点列头结点
3 0 0 7
0 0 -1 0
-1 -2 0 0
0 0 0 0
例,A4*4=
4 4
0 0 3 0 3 7
2 1 -2
1 2 -1
2 0 -1
head h0
h0
h1
h1
h2
h2
h3
h3
2009-7-30 软件基础教案（第五章 数组）
i j value
down right
i j link
down right
(a)结点结构 (b)头结点结构十字链表结点结构?链表头结点?行列头结点
typedef struct node
{ int i;
int j;
elemtype value;
struct node *down,right;
} crossntype;
typedef struct node
{ int i;
int j;
struct node *link;
struct node *down,right;
} crosshtype;
十字链表的 C语言描述
B3× 4=
20 0 0 19
0 0 30 0
0 0 0 50
0 0 20 0 3 19
1 2 30
2 3 50
3 4
head h0 h1 h2 h3
h0
h1
h2
h3
十字链表例 2：
0 0 20 0 3 19
1 2 30
2 3 50
B3× 4=
20 0 0 19
0 0 30 0
0 0 0 50
h0 h1 h2 h3
m n pc[0] pc[1] pc[2] pc[3]
3 4
*采用数组指针的十字链表
2009-7-30 软件基础教案（第五章 数组）
#define max 100
typedef struct node
{
int i;
int j;
elemtype value;
struct node *down;
struct node *right;
} cross2type;
typedef struct
{
int m;
int n;
cross2type *pc[max];
}clinktype;
采用数组指针十字链表的 C语言描述
2009-7-30 软件基础教案（第五章 数组）
1.一般数组：按行、列存放，计算公式。
2.特殊矩阵：计算公式。
3.稀疏矩阵：表示方法：
顺序存储：三元组表
*二元组表链接存储：三元组表的单链表带行指针向量的单链表十字链表 普通的十字链表
*采用数组指针的十字链表总 结,
2009-7-30 软件基础教案（第五章 数组）
（二）看书 p122 5.4.1三元组顺序表
（一）自学 p116 5.2 动态数组思考题,
（三）自学课本 p123，了解矩阵转置
（四）预习实验五
（五）作业,p129 5-5,5-6,5-8,5-10,5-12