数据结构组广义表课件

数组和广义表可以看成是线性表在以下含义上的扩展：

——表中的数据元素本身也是一个数据结构。数组和广义表可以看成是线性表在以下含义上的扩展：—15.1数组数组是大家都已经很熟悉的一种数据类型，几乎所有高级程序设计语言中都设定了数组类型。在此，我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式。5.1数组数组是大家都已经很熟悉的一种数2一.多维数组的概念1．一维数组一维数组可以看成是一个线性表或一个向量，它在计算机内存放在一块连续的存储单元中，适合于随机查找。这在第2章的线性表的顺序存储结构中已经讨论。一.多维数组的概念1．一维数组32．二维数组二维数组可以看成是向量的推广。例如，设A是一个有m行n列的二维数组，则A可以表示为：在此，可以将二维数组A看成是由m个行向量[X0，X1，…，Xm-1]T组成，其中，Xi=(ai0,ai1,….,ain-1)，0≤i≤m-1；也可以将二维数组A看成是由n个列向量[Y0,Y1,……,Yn-1]组成，其中Yj=(a0j,a1j,…..,am-1j)，0≤j≤n-1。由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接后继（边界除外）。2．二维数组二维数组可以看成是向量的推广。例如，设A43．多维数组同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继。3．多维数组同理，三维数组最多可有三个直接前5二.多维数组在计算机内的存放高级语言对数组的存储都是采取顺序存储的方式，由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中，具体实现方法在下面介绍。二.多维数组在计算机内的存放高级语言对数组65.1.1数组的类型定义5.1.3矩阵的压缩存储5.1.2数组的顺序表示和实现（数组）提要5.1.1数组的类型定义5.1.3矩阵的压缩存储7ADTArray{

数据对象：

D＝{aj1,j2,...,

jn|ji=0,...,bi-1,i=1,2,..,n(n>0),aj1,j2,...,

jn∈ElemSet}

数据关系：

R＝{R1,R2,...,Rn}Ri＝{<aj1,...

ji,...

jn

,aj1,

...ji

+1,

...jn

>|0

jk

bk-1,1

k

n且k

i,0

ji

bi-2,i=2,...,n}

}ADTArray基本操作:5.1.1数组的类型定义ADTArray{基本操作:5.1.1数组的类型定义8数据对象:

D={aij|0≤i≤b1-1,0≤j≤b2-1,

aij∈ElemSet}数据关系:

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}二维数组的定义:数据对象:二维数组的定义:9基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)基本操作：InitArray(&A,n,bound1,10操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，InitArray(&11

DestroyArray(&A)操作结果：销毁数组A。DestroyArray(&A)操作结果：销毁数组A。12初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，Value(A,&e13初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回

OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，Assign(&A,14

类型特点:

数组是多维的结构，而存储空间是一维的结构。有两种顺序映象的方式:1)以行序为主序(行优先，低下标优先)；2)以列序为主序(列优先，高下标优先)。5.1.2数组的顺序表示和实现由于一旦建立了数组，则结构中的数组元素个数和元素之间的关系就已确定，即它们的逻辑结构就固定下来了，不再发生变化；数组一般不作插入或删除操作。因此，采用顺序存储结构表示数组是顺理成章的事了。类型特点:有两种顺序映象的方式:5.1.2数组的顺15例如：

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

的存储位置

LOC(i,j)=LOC(0,0)+(n×i＋j)×L

L

以“行序为主序”的存储映象按行号从小到大的顺序，先将第一行中元素全部存放完，再存放第二行元素，第三行元素，依次类推……二维数组Am×n

a0,0

a0,1

…

a0,n-1……am-1,0am-1,1

…am-1,n-1例如：称为基地址或基址。二维数组A中任一元素ai,j16同理，三维数组Al×m×n按行优先存放的地址计算公式为：LOC(i,j,k)=LOC(0,0,0)+(i×m×n+j×n+k)×L0l-1m-1n-1ijk同理，三维数组Al×m×n按行优先存放的地址计算公式17行序为主序排列规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。行序为主序排列规律：最左边下标变化最慢，最右18称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。推广到一般情况，可得到n维数组数据元素存储位置的映象关系:其中cn=L，ci-1=bi×ci,1<i

n。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n见教材P.93称为n维数组的映象函数。数组元素19例如：

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

的存储位置

LOC(i,j)=LOC(0,0)+(m×j＋i)×L

L

以“列序为主序”的存储映象按列号从小到大的顺序，先将第一列中元素全部存放完，再存放第二列元素，第三列元素，依次类推……二维数组Am×n

a0,0

a1,0

…

am-1,0……a0,n-1a1,n-1

…am-1,n-1例如：基地址或基址。二维数组A中任一元素ai,j的存20列序为主序排列规律：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。列序为主序排列规律：最右边下标变化最慢，最左215.1.3矩阵的压缩存储1.特殊矩阵2.稀疏矩阵5.1.3矩阵的压缩存储1.特殊矩阵2.稀疏矩阵221.特殊矩阵——非零元在矩阵中的分布有一定的规律。

例如:对称矩阵三角矩阵对角矩阵a11a12…a1na21a22…a2n

……an1an2…annA=1.特殊矩阵——非零元在矩阵中的分布有一定的规律。a1123以对称矩阵为例，n阶对称矩阵A满足：aij=aji1≤i,j≤n可为每一对对称元分配一个存储空间。若以行序为主序存储其下三角中的元，以一维数组s[n(n+1)/2]作为其存储结构，则s[k]和矩阵元aij之间的对应关系为：k=i(i-1)/2+j-1(i≥j)

j(j-1)/2+i-1(i<j)以对称矩阵为例，n阶对称矩阵A满足：aij=aji242.稀疏矩阵假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为

0.05的矩阵为稀疏矩阵。何谓稀疏矩阵？非零元在矩阵中随机出现。2.稀疏矩阵假设m行n列的矩阵含t个非零元素，251)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。以常规方法，即以二维数组表示高阶的稀疏矩阵时会产生的问题:例如：

012900000000000-3000014000240000018000001500-7000M=1)零值元素占了很大空间;2)计算中进行了很多和零值261)尽可能少存或不存零值元素；2)尽可能减少没有实际意义的运算；3)操作方便。即：尽可能快地找到与下标值(i，j)对应的元素，尽可能快地找到同一行或同一列的非零元素。解决问题的原则:1)尽可能少存或不存零值元素；2)尽可能减少没有实际意义27一、三元组顺序表二、行逻辑链接的顺序表三、十字链表稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑链接的顺序表三、十字链表稀疏矩阵28

