数组和广义表课件

数组和广义表5.1数组

数组可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。一维数组：A1=（a0，a1，a2，……，an-1）二维数组：a00a01

……a0n-1A2=……

am-10am-11am-1n-1又可表示为：A2=（a0，a1，a2，……，an-1）其中ai=（a0i，a1i，……，am-1i）为列向量。5.1数组N维数组：b1×b2×b3×……×bn也可以表示为一个线性表（a0，a1，a2，……，abn-1）表中的每个元素均为一个N-1维的数组。数组的抽象数据类型（了解）数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储

5.3.1特殊矩阵

5.3.2稀疏矩阵5.4广义表的定义及存储结构5.2数组的顺序表示和实现类型特点:1)只有引用型操作，没有加工型操作;2)数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:

1)以行序为主序;2)以列序为主序;数组的顺序存储方式⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn

在PASCAL、C语言中，数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN语言中，数组就是按列优先顺序存储的。例如：数组A

b1×b2

称为基地址或基址。数组元素地址计算二维数组A中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1

a0,0

a0,2

a1,0

a1,1

a1,2

a0,1

a0,0

a0,2

a1,0

a1,1

a1,2

L

L

数组元素地址计算同样，三维数组Ab1×b2×b3按“行优先顺序”存储，元素aijk的地址计算函数为：

LOC(aijk)=LOC(a000)+(i*b2*b3+j*b3+k)*L结论:只要知道开始元素的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。

了解数组的顺序存贮表示和实现例2：已知二维数组Am,m按行存储的元素地址公式是：Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,按列存储的公式是？

Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K例1、一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是

个字节。

288例3、设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为

。8950LOC(aij)=LOC(ac1，c2)+[(j-c2)*b1+i-c1)]*L答：请注意审题！利用列优先通式：第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储

5.3.1特殊矩阵

5.3.2稀疏矩阵5.4广义表的定义及存储结构5.3矩阵的压缩存储矩阵的一般存贮表示?元素的访问?矩阵类似二维数组，存储方式同二维数组。15137003005080040005A=18926B=00007302516000370613但以二维数组表示的特殊矩阵有重复元素值反复存储的缺点，及高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。5.3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵

在一个n阶方阵A中，若元素满足下述性质：

aij=aji1≦i,j≦n则称A为对称矩阵。如下图便是一个5阶对称矩阵。

15137a1150800a21a2218926a31a32a3330251………………..70613an1an2an3

…ann

对称矩阵A在这个下三角矩阵中，第i行恰有i个元素，元素总数为：∑(i)=(1+2+3+……+n)=n(n+1)/2压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的n(n+1)/2个（主对角线和下三角）元素内容，这些元素的存储顺序以行为主序。因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。

0123n(n-1)/2n(n+1)/2-1i=1i=na11a21a22a31……an,

1……

an,n为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。

若i≧j，则aij在下三角形中。ai

j之前的i-1行（从第1行到第i-1行）一共有1+2+…+(i-1)=i(i-1)/2个元素，在第i行上，aij之前恰有j-1个元素（即ai1,ai2,ai3,…,aij-1），因此有：

k=i*(i-1)/2+j-1i≧j

若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：

k=j*(j-1)/2+i-1i<j2、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。

a11a12…a1na11c…cca22…a2na21a22…c

…..……………..cc…annan1an2…ann(a)上三角矩阵(b)下三角矩阵三角矩阵三角矩阵存储a1,1a1,2…a1,na2,2a2,3…a2,n

……

an,n对上三角阵只需存上三角部分，一维数组B中从0号位置开始存放，并按行优先存储，如下图所示：01…n-1nn+1…2n-2…

n(n+1)/2-1

则对矩阵A的任意矩阵元素aij（i≤j），在按行优先存储的情况下，它在一维数组B中对应的存储位置为：

LOC(i,j)=n+(n-1)+(n-2)……+(n-(i-1)+1)+(j-i)=(2n-i+2)(i-1)/2+j-i

3、对角矩阵(了解)对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，

a00a01a10a11a12a21a22a23

….…..….

an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。

(0≤i≤n-1,i-1≤j≤i+1)LOC(i,j)=2i+j5.3.2稀疏矩阵什么是稀疏矩阵？简单说，矩阵非零元素远远小于矩阵元素的总数，则称为稀疏矩阵.

在存储稀疏矩阵时，为了节省存储单元，只存储非零元素。故用一个三元组(i,j,aij)来存储矩阵的一个非零元。一个三元组(i,j,aij)唯一确定了矩阵的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。例如，下列三元组表((1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))

加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述

012900000000000-3000014000240000018000001500–7000稀疏矩阵M而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。一、三元组顺序表（理解）二、行逻辑链接的顺序表（了解）三、十字链表（了解）一、三元组顺序表（以行为主的顺序）ijv121415-522-731363428三元组顺序表存储表示

#defineMAXSIZE12500//非0元个数最大值

typedef

int

ElemType;//元素值类型

typedef

struct{

int

i,j;//非0元的行列下标值

ElemTypee;}Triple;//三元组类型

typedef

struct{Tripledata[MAXSIZE+1];//data[0]不用

int

mu,nu,tu;//行数、列数、非0元个数}TSMatrix;//三元组顺序表类型矩阵的转置运算

普通矩阵的转置如何实现?

aij和aji互换.算法实现思想?在转置之前需要完成的任务:矩阵信息存贮到在计算机中,运用实际的存贮形式来完成转置任务,结果需要显示给用户.矩阵的转置运算算法思想一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][j]=b[j][i]，1≦i≦m，1≦j≦n，即A的行是B的列，A的列是B的行。将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。

