第五章数组和广义表

第五章数组和广义表第一页，共五十七页，编辑于2023年，星期四学习提要：1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4.掌握广义表的结构特点及其存储表示方法。第二页，共五十七页，编辑于2023年，星期四ADTArray{

数据对象：D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}

数据关系：R＝{R1,R2,...,Rn}Ri＝{<aj1,...ji,...jn

,aj1,...ji+1,...jn

>|0jkbk-1,1kn且ki,0ji

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

}ADTArray基本操作:5.1数组的类型定义第三页，共五十七页，编辑于2023年，星期四基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)第四页，共五十七页，编辑于2023年，星期四InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)

操作结果：销毁数组A。第五页，共五十七页，编辑于2023年，星期四

Value(A,&e,index1,...,indexn)

初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。第六页，共五十七页，编辑于2023年，星期四

Assign(&A,e,index1,...,indexn)

初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返OK。第七页，共五十七页，编辑于2023年，星期四二维数组的定义:数据对象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:

R={ROW,COL}

ROW={<ai,j,ai,j+1>|0≤i≤b1-2,0≤j≤b2-1}

COL={<ai,j,ai+1,j>|0≤i≤b1-1,0≤j≤b2-2}第八页，共五十七页，编辑于2023年，星期四二维数组的定义:第九页，共五十七页，编辑于2023年，星期四5.2数组的顺序表示和实现类型特点:（1）

只有引用型操作，没有加工型操作；（2）数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:（1）以行序为主序（2）以列序为主序第十页，共五十七页，编辑于2023年，星期四

a00a01……a0n-1

a10a11……a1n-1

am-10am-11…am-1n-1….

按行序为主序存放

am-1n-1……..

am-11

am-10

……….a1n-1……..

a11a10a0n-1

…….a01

a0001n-1m*n-1nLOC(i,j)=LOC(0,0)+(n×i＋j)×L第十一页，共五十七页，编辑于2023年，星期四

按列序为主序存放01m-1m*n-1m

am-1n-1……..

a1n-1

a0n-1……….am-11……..

a11a01am-10

…….a10

a00

a00

a01

……..

a0n-1

a10

a11……..

a1n-1

am-10

am-11

…am-1n-1….LOC(i,j)=LOC(0,0)+(m×j＋i)×L第十二页，共五十七页，编辑于2023年，星期四称为基地址或基址以“行序为主序”的存储映象:二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(n×i＋j)×

L

以“列序为主序”的存储映象:二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(m×j＋i)×

L

第十三页，共五十七页，编辑于2023年，星期四推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1<in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n第十四页，共五十七页，编辑于2023年，星期四

5.3.1特殊矩阵5.3矩阵的压缩存储

5.3.2稀疏矩阵第十五页，共五十七页，编辑于2023年，星期四第十六页，共五十七页，编辑于2023年，星期四

以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:(1)零值元素占了很大空间;(2)计算中进行了很多和零值的运算。第十七页，共五十七页，编辑于2023年，星期四(1)尽可能少存或不存零值元素；解决问题的原则:(2)尽可能减少没有实际意义的运算；(3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。第十八页，共五十七页，编辑于2023年，星期四5.3.1特殊矩阵

特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。对称矩阵元素满足条件

aij=aji1=<i,j=<n的n阶矩阵。第十九页，共五十七页，编辑于2023年，星期四按行序为主序：

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann….a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1第二十页，共五十七页，编辑于2023年，星期四三角矩阵按行序为主序：Loc(aij)=Loc(a11)+[i*(i-1)/2+(j-1)]*L

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1第二十一页，共五十七页，编辑于2023年，星期四对角矩阵

a11

a120

…………….0

a21

a22

a23

0

……………00

0

…an-1,n-2an-1,n-1

an-1,n0

0

……an,n-1ann

0

a32a33

a34

0

………0……………Loc(aij)=Loc(a11)+2(i-1)+(j-1)

按行序为主序：a11a12a21a22a23ann-1ann…...…...k=01234n(n+1)/2-1第二十二页，共五十七页，编辑于2023年，星期四5.3.2稀疏矩阵假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为

0.05的矩阵为稀疏矩阵。第二十三页，共五十七页，编辑于2023年，星期四稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑链接的顺序表三、十字链表第二十四页，共五十七页，编辑于2023年，星期四

#defineMAXSIZE12500

typedefstruct{

inti,j;

//该非零元的行下标和列下标

ElemTypee;

//该非零元的值

}Triple;//三元组类型一、三元组顺序表typedefunion{

Tripledata[MAXSIZE+1];

intmu,nu,tu;}TSMatrix;//稀疏矩阵类型第二十五页，共五十七页，编辑于2023年，星期四6

7

8

121213931-3361443245218611564-7ije012345678第二十六页，共五十七页，编辑于2023年，星期四T如何求转置矩阵？第二十七页，共五十七页，编辑于2023年，星期四用常规的二维数组表示时的算法其时间复杂度为:O(mu×nu)for(col=1;col<=nu;++col)