#defineMAXSIZE12500

typedefstruct{

inti,j;//该非零元的行下标和列下标

ElemTypee;//该非零元的值

}Triple;//三元组类型typedefstruct{

Tripledata[MAXSIZE+1];//data[0]未用

intmu,nu,tu;}TSMatrix;//稀疏矩阵类型一、三元组顺序表#defineMAXSIZE12500typede29矩阵M可表示为：

012900000000000-3000014000240000018000001500-7000M=2121391-3361432421811564-7ijeM.data:M.mu=6M.nu=7M.tu=8(TSMatrixM)例如：矩阵M可表示为：0129030三元组顺序表表示的稀疏矩阵的转置运算。转置是矩阵中最简单的一种运算。对于一个m

n的矩阵A，它的转置矩阵B是一个nm的矩阵，且B[i][j]=A[j][i]，1≤i≤n,1≤j≤m。三元组顺序表表示的稀疏矩阵的转置运算。转置是矩阵中最31在三元组表表示的稀疏矩阵中，怎样求得它的转置呢?从转置的性质知道，将A转置为B，就是将A的三元组表a.data变为B的三元组表b.data，这时可以将a.data中i和j的值互换，则得到的b.data是一个按列序为主序排列的三元组表，再将它的顺序适当调整，变成行序为主序排列，即得到转置矩阵B。下面将用两种方法处理：(1)按照A的列序进行转置由于A的列即为B的行，在a.data中，按列扫描，同一列的元素必按行序递增，因此得到的b.data必按行优先存放。但为了找到A的每一列中所有的非零元素，每次都必须从头到尾扫描A的三元组表（有多少列，则扫描多少遍）。在三元组表表示的稀疏矩阵中，怎样求得它的转置呢?32121415-522-731363428211451-522-713364328例如：121415-522-73133voidtransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组表存储表示，求稀疏矩阵M的转置矩阵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].j=M.data[p].i;T.data[q].i=M.data[p].j;T.data[q].e=M.data[p].e;++q;}}}//transposeSMatrix算法的时间复杂度：O(nu×tu)voidtransposeSMatrix(TSMatr34其时间复杂度为:O(mu×nu)

