第5章数组和广义表

第5章数组和广义表

数组(array)是最常用的数据结构之一。几乎所有的程序设计语言都把数组类型设定为固有类型。数组的定义

线性结构中的数据都是非结构的原子类型，元素的值是不再分解的。而数组可以看成是线性表在下述含义上的扩展：5.1数组的逻辑结构2数组的基本操作表中的数据元素本身也是一种数据结构。

数组是由下标和值组成的序对集合。在数组中，一旦给定下标，都存在一个与其相对应的值，这个值就称为数组元素。

也可以说，数组中的每个数据元素都对应于一组下标（j1

,j2

,…,jn

），每个下标取值范围是1≤ji≤bi，bi称为第i

维的长度（i=1,2,…,n）。显然，当n=1时，n维数组就退化为定长的线性表。反之，n

维数组也可以看成是线性表的推广。3 5.1.1数组的定义

可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。Am×n=a11a21…am1a12a22…am2a13a23…am3…………a1.na2,n…am,n4

例如，下面是一个二维数组，且以m

行n

列的矩阵形式表示。

每个数据元素aj是一个列向量形式的线性表Am×n=…a1,na2,n…am,na13a23…am,3a12a22…am,2a11a21…am,1

二维数组A

还可以看成是一个线性表：A=(α1,α

2,…,α

n)

α

j=(a1j

,a2j

,…,am,j) 1≤j≤n

每个数据元素是一个行向量形式的线性表

B=(β1β2β3…,

βm)Am×n=((a11

a12

…a1,n

),…,(am,1am,2…am,n

))(a21

a22

…a2,n

),…,βi=(ai1,ai2,…,ai,n) 1≤i≤m5 5.1.2数组的抽象类型定义ADTArray{D={aj1j2j3…..jn|n>0,称为数组的维数,ji是数组的第i维下标,1≤ji

≤bi,bi为数组第i维的长度，aj1j2j3…..jn∈ElementSet}数据关系：Ｒ

={R1,R2,…….Rn}Ri=<aj1…ji….jn,aj1…ji+1…jn>|1≤jk≤bk,1≤k≤n且k≠i,1≤ji

≤bi-1,aj1…j2….jn,aj1…ji+1…jn∈D,i=1,…n}基本操作:

InitArray(A,n,bound1,…,boundn);

操作结果：如果维数n

和各维长度合法，则构造 相应的数组A，并且返回TRUE。基本操作

DestroyArray(A):销毁数组A。

GetValue(A,e,index1,…,indexn):

初始条件：A

是n

维数组，e

为元素变量，随后是n

个下标值。 操作结果：若各下标合法，则用e返回数组Ａ中由由index1,…indexn所指定的元素的值.

SetValue(A,e,index1,…,indexn);

初始条件：A

是n

维数组，e

为元素变量，随后是 n

个下标值。 操作结果：若各下标合法，则将数组A中由index1,…indexn所指定的元素的值置为e.

由于内存储器的结构是一维的。一维数组可直接采用顺序存储。用一维的内存存储表示多维数组时，需按某种次序将数组中元素排成一线性序列，再将这个线性序列存放在一维的内存中，即数组的顺序存储结构表示。顺序存储的定位公式5.2数组的顺序存储结构8数组的顺序存储表示基本操作的算法描述

用顺序存储结构来存储数组中的元素，一定要按照某种次序将元素排成一个线性序列。对二维数组可以有两种存储方式：

(1)以列为主序(columnmajororder)的存储方式，即按列优先，逐列顺序存储。

(2)以行为主序(rowmajororder)的存储方式，即按行优先，逐行顺序存储。9 5.2.1顺序存储的定位公式

⑵二维数组的地址计算

假设每个数据元素占C

个存储单元，且以行序为主序的进行存储，则二维数组A

中任一元素aij

的存储位置可以由下面定位公式确定LOC(A[i],[j])=LOC(A[1],[1])+（n*(i-1)+(j-1)）*C其中：

