第五章-数组和广义表.ppt

数据结构第五章数组与广义表*数组的逻辑结构及ADT描述数组的顺序存储表示矩阵及特殊矩阵的定义及存储表示稀疏矩阵的存储表示内容提要：第五章数组目标、要求：要求掌握数组的逻辑结构定义和存储方法、特殊矩阵和稀疏矩阵的压缩方法以及数组经过压缩存储后基本运算的实现。重点、难点：数组经过压缩存储后基本运算的实现。数组是一种典型的数据结构。由于数组中各元素之间的关系仍具备线性结构的特征，故数组也是一种线性结构。数组的数据元素也可以是结构类型。由于在程序设计语言中都把数组类型定为固有类型，提供给编程人员使用，这使得大家非常熟悉。因此，本章从数组的定义、存储方式和运算处理方面简单加以介绍。5.1数组的逻辑结构及表示一、数组的逻辑结构1、数组(Array):简单说是数据类型相同的一组数据元素的有序集合，元素在集合中的序是由一组称作”下标”的值确定的，一个数据元素称为一个数组元素。一个数据元素的位置由多个下标值确定，即参与多个线性关系，每个线性关系上都有前驱，后继！2、数组的维数:确定一个数据元素在集合位置的下标的个数。5.1数组的逻辑结构及表示3、数组的逻辑结构定义:1_Array=(D,R)D={ai|i=c1……..d1ai∈D0}“一维”R={N}N={ai-1,ai|ai-1,ai∈D0c1+1=i=d1}5.1数组的逻辑结构及表示2_Array=(D,R)D={aij|i=c1……..d1j=c2…d2aij∈D0}“二维”R={Row,Col}Row={aij,aij+1|aij,aij+1∈D0c1=i=d1c2=j=d2-1}Col={aij,ai+1j|aij,ai+1j∈D0c1=i=d1-1c2=j=d2}注意：1、数组中每个数据元素受多个线性关系制约，元素在每个线性关系上都有前驱、后继。2、一个N维数组可以看作一个线性表，其每个数据元素是一个N-1维的数组。5.1数组的逻辑结构及表示4、数组的操作：初始化Creat(A)赋值Store(A,Index,Value)取一元素Get(A,Index)5.1数组的逻辑结构及表示ADTArray{Datastructure:N-Array={D,R}D={aj1j2…jm|ji=ci……..dii=1,2…naj1j2….jm∈D0}R={R1,R2….Rn}Ri={aj1j2..ji..jn-1,aj1j2..jn|aj1j2..ji..jn-1∈D0ck=jk=dk1=k=nkici=ji=di-1}Operations:Creat(A)Store(A,Index,Value)Get(A,Index)}ADTArray5、数组的ADT定义：5.2数组的顺序存储表示及操作的实现由于数组数据结构的运算较少，且没有插入、删除运算，所以一般采用顺序存储结构。一、数组的顺序存储结构1、存储方式：同一般线性表的顺序存储结构完全相同，用一组地址连续的存储单元依次存放数组的各个元素。但是，在一般线性表时是第i个存储单元存储第i个数据元素（由于只有一个线性关系）那么在数组中第i个存储单元存储哪个数据元素呢？因为元素位置受多个线性关系的制约（即哪个关系上的顺序号？？）5.2数组的顺序存储表示及操作的实现2、数据元素的存储位置：假设数组的每个元素占用L个存储单元，第1个数据元素的存储地址已知，根据顺序存储的特点可以容易地求出任意一个元素的存储地址！用Loc(a)表示元素a的地址一维数组：A[c1…..d1]Loc(a[i])=Loc(a[c1])+(i-c1)*L……..a[c1]a[i]5.2数组的顺序存储表示及操作的实现2、数据元素的存储位置：假设数组的每个元素占用L个存储单元，第1个数据元素的存储地址已知，根据顺序存储的特点可以容易地求出任意一个元素的存储地址！用Loc(a)表示元素a的地址一维数组：A[c1…..d1]行主序：Loc(a[i])=Loc(a[c1])+(i-c1)*L列主序：Loc(a[i])=Loc(a[c1])+(i-c1)*L…….