2001 -- 4 --2
华中科技大学计算机学院 (5)数据结构第五章 数组和广义表引言：
线性表,L=(a1,a2,...,an),ai是 同类型的元素,1≤ i≤n
数组,A=(a1,a2,...,an)
若 ai是同类型的元素,A是 一维数组,1≤ i≤n
若 ai是同类型的定长线性表,A是多 维数组,1≤ i≤n
广义表,Ls=(a1,a,...,an)
ai可以是同类型的元素或不定长的线性表,1≤ i≤n
5.1 数组及其操作简单地说，向量和矩阵称为 数组 。
5.1.1 数组的递归定义
1.一维数组 是一个定长线性表 (a1,a2,...,an )。
其中,ai为元素,i为下标 /序号,1≤ i≤n
(a1,a2,...,an )又称为向量。
2.二维数组 是一个定长线性表 (?1,?2,...,?m)，
其中,?i=(ai1,ai2,...,ain)为行向量,1≤ i≤m
由 m个 行向量组成,记作：
( a11 a12,.,a1n )
( a21 a22,.,a2n )
............
( am1 am2,.,amn )
Am*n=
即 Am*n=((a11 a12,..a1n),(a21 a22,..a2n),...,(am1 am2,..amn))
或由 n个列 向量组成,记作：
a11 a12 a1n
a21 a22 a2n
am1 am2 amn
Amxn=
3.三维数组 是一个定长线性表 (?1,?2,...,?p )。
其中,?k=(?1,?2,...,?m )为定长二维数组,1≤ k≤p
例 三维数组 A[1..3,1..4,1..2],p=3,m=4,n=2
a111 a112
a121 a122
a131 a132
a141 a142
a211 a212
a221 a222
a231 a232
a241 a242
a311 a312
a321 a322
a331 a332
a341 a342
第 1页第 2页第 3页
5.1.2 数组的类型定义和变量说明：
例 1 int a[10]； //10个整数的一维数组
char b[4][5]； //4行 5列个字符的二维数组
float c[3][4][2]； //3*4*2个实数的三维数组
A3*4*2 =
例 2 #define m 4 //定义符号常量 m
#define n 5 //定义符号常量 n
int a[m]； //m个整数的一维数组
char b[m][n]； //m行 n列个字符的二维数组例 3 #define m 4 //定义符号常量 m
#define n 5 //定义符号常量 n
typedef int ara[m]； //一维数组类型 ara
typedef char arb[m][n]； //二维数组类型 arb
ara a； //ara类型的变量 a
arb b； //arb类型的变量 b
C语言中定义静态 数组时,元素数目必须是常量错例 1 int m=4,n=5；
int a[m][n]； //m,n是变量错例 2 int p；
scanf(”%d”,&p)；
int c[p]； //p是变量
5.1.3 数组的操作
1.生成一个数组,int a[7]； //生成静态一维数组 (存储结构）
2.销毁一个数组
3.赋值 /修改
a[1]=15； (a[1])++；
4.取元素的值,
a[0]=a[1]*2；
5.1.4 程序设计举例例 1 main()
{ int i,a[10]； //生成一维数组 a
for (i=0； i<10； i++)
scanf(”%d”,&a[i])； //输入元素
for (i=0； i<10； i++)
printf(”%d,,a[i]*a[i])； //输出元素的平方
}
a
0 1 2 3 4 5 6
32 16a
0 1 2 3 4 5 6
例 2 生成动态的 10个整数的一维数组
int *pa； //指针变量 pa
pa=(int *)malloc(10*sizeof(int))； //动态数组 pa*
main()
{ int i,n,*pa；
scanf(”%d”,&n)； //动态输入 n
pa=(int *)malloc(n*sizeof(int))； //生成动态数组 *pa
for (i=0； i<n； i++)
*(pa+i)=2*i； //指针法引用数组元素,赋值
for (i=0； i<n； i++)
printf(“%d,”,*(pa+i))； //输出数组元素 0,2,4,6,...
for (i=0； i<n； i++)
scanf(“%d”,&pa[i])； //下标法引用数组元素,输入
for (i=0； i<n； i++)
printf("%d,",pa[i])； //输出数组元素
free(pa)； //释放 (销毁 )数组空间
}
pa →
0 1 2 3 4 5 6 7 8 9
5.2数组的顺序表示和实现
5.2.1顺序表示 (顺序存储结构）
1.以行序为主序的顺序存储方式左边的下标后变化，右边的下标先变化
2.以列序为主序的顺序存储方式左边的下标先变化，右边的下标后变化例 1 二维数组 a[1..3,1..2],b是首地址,s是元素所占的单元数
a11 a12
a21 a22
a31 a32
a11
a12
a21
a22
a31
a32
a11
a21
a31
a12
a22
a32
序号 内存 地址
1
2
3
4
5
6
1
2
3
4
5
6
序号 内存 地址
b
b+s
b+2*s
b+3*s
b+4*s
b+5*s
b
b+s
b+2*s
b+3*s
b+4*s
b+5*s
以行序为主序 以列序为主序逻辑结构例 2 三维数组 a[1..2,1..3,1..2]
a111 a112
a121 a122
a131 a132
a111
a112
a121
a122
a131
a132
a211
a212
a221
a222
a231
a232
序号 内存 地址
1
2
3
4
5
6
7
8
9
10
11
12
序号 内存 地址
b
b+s
b+2*s
b+3*s
b+4*s
b+5*s
b+6*s
b+11*s
b
b+s
b+2*s
b+3*s
b+4*s
b+5*s
b+6*s
b+11*s
以行序为主序 以列序为主序逻辑结构
a211 a212
a221 a222
a231 a232
第 1页第 2页
1
2
3
4
5
6
7
8
9
10
11
12
a111
a211
a121
a221
a131
a231
a112
a212
a122
a222
a132
a232
5.2.2数组的映象函数数组元素的存储地址例 1 一维数组 a[0..n-1]
设,b为首地址,s为每个元素所占的存储单元数则,元素 a[i]的 存储地址,
Loc(i)=Loc(0)+i*s=b+i*s 0≤ i≤n -1
a(n-1)...ai...a2a1a0
下标 0 1 2 i n-1
地址 b b+s b+2*s b+i*s b+(n-1)*s
a1 a2 a3,.,ai,.,an
下标 1 2 3 i n
地址 b b+s b+2s b+(i-1)s b+(n-1)s
例 2 一维数组 a[1..n]
元素 a[i]的 存储地址
Loc(i)=Loc(1)+(i-1)*s=b+(i-1)*s 1≤ i≤n
例 3 二 维数组 a[1..m,1..n],假定无零行零列
a11,.,a1j,.,a1n
.................
ai1,.,aij,.,ain
.................
am1,.,amj,.,amn
Amxn=
(1)以行序为主序,a[i][j]的地址为
Loc(i,j)=Loc(1,1)+(n*(i-1)+j-1)*s
=b+(n*(i-1)+j-1)*s 1≤ i≤m,1 ≤ j≤n
其中,b为首地址,s为每个元素所占的存储单元数
n:列数 m:行数共 i-1行共 j-1列例 3 二 维数组 a[1..m,1..n],假定无零行零列
a11 a12,.,a1j,.,a1n
............,.....
ai1 ai2,.,aij,.,ain
........,.........
am1 am2,.,amj,.,amn
Amxn=
(2)以列序为主序,a[i][j]的地址为
Loc(i,j)=Loc(1,1)+(m*(j-1)+i-1)*s
=b+(m*(j-1)+i-1)*s 1≤ i≤m,1 ≤ j≤n
其中：
b为首地址,s为每个元素所占的存储单元数
n,列数 m,行数共 i-1行共 j-1列例 4 二 维数组 a[0..m-1,0..n-1]（有零行零列）
a00,.,a0j,.,a0n-1
a10,.,a1j,.,a1n-1
....................
ai0,.,aij,.,ain-1
....................
am-10,.,am-1j,.,am-1n-1
Amxn=
(1)以行序为主序,a[i][j]的地址为
Loc(i,j)=Loc(0,0)+(n*i+j)*s
=b+(n*i+j)*s 0≤ i≤m -1,0≤ j≤n -1
其中：
b为首地址,s为每个元素所占的存储单元数
n,列数 m,行数共 i行共 j列例 4 二 维数组 a[0..m-1,0..n-1]（有零行零列）
a00 a01,.,a0j,.,a0n-1
a10 a11,.,a1j,.,a1n-1
.........,..,........
ai0 ai1,.,aij,.,ain-1
.........,..,.......
am-10 am-11,..am-1j,.,am-1n-1
Amxn=
(2)以列序为主序,a[i][j]的地址为
Loc(i,j)=Loc(0,0)+(m*j+i)*s
=b+(m*j+i)*s 0≤ i≤m -1,0≤ j≤n -1
其中：
b为首地址,s为每个元素所占的存储单元数
n,列数 m,行数共 i行共 j列例 5 三 维数组 a[1..p,1..m,1..n],假定无 0页 0行 0列
1)以行序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(1,1,1)+(m*n*(k-1)+n(i-1)+j-1)*s
=b+(m*n*(k-1)+n(i-1)+j-1)*s
1≤ k≤p,1 ≤ i≤m,1 ≤ j≤n
其中：
b为首地址,s为每个元素所占的存储单元数
p---页数 n--列数 m-行数
(2)以列序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(1,1,1)+(p*m*(j-1)+p*(i-1)+k-1)*s
=b+(p*m*(j-1)+p*(i-1)+k-1)*s
1≤ k≤p,1 ≤ i≤m,1 ≤ j≤n
其中：
b为首地址,s为每个元素所占的存储单元数
p---页数 n--列数 m-行数例 5 三 维数组 a[0..p-1,0..m-1,0..n-1],
(1)以行序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(0,0,0)+(m*n*k+n*i+j)*s
=b+(m*n*k+n*i+j)*s
0≤ k≤p -1,0≤ i≤m -1,0≤ j≤n -1
其中：
b为首地址,s为每个元素所占的存储单元数
p---页数 n--列数 m-行数
(2)以列序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(0,0,0)+(p*m*j+p*i+k)*s
=b+(p*m*j+p*i+k)*s
0≤ k≤p -1,0≤ i≤m -1,0≤ j≤n -1
其中：
b为首地址,s为每个元素所占的存储单元数
p---页数 n--列数 m-行数
5.3 矩阵的压缩存储
5.3.1特殊 矩阵的压缩存储
1,n阶对称 矩阵
a11 a1n
aji
aij
an1 ann
Anxn=
上三角下三角
aij==aji
1≤ i,j≤n
假定以行序为主，顺序存储下三角元素到 SA[1..maxleng]：
a11 a21 a22 a31,..ai1,..aij,..aii,..an1,..ann
k=1 2 3 4,.,i(i-1)/2+j,.,n(n+1)/2
如何求 aij在 SA中的位置，即序号 k？
(1) 设 aij在下三角,i≥ j
∵ 第 1?i-1行共有元素
1+2+3+… (i-1)=i(i-1)/2 (个 )
ai1?aij共有 j个元素
∴ aij的序号为,
k=i(i-1)/2+j
(2) 设 aij在上三角,i<j
∵ 上三角的 aij=下三角的 aji
下三角的 aji的序号为
k=j(j-1)/2+i i<j
∴ 上三角的 aij的序号为
k=j(j-1)/2+i i<j
由 (1)和 (2)，任意 aij在 SA中 的序号，为
i(i-1)/2+j i≥ j
j(j-1)/2+i i<j
称为在 SA中的映象函数，下标转换公式
k(i,j)=
2.三对角矩阵
a11 a12
a21 a22 a23
a32 a33 a34
..,aij....,
an-1n-1an-1n
ann-1 ann
Anxn=
全 0
全 0
假定以行序为主，顺序存储非 0元素到 SA[1..maxleng]：
a11 a21 a22 a23 a32 a33,.,aij,..ann-1 ann
k=1 2 3 4 5 6,.,?,.,3n-2
任意 aij≠ 0,在 SA中 的序号,
k= (3*(i-1)-1)+(j-i+2) = 2(i-1)+j
5.3.2 稀疏 矩阵的压缩存储
1.三元组表例 稀疏 矩阵 M及其转置 矩阵 T
0 13 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
0 0 0 -7 0 0 0
0 0 -3 0 0 0
13 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 0 14 0 0 0
0 0 0 0 0 0
M=
T=
1 2 13
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 4 -7
i j v=aij
1 3 -3
2 1 13
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
i j v=aij
M的三元组表
T的三元组表表 A
表 B
问题,如何由 矩阵 M求 矩阵 T,即由表 A求表 B？
行数 (mu),6
列数 (nu),7
非零元 (tu),7
M的三元表存储结构 用 C语言定义三元组表
#define MAXSIZE 12500
typedef struct {
int i,j;//非零元行、列下标
ElemType e;
} Triple; //定义三元组
typedef struct {
Triple data[MAXSIZE+1];
int mu,nu,tu;
} TSMatrix; //定义三元组表
TSMatrix M;
-7 4 6
182 5
2434
1463
-3 13
931
1321
行数 (mu),6
列数 (nu),7
非零元 (tu),7
-7 4 6
182 5
2434
1463
-3 13
931
1321
行数 (mu),7
列数 (nu),6
非零元 (nu),7
-7 6 4
185 2
2443
1436
-3 31
913
1312
行、列互换不符合以行为主的存放
M的三元表存储结构 T的三元表存储结构行数 (mu),6
列数 (nu),7
非零元 (tu),7
-7 4 6
182 5
2434
1463
-3 13
931
1321
M的三元表存储结构 T.mu=M.nu;T.nu=M.Mu; T.tu=M.tu;
if (T.tu) {
q=1; /*指示向 T写时的位置 */
for(col=1;col<=M.nu; ++col)
for(p=1;p<=M.tu;++p) /*扫描 M三元表 */
if(M.data[p].j==col) /*当前行 */
{T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
q++; }
}
return OK;
算法 1：
时间复杂度,
O(mu*nu)
col 1 2 3 4 5 6 7
num[col] 1 2 2 1 0 1 0
cpot[col] 1 2 4 6 7 7 8
cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1] 2≤col≤a.nu
for(p=1;p<=M.tu;++p) /*扫描 M三元表 */
{col=M.data[p].j; /*确定当前元素列号 */
q=cpot[col]; /*确定当前元素 M.data[p]
在 T的当前存放位置 */
T.data[q].j=M.data[p].i; T.data[q].i=M.data[p].j;
T.data[q].e=M.data[p].e;
++cpot[col]; /*T的当前列指示下一空位置 */
}
算法 2：
时间复杂度,
O(nu+tu)
2.十字链接表例 稀疏 矩阵 25 0 0 64
0 -8 0 0
20 0 0 0
M=
3 1 20
∧ ∧
2 2 -8
∧ ∧
1 4 64
∧ ∧
1 1 25
∧
i j v
行号 列号 值下一行的非 0元素下一列的非 0元素列头指针数组行头指针数组
5.4 广义表 (generalized list),列表 (lists)
5.4.1广义表的定义和术语
n(n≥ 0)个数据元素或广义表的一个有限序列叫做 广义表 。
记作,LS=(e1,e2,...,en)。 n为 LS的长度。
其中,
LS----广义 表名
ei----单元素、原子,约定用小写,1≤ i≤n
ei----广义表，约定用大写,1≤ i≤n
(1)空表 LS=( ),n=0
(2)非空表 LS=(e1,e2,...,en) n>0
其中,
e1---LS的 表头 /首部,记作,Head(LS)=e1
(e2,...,en)--- LS的 表尾 /尾部,记作：
Tail(LS)=(e2,...,en)
例
(1) A=( ) // 空表
(2) B=(e)
Head(B)=e Tail(B)=( )
(3) C=(a,b,c)
Head(C)=a Tail(C)=(b,c)
Head(Tail(C))=b Tail(Tail(C))=(c)
(4) D=(a,(b,c))
Head(D)=a Tail(D)=((b,c))
D2=((a,b),c)
Head(D2)=(a,b) Tail(D2)=(c)
(5) E=((a,b),c,(d,e))
Head(E)=(a,b) Tail(E)=(c,(d,e))
Head(Tail(E))=c Tail(Tail(E))=((d,e))
(6) F=(A,B,C,d)=(( ),(e),(a,b,c),d)
Head(F)=( ) Tail(F)=((e),(a,b,c),d)
(7) G=(a,G) //递归广义表
=(a,(a,G))=(a,(a,(a,G)))
=(a,(a,(a,(a,...G))))
Head(G)=a Tail(G)=(G)=((a,G))
(8) H=(( ),(( ),( )))
Head(H)=( ) Tail(H)=((( ),( )))
5.4.2 广义表的图型表示 ----树型结构约定 □ ----单元素 /原子
○ ----列表,若有表名,附表名例 (1) A=( ) (2) B=(a)
A B
a
(3) C=(a,b,c) (4) D=(a,(b,c))
C
b
B
aca
b c
(5) E=((a,b),c,(d,e)) (6) F=(A,B,C,d)=(( ),(e),(a,b,c),d)
E
b
c
a ed a
d
e cb
F
BA C
(7) G=(a,G) (8) H=(( ),(( ),( )))
HG
a
a
G
a
G
...
5.4.3 广义表的操作
1.求长度,Leng(LS)
a=( ) Leng(A)=0
G=(a,G) Leng(G)=2
H=(( ),(( ),( ))) Leng(H)=2
F=(A,B,C,d) Leng(F)=4
2.求表头,Head(LS)
G=(a,G) Head(G)=a
E=((a,b),c,(d,e)) Head(E)=(a,b)
3.求表尾,Tail(LS)
G=(a,G) Tail(G)=(G)=((a,G))
E=((a,b),c,(d,e)) Tail(E)=(c,(d,e))
4.求第 i个元素,GetElem(LS,i)=ei 1≤ i≤n
I=((a,b),c,( ),(d))
GetElem(I,1)=(a,b) Get(I,2)=C
GetElem(E,3)=( ) Get(I,4)=(d)
5.求 深度,Depth(LS)---LS所含括号的层数
(1) A=( ) Depth(A)=1
(2) E=((a,b),c,(d,e)) Depth(E)=2
(3) H=(( ),(( ),( ))) Depth(H)=3
6.插入,InsertFirst(LS,e)---e插入 LS的第一个位置设 A=( )
执行,InsertFirst(A,a)；
得,A=(a)
执行,InsertFirst(A,(b,(c)))；
得,A=((b,(c)),a)
执行,InsertFirst(A,( ))；
得,A=(( ),(b,(c)),a)
7.其它,......
5.5 广义表的存储结构广义表的的元素具有结构，一般用链式存储结构。
tag=1 hp(表头） tp(表尾 )tag=0 atom(元素 )
原子结点,列表结点,
typedef struct GLNode{
ElemTag tag;
union { AtomType atom;
struct { struct GLNode *hp,*tp; }ptr;
}
} *GList;
(1) A=( )
(2) B=(e)
(3) C=(a,b,c)
A=NULL 1 ^
0 e
B
1
0 a
C 1
0 b
1 ^
0 c
家庭作业
1。已知二维数组 A[4][6]，其每个元素占三个存储单元，且
A[0][0]的存储地址为 1200，试求元素 A[2][4]的存储地址
（分别讨论以行为主和以列为主进行分配时的结论）。该数组共占用多少存储单元。
2。 1。已知稀疏矩阵 A[6][5]如下所示，试写出它的三元组表和十字链表。
0 1 0 0 5
4 0 0 0 0
0 0 0 7 0
0 6 0 0 0
8 0 9 0 0
0 0 0 0 0
华中科技大学计算机学院 (5)数据结构第五章 数组和广义表引言：
线性表,L=(a1,a2,...,an),ai是 同类型的元素,1≤ i≤n
数组,A=(a1,a2,...,an)
若 ai是同类型的元素,A是 一维数组,1≤ i≤n
若 ai是同类型的定长线性表,A是多 维数组,1≤ i≤n
广义表,Ls=(a1,a,...,an)
ai可以是同类型的元素或不定长的线性表,1≤ i≤n
5.1 数组及其操作简单地说，向量和矩阵称为 数组 。
5.1.1 数组的递归定义
1.一维数组 是一个定长线性表 (a1,a2,...,an )。
其中,ai为元素,i为下标 /序号,1≤ i≤n
(a1,a2,...,an )又称为向量。
2.二维数组 是一个定长线性表 (?1,?2,...,?m)，
其中,?i=(ai1,ai2,...,ain)为行向量,1≤ i≤m
由 m个 行向量组成,记作：
( a11 a12,.,a1n )
( a21 a22,.,a2n )
............
( am1 am2,.,amn )
Am*n=
即 Am*n=((a11 a12,..a1n),(a21 a22,..a2n),...,(am1 am2,..amn))
或由 n个列 向量组成,记作：
a11 a12 a1n
a21 a22 a2n
am1 am2 amn
Amxn=
3.三维数组 是一个定长线性表 (?1,?2,...,?p )。
其中,?k=(?1,?2,...,?m )为定长二维数组,1≤ k≤p
例 三维数组 A[1..3,1..4,1..2],p=3,m=4,n=2
a111 a112
a121 a122
a131 a132
a141 a142
a211 a212
a221 a222
a231 a232
a241 a242
a311 a312
a321 a322
a331 a332
a341 a342
第 1页第 2页第 3页
5.1.2 数组的类型定义和变量说明：
例 1 int a[10]； //10个整数的一维数组
char b[4][5]； //4行 5列个字符的二维数组
float c[3][4][2]； //3*4*2个实数的三维数组
A3*4*2 =
例 2 #define m 4 //定义符号常量 m
#define n 5 //定义符号常量 n
int a[m]； //m个整数的一维数组
char b[m][n]； //m行 n列个字符的二维数组例 3 #define m 4 //定义符号常量 m
#define n 5 //定义符号常量 n
typedef int ara[m]； //一维数组类型 ara
typedef char arb[m][n]； //二维数组类型 arb
ara a； //ara类型的变量 a
arb b； //arb类型的变量 b
C语言中定义静态 数组时,元素数目必须是常量错例 1 int m=4,n=5；
int a[m][n]； //m,n是变量错例 2 int p；
scanf(”%d”,&p)；
int c[p]； //p是变量
5.1.3 数组的操作
1.生成一个数组,int a[7]； //生成静态一维数组 (存储结构）
2.销毁一个数组
3.赋值 /修改
a[1]=15； (a[1])++；
4.取元素的值,
a[0]=a[1]*2；
5.1.4 程序设计举例例 1 main()
{ int i,a[10]； //生成一维数组 a
for (i=0； i<10； i++)
scanf(”%d”,&a[i])； //输入元素
for (i=0； i<10； i++)
printf(”%d,,a[i]*a[i])； //输出元素的平方
}
a
0 1 2 3 4 5 6
32 16a
0 1 2 3 4 5 6
例 2 生成动态的 10个整数的一维数组
int *pa； //指针变量 pa
pa=(int *)malloc(10*sizeof(int))； //动态数组 pa*
main()
{ int i,n,*pa；
scanf(”%d”,&n)； //动态输入 n
pa=(int *)malloc(n*sizeof(int))； //生成动态数组 *pa
for (i=0； i<n； i++)
*(pa+i)=2*i； //指针法引用数组元素,赋值
for (i=0； i<n； i++)
printf(“%d,”,*(pa+i))； //输出数组元素 0,2,4,6,...
for (i=0； i<n； i++)
scanf(“%d”,&pa[i])； //下标法引用数组元素,输入
for (i=0； i<n； i++)
printf("%d,",pa[i])； //输出数组元素
free(pa)； //释放 (销毁 )数组空间
}
pa →
0 1 2 3 4 5 6 7 8 9
5.2数组的顺序表示和实现
5.2.1顺序表示 (顺序存储结构）
1.以行序为主序的顺序存储方式左边的下标后变化，右边的下标先变化
2.以列序为主序的顺序存储方式左边的下标先变化，右边的下标后变化例 1 二维数组 a[1..3,1..2],b是首地址,s是元素所占的单元数
a11 a12
a21 a22
a31 a32
a11
a12
a21
a22
a31
a32
a11
a21
a31
a12
a22
a32
序号 内存 地址
1
2
3
4
5
6
1
2
3
4
5
6
序号 内存 地址
b
b+s
b+2*s
b+3*s
b+4*s
b+5*s
b
b+s
b+2*s
b+3*s
b+4*s
b+5*s
以行序为主序 以列序为主序逻辑结构例 2 三维数组 a[1..2,1..3,1..2]
a111 a112
a121 a122
a131 a132
a111
a112
a121
a122
a131
a132
a211
a212
a221
a222
a231
a232
序号 内存 地址
1
2
3
4
5
6
7
8
9
10
11
12
序号 内存 地址
b
b+s
b+2*s
b+3*s
b+4*s
b+5*s
b+6*s
b+11*s
b
b+s
b+2*s
b+3*s
b+4*s
b+5*s
b+6*s
b+11*s
以行序为主序 以列序为主序逻辑结构
a211 a212
a221 a222
a231 a232
第 1页第 2页
1
2
3
4
5
6
7
8
9
10
11
12
a111
a211
a121
a221
a131
a231
a112
a212
a122
a222
a132
a232
5.2.2数组的映象函数数组元素的存储地址例 1 一维数组 a[0..n-1]
设,b为首地址,s为每个元素所占的存储单元数则,元素 a[i]的 存储地址,
Loc(i)=Loc(0)+i*s=b+i*s 0≤ i≤n -1
a(n-1)...ai...a2a1a0
下标 0 1 2 i n-1
地址 b b+s b+2*s b+i*s b+(n-1)*s
a1 a2 a3,.,ai,.,an
下标 1 2 3 i n
地址 b b+s b+2s b+(i-1)s b+(n-1)s
例 2 一维数组 a[1..n]
元素 a[i]的 存储地址
Loc(i)=Loc(1)+(i-1)*s=b+(i-1)*s 1≤ i≤n
例 3 二 维数组 a[1..m,1..n],假定无零行零列
a11,.,a1j,.,a1n
.................
ai1,.,aij,.,ain
.................
am1,.,amj,.,amn
Amxn=
(1)以行序为主序,a[i][j]的地址为
Loc(i,j)=Loc(1,1)+(n*(i-1)+j-1)*s
=b+(n*(i-1)+j-1)*s 1≤ i≤m,1 ≤ j≤n
其中,b为首地址,s为每个元素所占的存储单元数
n:列数 m:行数共 i-1行共 j-1列例 3 二 维数组 a[1..m,1..n],假定无零行零列
a11 a12,.,a1j,.,a1n
............,.....
ai1 ai2,.,aij,.,ain
........,.........
am1 am2,.,amj,.,amn
Amxn=
(2)以列序为主序,a[i][j]的地址为
Loc(i,j)=Loc(1,1)+(m*(j-1)+i-1)*s
=b+(m*(j-1)+i-1)*s 1≤ i≤m,1 ≤ j≤n
其中：
b为首地址,s为每个元素所占的存储单元数
n,列数 m,行数共 i-1行共 j-1列例 4 二 维数组 a[0..m-1,0..n-1]（有零行零列）
a00,.,a0j,.,a0n-1
a10,.,a1j,.,a1n-1
....................
ai0,.,aij,.,ain-1
....................
am-10,.,am-1j,.,am-1n-1
Amxn=
(1)以行序为主序,a[i][j]的地址为
Loc(i,j)=Loc(0,0)+(n*i+j)*s
=b+(n*i+j)*s 0≤ i≤m -1,0≤ j≤n -1
其中：
b为首地址,s为每个元素所占的存储单元数
n,列数 m,行数共 i行共 j列例 4 二 维数组 a[0..m-1,0..n-1]（有零行零列）
a00 a01,.,a0j,.,a0n-1
a10 a11,.,a1j,.,a1n-1
.........,..,........
ai0 ai1,.,aij,.,ain-1
.........,..,.......
am-10 am-11,..am-1j,.,am-1n-1
Amxn=
(2)以列序为主序,a[i][j]的地址为
Loc(i,j)=Loc(0,0)+(m*j+i)*s
=b+(m*j+i)*s 0≤ i≤m -1,0≤ j≤n -1
其中：
b为首地址,s为每个元素所占的存储单元数
n,列数 m,行数共 i行共 j列例 5 三 维数组 a[1..p,1..m,1..n],假定无 0页 0行 0列
1)以行序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(1,1,1)+(m*n*(k-1)+n(i-1)+j-1)*s
=b+(m*n*(k-1)+n(i-1)+j-1)*s
1≤ k≤p,1 ≤ i≤m,1 ≤ j≤n
其中：
b为首地址,s为每个元素所占的存储单元数
p---页数 n--列数 m-行数
(2)以列序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(1,1,1)+(p*m*(j-1)+p*(i-1)+k-1)*s
=b+(p*m*(j-1)+p*(i-1)+k-1)*s
1≤ k≤p,1 ≤ i≤m,1 ≤ j≤n
其中：
b为首地址,s为每个元素所占的存储单元数
p---页数 n--列数 m-行数例 5 三 维数组 a[0..p-1,0..m-1,0..n-1],
(1)以行序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(0,0,0)+(m*n*k+n*i+j)*s
=b+(m*n*k+n*i+j)*s
0≤ k≤p -1,0≤ i≤m -1,0≤ j≤n -1
其中：
b为首地址,s为每个元素所占的存储单元数
p---页数 n--列数 m-行数
(2)以列序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(0,0,0)+(p*m*j+p*i+k)*s
=b+(p*m*j+p*i+k)*s
0≤ k≤p -1,0≤ i≤m -1,0≤ j≤n -1
其中：
b为首地址,s为每个元素所占的存储单元数
p---页数 n--列数 m-行数
5.3 矩阵的压缩存储
5.3.1特殊 矩阵的压缩存储
1,n阶对称 矩阵
a11 a1n
aji
aij
an1 ann
Anxn=
上三角下三角
aij==aji
1≤ i,j≤n
假定以行序为主，顺序存储下三角元素到 SA[1..maxleng]：
a11 a21 a22 a31,..ai1,..aij,..aii,..an1,..ann
k=1 2 3 4,.,i(i-1)/2+j,.,n(n+1)/2
如何求 aij在 SA中的位置，即序号 k？
(1) 设 aij在下三角,i≥ j
∵ 第 1?i-1行共有元素
1+2+3+… (i-1)=i(i-1)/2 (个 )
ai1?aij共有 j个元素
∴ aij的序号为,
k=i(i-1)/2+j
(2) 设 aij在上三角,i<j
∵ 上三角的 aij=下三角的 aji
下三角的 aji的序号为
k=j(j-1)/2+i i<j
∴ 上三角的 aij的序号为
k=j(j-1)/2+i i<j
由 (1)和 (2)，任意 aij在 SA中 的序号，为
i(i-1)/2+j i≥ j
j(j-1)/2+i i<j
称为在 SA中的映象函数，下标转换公式
k(i,j)=
2.三对角矩阵
a11 a12
a21 a22 a23
a32 a33 a34
..,aij....,
an-1n-1an-1n
ann-1 ann
Anxn=
全 0
全 0
假定以行序为主，顺序存储非 0元素到 SA[1..maxleng]：
a11 a21 a22 a23 a32 a33,.,aij,..ann-1 ann
k=1 2 3 4 5 6,.,?,.,3n-2
任意 aij≠ 0,在 SA中 的序号,
k= (3*(i-1)-1)+(j-i+2) = 2(i-1)+j
5.3.2 稀疏 矩阵的压缩存储
1.三元组表例 稀疏 矩阵 M及其转置 矩阵 T
0 13 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
0 0 0 -7 0 0 0
0 0 -3 0 0 0
13 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 0 14 0 0 0
0 0 0 0 0 0
M=
T=
1 2 13
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 4 -7
i j v=aij
1 3 -3
2 1 13
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
i j v=aij
M的三元组表
T的三元组表表 A
表 B
问题,如何由 矩阵 M求 矩阵 T,即由表 A求表 B？
行数 (mu),6
列数 (nu),7
非零元 (tu),7
M的三元表存储结构 用 C语言定义三元组表
#define MAXSIZE 12500
typedef struct {
int i,j;//非零元行、列下标
ElemType e;
} Triple; //定义三元组
typedef struct {
Triple data[MAXSIZE+1];
int mu,nu,tu;
} TSMatrix; //定义三元组表
TSMatrix M;
-7 4 6
182 5
2434
1463
-3 13
931
1321
行数 (mu),6
列数 (nu),7
非零元 (tu),7
-7 4 6
182 5
2434
1463
-3 13
931
1321
行数 (mu),7
列数 (nu),6
非零元 (nu),7
-7 6 4
185 2
2443
1436
-3 31
913
1312
行、列互换不符合以行为主的存放
M的三元表存储结构 T的三元表存储结构行数 (mu),6
列数 (nu),7
非零元 (tu),7
-7 4 6
182 5
2434
1463
-3 13
931
1321
M的三元表存储结构 T.mu=M.nu;T.nu=M.Mu; T.tu=M.tu;
if (T.tu) {
q=1; /*指示向 T写时的位置 */
for(col=1;col<=M.nu; ++col)
for(p=1;p<=M.tu;++p) /*扫描 M三元表 */
if(M.data[p].j==col) /*当前行 */
{T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
q++; }
}
return OK;
算法 1：
时间复杂度,
O(mu*nu)
col 1 2 3 4 5 6 7
num[col] 1 2 2 1 0 1 0
cpot[col] 1 2 4 6 7 7 8
cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1] 2≤col≤a.nu
for(p=1;p<=M.tu;++p) /*扫描 M三元表 */
{col=M.data[p].j; /*确定当前元素列号 */
q=cpot[col]; /*确定当前元素 M.data[p]
在 T的当前存放位置 */
T.data[q].j=M.data[p].i; T.data[q].i=M.data[p].j;
T.data[q].e=M.data[p].e;
++cpot[col]; /*T的当前列指示下一空位置 */
}
算法 2：
时间复杂度,
O(nu+tu)
2.十字链接表例 稀疏 矩阵 25 0 0 64
0 -8 0 0
20 0 0 0
M=
3 1 20
∧ ∧
2 2 -8
∧ ∧
1 4 64
∧ ∧
1 1 25
∧
i j v
行号 列号 值下一行的非 0元素下一列的非 0元素列头指针数组行头指针数组
5.4 广义表 (generalized list),列表 (lists)
5.4.1广义表的定义和术语
n(n≥ 0)个数据元素或广义表的一个有限序列叫做 广义表 。
记作,LS=(e1,e2,...,en)。 n为 LS的长度。
其中,
LS----广义 表名
ei----单元素、原子,约定用小写,1≤ i≤n
ei----广义表，约定用大写,1≤ i≤n
(1)空表 LS=( ),n=0
(2)非空表 LS=(e1,e2,...,en) n>0
其中,
e1---LS的 表头 /首部,记作,Head(LS)=e1
(e2,...,en)--- LS的 表尾 /尾部,记作：
Tail(LS)=(e2,...,en)
例
(1) A=( ) // 空表
(2) B=(e)
Head(B)=e Tail(B)=( )
(3) C=(a,b,c)
Head(C)=a Tail(C)=(b,c)
Head(Tail(C))=b Tail(Tail(C))=(c)
(4) D=(a,(b,c))
Head(D)=a Tail(D)=((b,c))
D2=((a,b),c)
Head(D2)=(a,b) Tail(D2)=(c)
(5) E=((a,b),c,(d,e))
Head(E)=(a,b) Tail(E)=(c,(d,e))
Head(Tail(E))=c Tail(Tail(E))=((d,e))
(6) F=(A,B,C,d)=(( ),(e),(a,b,c),d)
Head(F)=( ) Tail(F)=((e),(a,b,c),d)
(7) G=(a,G) //递归广义表
=(a,(a,G))=(a,(a,(a,G)))
=(a,(a,(a,(a,...G))))
Head(G)=a Tail(G)=(G)=((a,G))
(8) H=(( ),(( ),( )))
Head(H)=( ) Tail(H)=((( ),( )))
5.4.2 广义表的图型表示 ----树型结构约定 □ ----单元素 /原子
○ ----列表,若有表名,附表名例 (1) A=( ) (2) B=(a)
A B
a
(3) C=(a,b,c) (4) D=(a,(b,c))
C
b
B
aca
b c
(5) E=((a,b),c,(d,e)) (6) F=(A,B,C,d)=(( ),(e),(a,b,c),d)
E
b
c
a ed a
d
e cb
F
BA C
(7) G=(a,G) (8) H=(( ),(( ),( )))
HG
a
a
G
a
G
...
5.4.3 广义表的操作
1.求长度,Leng(LS)
a=( ) Leng(A)=0
G=(a,G) Leng(G)=2
H=(( ),(( ),( ))) Leng(H)=2
F=(A,B,C,d) Leng(F)=4
2.求表头,Head(LS)
G=(a,G) Head(G)=a
E=((a,b),c,(d,e)) Head(E)=(a,b)
3.求表尾,Tail(LS)
G=(a,G) Tail(G)=(G)=((a,G))
E=((a,b),c,(d,e)) Tail(E)=(c,(d,e))
4.求第 i个元素,GetElem(LS,i)=ei 1≤ i≤n
I=((a,b),c,( ),(d))
GetElem(I,1)=(a,b) Get(I,2)=C
GetElem(E,3)=( ) Get(I,4)=(d)
5.求 深度,Depth(LS)---LS所含括号的层数
(1) A=( ) Depth(A)=1
(2) E=((a,b),c,(d,e)) Depth(E)=2
(3) H=(( ),(( ),( ))) Depth(H)=3
6.插入,InsertFirst(LS,e)---e插入 LS的第一个位置设 A=( )
执行,InsertFirst(A,a)；
得,A=(a)
执行,InsertFirst(A,(b,(c)))；
得,A=((b,(c)),a)
执行,InsertFirst(A,( ))；
得,A=(( ),(b,(c)),a)
7.其它,......
5.5 广义表的存储结构广义表的的元素具有结构，一般用链式存储结构。
tag=1 hp(表头） tp(表尾 )tag=0 atom(元素 )
原子结点,列表结点,
typedef struct GLNode{
ElemTag tag;
union { AtomType atom;
struct { struct GLNode *hp,*tp; }ptr;
}
} *GList;
(1) A=( )
(2) B=(e)
(3) C=(a,b,c)
A=NULL 1 ^
0 e
B
1
0 a
C 1
0 b
1 ^
0 c
家庭作业
1。已知二维数组 A[4][6]，其每个元素占三个存储单元，且
A[0][0]的存储地址为 1200，试求元素 A[2][4]的存储地址
（分别讨论以行为主和以列为主进行分配时的结论）。该数组共占用多少存储单元。
2。 1。已知稀疏矩阵 A[6][5]如下所示，试写出它的三元组表和十字链表。
0 1 0 0 5
4 0 0 0 0
0 0 0 7 0
0 6 0 0 0
8 0 9 0 0
0 0 0 0 0