LOC(A[i[,[j]) 是aij

的存储位置；

LOC(A[1],[1]) 是a11

的存储位置，即二维数组A

的起始存储位置，也称为基地址或基址；

n 是数组第二维的长度。10

一般地：LOC(A[i],[j])=LOC(A[s],[t])+（n*(i-s)+(j-t)）*C

⑶三维数组的地址计算

三维数组A(1:r,1:m,1:n)。假设每个数据元素占size个存储单元，且以行序为主序的进行存储，首元素a111的地址为Loc(A[1][1][1]),求任意元素aijk的地址。

显然，ai11地址为

Ｌoc(A[i][1][1])=Loc(A[1][1][1])+(i-1)*m*n,因为在该元素之前有i-1个m*n的二维数组。11不难得到三维数组任意元素aijk的地址：Loc(A[i][j][k])=Loc(A[1][1][1])+((i-1)*m*n+(j-1)*n+(k-1))*size,其中：１≤i≤r,１≤j≤m,１≤k≤n。

矩阵(matrix)是很多科学与工程计算问题中研究的数学对象。在数据结构中，我们感兴趣的不是矩阵本身，而是如何存储矩阵的元素而使矩阵的各种运算能够有效地进行。

在数值分析中经常出现有些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。5.3矩阵的压缩存储12特殊矩阵的压缩存储

所谓压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配空间。13稀疏矩阵的逻辑结构稀疏矩阵的存储结构

假若相同的元素或者零元素在矩阵中的分布有一定规律，则称特殊矩阵。特殊矩阵主要有3种：对称矩阵、三角矩阵、带状矩阵。

在所有这些统称为“特殊矩阵”的矩阵中，非零元的分布都有一个明显的规律，从而都可以将其压缩存储到一维数组中，并且找到每个非零元在一维数组中的对应关系。14 5.3.1特殊矩阵的压缩存储

若一个n

阶矩阵M

中的元满足下述性质1.对称矩阵aij=aji

1≤i，j≤n则称为n

阶对称矩阵。15

一个n

阶方阵，若它的全部非零元素落在一个以对角线为中心的带状区域中，则称该矩阵为带状矩阵，或对角矩阵。这个带状区域若包含主对角线上下各b

条对角线道上元素，那么，b

称为该带状矩阵的半带宽，或称该带状矩阵的带宽为(2b+1)。3.带状矩阵00b

条b

条16带状矩阵中最常见的是三对角带状矩阵。17

特点：当i=1j=1,21<i<n,j=i-1,i,i+1

i=n,j=n-1,n

aij非零，其它元素均为零

a11Ann=a12０00a21a22a23０00a32a33a34０0０a43a44a4500………

1.确定存储该矩阵所需的一维向量空间的大小除第一行和最后一行只有两个元素外，其余各行均有3个非零元素，由此得到一维向量所需的空间大小为：３n-2

2.确定非零元素在一维数组空间中的位置Ｌoc(a[i][j])=Loc(a[1][1])+2(i-1)+j-118

三对角带状矩阵的压缩存储，以行序为主序进行存储，且只存储非零元素。其方法为19

一般来说，当矩阵中非零元素的个数远远小于矩阵元素的总数时，称之为稀疏矩阵。假设在m×n

的矩阵中，若有t

个元素不为零，令

=t/(m×n)，则称

为矩阵的稀疏因子。通常认为

≤0.05

时称为稀疏矩阵。 5.3.2稀疏矩阵的逻辑结构1.稀疏矩阵的定义

按照压缩存储的概念，只存储稀疏矩阵的非零元素。因此，除了存储非零元素的值aij

之外，还必须同时记下它所在矩阵的行i

和列j的位置。反之，一个三元组(i,j,aij)唯一确定了矩阵的一个非零元素。因此，稀疏矩阵可以由表示非零元的三元组及其矩阵的总的行列数唯一确定。

假设以顺序存储结构表示三元组表，则可以得到稀疏矩阵的一种压缩存储方式，这种方式称之为三元组顺序表。20 5.3.3稀疏矩阵的存储结构

1.三元组顺序表012900000000000-3000014000240000018000001500-7000M=

矩阵M

可以由三元组表(1,3,-3)，(1,6,15)，(2,1,12)，(2,5,18)，(3,1,9)，(3,4,24)，(4,6,-7)，(6,3,14)再加上（7,6）这一对总的行列值来描述。21#defineMAXSIZE 1000//假设非零元个数的最大值为1000typedefstruct{ //三元组顺序表的元素结构定义

int row,;col //该非零元的行下标和列下标

ElementTypee; //该非零元的值}//Triple;typedefstruct{ //三元组顺序表存储结构定义

Tripledata[MAXSIZE+1];//非零元三元组表，data[0]未用

int m,n,len; //矩阵的行数、列数和非零个数}//TSMatrix; //三元组顺序表的类型名22(1)三元组顺序存储表示(2)利用三元组顺序表实现矩阵的转置运算

将矩阵的行列值相互交互；

在这3点中，最关键的是第3条，即如何使b.data中的三元组以Ｔ的行（Ｍ的列）为主序依次排列。23

显然，一个稀疏矩阵的转置矩阵仍是稀疏矩阵。假设a

和b

是TSMatrix（三元组顺序表）类型变量，分别表示矩阵Ｍ和其转置矩阵Ｔ。那么，只要做到下面3点就可以由a

得到b，实现矩阵的转置。

将每三元组中的row

和col

相互调换；

重排三元组之间的次序。24原始的三元组表原矩阵012900000000000-3000014000240000018000001500-7000Ｍ=a.data[1]a.data[2]a.data[3]a.data[4]a.data[5]a.data[6]a.data[7]a.data[8]a.data13-3161521122518319342446-76314rowcole转置矩阵00-3001512000180900240000000-70000000014000000000Ｔ=转置的三元组表b.data[1]b.data[2]b.data[3]b.data[4]b.data[5]b.data[6]b.data[7]b.data[8]b.data121213931-3361443245218611564-7rowcole

使b.data中的三元组以T

的行（M

的列）为主序依次排列的方法有如下两种：25

方法一：按照b.data中三元组的次序，依次在a.data中找到相应的三元组进行转置。

方法二：按照a.data中三元组的次序进行转置，并将转置后的三元组置入b.data中恰当的位置。①算法思想

在A中按三元组的列域值(col)开始扫描，依序将三元组a.data的列域值(col

)与行域值(row

)进行对换，并且存入B中。由于A是以M的行序为主序来存放每个非零元的，由此得到转置后矩阵的三元组表B恰是以“行主为主序”。26

按照方法一，即按照“被转置矩阵”M的三元组表A

的“列序”递增顺序进行转置。为了找到矩阵M

的每一列中所有的非零元素，需要对其三元组a.data从第一行起进行扫描，方法如下：

转置的三元组表b.data原始的三元组表a.datai

j

v

1

2

12

1

3

9

3

1

-3

3

6

14

4

3

24

5

2

18

6

1

15

6

4

-727利用三元组顺序表存储实现矩阵的转置j

36151463i

11223346v

-3151218924-714

voidTransposeTSMatrix(TSMatrixA,TSMatrix*B)/*采用三元组表结构，求稀疏矩阵A

的转置矩阵B。在程序中，

{inti,j,k;//j

指示B->data中三元组的序号，i

指示A.data中三元组的序号，

//k指示A的列号（即B的行号）B->m=A.n;

//将稀疏矩阵A

的列数值作为其转置矩阵B

的行数值

B->n=A.m;

//将稀疏矩阵A

的行数值作为其转置矩阵B

的列数值

B->len=A.len;

//转置矩阵B与稀疏矩阵A的非零元个数相等②算法描述(稀疏矩阵“列序”递增转置算法）if(B->len>0){j=1;28for(k=1;k<=A.n;k++) for(i=1;i<=A.len;i++) if(A.data[i].col==k){ //进行转置returnOK;}/*TransposeSMatrix*/ B->data[j].row=A.data[i].col;

//稀疏矩阵A的列域值成为其转置矩阵B

的行域值 B->data[j].col=A.data[i].row;

//稀疏矩阵A

的行域值成为其转置矩阵M

的列域值 B->data[j].e=A.data[i].e;

//将稀疏矩阵M

的非零元值赋给其转置矩阵T

j++;

//B->data中三元组的序号加1 }//if}//if29③算法分析

一般矩阵的转置算法（经典算法）为：30for(col=1;col<=n;++col) for(row=1;row<=m;++row) B[col][row]=B[row][col];时间复杂度为O(m×n)。

前面给出的求转置矩阵算法的主要工作是在i

和k的两重循环中完成的，所以此算法的时间复杂度为O(A.n×A.len)即和矩阵A

的列数和非零元的个数的乘积成正比。31

当矩阵M

中非零元个数几乎和矩阵元素个数相等时，即len

和m×n等数量级时，算法时间复杂度就为O(m×n2)，虽然节省了存储空间，但时间复杂度提高了。由此可见，上述求转置矩阵算法只适合于len<<m×n

的情况。

当矩阵非零元素的位置或个数经常变动时，就不易采用顺序存储结构表示三元组的线性表。例如，在进行“将矩阵

B

加到矩阵A

上”的操作时，由于非零元素的插入或删除将会引起A.data中元素的大量移动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。322.十字链表

(1)稀疏矩阵的十字链表存储表示

矩阵中非零元的行号row；

矩阵中非零元的列号col；

矩阵中非零元的值e；

向右域right，用以链接同一行中下一个非零元；

向下域down，用以链接同一列中下一个非零元。33rowdowncolvalueright非零元行号非零元列号非零元的值向下域向右域

在链表中，矩阵的非零元素可用如下结点表示：typedefstructOLNode{ //结点定义

int row,col; //该非零元的行和列下标

ElementTypevalue; //该非零元的值

structOLNode *right,*down;

//该非零元所在的行表和列表的后继链域}OLNode;*Olink;typedefstruct{ //十字链表定义

int m,n,len; //稀疏矩阵行数、列数和非零元个数

Olink *row_head,*col_head;

//行和列链表头指针向量基址，由CreateSMatrix分配}CrossList; //十字链表存储结构的类型名34

广义表(generalizedlist)

是线性表的推广，有时也称为列表（lists，用复数形式以示与统称的表list的区别）。广泛地应用于人工智能等领域的LISP（表处理语言），把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。355.4广义表广义表的逻辑结构

和数组一样，广义表也可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一种数据结构。36广义表的存储结构37 5.4.1广义表的逻辑结构

广义表一般记作：GL=(a1,a2,…,an)其中：

n

是广义表GL

的长度；

ai

可以是单个元素，也可以是广义表，分别称为广义表GL

的原子和子表，习惯上用大写字母表示广义表的名称，用小写字母表示原子的名称。GL

是广义表(a1,a2,…,an)的名称；1.广义表的定义

例5-1

A=()，A

是一个空表，它的长度为零。

例5-2

B=(e)，B

只有一个原子e，它的长度为1。

例5-3

C=(a,(b,c,d))，C

的长度为2，两个元素分别为原子a

和子表(b,c,d)。

例5-4

D=(A,B,C)，D

的长度为3，三个元素分别为A、B和C，都是广义表。显然，将上面所述三个子表的值代入以后，则有D=((),(