数据结构第五章数组和广义表

数据结构第五章数组和广义表第一页，共四十八页，2022年，8月28日

第五章

数组和广义表

5.1数组的定义5.2数组的顺序存储结构5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构第二页，共四十八页，2022年，8月28日3

前4章介绍的数据结构共同特点：▲都属于线性数据结构；▲每种数据结构中的数据元素，都作为原子数据，不再进行分解；本章讨论的两种数据结构：数组和广义表，其共同特点是：▲从逻辑结构上看它们，可看成是线性结构的一种扩展；▲数据元素本身也是一个数据结构；第五章

数组和广义表第三页，共四十八页，2022年，8月28日4

一、数组的定义(1)数组的抽象数据类型定义

ADTArray

{数据对象：D＝{aj1,j2,…,ji,…,jn|ji=0,…,bi-1,i=1,2,…,n(n>0)称为数组的维数,bi是数组第i维的长度，ji是数组元素的第i维下标}

5．1数组的定义

数据关系：R＝{R1,R2,…

,Rn}第四页，共四十八页，2022年，8月28日5

Ri＝{<aj1…ji…jn,aj1…ji+1

…jn>|0≤jk≤bk-1,1≤k≤n

且ki,0≤ji≤bi-2,aj1…ji…jn,aj1…ji+1

…jn∈D，

i=2,…

,n}

如二维数组的定义:数据对象:D={aij|0≤i≤b1-1,0≤j≤b2-1}

数据关系:R={ROW,COL}ROW={<ai,j,ai+1,j>|0≤i≤b1-2,0≤j≤b2-1}COL={<ai,j,ai,j+1>|0≤i≤b1-1,0≤j≤b2-2}

第五页，共四十八页，2022年，8月28日6

(2)

二维数组的解释a00

a01…

a0n-1a10

a11…

a1n-1┋┋┋am-10

am-11

…

am-1n-1

二维数组中的每个元素都受两个线性关系的约束，即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。在行关系中

aij直接前趋是aij-1aij直接后继是aij+1在列关系中

aij直接前趋是ai-1jaij直接后继是ai+1j第六页，共四十八页，2022年，8月28日7

A=(0,1,2,3,

4,……,p)

p=m-1或n-1

其中每一个数据元素j

是一个列向量的线性表

j=（a0j,

a1j,a2j,

a3j,……

,am-1j)0≤j≤n-1

二维数组也可看作这样的线性表：其每一个数据元素也是一个线性表。a00

a01…

a0n-1a10

a11…

a1n-1┋┋┋am-10

am-11…

am-1n-1Amn=a00

a10

┋

am-10Amn=第七页，共四十八页，2022年，8月28日8或i

是一个行向量的线性表

i=（ai0,ai1,ai2,

ai3,……

,ain-1)0≤i≤m-1Amn=((a00a01…

a0n-1),(a10a11…

a1n-1),(am-10am-11…

am-1n-1))(3)C语言中二维数组类型的一种定义

typedefelemtypeArray2[m][n];

等价于

typedefelemtypeArray1[n];typedefArray1Array2[m];

同理，可以用n-1维数组的数据类型来定义n维数组。第八页，共四十八页，2022年，8月28日9一、数组的顺序表示和实现

(1)类型特点

①只有引用型操作，一般不作插入或删除操作；

②数组是多维的结构，而存储空间是一个一维的结构。(2)两个策略----两种顺序映象的方式①以行序为主序(低下标优先)；②以列序为主序(高下标优先)。5．2数组的顺序存贮结构第九页，共四十八页，2022年，8月28日10a00

a01…

a0n-1a10

a11…

a1n-1┋┋┋am-10

am-11…

am-1n-1Amn=以行为主序的方式：a00a01a0n-1

a10a11a1n-1a(m-1)n-1amn-101n-1nn+12n-1mn-1第十页，共四十八页，2022年，8月28日1101m-1mm+12m-1nm-1a00a10am-10

a01

a11am-11

a0n-1a1n-1

