1
第五章 数组和广义表
数组和广义表的定义
数组和广义表的基本运算
数组的存储结构
广义表的存储结构
数
据
结
构
之
数
组
和
广
义
表
2
5. 1 数组的概念
?数组：是一种线性数据结构，它是有
限个相同类型数据元素的有序集合。
?数组的数据元素是值和下标的偶对，
对每个有定义的下标，都有一个相关
连的值。
a
11
a
12
… a
1n
A
mxn
＝ a
21
a
22
… a
2n
··
a
m1
a
m2
… a
mn
2
数
据
结
构
之
数
组
和
广
义
表
3
?基本操作：两种主要的运算：
（ 1）给定一组下标，读取相应的数据
元素；
GetValue( A, &e, i, j )
（ 2）修改元素值。
ChangeValue(A, e , i , j )
?数组一般不作插入和删除操作。
数
据
结
构
之
数
组
和
广
义
表
4
5. 2 数组的顺序表示和实现
? 逻辑多维到存储一维的映射，即寻找多维下标和
一维下标的关系。
? 存储方式
? 行序为主序的存储方式
? 以列序为主序的存储方式
a
11
:
a
1n
a
21
:
a
2n
:
a
mn
A
1
[1]
a
11
:
a
m1
a
12
:
a
m2
:
a
mn
A
1
[1]
以行为主
以列为主
3
数
据
结
构
之
数
组
和
广
义
表
5
? 数组元素的存储位置是其下标的线
性函数，存取数组中任一元素的时
间相等，所以，数组是随机的存储
结构。
数
据
结
构
之
数
组
和
广
义
表
6
? 计算一维下标
? 以二维数组 A[n][m]为例，计算数组元素
A[i][j] 的存储空间下标 w:
? 以行序为主序的存储方式
w=i*m+j
? 以列序为主序的存储方式
w= j*n+i
? 有三维数组 A[3][4][5],计算数组元素
A[2][3][3]的存储空间下标：以行序为主
w=2*(4*5)+3*5+3=58
4
数
据
结
构
之
数
组
和
广
义
表
7
? 数组的顺序存储表示和实现
typedef struct{
ElemType *base;
int dim ;
int *bounds ; //数组维界基址
int *constants ;//数组映象函数 (Page93的式 (5-2))
}Array; 常量 Ci基址， Cn=L=1,Ci-1 =bi*Ci;
第一维界 第二维界 第三维界 第四维界
bounds
2 (块 ) 5 (页 ) 3 (行 ) 4 (列 )
constants 5*12=60 3*4=12 4*1=4 1
c1=b2*c2 c2=b3*c3 c3=b4*c4 c4=1
数
据
结
构
之
数
组
和
广
义
表
8
? 数组的算法实现
#include <stdarg.h>
typedef void *va_list;
#define va_start(ap, parmN) (ap = ...)
#define va_arg(ap, type) (*((type *)(ap))++)
#define va_end(ap)
va_list ap;
va_start(ap,dim):使ap 指向dim后面的实参表；
va_arg(ap,int):取出ap所指向的int型数据后，
ap++。
va_end(ap):空语句
5
数
据
结
构
之
数
组
和
广
义
表
9
main( )
{ Array A ; int dim=4;
InitArray( A , dim , 2 , 5 , 3 , 4 );
……
}
数
据
结
构
之
数
组
和
广
义
表
10
Status InitArray(Array &A , int dim , ...){
if (dim<1 || dim>8 ) return ERROR ;
A.dim=dim;
A.bounds=(int*)malloc(dim*sizeof(int));
if( !A.bounds) exit(OVERFLOW);
elemtotal=1;
va_start(ap,dim);
for(i=0 ; i<dim ; i++){
A.bounds[i]=va_arg(ap , int );
if(A.bounds[i]<1) return UNDERFLOW;
elemtotal*=A.bounds[i]; }
va_end(ap) ;
6
数
据
结
构
之
数
组
和
广
义
表
11
A.base=(ElemType*)malloc(elemtotal*sizeof(ET));
if( ! A.base) exit(OVERFLOW);
A.constants=(int *)malloc(dim *sizeof(int));
if( !A.constants) exit(OVERFLOW);
A.constants[dim-1]=1;
for(i=dim-2 ; i >=0 ; i--)
A.constants[i]=A.constants[i+1]*A.bounds[i+1];
return OK; }
数
据
结
构
之
数
组
和
广
义
表
12
5. 3 特殊矩阵的压缩存储
?特殊矩阵：数值相同的元素或零元素
在矩阵中的分布有一定规律。
例：对称矩阵的压缩存储：以行序为主
序存储下三角中的元素，包括对角线
上的元素。
a
ij
= a
ji
1<= i, j <= n
7
数
据
结
构
之
数
组
和
广
义
表
13
(1) 二维下标为 ( i , j ),存储空间的一维下标
为 k，给出 k与 i , j 的关系（ 1<= i, j <= n ,
0<= k < n*(n+1)/2);
k=(i-1)*i/2+j-1 ( i>=j) (i, j)在下三角区
k=(j-1)*j/2+i-1 (i< j) (i, j)在上三角区
int ij_TO_k(int i , int j){
if( i<1 || j<1 )return(-1);
if(i>=j) return((i-1)*i/2+j-1);
return ((j-1)*j/2+i-1); }
数
据
结
构
之
数
组
和
广
义
表
14
(2)输入并存储对称矩阵的算法 (以行序为主序 )
void Input(ET A[ ], int n){
for(k=0;k<(n+1)*n/2; k++)
scanf(&A[k]); }
(3)读取对称矩阵中某个元素的算法 :
Status GetElem(ET A[ ], int i, int j , ET &e) {
if(k=ij_TO_k(i , j)>=0){
e=A[k];return OK; }
else return ERROR; }
8
数
据
结
构
之
数
组
和
广
义
表
15
(4)修改对称矩阵中某元素的算法 :
Status Change(ET A[ ] ,int i, int j, ET e){
if(k=ij_TO_k(i , j)>=0) {
A[k]=e; return OK;
}
else return ERROR;
}
数
据
结
构
之
数
组
和
广
义
表
16
(5)输出打印对称矩阵的算法 :
void PrintPro( ET A[ ], int n){
for(i=1;i<=n;i++){
printf(“\n”);
for(j=1;j<=n;j++) {
GetElem(A, i, j, e);
printf(“%3d ”,e) ; }
}
}
9
数
据
结
构
之
数
组
和
广
义
表
17
思考题
上三角矩阵、下三角矩
阵、对角矩阵、等特殊矩
阵的压缩存储和相关的算
法描述。
数
据
结
构
之
数
组
和
广
义
表
18
?稀疏矩阵及其存储结构
? 定义：如果一个 m*n 矩阵的非零元素
个数 r比零元个数少，且非零元的分布
没有一定规律。
? 压缩存储：只存储稀疏矩阵的非零元素。
10
数
据
结
构
之
数
组
和
广
义
表
19
? 稀疏矩阵的三元组表存储方式
typedef struct { int i , j ; ElemType e ;
}Triple ;
Triple *data;
data[0]的三元分别用于存放矩阵总的行数、列
数和非零元个数；用三元组表示的非零元以行序
为主序依次存放在data中。
数
据
结
构
之
数
组
和
广
义
表
20
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
? 转置算法一
a i j v b i j v
由a求其转置矩阵b，需做以下事情：
⑴ 矩阵的行列值互换，即若a为 m×n,则 b为 n×m；
⑵ 每个三元组的行列号互换，即a
ij
对应于 b
ji
；
⑶ a中三元组以原矩阵的行号为序，而b中三元组是
以原矩阵的列号为序。
11
数
据
结
构
之
数
组
和
广
义
表
21
Statue TranSM( Triple A[ ] , Triple &B[ ]){
B[0].i=A[0].j; B[0].j=A[0].i; B[0].e=A[0].e ;
if( A[0].e){ k=1; //B 数组的下标
for(col=1;col<=A[0].j;col++)
for(p=1;p<=A[0].e;p++) //p是 A数组的下标
if(col==A[p].j){
B[k].i=A[p].j; B[k].j=A[p].i;
B[k].e=A[p].e ; k++;}
}
return OK ;
}
该方法实现直观、易理解，时间复杂度为 O(a.nu*a.tu)。
数
据
结
构
之
数
组
和
广
义
表
22
?快速转置
?算法思想
?设置num[l..a.nu]和cpot[l..a.nu]两个辅助向量；
?在a.data中求矩阵M的每一列中非零元素个数，存于辅
助向量num的对应列中；
?用递推公式算出每一列第一个非零元素在b.data中的
位置，存于辅助向量cpot的对应列中，递推公式为：
cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1],
col=2..a.nu
?依次对a.data中的三元组进行转置，并按三元组的列
号，从cpot的对应列取出该三元组应存放在b.data中
的位置，然后将cpot该列中的值加1，使其记载该列下
一非零元素在b.data中的位置。
12
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
a i j v
1 2 3 4 5 6 7
num 2 2 2 1 0 1 0
cpot 1 3 5 7 8 8 9
用递推公式算出每一列第一个非零元素在
b.data中的位置，存于辅助向量cpot的对
应列中， cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1],
col=2..a.nu
数
据
结
构
之
数
组
和
广
义
表
24
Status FastTranSM(Triple A[],Triple &B[]){
B[0].i=A[0].j; B[0].j=A[0].i ; B[0].e=A[0].e ;
if( A[0].e) { cpot[1]=1;
for(col=1;col<=A[0].j;col++) num[col]=0;
for(p=1;p<=A[0].e;p++) num[A[p].j]++;
for(col=2;col<=A[0].j;col++)
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=A[0].e;p++){
col =A[p].j; k =cpot[col]++;
B[k].i=A[p].j; B[k].j=A[p].i; B[k].e=A[p].e ; }
} return OK; }
该方法称为快速转置，时间复杂度为 O(a.nu+a.tu)。
13
数
据
结
构
之
数
组
和
广
义
表
25
? 稀疏矩阵的十字链表的存储方式
?参见 Page 103的叙述；
?结点包含的数据域有：非零元的三元组、行向后
继指针 right、列向后继指针 down。
typedef struct OLN{
int i , j ; ElemType e ;
struct OLN *right , *down ;
}OLNode;
链域down:链接同一列中下一个非零元；
链域right:链接同一行中下一个非零元；
稀疏矩阵中同一列的非零元通过down链接成
一个链表，同一行的非零元通过right链接
成一个链表。
i j e
down right
数
据
结
构
之
数
组
和
广
义
表
26
? 例：用十字链表表示下面的矩阵。
?
?
?
?
?
?
?
?
?
?
?=
0002
0010
5003
M
^^
1 1 3 1 4 5
2 2 -1
3 1 2
^
^^
M.chead
M.rhead
^^
14
数
据
结
构
之
数
组
和
广
义
表
27
十字链表的程序实现
Status CreatLinkmatrix(CrossList M) {
if(M) free(M);
//输入矩阵行，列值和非零元个数
scanf（ &m， &n， &t） ;
M.mu=m; M.nu=n; M.tu=t;
if(!M.rhead=(Olink*)malloc((m+1)*sizeof(Olink))))
return OVERFLOW; //内存分配失败
if(!M.chead=(Olink*)malloc((n+1)*sizeof(Olink))))
return OVERFLOW;
数
据
结
构
之
数
组
和
广
义
表
28
for( scanf(&i,&j,&e); i!=0;scanf(&i,&j,&e)){ //按任意次序输入
非零元
if(!(p=(OLNode*)malloc(sizeof(OLNode))))
return OVERFLOW;
p->i=i; p->j=j; p->e=e; //生成结点
if(M.rhead[i] ==NULL) M.rhead[i]=p; //生成第一个结点
else{
for(q=M.rhead[i]; (q->right) && q->right->j<j; q=q-
>right) ; //寻找插入位置
p->right=q->right; q->right=p; //完成行插入 }
15
数
据
结
构
之
数
组
和
广
义
表
29
if(M.chead[i] = =NULL) M.chead[j]=q; //产生第一个结点
else{
for(q=M.rhead[j]; (q->down) && q->down->i<i; q=q-
>down);
//寻找插入位置
p->down=q->down; q->down=p; //完成列插入
}
}
}
数
据
结
构
之
数
组
和
广
义
表
30
5. 4 广义表的定义
? 广义表：是 n(n>=0)个元素的集合。
LS=(d1 , d2 , d3 , ...... , dn )
? LS为 表名
? d
i
∈D
0
时，称d
i
为 单元素 (用小写字母表示)；
? d
i
∈Lists时,称d
i
为 子表 (用大写字母表示)；
? n为表的长度，当长度为0时称为 空表 ；
? n>0时,第一个元素d
1
为 表头 ;
? n>0时,(d
2
,…,d
n
)称为 表尾 。
16
数
据
结
构
之
数
组
和
广
义
表
31
?. 广义表的长度和深度
? 长度 n:是广义表的元素个数；
? 深度 k:
广义表的元素之间除了存在次
序关系外，还存在层次关系。 广义
表中元素的最大层次 为表的深度。
提示： 元素的层次就是包括该元
素的括号对的数目。
数
据
结
构
之
数
组
和
广
义
表
32
? 广义表举例：
? A= ( ) n= 0 , k =1
? B=(e) n=1 , k=1
? C=(a,(b,c,d)) n=2 , k =2
? D=( A , B , C ) n=3 , k = 3
{ 即D=((),(e),(a,(b,c,d))) }
? E=(a , E ) n=2 , k = ∞
{ 定义一个无限表(a,(a,(a, …))) }
Gethead(C )=a Gethead(D)=A
Gettail(C)=((b,c,d)) Gettail(B)=( )
17
数
据
结
构
之
数
组
和
广
义
表
33
5.5 广义表的链式存储结构
? 结点结构：
typedef struct GLN{
int tag;
union{ AtomType atom;
struct GLN *hp; };
struct GLN *tp;
}*Glist ;
广义链表表头表尾结点表示法 (Page 110)
tag=1 hp tp
tag=0 atom tp
原子结点
表结点
数
据
结
构
之
数
组
和
广
义
表
34
例： 画广义表的存储结构
C=(a,(b,c,(d))) ; n=2 ; k=3
C
1 ^
0 a 1 ^
0 b 0 c
0 d ^
广义表： F=(e,C,( )) , 长度： n=3; 深度： k=4
F
1 ^
0 e 1 1 ^ ^
1 ^
18
数
据
结
构
之
数
组
和
广
义
表
35
例：用存储结构表示广义表达式
A=( ) B=(e) C=(a， (b， c， d))
D=(A， B， C) =(( )， (e)， (a， (b， c， c)))
E=(a. E)=(a， (a， (a， …)))
1 ^ ^A
CB
D
1 ^
1 ^
0 e ^
1 ^ 1 1 ^
E 1 ^
0 a 1 ^
1 ^
1 ^0 a
0 b 0 c 0 d ^
数
据
结
构
之
数
组
和
广
义
表
36
?本章重点
? 一般多维数组的存储及初始化
? 特殊矩阵的存储
? 稀疏矩阵的三元组表示和运算（初始
化和转置）
? 广义表的定义
