数据结构与算法 课件.ppt

《数据结构与算法 课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章.数组和广义表（Chapter5.ArraysandGeneralizedLists）§5.1数组的定义数组和广义表都是数据元素为结构类型的一种特殊的线性表。数组的每一个元素的结构都是相同的。数组通常分为二维数组、三维数组…和n维数组。2-Array=(D,R)D={aij

2、i=0,1,…,d1-1,j=0,1,…,d2-1,aij∈D0}R={ROW,COL}ROW={

3、0≤i≤d1-1,0≤j≤d2-2,aij,ai,j+1∈D}COL={

4、0≤i≤d1-

5、2,0≤j≤d2-1,aij,ai+1,j∈D}D0为某数据对象，d1,d2为整数。下面是二维数组的定义：下面是多维数组的定义：n-Array=(D,R)D={aj1j2…jn

6、ji=0,1,…,di-1,i=1,2,…,n,(n>0),aj1j2…jn∈D0}R={R1,R2,…,Rn}Ri={

7、0≤jk≤dk-1,1≤k≤n,且k≠i,0≤ji≤di-2,aj1...ji…jn,aj1...ji+1…jn∈D,D0为某数据对象，di为整数。i=2,3,…,

8、n}求每个给定下标的数据元素的存储地址：§5.2数组的顺序存储数组的顺序存储有两种存储方式：即按行优先（rowmajororder）存储或按列优先（columnmajororder）存储。Loc(j1,j2,…,jn)=Loc(0,0,…,0)+[d2*…*dn*j1+d3*…*dn*j2+...+dn*jn-1+jn]*l=Loc(0,0,…,0)+(∑ji∏dk+jn)*li=1k=i+1n-1n这就说明了多维数组是一种随机存取的存储结构。§5.3矩阵压缩存储矩阵是很多科学与工程计算中常使用的数据结构。在实际

9、应用中，很多矩阵存在大量零元素或重复元素，为节省存储空间，可对这类矩阵进行压缩存储。=Loc(0,0,…,0)+∑ci*jii=1n其中ci=l,ci-1=di*ci,1＜i≤n特殊矩阵：这类矩阵由于零元素或重复元素的分布很有规律，可以很容易地把矩阵压缩存储在一个一维数数组中。An×nBm，即B[k]=A[i][j]，需求出下标映射函数k=f(i,j)。上三角矩阵0对角矩阵000下三角矩阵ajiaij对称矩阵稀疏矩阵：这类矩阵非零元素很少，但它们的分布没有规律，因此在压缩存储时须同时存储非零元素的下标和值。可用三

10、元组表（listof3-tuples）来存储（行号，列号，值）。如下三角矩阵有映射k=i(i-1)/2+j(i≥j),Aij=Bk(i≥j)，Aij=0(i

11、ct{tripledata[MAXNUM+1];intmu,nu,tu;}matrix;稀疏矩阵还可用带行索引的二元组表、十字链表等表示。最常用的一种算法是求矩阵的转置：因三元组表是按行优先排序的，故需先确定转置后矩阵各行的元素个数，预留出位置再进行转置。ijv1212211253345522566ijv1212112252435523656A’作业9.设有上三角矩阵（aij)n×n，将其上三角元素逐行存于数组B(1:m)中，使得B[k]=aij，且k=f1(i)+f2(j)+c。试推导函数f1、f2和常数项c，

12、其中1≤i，j≤n。10.设计一个算法，将数组A(1:n)中的元素循环右移k位，要求只用一个元素的附加空间，元素移动或交换次数为O(n)。§5.4广义表的定义广义表又称列表，其每一个元素的结构都可能是不同的。Lists=(D,R)D={di

13、i=1,2,…,n,n≥0,且di∈D0或di∈Lists}R={LR}LR={

14、di-1,di∈D,2≤i≤n}通常广义表记着：LS=(d1,d2,d3,...,dn)其中D0为某数据对象，di可以是原子（atom），也可以是广义表，称为LS的子表（sub

15、list）。其中第一个元素d1称为表LS的表头（head），由余下元素组成的表(d2,d3,...,dn)称为LS的表尾（tail）。广义表中括号的重数称为广义表的深度。函数Head与函数Tail分别求广义表的表头和表尾。函数Depth求广义表的深度。如下列均为广义表：1、A=()3、C=(a,(a,b,c))4、D=(A,B,C,d)5、E=(E,e)2、B=(a)1、