amn-1以列为主序的方式：第十一页，共四十八页，2022年，8月28日1212(4)存储位置的公式

假设二维数组A每个元素占用L个存储单元，若以行序为主序的方式存储二维数组，二维数组A中任一元素ai,j的存储位置为：

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

L

三维数组A中任一元素ai,j,k的存储位置为：

LOC(i,j,k)=LOC(0,0,0)+(b2×b3×i＋b3×j+k)×L若以列序为主序的方式存储二维数组，则元素aij

的存储位置可由下式确定：Loc(aij)=Loc(a00)+（b1

j+i)L第十二页，共四十八页，2022年，8月28日1313三维二维一维123123412a111a121a131a141a211a231a241a221a331a341a321a311a142a132a122a112a242a342第十三页，共四十八页，2022年，8月28日141414推广到一般情况，可得到n维数组数据元素存储位置的映象关系:P93称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。

▲

是随机存储结构。三维二维一维123123412a111a121a131a141a211a231a241a221a331a341a321a311a142a132a122a112a242a342其中cn=L,ci-1=bi*ci,1<i<=n第十四页，共四十八页，2022年，8月28日151515(5)结构定义

#definemaxarraydim8typedefstruct{elemtype*base;//数组元素基址

intdim;//数组维数

int*bounds;//数组维界基址(各维容量)

int*constants;//数组映象函数常量基址｝array;第十五页，共四十八页，2022年，8月28日5.3矩阵的压缩存储

一特殊矩阵的压缩存储二稀疏矩阵的压缩存储

1三元组表的存储结构2十字链表的存储结构第十六页，共四十八页，2022年，8月28日(1)矩阵压缩存储的必要性矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。通常程序员是用二维数组存储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素，因而能较为容易地实现矩阵的各种运算。应用中常遇到一些阶数很高的矩阵，矩阵中有许多值相同的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。例如，设一个10001000的矩阵中有800个非零元素，若用二维数组存储需要106个存储单元。因此，需要使用高效的存储方法，减少数据的存储量，即对原矩阵，根据数据分布特征进行压缩存储。1、矩阵的压缩存储5．3矩阵的压缩存储第十七页，共四十八页，2022年，8月28日(2)压缩存储的有关概念①

压缩存储：为多个值相同的元素分配一个存储空间，对零元不分配空间。②

特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定规律。③稀疏矩阵：值相同的元素或者零元素在矩阵中的分布无规律。第十八页，共四十八页，2022年，8月28日a11a11a1na21a22a2nan1an2anna11a21a22a31a32a33

an1an2an3ann②压缩存储方法为每一对对称元分配一个存储空间，则可将n2个元压缩存储到n(n+1)/2个元的空间中。(3)特殊矩阵①概念：若n阶矩阵A中的元满足：aij=aji1≤i,j≤n，则称为n阶对称矩阵。a11a21

a22

a31

a32

a33

an1

an2

annk=012345n(n+1)/2-1第十九页，共四十八页，2022年，8月28日③下标对应关系k=当i≥j当ij矩阵的上(下)三角(不含对角线)中的元均为常数C或0的n阶矩阵(三角矩阵)，其存储方法相同。例如，

a32在sa[]中的存储位置是：k=3*(3-1)/2+2-1=4sa[4]=a32(4)对角矩阵①概念：非零元都集中在以主对角线为中心的带状区域中。②存储：这种矩阵可以某个原则(以行为主，或以对角线的顺序)将其压缩存储到一维数组上。第二十页，共四十八页，2022年，8月28日

压缩存储的对称矩阵的取值算法intget_M(inti,intj){if(i>=j)return(sa[i*(i+1)/2+j])elsereturn(sa[j*(j+1)/2+i]);}压缩存储的对称矩阵的赋值算法voidassign_M(inti,intj,intvalue){if(i>=j)sa[i*(i+1)/2+j]=value;elsesa[j*(j+1)/2+i]=value;}第二十一页，共四十八页，2022年，8月28日