for(col=1;col<=nu;++col)

for(row=1;row<=mu;++row)T[col][row]=M[row][col];用常规的二维数组表示时的算法：相比较后可以发现，当非零元的个数tu与mu×nu同数量级时，transposeSMatrix算法的时间复杂度就成为O(mu×nu2)了，比不压缩存储时的时间复杂度要大。因此，该算法仅适于tu<<mu×nu的情况。其时间复杂度为:O(mu×nu)for(co35（2）按照A的行序进行转置(快速转置)即按a.data中三元组的次序进行转置，并将转置后的三元组放入b中恰当的位置。首先，在转置前求出矩阵A的每一列col（即B中每一行）的第一个非零元转置后在b.data中的正确位置cpot[col](1≤col≤a.nu)，然后，在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.data[cpot[col]]中，之后将cpot[col]内容加1，以指示第col列的下一个非零元的正确位置。为了求得位置向量cpot，要先求出A的每一列中非零元个数num[col]，然后利用下面公式：

cpot[1]=1cpot[col]=pot[col-1]+num[col-1](2≤col≤a.nu){（2）按照A的行序进行转置(快速转置)即按a.dat36cpot[1]=1;for(col=2;col<=a.nu;++col)cpot[col]=cpot[col-1]+num[col-1];例如：

21153

51-56

22-74

13362

432851234512345cpot[1]=1;例如：211537T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu)

{

for(col=1;col<=M.nu;++col)num[col]=0;

for(t=1;t<=M.tu;++t)++num[M.data[t].j];

cpot[1]=1;

for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){}

}//if

returnOK;}//FastTransposeSMatrix

