《数组和广义表》PPT课件.ppt

《《数组和广义表》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数组和广义表》PPT课件.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5章章数组和广义表数组和广义表 元素的值并非原子类型，可以再分解，表中元素元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。也是一个线性表（即广义的线性表）。所有数据元素仍属所有数据元素仍属同一数据类型。同一数据类型。5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构数组和广义表的特点：数组和广义表的特点：一种特殊的线性表一种特殊的线性表5.1数组的定义数组的定义数组：数组：由一组名字相同、下标不同的变量构成由一组名字相同、下标不同

2、的变量构成注意：注意：本章所讨论的数组与高级语言中的数组有所区别：高本章所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；而级语言中的数组是顺序结构；而本章的数组既可以是顺序的，本章的数组既可以是顺序的，也可以是链式结构，也可以是链式结构，用户可根据需要选择。用户可根据需要选择。答：答：对的对的。因为：。因为：数组中各元素具有数组中各元素具有统一的类型统一的类型；数组元素的下标一般具有数组元素的下标一般具有固定的上界和下界固定的上界和下界，即数组一，即数组一旦被定义，它的维数和维界就不再改变。旦被定义，它的维数和维界就不再改变。数组的数组的基本操作比较简单基本操作比较简单，除

3、了结构的初始化和销毁之，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。外，只有存取元素和修改元素值的操作。讨论：讨论：“数组的处理比其它复杂的结构要简单数组的处理比其它复杂的结构要简单”，对吗？，对吗？二维数组的特点：二维数组的特点：二维数组的特点：二维数组的特点：一维数组的特点：一维数组的特点：1 1个下标，个下标，a ai i 是是a ai+1i+1的直接前驱的直接前驱2 2个下标，个下标，每个元素每个元素ai,j受到两个关系受到两个关系（行关系和列关系）的约束：（行关系和列关系）的约束：一个一个mn的二维数组可以的二维数组可以看成是看成是m行的一维数组，或行的一维数组，或者

4、者n列的一维数组。列的一维数组。N N维数组的特点：维数组的特点：n n个下标，个下标，每个元素受到每个元素受到n n个关系约束个关系约束一个一个n维数组可以看成是维数组可以看成是由若干个由若干个n1维数组组成的线性表。维数组组成的线性表。a11a12a1na21a22a2naijam1am2amnAmn=数组的抽象数据类型定义数组的抽象数据类型定义ADTArray数据对象数据对象：n是维数；bi是第i维的长度Daj1,j2,.,ji,jn|ji=0,.,bi-1,i=1,2,.,n数据关系数据关系：RR1,R2,.,RnRi|0jkbk-1,1kn且ki,0jibi-2,i=2,.,nADT

5、Array基本操作基本操作:基本操作基本操作：InitArray(&A,n,bound1,.,boundn)DestroyArray(&A)Value(A,&e,index1,.,indexn)Assign(&A,e,index1,.,indexn)InitArray(&A,n,bound1,.,boundn)操作结果：操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：操作结果：销毁数组A。Value(A,&e,index1,.,indexn)初始条件：初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：操作结果：若各下标

6、不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,.,indexn)初始条件：初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。二维数组的定义二维数组的定义:数据对象数据对象:D=aij|0ib1-1,0jb2-1数据关系数据关系:R=ROW,COLROW=|0ib1-2,0jb2-1COL=|0ib1-1,0jb2-25.2 5.2 数组的顺序存储表示和实现数组的顺序存储表示和实现问题：问题：计算机的存储结构是一维的，而数组一般是多计算机的存储结构是一维的，而数组一般是多

7、维的，怎样存放？维的，怎样存放？解决办法：解决办法：事先约定按某种次序将数组元素排成一个事先约定按某种次序将数组元素排成一个序列，然后将这个线性序列存入存储器中。序列，然后将这个线性序列存入存储器中。例如：例如：在二维数组中，我们既可以规定按在二维数组中，我们既可以规定按行行存储，也存储，也可以规定按可以规定按列列存储存储。注意：注意：若规定好了次序，则数组中任意一个元素的存放地址便若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；约定的次序不同，则计算元素地址的公式也有所不同；C C