带状矩阵

所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时,非0元素有(2d+1)*n-(1+d)*d个a00a01a020

0

0

0

0

0

0

0

0

a10a11a12a130

0

00

0

0

0

0a20a21a22a23a24000

0

0

0

00

a31a32a33a34a3500

0

0

0

00

0

a42a43a44a45a460

0

0

0

00

0

0a53a54a55a56a5700

0

0

0

0

00

a64a65a66a67a680

0

00

00

0

0

a75a76a77a78a790

0

00

0

0

0

0a86a87a88a89a810

0

00

0

0

0

0

0

a97

a98a99a910a91100

0

0

0

0

0

0

a108a109a1010a101100

0

0

0

0

0

0

0

a119a1110a1111d第二十二页，共四十八页，2022年，8月28日a00a010

0

0

a10a11a1200

0

a21a22a2300

0

a32a33a340

0

0a43a44为计算方便，认为每一行都有2d+1个非0元素，若少则用0补足，所以，存放矩阵的数组sa[]有n(2d+1)个元素数组元素sa[k]与矩阵元素aij

之间有关系：

k=i*(2d+1)+d+(j-i)0

a00

a01

a10

a11a12a21a22a23a32a33a34a43a440K=01234567891011121314第二十三页，共四十八页，2022年，8月28日

压缩存储的带状矩阵的取值算法intget_Md(inti,intj){if(abs(i-j)<=d）return(sa[i*(2*d+1)+d+(j-i)])；elsereturn(0);}压缩存储的带状矩阵的赋值算法voidassign_Md(inti,intj,intvalue){if(abs(i-j)<=d）sa[i*(i+1)/2+j]=value;}第二十四页，共四十八页，2022年，8月28日(5)稀疏矩阵①含义：在m×n的矩阵中，有t个元素不为零，令：称δ为矩阵的稀疏因子，通常认为δ≤0.05时称稀疏矩阵②抽象数据类型稀疏矩阵的定义③分析按常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:

I零值元素占了很大空间；

II计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。

第二十五页，共四十八页，2022年，8月28日解决问题的原则:

I尽可能少存或不存零值元素；

II

尽可能减少没有实际意义的运算；

III

操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。

为此提出一种存储方法：为了能找到相应的元素，仅存储非零元素的值是不够的，还要记下它所在的行和列。于是采取将非零元素所在的行、列以及它的值构成一个三元组(i,j,v)，然后再按某种规律存储这些三元组，这种方法可以节约存储空间。第二十六页，共四十八页，2022年，8月28日例如：稀疏矩阵：

A

=012900000000000-3000014000240000018000001500-7000可用三元组表(i,j,aij)A=((0,1,12),(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,15),(5,3,-7))加上行、列数、非零元个数6，7,8表示。

▲用三元组表存储稀疏矩阵有三种方法：

I三元组顺序表

II行逻辑链接的顺序表

III十字链表第二十七页，共四十八页，2022年，8月28日④三元组顺序表

I概念：以顺序存储结构来表示三元组表，得稀疏矩阵的一种压缩存储方式——称之为三元组顺序表。如：

A

=

012900000000000-3000014000240000018000001500-7000

i

jV01234567831-3611512125218139432464-73614678第二十八页，共四十八页，2022年，8月28日如：ma[1].row=1,ma[1].col=1,ma[1].value=12

II结构定义#definemaxsize1024typedefstruct{inti,j;elemtypev;}triple;typedefstruct{tripledata[maxsize+1];intmu,nu,tu;}tsmatrix;

III转置运算算法

转置运算是一种最常用的矩阵运算。对于一个m

行n列的矩阵A，它的转置矩阵B是一个n行m

列的矩阵。如，下图中的矩阵A

和B

互为转置矩阵。第二十九页，共四十八页，2022年，8月28日

A第0列第一列第二列第三列第四列第五列第六列

….

B第0行第一行第二行第三行第四行第五行第六行

….转置运算算法第三十页，共四十八页，2022年，8月28日B

=00-3001512000180

900240000000-70000000014000000000

分析：

◆

将矩阵的行列数的值交换

◆将每一个三元组的i和j相互调换

◆重排三元组之间的次序

A

=

012900000000000-3000014000240000018000001500-7000第三十一页，共四十八页，2022年，8月28日

算法一

i

j

v01234567831-3611512125218139432464-73614678

i

j

v012345678211246-713-33424161531963142518768第三十二页，共四十八页，2022年，8月28日按照A的列序来进行转换的基本思想

对ma[]从头至尾扫描：第一次扫描时，将ma[]中列号为0的所有元组交换行列值后，依次赋值到mb[]中；第二次扫描时，将ma[]中列号为1的所有元组交换行列值后，依次赋值到mb[]中；依此类推，直至将ma[]的所有三元组赋值到mb[]中。第三十三页，共四十八页，2022年，8月28日

ijv121213931-3361443245218611564-7ijv31-3251813-3611516151212211252181393194324342464-746-736146314A矩阵B矩阵对A六次扫描完成转置运算第一次扫描查找第1列元素第一次扫描结束第二次扫描结束第二次扫描查找第2列元素第三次扫描查找第3列元素第四次扫描查找第4列元素第五次扫描查找第5列元素第六次扫描查找第6列元素转置运算算法图示012345678678768第三十四页，共四十八页，2022年，8月28日

算法一描述(保持以行序为主序存储)inttpm(tsmatrixm,tsmatrix*t){t->mu=m.nu;t->nu=m.mu;t->tu=m.tu;if(t->tu){q=1;for(col=1;col<=m.nu;col++)for(p=1;p<=m.tu;p++)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].v=m.data[p].v;q++;}}returnok;}▲

