第5 章数组与广义表.ppt

数据结构
——C语言描述
第5章数组和广义表
数组的定义和运算
数组的顺序存储和实现
特殊矩阵的压缩存储
三角矩阵
带状矩阵
稀疏矩阵
广义表
总结与提高
数组的定义和运算
数组是一种数据类型。从逻辑结构上看,数组可以看成是一般线性表的扩充。二维数组可以看成是线性表的线性表。例如:
Am×n=
a12 a12 ┅ a1j ┅ a1n
a21 a22 ┅ a2j ┅ a2n
┇┇
ai1 ai2 ┅ aij ┅ ain
┇┇
am1 am2 ┅ amj ┅ amn
Am×n=
a12 a12 ┅ a1j ┅ a1n
a21 a22 ┅ a2j ┅ a2n
┇┇
ai1 ai2 ┅ aij ┅ ain
┇┇
am1 am2 ┅ amj ┅ amn
A=( 1  2 ┅j ┅n)
我们可以把二维数组看成一个线性表:
A=( 1  2 …j …n),其中j(1≤j ≤n)本身也是一个线性表,称为列向量。
矩阵Am×n看成n个列向量的线性表,即j=(a1j,a2j, …,amj)
Am×n=
a12 a12 … a1j … a1n
a21 a22 … a2j … a2n
┇┇
ai1 ai2 … aij … ain
┇┇
am1 am2 … amj … amn
B
‖
1
2
┇
i
┇
m
我们还可以将数组Am×n看成另外一个线性表:
B=(1,,2,,…,m),其中i(1≤i ≤m)本身也是一个线性表,称为行向量,即: I= (ai1,ai2, …,aij ,…,ain)。
上面二维数组的例子,介绍了数组的结构特性,实际上数组是一组有固定个数的元素的集合。由于这个性质,使得对数组的操作不象对线性表的操作那样,可以在表中任意一个合法的位置插入或删除一个元素。
对于数组的操作一般只有两类:
(1)获得特定位置的元素值;
(2)修改特定位置的元素值。
数组的抽象数据类型定义(ADT Array)
数据对象:D={ aj1j2…jn| n>0,称为数组的维数,ji是数组的第i维下标,1≤ji≤bi,bi为数组第i维的长度, aj1j2…jn ∈ElementSet}
数据关系:R={R1,R2,…,Rn}
Ri={< aj1 … ji…jn ,aj1 … ji+1…jn > | 1≤jk≤bk,1≤k≤n 且k≠i,1≤ji≤bi-1, aj1 … ji…jn ,aj1 … ji+1…jn ∈D,i=1,…,n}
基本操作:
(1)InitArray(A,n,bound1,…,boundn): 若维数n和各维的长度合法,则构造相应的数组A,并返回TRUE;
(2)DestroyArray(A): 销毁数组A;
(3)GetValue(A,e, index1, …,indexn): 若下标合法,用e返回数组A中由index1, …,indexn所指定的元素的值。
(4)SetValue(A,e,index1, …,indexn): 若下标合法,则将数组A中由index1, …,indexn所指定的元素的值置为e。
注意:这里定义的数组下标是从1开始,与C语言的数组略有不同。
数组的顺序存储和实现
对于数组A,一旦给定其维数n及各维长度bi(1≤i≤n),则该数组中元素的个数是固定的,不可以对数组做插入和删除操作,不涉及移动元素操作,因此对于数组而言,采用顺序存储法比较合适。
数组的顺序存储结构有两种:
一种是按行序存储,如:高级语言BASIC、COBOL和PASCAL语言都是以行序为主。
另一种是按列序存储,如:高级语言中的FORTRAN语言就是以列序为主。
对于二维数组Amxn
以行为主的存储序列为:a11 ,a12, … a1n ,a21 ,a22 ,…,a2n , ……,am1 ,am2 , …, amn
以列为主存储序列为:a11, a21,… am1 ,a12 ,a22 ,…,am2 ,……,a1n ,a2n , …,amn
假设有一个3×4×2的三维数组A ,其逻辑结构图为:
列
行
纵