8、和和PASCALPASCAL中一般采用行优先顺序；中一般采用行优先顺序；FORTRANFORTRAN采用列优先。采用列优先。例如：例如：称为基地址基地址或基址。以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2LL012345二维数组的顺序存储二维数组的顺序存储n n二维数组二维数组Amn按行优先按行优先寻址计算方法，寻址计算方法，每个数组元素占据每个数组元素占据L个地址单元。个地址单元。设数组的基址为设数组的基址为

9、设数组的基址为设数组的基址为LOC(aLOC(a1111)：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*L设数组的基址为设数组的基址为设数组的基址为设数组的基址为LOC(aLOC(a0000)：LOC(aij)=LOC(a00)+(i*n+j)*L二维数组的顺序存储二维数组的顺序存储n n二维数组二维数组Amn按列优先按列优先寻址计算方法，寻址计算方法，每个数组元素占据每个数组元素占据L个地址单元。个地址单元。设数组的基址为设数组的基址为设数组的基址为设数组的基址为LOC(aLOC(a1111)：LOC(aij)=LOC(a11)+(j-1)*m+i-1)*L设数组的基址为设

10、数组的基址为设数组的基址为设数组的基址为LOC(aLOC(a0000)：LOC(aij)=LOC(a00)+(j*m+i)*L例例1.二维数组二维数组A的每个元素是由的每个元素是由6个字符组成的个字符组成的串，设每个字符占一个字节。其行下标串，设每个字符占一个字节。其行下标i=0,1,8,列下标列下标j=1,2,10。若。若A按行优先按行优先存储，元素存储，元素A8,5的起始地址与当的起始地址与当A按列优按列优先存储时的元素（先存储时的元素（）的起始地址相同。）的起始地址相同。A.A8,5B.A3,10A.A8,5B.A3,10C.A5,8D.A4,10C.A5,8D.A4,10例例2.二维数

11、组二维数组N的每个元素占的每个元素占4个存储单元，个存储单元，行下标行下标i的范围从的范围从0到到4，列下标，列下标j的范围从的范围从0到到5，N按行存储时元素按行存储时元素N35的起始地址的起始地址与与N按列存储时元素（按列存储时元素（）的起始地址相同。）的起始地址相同。A.N24A.N24B.N34B.N34C.N35C.N35D.N44D.N44可见，无论规定按行优先或按列优先，可见，无论规定按行优先或按列优先，只要知道以下三要素便可随时求出任只要知道以下三要素便可随时求出任一元素的地址（一元素的地址（这样数组中的任一元这样数组中的任一元素便可以随机存取！素便可以随机存取！）：开始结点的

12、存放地址（即基地址）；开始结点的存放地址（即基地址）；维数和每维的长度（上、下界）；维数和每维的长度（上、下界）；每个数组元素所占用的单元数。每个数组元素所占用的单元数。二维数组二维数组 三维数组三维数组行向量行向量下标下标j页向量页向量下标下标i列向量列向量下标下标k行向量行向量下标下标j列向量列向量下标下标k三维数组三维数组各维长度为各维长度为b1,b2,b3下标为下标为j1,j2,j3的数组元素的存储地址：的数组元素的存储地址：（按页（按页/行行/列存放）列存放）LOC(j1,j2,j3)=LOC(0,0,0)+(j1*b2*b3+j2*b3+j3)*l 前前j1页总页总元素个数元素个数

13、第第j1页的页的前前j2行行总总元素个数元素个数推广推广n维数组维数组各维长度为各维长度为b1,b2,b3,bn下标为下标为j1,j2,j3,jn的数组元素的存储的数组元素的存储地址：地址：LOC(j1,j2,jn)=a+(j1*b2*b3*bn+j2*b3*b4*bn+jn-1*bn+jn)*L 可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素数组元素的存储位置是其下标的线性函数。的存储位置是其下标的线性函数。其中cn=L，ci-1=bici,1in。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+cijii=1n前面若干元素占用前面若干元素占用的地址字节总

14、数的地址字节总数与所存元素个数与所存元素个数有关的系数，可有关的系数，可用递推法求出用递推法求出#include/提供宏提供宏va_start、va_end、va_arg#defineMAX_ARRAY_DIM8/假设最大维数为假设最大维数为8typedefstructELemType*base;/数组元素基址数组元素基址intdim;/数组维数数组维数int*bounds;/数组数组各维长度信息保存区的各维长度信息保存区的基址基址int*constants;/数组数组映像函数常量映像函数常量的基址的基址Array;即即Ci信息保存区信息保存区数组的基本操作函数说明（有数组的基本操作函数说明（

15、有5个）个）（请参阅教材（请参阅教材P93-95P93-95）n维数组的顺序存储表示维数组的顺序存储表示（见教材见教材P93P93）以初始化数组函数为例以初始化数组函数为例StatusInitArray(Array&A,intdim,)/若维数若维数dimdim和各维长度合法，则和各维长度合法，则构造相应的数组构造相应的数组构造相应的数组构造相应的数组A A A A并返回并返回OKOKif(dimMAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int);if(!A.bounds)exit(OVERFLOW

16、);/若各维长度合法，则存入若各维长度合法，则存入A.bounds,A.bounds,并求出并求出A A的元素总数的元素总数elemtotalelemtotalelemtotal=1;va_start(ap,dim);/ap/ap为为va_listva_list类型，是存放变长参数表信类型，是存放变长参数表信息的类型息的类型数组的基本操作函数说明（数组的基本操作函数说明（5个）个）（见教材见教材P93-95P93-95）for(i=0;idim;+i)A.boundsi=va_arg(ap,int);if(A.boundsi=0;-i)A.constantsi=A.boundsi+1*A.co

17、nstantsi+1;returnOK;数组基址指针数组基址指针各维长度保各维长度保存区指针存区指针映像函数映像函数CiCi保存区指针保存区指针StatusDestroyArray(Array&A)/销毁数组销毁数组A Aif(!A.base)returnERROR;free(A.base);A.base=NULL;if(!A.bounds)returnERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;free(A.constants);A.constants=NULL;returnOK;StatusLocate(Ar

18、rayA,va_listap,int&off)/若若apap指示的各下标值合法，则求出该元素在指示的各下标值合法，则求出该元素在A A中相对地址中相对地址offoffoff=0;for(i=0;iA.dim;+i)ind=va_arg(ap,int);if(indA.boundsi)returnOVERFLOW;off+=A.constantsi*ind;returnOK;StatusValue(ArrayA,ElemType&e,)/A/A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n个下标值，若各下标不个下标值，若各下标不超界，则超界，则e e赋值为所指定的赋值

19、为所指定的A A的元素值，即将指定元素值读到的元素值，即将指定元素值读到e e变变量中。量中。va_start(ap,e);if(result=Locate(A,ap,off)=0)returnresult;e=*(A.base+off);returnOK;StatusAssign(Array&A,ElemTypee,)/A/A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n个下标值，个下标值，若各下标不超界，则若各下标不超界，则e e的值赋为所指定的的值赋为所指定的A A的元素值，的元素值，即：将即：将即：将即：将e e e e值写入指定数组单元值写入指定数组单元值

20、写入指定数组单元值写入指定数组单元。va_start(ap,e);if(result=Locate(A,ap,off)=0)returnresult;*(A.base+off)=e;returnOK;顺序存储方式：顺序存储方式：顺序存储方式：顺序存储方式：按低下标优先（或高下标优先）顺序存按低下标优先（或高下标优先）顺序存按低下标优先（或高下标优先）顺序存按低下标优先（或高下标优先）顺序存入一维数组。入一维数组。入一维数组。入一维数组。难点是多维数组与一维空间地址映射关系难点是多维数组与一维空间地址映射关系行指针向量行指针向量a11a12a1nam1am2amn链式存储方式：链式存储方式：用用

21、带行指针向量的单链表带行指针向量的单链表来表示。来表示。作业5-1：1、谈谈n维数组中第i维的长度、“第i维的元素个数”、n维数组元素个数的区别和联系。2、推导和解释教材第93页公式5-2。注：写到作业本上注：写到作业本上5.3 5.3 矩阵的压缩存储矩阵的压缩存储1.什么是压缩存储？什么是压缩存储？若多个数据元素的若多个数据元素的值都相同值都相同，则只分配一，则只分配一个元素值的存储空间，且零元素不占存储空间。个元素值的存储空间，且零元素不占存储空间。2.所有矩阵都能压缩吗？所有矩阵都能压缩吗？不一定，要看该矩阵是否具备压缩条件。不一定，要看该矩阵是否具备压缩条件。3.什么样的矩阵具备压缩条

22、件？什么样的矩阵具备压缩条件？一些特殊矩阵，如：对称矩阵，对角矩阵，一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。三角矩阵，稀疏矩阵等。4.什么叫什么叫稀疏矩阵？稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）5.3.1特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储的

23、元素，如零元素或对称元素，不再存储。存储。对称矩阵（上三角矩阵、下三角矩阵）对称矩阵（上三角矩阵、下三角矩阵）对角矩阵（主要是三对角矩阵）对角矩阵（主要是三对角矩阵）一、对称矩阵的压缩存储一、对称矩阵的压缩存储设有一个设有一个n n的对称矩阵的对称矩阵A。在矩阵中，在矩阵中，aij=ajin为节约存储空间，只存对角线及对角线以为节约存储空间，只存对角线及对角线以上的元素，或者上的元素，或者只存对角线及对角线以下只存对角线及对角线以下的元素的元素。前者称为。前者称为上三角矩阵上三角矩阵，后者称为，后者称为下三角矩阵下三角矩阵。n把它们按行把它们按行存放于一个一维数组存放于一个一维数组B中，中，称

24、之为对称矩阵称之为对称矩阵A的压缩存储。的压缩存储。n数组数组B共有共有n+(n-1)+1=n*(n+1)/2个元素。个元素。上三角矩阵下三角矩阵下三角矩阵B a00a10a11a20a21a22a30a31a32 an-1n-1 012345678n(n+1)/2-1若若i j,数组元素数组元素Aij在数组在数组B中的存放位置中的存放位置为为1+2+i+j=(i+1)*i/2+j前前i行行元素总数元素总数第第i行第行第j个个元素前元素个数元素前元素个数若若ij，数组元素，数组元素Aij在矩阵的在矩阵的上三角部分上三角部分,在数组在数组B中中没有存放没有存放，可，可以找它的对称元素以找它的对称

25、元素Aji的存放位置：的存放位置：j*(j+1)/2+i注：书上注：书上P95公式（公式（5-3）i和和j的范围的范围例3.设有一个10阶的对称矩阵A，采用下三角压缩存储方式，以行序为主序存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85（即该元素下标ij=85）的地址为（）。A.13B.33C.18D.40例4.若对n阶对称矩阵A1.n，1.n以行序为主序方式下将其下三角的元素（包括主对角线上的所有元素）依次存放于一维数组B1.n(n+1)/2中，则在B中确定aij(ij，数组元素，数组元素Aij在矩阵的下三角在矩阵的下三角部分，在数组部分，在数组B中没有存放。因此，找

26、它中没有存放。因此，找它的对称元素的对称元素Aji。Aji在数组在数组B的第的第(2*n-j-1)*j/2+i的的位置中找到。位置中找到。二、二、三对角矩阵的压缩存储三对角矩阵的压缩存储B a00a01a10a11a12a21a22a23an-1n-2an-1n-1012345678910n三对角矩阵中除主对角线及在主对角三对角矩阵中除主对角线及在主对角线上线上下最临近的两条对角线上的元素下最临近的两条对角线上的元素外，所有其它元素均为外，所有其它元素均为0。总共有。总共有3n-2个非零元素。个非零元素。n在三条对角线上的元素在三条对角线上的元素aij满足满足0 i n-1,i-1 j i+1

27、三对角矩阵的特性n将三对角矩阵将三对角矩阵A中三条对角线上的元中三条对角线上的元素按行存放在一维数组素按行存放在一维数组B中，且中，且a00存存放于放于B0。n在一维数组在一维数组B中中Aij在第在第i行，它行，它前面有前面有3*i-1个非零元素个非零元素,在本行中第在本行中第j列前面有列前面有j-i+1个，所以元素个，所以元素Aij在在B中位置为中位置为k=2*i+j。三对角矩阵的压缩存储作业5-2：1、任任意意选选择择对对称称矩矩阵阵或或三三对对角角矩矩阵阵之之一一总总结其压缩存储的规律。结其压缩存储的规律。5.4广义表的定义广义表的定义ADTGList数据对象数据对象：Dei|i=1,2

28、,.,n;n0;eiAtomSet或eiGList,AtomSet为某个数据对象数据关系：数据关系：LR|ei-1,eiD,2inADTGList基本操作基本操作:结构的创建和销毁结构的创建和销毁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

29、);遍历遍历Traverse_GL(L,Visit();广义表，也称为列表（广义表，也称为列表（广义表，也称为列表（广义表，也称为列表（listslists），一般），一般），一般），一般记为：记为：记为：记为：LS=(LS=(1 1,2 2,，n n)广义表名广义表名广义表名广义表名 表头表头表头表头(Head(Head）表尾表尾表尾表尾(Tail)(Tail)第一个第一个元素是表头元素是表头，而其余元素组，而其余元素组成的成的表表称为表尾称为表尾；用小写字母表示用小写字母表示原子原子类型，用类型，用大写大写字母字母表示列表。表示列表。n n是表长是表长在广义表中约定：在广义表中约定：显然，

30、广义表是递归递归定义的线性结构线性结构，LS=(1,2,n)其中：i或为原子或为广义表例如例如:A=()F=(d,(e)D=(a,(b,c),F)C=(A,D,F)E=(a,E)=(a,(a,(a,)广义表广义表LS=(1,2,n)的结构特点的结构特点:1)广义表中的数据元素有相对次序次序;2)广义表的长度长度定义为最外层包含元素个数;3)广义表的深度深度定义为所含括弧的重数;注意:“原子”的深度为0;“空表”的深度为1。4)广义表可以共享共享;5)广义表可以是一个递归递归的表;递归表的深度是无穷值，长度是有限值。6)任何一个非空广义表非空广义表LS=(1,2,n)均可分解为表头表头Head(

31、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)=()广义表是一个多层次多层次的线性结构线性结构例如：例如：D=(E,F)其中:E=(a,(b,c)F=(d,(e)DEFa()d()bce5.5 广义表的存储结构广义表的存储结构通常采用头、尾指针的链表结构，每个数据元素可用一个结点表示。表结点表结点:原子结点：原子结点：tag

32、=0datatag=1hptp广义表的头尾链表存储表示：广义表的头尾链表存储表示：typedefenumATOM,LISTElemTag;/ATOM=0:原子,LIST=1:子表typedefstructGLNodeElemTagtag;unionAtomTypeatom;/原子结点的数据域structstructGLNode*hp,*tp;ptr;*GListtag=1 hptpptr表结点广义表采用表头表尾指针的链表广义表采用表头表尾指针的链表存储结构的示例存储结构的示例:若表头为原子，则为若表头为原子，则为空表空表ls=NIL非空表非空表lstag=1指向表头的指针指向表尾的指针tag=

33、0data否则，依次类推。否则，依次类推。L=(a,(x,y),(x)a(x,y)()1LL=()0a111110 x ()xA=()10eC=(a,(b,c,d)1110a0b0d0c11例：例：B=(e)A=NILE=(a,E)D=(A,B,C)(),(e),(a,(b,c,d)0a1110e111110a0b0d0c111（参见教材参见教材P109图图5.9）1.1.了了解解数数组组的的定定义义和和存存储储表表示示方方法法，并并掌掌握握数数组在以行为主的存储结构中的地址计算方法。组在以行为主的存储结构中的地址计算方法。2.2.掌掌握握对对称称矩矩阵阵、对对角角矩矩阵阵等等特特殊殊矩矩阵阵进进行行压压缩存储时的下标变换公式。缩存储时的下标变换公式。3.3.了了解解广广义义表表的的定定义义、结结构构特特点点及及其其存存储储表表示示方法。方法。本章小结