例如：A=ijv121415-522-731363428úúúûùêêêëé0280036000-70-500140ijv211451-522-713364328B=矩阵的转置运算算法思想要得到转置结果,结合转置前后三元组信息的特点,用哪些方法可以得到转置结果?

由于A的列是B的行，因此，按a.data的列序转置(先放第一列所有非0员，再放下一列所有非0元)，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。两种方法：按照b.data中三元组的次序依次在a.data中找相应的三元组进行转置按照a.data中三元组的次序进行转置，并将转置后的三元组置入b.data中恰当位置矩阵的转置

运算算法思想对A中的每一列

col(1≦col≦n)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组（col从1依次递增到n），将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。ijv121415-522-731363428ijv1336211422-7432851-5úúúûùêêêëé0280036000-70-500140算法实现（理解算法，程序填空）:p99voidTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;

T.nu=M.mu;T.tu=M.tu;//行列互换if(T.tu!=0)//非0元个数不为0则进行非0元素转置{q=1;//转置矩阵T对应三元组中最新非0元的位置for(col=1;col<=M.nu;col++)//按照M的列进行扫描转置

for(p=1;p<=M.tu;p++)//对于每一行，都从三元组所有元素中扫描

if(M.data[p].j==col)//col值比较,该列出现一个非0元，信息加入

{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++;//q指向下一个位置

} }}算法分析该算法主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu*tu)。而一般传统矩阵的转置算法为：

for(col=1;col<=nu;++col)for(row=1;row<=mu;++row)t[col][row]=m[row][col];

其时间复杂度为O(mu*nu)。当非零元素的个数tu和mu*nu同数量级时，该算法的时间复杂度为O(mu*nu2)。因此，此算法仅适用于tu<=mu*nu的情况。快速转置的算法设置两个一维数组num[1..n]和cpot[1..n]

num[col]：表示M中第col列非零元素的个数

cpot[col]：指示M中第col列第一个非0元的存贮位置

显然有：

cpot[1]=1

cpot[col]=cpot[col-1]+num[col-1]2<=col<=a.nu

快速转置的算法算法思想：对A进行扫描，按A提供的列号一次确定装入B的一个三元组的位置。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。第一遍扫描A

1.确定A的每一列即B的每一行的元素个数，

2.确定B每一行的第一个非0元应该存贮的位置第二遍扫描：对A进行扫描，对当前非0元进行定位和存贮。快速转置的算法

图5.5(P97)中的矩阵M和相应的三元组A可以求得num[col]和cpot[col]的值如下：

下面通过num和cpot数组值来观察几个非0元的存入过程。ijv121213931-3361443245218611564-7

col1234567

num[col]2221010

cpot[col]1357889ijv13-3161521122518319342446-7631412346Col序号123456789当对A扫描并将所有元素存入B后，B的每行的位置与下一行的初始值重合快速转置的算法实现（P100）voidFastTransposeSMatrix(TSMatrixM,TSMatrix&T){

T.mu=M.nu;//行列互换

T.nu=M.mu;

T.tu=M.tu;if(T.tu!=0) {for(col=1;col<=M.nu;++col)//设置num初值

num[col]=0; //扫描第一遍M三元组信息，计算num for(p=1;p<=M.tu;++p)

num[M.data[p].j]++;快速转置的算法实现（P100）

cpot[1]=1;//计算cpot值 for(p=2;p<=M.nu;p++)

cpot[p]=cpot[p-1]+num[p-1];

//第二遍扫描M三元组，一次性定位和转置

for(p=1;p<=M.tu;++p){

col=M.data[p].j;//取出该元素的列号

k=cpot[col];//确定在T三元组中的应放位置

T.data[k].i=M.data[p].j;//放置信息

T.data[k].j=M.data[p].i;

T.data[k].e=M.data[p].e;

cpot[col]++;//为该列出现的下一个非0元定位}

} }快速转置的算法分析1、多用了两个辅助向量；2、时间复杂度：O（nu+tu）；3、当非零元素的个数tu和mu*nu同数量级时，时间复杂度：O（mu×nu）三元组顺序表特点非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算；然而，若需按行号存取某一行的非零元，则需从头开始进行查找。另当矩阵的非零元个数和位置在操作过程中变化较大时，就不适宜了。解决方法：三元组采用其他表示方法行逻辑链接的顺序表和十字链表作业1、设定二维整数数组B[0..m-1，0..n-1]的数据在行、列方向上都按从小到大的顺序排序，且整型变量x中的数据在B中存在。试设计一个算法，找出一对满足B[i][j]=x的i、j值。要求比较次数不超过m+n。2、编写一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储

5.3.1特殊矩阵

5.3.2稀疏矩阵5.4广义表的定义及存储结构5.4广义表1、定义：广义表（Lists，又称列表）是线性表的推广。

广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。广义表是递归定义的线性结构，LS=(

1,

2,

,

n)

其中：

i

或为原子或为广义表例：（1）A=（）（2）B=（e）(3)C=(a,(b,c,d))(4)D=(A,B,C)(5)E=(a,E)习惯上，大写字母表示名称，小写字母表示原子。当广义表非空时，第一个元素称为表头