转置矩阵元素StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){col=M.data[p].j;q=cpot[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;++cpot[col]T.mu=M.nu;T.nu=M.mu;T.38时间复杂度为:O(M.nu+M.tu)for(col=1;col<=M.nu;++col)……for(t=1;t<=M.tu;++t)……for(col=2;col<=M.nu;++col)……for(p=1;p<=M.tu;++p)……分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为:O(M.nu+M.tu)for(col=139三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需存取某一行中的非零元，则需从头开始进行查找。二、行逻辑链接的顺序表三元组顺序表又称有序的双下标法，它的特点是，40修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos[]，其各分量的值为对应各行第一个非零元的位置(下标)（在稀疏矩阵的初始化函数中确定）。#defineMAXMN500

typedefstruct{

Tripledata[MAXSIZE+1];

intrpos[MAXMN+1];

intmu,nu,tu;

}RLSMatrix;//行逻辑链接顺序表类型修改前述的稀疏矩阵的结构定义，增加一个数据成41ElemTypevalue(RLSMatrixM,intr,intc){

p=M.rpos[r];

while(p<=M.tu&&M.data[p].i==r&&M.data[p].j<c)p++;

if(p<=M.tu&&M.data[p].i==r&&M.data[p].j==c)

returnM.data[p].e;

elsereturn0;}//value例如：给定一组下标，求矩阵的元素值ElemTypevalue(RLSMatrixM,in42for(i=1;i<=m1;++i)

for(j=1;j<=n2;++j){Q[i][j]=0;

for(k=1;k<=n1;++k)Q[i][j]+=M[i][k]*N[k][j];

}其时间复杂度为:O(m1×n2×n1)矩阵乘法的精典算法:for(i=1;i<=m1;++i)其时间复杂度为:43

Q初始化；

ifQ是非零矩阵{//逐行求积

for(arow=1;arow<=M.mu;++arow){

//处理M的每一行

ctemp[]=0;//累加器清零计算Q中第arow行的积并存入ctemp[]中；将ctemp[]中非零元压缩存储到Q.data；

}//forarow}//if两个稀疏矩阵相乘（Q

M

N）

的过程可大致描述如下：Q初始化；两个稀疏矩阵相乘（QMN）

44

if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;

if(M.tu*N.tu!=0){//Q是非零矩阵

for(arow=1;arow<=M.mu;++arow){

//处理M的每一行

}//forarow}//ifreturnOK;}//MultSMatrixStatusMultSMatrix

(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){if(M.nu!=N.mu)returnERR45

ctemp[]=0;//当前行各元素累加器清零

Q.rpos[arow]=Q.tu+1;for(p=M.rpos[arow];p<M.rpos[arow+1];++p){//对当前行中每一个非零元

brow=M.data[p].j;if(brow<N.nu)t=N.rpos[brow+1];

else{t=N.tu+1}

for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j;//乘积元素在Q中列号

ctemp[ccol]+=M.data[p].e*N.data[q].e;

}//forq

}//求得Q中第crow(=arow)行的非零元

for(ccol=1;ccol<=Q.nu;++ccol)if(ctemp[ccol]){

if(++Q.tu>MAXSIZE)returnERROR;Q.data[Q.tu]={arow,ccol,ctemp[ccol]};

}//if处理的每一行

Mctemp[]=0;46累加器ctemp初始化的时间复杂度为

(M.mu

N.nu)，求Q的所有非零元的时间复杂度为

(M.tu

N.tu/N.mu)，进行压缩存储的时间复杂度为

(M.mu

N.nu)，总的时间复杂度就是

(M.mu

N.nu+M.tu

N.tu/N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数M.tu=

M

m

n，

N中非零元的个数

N.tu=

N

n

p，相乘算法的时间复杂度就是

(m

p

(1+n

M

N))

，当

M<0.05和

N<0.05及n<1000时，相乘算法的时间复杂度就相当于

(m

p)。分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)47当稀疏矩阵中非零元的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构更为恰当。三、十字链表当稀疏矩阵中非零元的位置或个数经常变动时，三元组就不48十字链表是稀疏矩阵的链式存储方法，在该方法中，每一个非零元用一个结点表示，结点形式为：ijedownright其中i,j,e表示非零元所在的行、列和值的三元组；right：行指针域，用来指向本行中下一个非零元素；down：列指针域，用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元通过right指针链接成一个带表头结点的链表。同一列的非零元通过down指针链接成一个带表头结点的链表。因此，每个非零元既是第i行链表中的一个结点，又是第j列链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。十字链表是稀疏矩阵的链式存储方法，在该方法中，每一个49十字链表的类型定义typedefstructOLNode{inti,j;ElemTypee;structOLNode*down,*right;}OLNode;*Olink;typedefstruct{Olink*rhead,*chead;//行、列链表头指针向量基址

intmu,nu,tu;}CrossList;十字链表的类型定义typedefstructOLNod5030050-100200011314522-1312^^^^^^^例：M.mu=3M.nu=4M.tu=4300511314522-1312^^^^^^^515.2广义表广义表的概念广义表是线性表的推广，也称为列表。线性表中的元素仅限于原子，即从结构上是不可以再分的，而广义表中的元素既可以是原子，也可以是广义表。

LISP语言把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。5.2广义表广义表的概念线性表中的元素仅521.广义表广义表一般记作：LS=(

1,

2,…,

n)其中,LS为广义表的名字，n为广义表的长度，每一个

i为广义表的元素。

i可以是原子(或称单元素)，也可以是广义表(称为子表)。在习惯中，一般用大写字母表示广义表，小写字母表示原子。2.广义表的长度广义表的长度定义为最外层包含元素个数。1.广义表广义表一般记作：LS=(1,2,…,n)53若广义表LS非空，则称第一个元素

1为LS的表头，其余元素组成的表(

2,…

n)为LS的表尾。4.表头和表尾广义表的深度定义为所含括弧的重数。注意：“原子”的深度为0

“空表”的深度为13.广义表的深度任一非空的广义表，均可分解为表头和表尾；一对确定的表头和表尾，可唯一确定一个广义表。若广义表LS非空，则称第一个元素1为LS的表头，其余元素组545.广义表举例（1）A=(e)GetHead(A)=e,GetTail(A)=()（2）B=(a,(b,c),d)GetHead(B)=a,GetTail(B)=((b,c),d)（3）C=()无表头、也无表尾广义表A只有一个单元素，其长度为1，深度为1。B是长度为3的广义表，其深度为2。C是一个空表，其长度为0，深度为1。5.广义表举例（1）A=(e)GetHead(A)=e,55广义表举例（5）E=(a,E)（4）D=(A,B,C)GetHead(D)=(e),GetTail(D)=((a,(b,c),d),())GetHead(E)=a,GetTail(E)=(E)（6）F=(())GetHead(F)=(),GetTail(F)=()D是长度为3的广义表，每一项都是上面提到的子表,即:D=((e),(a,(b,c),d),())，其深度为3。E是长度为2的广义表，第一项为原子，第二项为它本身。即：E=(a,(a,(a,…))),其深度为无穷。F是长度为1的广义表，其元素为空表，其深度为2。广义表举例（5）E=(a,E)（4）D=(A,B,C)Get56（广义表）提要5.2.1广义表的类型定义5.2.2

广义表的表示方法（广义表）提要5.2.1广义表的类型定义5.2.2广义57ADTGlist{

数据对象：D＝{ei|i=1,2,..,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet为某个数据对象}

数据关系：

LR＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n}}ADTGlist基本操作:5.2.1广义表的类型定义ADTGlist{基本操作:5.2.1广义表的类型定义58

LS=(

1,

2,

,

n)其中：

i

或为原子或为广义表广义表

LS=(

1,

2,…,

n)的结构特点:2)广义表是递归定义的线性结构1)广义表中的数据元素有相对次序；LS=(1,2,,n59例如：D=(E,F)其中:

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce3)广义表是一个多层次的线性结构例如：D=(E,F)其中:DEFa()d()bce604)广义表可以共享；5)广义表可以是一个递归的表。例如：A=(e)B=(a,(b,c),d)C=(A,B)D=(d,A,f,B)例如：E=(a,E)递归表的深度是无穷值，长度是有限值。4)广义表可以共享；5)广义表可以是一个递归的表。例61

