电子科数据结构pascal版课件chapt

第五章 数组和广义表5.1 数组和广义表的定义5.2 数组和广义表的基本运算5.3 数组的存储结构5.1数组和广义表的定义

数组和广义表可以视为是线性表的扩展，即线性表中的数据元素本身也是一个数据结构。⒈二维数组定义

┌

a11a12

…a1n

┐

Amxn＝│a21a22

…a2n││·

·││·

·│

└am1am2

…amn

┘(1)Amxn可定义为一个线性表A＝(1,2,…,n)，其中：每个数据元素j(j＝1,2,…n)又是一个列向量的线性表，即：j＝(a1j,a2j,…,amj),1≤j≤n

5.1数组和广义表的定义(2)二维数组Amxn可定义为一个线性表：A＝(1,2,…,m)其中：每个数据元素j又是一个行向量的线性表，即：j＝(aj1,aj2,…,ajn),1≤j≤m即A＝(1,2,…,m)＝((a11,a12,…,a1n),(a21,a22,…,a2n),…,(am1,am2,…,amn))┌

a11a12

…a1n

┐

Amxn＝│a21a22

…a2n││·

·││·

·│

└am1am2

…amn

┘类似地，可以定义n维数组。5.1数组和广义表的定义(3)二维数组的形式定义2_array=(D,R)其中,D={aij|aijD0,i=c1,c1+1,…,d1,j=c2,c2+1,…,d2}R={ROW,COL}ROW={<ai,j-1,aij>|ai,j-1,aijD,c1id1,c2+1jd2}COL={<ai-1,j,aij>|ai-1,j,aijD,c1+1id1,c2jd2}D0为某个数据对象上述数组可表示为:A[c1:d1,c2:d2]维数:2第一维维长w1=d1-c1+1;第二维维长w2=d2-c2+1元素个数=w1*w2=(d1-c1+1)*(d2-c2+1)5.1数组和广义表的定义⒉广义表定义广义表可定义为：数据元素可以是表的线性表。

它的形式化定义为：Lists=(D,R)其中，D={di|di∈D0或di∈Lists,i=1,2,...,n,n0}R={N}N={<di-1,di>|di-1,di∈D,i=2,3,...,n}D0为某个数据对象5.1数组和广义表的定义广义表也称列表,记为：LS＝(d1,d2,…,dn)LS为表名di∈D0时，称di为单元素(用小写字母表示)；di∈Lists时,称di为子表(用大写字母表示)；n为表的长度，当长度为0时称为空表；n>0时,第一个元素d1为表头;n>0时,(d2,…,dn)称为表尾。5.1数组和广义表的定义例:A=()B=(e)C=(a,(b,c,d))D=(A,B,C){即D=((),(e),(a,(b,c,d)))}E=(a,E){定义一个无限表(a,(a,(a,…)))}5.2数组和广义表的基本运算⒈数组的基本运算

⑴给定下标，存取相应的数据元素；⑵给定下标，修改相应的数据元素。⒉广义表的基本运算

⑴取表头函数HEAD(LS)； ⑵取表尾函数TAIL(LS)。5.2数组和广义表的基本运算例:对C=(a,(b,c,d)),取出其中的cHEAD(TAIL(HEAD(TAIL(C))))第一步:((b,c,d))第二步:(b,c,d)第三步:(c,d)第四步:c5.3数组的存储结构数组的顺序存储结构

由于数组不作插入、删除操作，所以常采用顺序存储结构来实现数组，即用一组连续的存储单元，以行主(或列主)顺序依次存放数组的数据元素。(1)按行存放设每个数据元素占L个存储单元，di为第i维的下标上界，ci为第i维的下标下界，令wi=di-ci+1,则二维数组中任一元素a[i,j]的存储地址为：

Loc[i,j]＝Loc[c1,c2]+((i-c1)*w2+(j-c2))*L5.3数组的存储结构三维数组中任一元素a[i,j,k]的存储地址为：

Loc[i,j,k]＝Loc[c1,c2,c3]+((i-c1)*w2*w3+(j-c2)*w3+(k-c3))*Ln维数组中任一元素a[j1,j2,…,jn]的存储地址为：设数组A[c1:d1,c2:d2,…,cn:dn]

Loc[j1,j2,…,jn]＝Loc[c1,c2,…,cn]+((j1-c1)*w2*w3*...*wn+(j2-c2)*w3*w4*...*wn

+…+(jn-1-cn-1)*wn+(jn-cn))*L5.3数组的存储结构令Loc[j1,j2,…,jn]＝CONSPART+VARPART其中,CONSPART=Loc[c1,c2,…,cn]-CC=(c1*w2*w3...*wn+c2*w3*w4...*wn+…+cn-1*wn+cn)*L=((…((c1*w2+c2)*w3+c3)*w4+…+cn-1)*wn+cn)*LVARPART=(j1*w2*w3...*wn+j2*w3*w4...*wn+…+jn-1*wn+jn)*L=((…((j1*w2+j2)*w3+j3)*w4+…+jn-1)*wn+jn)*L5.3数组的存储结构(2)按列存放设每个数据元素占L个存储单元，di为第i维的下标上界，ci为第i维的下标下界，令wi=di-ci+1,则二维数组中任一元素a