时间复杂度为〇(nu×tu)第三十五页，共四十八页，2022年，8月28日ijv012345678768

mb[]

算法二——快速转置算法

方法：以A矩阵的三元组为中心,依次取出ma[]中的每一个三元组，交换行列后，直接将其写入mb[]合适的位置中。

342416153196314251813-3i

jvma[]01234567831-361156785218139432464-736141212211246-7第三十六页，共四十八页，2022年，8月28日⑤十字链表

I概念：以三元组表示的稀疏矩阵，在运算中，若非0元素的位置发生变化，会引起数组元素的频繁移动。为解决这个问题，采用十字链表的存储结构在十字链表中，表示非0元素结点除了三元组,还有两个指针域：

向下域(down)

链接同一列下一个非0元素

向右域(right)

链接同一行下一个非0元素稀疏矩阵中同一行的非0元素结点通过向右域，链接成一个带头结点的行循环链表。同一列的非0元素结点通过向下域，链接成一个带头结点的列循环链表。

第三十七页，共四十八页，2022年，8月28日

rowcolvaldownrightII

十字链表的存储结构(结点的数据结构)如下：

structnode{introw,col,val;structnode*down,*right;}第三十八页，共四十八页，2022年，8月28日例如矩阵A

=

32050-1002000000044500000000000003501200300000000000020211-1head1022221022十字链表图示第三十九页，共四十八页，2022年，8月28日

小结

1矩阵压缩存储是指为多个值相同的元素分配一个存储空间，对零元素不分配存储空间；2特殊矩阵的压缩存储是根据元素的分布规律，确定元素的存储位置与元素在矩阵中的位置的对应关系；3稀疏矩阵的压缩存储除了要保存非零元素的值外，还要保存非零元素在矩阵中的位置；第四十页，共四十八页，2022年，8月28日1、广义表的定义(1)广义表的引入线性表是由n个数据元素组成的有限序列。其中每个组成元素被限定为单元素，有时这种限制需要拓宽。例如，中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式：(俄罗斯，巴西，(国家，河北，四川)，古巴，美国，()，日本)在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。5.4广义表第四十一页，共四十八页，2022年，8月28日(2)广义表的定义广义表（GeneralizedLists）是n（n≥0）个数据元素