结构的创建和销毁

InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);

状态函数

GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);

插入和删除操作

InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);

遍历

Traverse_GL(L,Visit());基本操作结构的创建和销毁状态函数插入和删除操作62由于广义表中的数据元素可以是原子，也可以是列表，即其中的元素可以有不同的结构，难以用顺序存储结构表示，因此，通常采用链式存储结构。在用链式结构时，需要两种结构的结点：

(1)表结点，用以表示列表；

(2)原子结点，用以表示原子。5.2.2

广义表的表示方法由于广义表中的数据元素可以是原子，也可以是列表，即其63有两种具体的表示方法：(1)头尾链表存储表示(2)扩展线性链表存储表示有两种具体的表示方法：(1)头尾链表存储表示(2)扩展线64typedefenum{ATOM,LIST}ElemTag;//枚举类型

//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;//

公共部分，标志域

union{//联合部分

AtomTypeatom;//原子结点的数据域

struct{structGLNode*hp,*tp;}ptr;

//表结点的指针域

};}*GList(1)广义表的头尾链表存储表示：

表结点:tag=1hptpptrtag=0atom原子结点：typedefenum{ATOM,LIST}Elem65空表非空表tag=1指向表头的指针指向表尾的指针LSLS=NULL空表非空表tag=1指向表头的指针指66例如:例如:67L

10a

1

10x

1

1

1

0x

1

0y(a,(x,y),((x)))a((x,y),((x)))(