数据结构第5章数组广义表课件

数组描述二维数组可用形式化语言描述，即：

A(2)=(D,R)其中：D={aij|aij∈datatype,0≤i≤m-1,0≤j≤n-1};R={Row,Col}

行关系：Row={<aij,aij+1>|aij,aij+1∈D,0≤i≤m-1,0≤j≤n-2}

列关系：Col={<aij,ai+1j>|aij,ai+1j∈D,0≤i≤m-2,0≤j≤n-1}

关系集Row和Col表明：除数组A(2)周边元素外的其它任一个元素aij，有两个直接前驱ai-1j，aij-1,和两个直接后继ai+1j，aij+1(周边元素的前驱或后继可不足两个)。n维数组也可按上述方法类似定义。二维数组还可以用如下形式描述:

A[0]

…A[i]…A[m-1]=(A[0]……A[i]……A[m-1])-----线性表形式a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1A(2)=A[m][n]=数组描述二维数组可用形式化语言描述，即：A[0]=(A[02.数组的基本运算 多维数组是线性表的推广，而线性表是多维数组的特例。 在算法语言中，数组一旦生成，其元素的存储空间就固定下来，故数组的运算一般不包括插入和删除这样的操作。对数组运算有：

(1)构造一个n维数组：Setarray(A,n,d1d2,......dn)，即生成：

A[d1][d2].....[dn]（C语言中，1≤n≤8）。

(2)撤消一个数组：Dearray(A)，释放数组A的存储空间。

(3)取值：Aget(A,i1,...,in,x)，将A[i1][i2],...,[in]的值传给变量x。

(4)赋值：Assign(A,i1,...,in,x)，将变量x的值传给A[i1][i2].....[in]。

5.2数组的存储映像由于计算机的存储空间是一维的（或线性的），所以存储数组时，要将多维数组中的元素按某种次序映象到一维存储空间，即解决“降维”问题。在PASCAL和C等语言中，是按低维下标优先变化（或按行优先）的方式，存储数组中的元素。如在C语言中，二维数组的映像如图5.1所示。但在FORTRAN语言中，数组元素是按高维下标优先变化或按列优先方式，存储数组中的元素。 2.数组的基本运算 多维数组是线性表的推广，而线性表数组的存储映像

a00…a0,n-1…ai0…ai,n-1……am-1,n-1映像

（存储器）a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1

A[m][n]=图5.1思考：1.三维以上数组如何映像? 2.“按列优先”如何映像?数组的存储映像a00…a0,n-1…ai0…ai,n-1…5.2.1数组元素的地址计算以C语言为例。设数组元素的起始地址为b,每个元素占用L个单元（元素所占单元量由元素的类型而定），元素a的地址用Loc(a)表示。1.一维数组： 即:Loc(a0)=b; Loc(a1)=b+L;

Loc(ai)=b+i×L;

规律：任一元素ai的地址:

a0a1

…ai-1ai…an-1A[n]=(

a0,

a1,……ai

,……an-1)

起始地址b+(ai前的元素个数i)×L

起址b:b+L:……b+i•L:L图5.35.2.1数组元素的地址计算以C语言为例。设数组元素的起始地数组元素的地址计算2.二维数组：a00…a0,n-1…ai0…aij……am-1,n-1映像

（存储器）起址b:b+L:……b+[i×n]×L:…b+[i•n+j]•L:由图5.4知：Loc(a00)=b Loc(ai0)=b+(ai0前元素个数)•L=b+(i•n)•L

Loc(aij)=b+(aij前元素个数)•L=b+[i×n+j]×L例5-1设二维数组A[7][8]，起始地址b=1000，每个元素所占单元量L=3，则Loc(a5,6)=1000+(5•8+6)3=1138。

inj图5.4a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1

A[m][n]=数组元素的地址计算2.二维数组：a00…a0,n-1…ai数组元素的地址计算3．三维数组：

由图5.5可知： Loc(a000)=b图5.5 Loc(ai00)=b+(i•n•p)•L Loc(aij0)=b+(i•n•p+j•p)•L

Loc(aijk)=b+(i×n×p+j×p+k)×L可以看出，i•n•p，i•n•p+j•p，i•n•p+j•p+k分别为ai00，aij0，aijk前的元素个数。a000ai00aij0aijk数组元素的地址计算3．三维数组：a000ai00aij0ai数组元素的地址计算4．n维数组从以上的地址公式推导中得出这样一条规律：任意维数组中任一元素的地址=起址b+该元素前的个数×元素单元量L。故n维数组A[u1][u2]…..[un]，其中任一元素ai1....in的地址为：

Loc(ai1i2……in)=b+(i1•u2•u3•

…

•un+i2•u3•u4•

…un+…+in-1•un+in)•L

=b+()×L

元素按“列优先”方式存储时，地址计算方法类似，不再赘述。 有了数组元素的地址计算公式，给出相应参数后，能够很快求出任一元素的地址，然后按地址存取相应元素，故对数组的存取是随机存取（或按公式存取）。5.2.2数组空间的动态生成（略）

数组元素的地址计算4．n维数组5.3矩阵的压缩存储信息的压缩存储是一项专业技术，在当今的多媒体应用中显得尤为重要。但本节只是讨论矩阵（或二维数组）中元素的压缩存储。在矩阵中，往往会出现许多值相同的元素或０元素，为节省存储空间，可以采用某些技术对这类矩阵进行压缩存储。压缩存储的原则是：对多个值相同的元素只存储其中之一，对０元素甚至不分配存储空间。5.3.1特殊矩阵的压缩存储特殊矩阵，指的是值相同的元素或０元素在矩阵中的分布遵循一定规律的矩阵。1.对称矩阵：

满足aij=aji，(1≤i,j≤n)a11a22

aii…

ann

An×n=

aijaji5.3矩阵的压缩存储信息的压缩存储是一特殊矩阵的压缩

显然，aij与aji对称相等，二者只需分配一个存储单元，即只存储矩阵中包括主对角线的下三角(或上三角)元素。于是An×n所需的存储单元数为n(n+1)/2，而不压缩存储需要n2个存储单元。当n很大时，几乎能压缩原存储空间的一半。具体做法是：设置一个一维数组S[n(n+1)/2+1]作为An.n的存储空间，且按行的次序存放An×n中包括主对角线的下三角元素，如图5.7所示。a11a21a22…aij…ann

S[n(n+1)/2+1]:123…..….….k………..n(n+1)/2

图5.7

a11a22

…aii

ann

An×n=

aij其中aij存入S[k]单元，下标（i,j）与k的关系为：

i(i-1)/2+j

当i≥j时；S[i(i-1)/2+j]当i≥j时；

k=即：aij=

j(j-1)/2+i

当i<j时。S[j(j-1)/2+i]当i<j时。特殊矩阵的压缩显然，aij与aji对称相等，二特殊矩阵的压缩２．三角矩阵：（下三角矩阵）(上三角矩阵）显然，对于下三角矩阵，类似于对称矩阵的压缩存储，即只存储包括主对角线的下三角元素。而当i<j时，aij取C即可。对于上三角矩阵，压缩方法如图5.8所示。a11a22

…aii

ann

An×n=

aijCa11a22

aii…

annCaijCa11a12…aij…annS[n(n+1)/2+1]:

012…..….….k………..n(n+1)/2

K=—+=(i-1)n–(i-1)(i-2)/2+(j-i+1)=(i-1)(2n-i)/2+j(i≤j)

而当(i>j)时，K=0.图5.8

特殊矩阵的压缩２．三角矩阵：a11An×n特殊矩阵的压缩3．对角线矩阵（三对角线）：按行顺序压缩于S中，如图5.9所示。

Ca11a12…aij…ann

S[3n-1]:

012…..….….k………..3n-2a11a12a21a22a23..…..…

aii-1aiiaii+1..…..…

ann-1ann

An×n=

CC图5.9

3(i-1)当i=j+1时；

3i-2当i=j时；归纳为：k=2i+j-2

当i=j+1,i=j,i+1=j时。

3i-1当i+1=j时；如将i=1,j=2代入,k=20其他。

k=特殊矩阵的压缩3．对角线矩阵（三对角线）：按行顺序压缩于S中5.3.2稀疏矩阵的压缩存储特殊矩阵中同值元素的分布有一定的规律可循，而有的矩阵，０元素很多（如同一个画面上有几个亮点，其余全是空白），但分布无规律，称这类矩阵为稀疏矩阵。例5-2设一个6×7的矩阵如下：则A6×7可以视为一个稀疏矩阵。对于矩阵Am×n，设非0元素个数为t，若δ=t/(m×n)≤0.2，则可以将其视为稀疏矩阵。显然，为节省存储空间，须对这类矩阵压缩存储空间，原则是只存储非0元素。一般有“三元组表”和“十字链表”的压缩存储方法。010200000000003000040005000006000007008000

A6×7

=

5.3.2稀疏矩阵的压缩存储特殊矩阵中同值元素

1．三元组表三元组：（i,j,v），其中i,j分别为非0元素的行、列号，v存放非0元的数值。以行优先的顺序将稀疏矩阵中非0元以三元组形式存入一数组，即所谓的三元组表。三元组表的存储结构的描述：

#definemaxsize64//最大非0元个数//typedefStruct//三元组类型//{inti,j;datatypev;}tritype;//三元组说明符//typedefStruct{tritypedata[maxsize+1];//三元组表//intmu,nu,tu;//原矩阵的行、列、非0元个数//}Tsmtype,*Tsmlink;//三元组表说明符//若说明：TsmlinkA;A=(Tsmlink)malloc(sizeof(Tsmtype));则指针变量A指向一个如图5.10所示的三元组表。对例5-3中A6×7，设每个元素占16个字节，若不压缩存储，需6×7×16=672（字节），而压缩成三元组表存储时，i,j为整型，故共需：

2×16+8×16=160（字节）。ijv121142313364435526617648A->data[1]……………A->data[tu]

图5.101．三元组表三元组：（i,j,v）三元组表的转置然而，稀疏矩阵的压缩存储会给矩阵运算带来一些不便，算法要复杂些。这里的运算指求矩阵的转置，两矩阵相加和相乘等。我们只讨论矩阵的转置的算法。未压缩前，求矩阵A的转置矩阵B，算法很简单：

for(col=1;col<=nu;col++)for(row=1;row<=mu;row++)B[col][row]=A[row][col];例5-3：02004608000900030000

A4×5=

ijv12215421623832941306032090080000004000

B5×4=

现在，要通过A的三元组表求其转置矩阵B的三元组表。ijv126143212239328514三元组表的转置然而，稀疏矩阵的压缩存储三元组表的转置算法思路：1)

矩阵A的所有列转化成B的所有行；

2)

对A中的每一列col(1～nu)，扫描所有非0元（1～tu），若有一非0元的列号j=当前列col，则将该非0元行列互换，送到目标三元组表。

如例5-3中矩阵A，当前列col=1时，因A->data[3].j=1,所以将A->data[3]的转置：（1，2，6）=>B->data[1]，又A->data[6].j=1，所以A->data[6]的转置：

(1，4，3)=>B->data[2]，完成第一列的转换，依此类推。算法描述：

voidTransm(TsmtypeA,TsmtypeB){intp,q,col;B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;if(A->tu!=0){q=1;//目标表的序号//for(col=1;col<=A->nu;col++)

//扫描A的所有列//for(p=1;p<=A->tn;p++)

//扫描所有非0元//

if(A->data[p].j==col){B->data[q].i=A->data[p].j;//行列互换//B->data[q].j=A->data[p].i;B->data[q].v=A->data[p].v;q++;}}}三元组表的转置算法思路：1)矩阵A的所有列转化成B的所有行三元组表的转置

ijv122154216238329413

p

123456

02004608000900030000

A4×5=

12345colijv126

q

12345614321223932851406032090080000004000

B5×4=

（矩阵A的三元组表）

图5.12

（转置后的三元组表）算法的时间复杂度：O(t×n)n=列数,t=非0元个数。改进算法的复杂度：O(t+n)（略）三元组表的转置ijv1221542162383294132.十字链表十字链表是以链表结构形式存储一个稀疏矩阵。矩阵中非0元设置成如下形式的结点：

其中i、j分别存放非0元的行列号，head/data或作为一非0元的值域（data）或作为头结点的链指针(head)；down为指向相同列下一个非0元结点的指针，right为指向相同行下一非0元结点的指针。结点类型描述：

typedefstructnode {inti,j; union{structnode*head; datatypedata; }vdata; structnode*down,*right; }nodetype,*tlink;ijhead/datadownright2.十字链表十字链表是以链表结构形式存储一个稀疏十字链表例5-4设稀疏矩阵：1004020030000005

A4×4=

111144222313445004400000000000000LA的十字链表如图5.13：十字链表例5-4设稀疏矩阵：100十字链表算法思路：先构造空表，其中S取矩阵行列数的最大值，即S=max(m,n)。依次读入每个非0元(i,j,v)，生成一个非0元的结点，对该结点赋读入的值后，将其插入第i行链表和第j列链表的正确位置。算法描述：voidCreattenlink(tlinkL,intm,n,t)//L为头指针，m,n,t分别为行列号和非0元个数//{tlinkp,q,H[maxsize];inti,j,k,s;datatypev;if(m>n)s=m;elses=n;//确定头结点的个数//L=(tlink)malloc(sizeof(nodetype));//申请总的头结点//L->i=m;L->j=n;//置行列数//H[0]=L;for(i=1;i<=s;i++)//建立头结点链表//{p=(tlink)malloc(sizeof(nodetype));p->i=p->j=0;p->down=p->right=p;H[i]=p;H[i-1]->vdata.head=p;}H[s]->vdata.head=L;//构成循环链表//

十字链表算法思路：先构造空表，其中S取矩阵行列数的最大值，即十字链表

for(k=1;k<=t;k++)//处理t个非0元//{scanf(“%d%d%d”,&i,&j,&v);//读入一个非0元（i,j,v）//p=(tlink)malloc(sizeof(nodetype));//申请结点存放非0元//p->i=i;p->j=j;p->vdata.data=v;//赋值//q=H[i]； //取第i行链表头结点指针//while((q->right!=H[i])&&(q->right->j<j)) q=q->right;//找当前非0元结点在行链表中的位置// p->right=q->right;q->right=p;//当前非0元结点插入q结点之后// q=H[j]； //取第j列链表头结点指针// while((q->down!=H[j])&&(q->down->i<i)) q=q->down;//找当前非0元结点在列链表中的位置// p->down=q->down;q->down=p;//非0元结点结点插入q结点之后// }}十字链表for(k=1;k<=t;k++)5.4广义表的定义 广义表又称列表(lists),是线型表的推广。在线型表L=(a0……ai……an-1)中，ai是单元素或称原子，即ai本身不再是一个数据结构，而广义表记为：LS=(d0d1……di……dn－1)

其中di（0≤i≤n-1）既可以是一个原子，又可以是另一个表（称为子表），即表中还可以套表。广义表LS的形式化描述为：

LS=(D,R)其中：D={di|di∈datatypeordi∈LS(递归定义)，i=0,1,.....n-1,n≥0}

R={<di,di+1>|di,di+1∈D,0≤i≤n-2}

式中n为表长（n=0时为空表），若di为原子，则称di为LS的单元素，否则di称为LS的子表（满足递归定义)。当广义表非空时，定义两个函数：

head(LS)=d0；tail(LS)=(d1...dn-1)。 即head(LS)是LS的第一元素d0（当然d0可以为子表），而tail(LS)是LS中d1...dn-1的一个子表。对广义表的其它运算（如查找，插入和删除等）类似于线性表的运算。5.4广义表的定义 广义表又称列表(lists),是线广义表例5-5广义表的例子。约定：大写字母A～Z为表名，小写字母a～z为单元素。

A=()或A()——空表，表长=0，无表头，表尾；

B=(a,b)或B(a,b)——线性表(广义表特例),表长=2,head(B)=a,tail(B)=(b)；

C=(e,B)或C(e,B)——表长=2，head(C)=e,tail(C)=(B)=((a,b)),

表C可以表示为：C(e,(a,b))；

D=(A,B,C)或D(A,B,C)——表长=3，head(D)=A=(), tail(D)=(B,C)=((a,b),(e,(a,b)))；

E=(a,E)——表长=2，head(E)=a,tail(E)=(E),整个表E为(a,(a,(a,...)))，它为一个特殊的广义表，称为递归表，或无限表。从例5-5可以看出，广义表有如下特点：（1）表可以嵌套——表中元素可以是一个表，称为子表，而子表还可以有子表。如例5-5中表B和表C的结构如图5.15所示。图5.15CeBababB广义表例5-5广义表的例子。约定：大写字母A～Z为表名，广义表（2）表可以共享——表可以是其它表的子表，或表中的元素可取自其他的表。如例5-5中表D包含表A、B、C，或A、B、C为D的子表,如图5.16所示。（3）表可以递归——表中元素可以是表本身。如例5-5中表E。

EaDABCabe^图5.16另外，表中任一单元素可由head(Ls)和tail(Ls)函数导出，如取表A=(a,(b,d,e))中单元素d的运算为：head(tail(head(tail(A))))

广义表（2）表可以共享——表可以是其它表的子表，或表中的元素5.5广义表的存储结构对于广义表LS=(d0…di…dn-1)，由于di可以是单元素或子表，故用顺序存储结构表示一个广义表较为困难，一般采用链表存储结构，称为广义链表。5.5.1单链及双链结构1．单链表示法元素di的结点形式：其中：0当di为单元素时；data当atom=0时；

atom=data/link=1当di为子表时。link当atom=1时。

next意义同线性链表，指向di+1所在结点。结点描述：typedefstructnode {intatom; union{datatypedata;structnode*link; }dtype; structnode*next; }Lsnode;atomdata/linknext5.5广义表的存储结构对于广义表LS=(d0广义表的存储为了广义表的运算方便，对每一广义表引入头结点，其形式同一般的表结点：

例5-5中广义表A、B、C、D、E的单链表如图5.17所示。1^1^^AA=()图5.170a0b^1^BB=(a，b)0e1^1^CC=(e，B)11^1^1^DD=(A，B，C)0a1^1^EE=(a，E)广义表的存储为了广义表的运算方便，对每一广义表引入头结点，其广义表的存储2．双链表示法元素di的结点形式：其中：指向子表的指针当di为子表时；

link1=^当di为原子时。

表名当di为子表时；

data=link2：指向di+1所在的结点。

原子值当di为原子时。例5-5中几个广义表的双链表结构如图5.18：

datalink1link2BA^C^DE^a^EB^e^Cb^^a^A=^B广义表的存储2．双链表示法datalink1link2BA^广义表的存储例5-6

设职工工资的表头H：

即