for(row=1;row<=mu;++row)T[col][row]=M[row][col];第二十八页，共五十七页，编辑于2023年，星期四6

7

8

121213931-3361443245218611564-7ije012345678ije7

6

8

13-3161521122518319342446-76314012345678?M.dataT.data第二十九页，共五十七页，编辑于2023年，星期四解决思路：

只要做到

将矩阵行、列值互换；将每个三元组中的i和j相互调换；重排三元组次序，使T.data中元素以N的行(M的列)为主序第三十页，共五十七页，编辑于2023年，星期四方法一：按M的列序转置按T.data中三元组次序依次在M.data中找到相应的三元组进行转置，即按照矩阵M的列序来进行置换。为找到M中每一列所有非零元素，需对其三元组表M.data从第一行起扫描一遍。由于M.data中以M行序为主序，所以由此得到的恰是T.data中应有的顺序。第三十一页，共五十七页，编辑于2023年，星期四6

7

8

121213931-3361443245218611564-7ije012345678M.data7

6

8

13-3161521122518319342446-76314ije012345678T.dataqppppppppqqqqppppppppcol=1col=2第三十二页，共五十七页，编辑于2023年，星期四StatusTransposeSMatix(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].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}}returnOK;}//TransposeSMatrixT(n)=O(nu*tu)第三十三页，共五十七页，编辑于2023年，星期四方法二：快速转置按M.data中三元组次序转置，转置结果放入T.data中恰当位置。此法关键是要预先确定M中每一列第一个非零元在T.data中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数。实现：设两个数组num[col]：表示矩阵M中第col列中非零元个数cpot[col]：指示M中第col列第一个非零元在T.data中位置显然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colM.nu)第三十四页，共五十七页，编辑于2023年，星期四6

7

8

121213931-3361443245218611564-7ije012345678M.dataije012345678T.datacolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp4629753第三十五页，共五十七页，编辑于2023年，星期四6

7

8

121213931-3361443245218611564-7ije012345678for(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];Col1234567Num[col]cpot[col]t1t1t1t1t2t2t2t1001357889第三十六页，共五十七页，编辑于2023年，星期四StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.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){//转置矩阵元素

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];}//for}//if

returnOK;}//FastTransposeSMatrixT(n)=O(nu+tu)T(n)=O(mu*nu)第三十七页，共五十七页，编辑于2023年，星期四三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。第三十八页，共五十七页，编辑于2023年，星期四#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];

//非零元三元组表

intrpos[MAXMN+1];

//各行第一个非零元的位置表

intmu,nu,tu;}RLSMatrix;//行逻辑链接顺序表类型二、行逻辑链接的顺序表第三十九页，共五十七页，编辑于2023年，星期四M=N=Q=Q=MN第四十页，共五十七页，编辑于2023年，星期四113145

ije123431222-1M.data122211

ije123432431-2N.data

21-1

ije1234

Q.dataparow123

rops[arow]134brow1234rops[brow]1235ccol12ctempt1tpq6p126tpp2tq-1tp=5p1tq4

324第四十一页，共五十七页，编辑于2023年，星期四三、十字链表30050-100200011314522-1312^^^^^^^第四十二页，共五十七页，编辑于2023年，星期四TypestructOLNode{

inti,j;

inte;

structOLNode*right,*down;

}OLNode;*OLink;

Typestruct{

OLink*rhead,*chead;

intmu,nu,tu;

}CrossList;第四十三页，共五十七页，编辑于2023年，星期四§5.4广义表的类型定义ADTGlist{

数据对象：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

基本操作:第四十四页，共五十七页，编辑于2023年，星期四广义表是递归定义的线性结构，LS=(1,2,,n)其中：i或为原子或为广义表例如:A=()F=(d,(e))D=((a,(b,c)),F)C=(A,D,F)B=(a,B)=(a,(a,(a,,)))第四十五页，共五十七页，编辑于2023年，星期四广义表是一个多层次的线性结构例如：D=(E,F)其中:

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce第四十六页，共五十七页，编辑于2023年，星期四广义表

LS=(1,2,…,n)的结构特点:1)广义表中的数据元素有相对次序；2)广义表的长度定义为最外层包含元素个数；3)广义表的深度定义为所含括弧的重数；注意：“原子”的深度为0

“空表”的深度为14)广义表可以共享；5)广义表可以是一个递归的表。递归表的深度是无穷值，长度是有限值。第四十七页，共五十七页，编辑于2023年，星期四6)任何一个非空广义表LS=(1,2,…,n)均可分解为

表头Head(LS)=1和

表尾Tail(LS)=(2,…,n)两部分。例如:

D=(E,F)=((a,(b,c))，F)Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=()第四十八页，共五十七页，编辑于2023年，星期四

结构的创建和销毁

InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);基本操作状态函数

GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);插入和删除操作

InsertFirst_GL(&L,e);DeleteFi