数据结构5-数组.ppt

,2006-9,华中科技大学计算机学院(5),数据结构,第五章数组和广义表引言：线性表：L=(a1,a2,.,an)，ai是同类型的元素，1in数组:A=(a1,a2,.,an)若ai是同类型的元素，A是一维数组，1in若ai是同类型的定长线性表，A是多维数组，1in广义表：Ls=(a1,a,.,an)ai可以是同类型的元素或不定长的线性表，1in5.1数组及其操作简单地说，向量和矩阵称为数组。5.1.1数组的递归定义1.一维数组是一个定长线性表(a1,a2,.,an)。其中：ai为元素，i为下标/序号，1in(a1,a2,.,an)又称为向量。,2.二维数组是一个定长线性表(1,2,.,m)，其中:i=(ai1,ai2,.,ain)为行向量，1im由m个行向量组成，记作：,(a11a12.a1n)(a21a22.a2n).(am1am2.amn),Am*n=,即Am*n=(a11a12.a1n),(a21a22.a2n),.,(am1am2.amn)或由n个列向量组成，记作：,),),a11a12a1na21a22a2nam1am2amn,),),),),Amxn=,3.三维数组是一个定长线性表(1,2,.,p)。其中:k=(1,2,.,m)为定长二维数组，1kp例三维数组A1.3,1.4,1.2,p=3,m=4,n=2,a111a112a121a122a131a132a141a142,a211a212a221a222a231a232a241a242,a311a312a321a322a331a332a341a342,第1页,第2页,第3页,5.1.2数组的类型定义和变量说明：例1inta10；/10个整数的一维数组charb45；/4行5列个字符的二维数组floatc342；/3*4*2个实数的三维数组,A3*4*2=,例2#definem4/定义符号常量m#definen5/定义符号常量nintam；/m个整数的一维数组charbmn；/m行n列个字符的二维数组例3#definem4/定义符号常量m#definen5/定义符号常量ntypedefintaram；/一维数组类型aratypedefchararbmn；/二维数组类型arbaraa；/ara类型的变量aarbb；/arb类型的变量bC语言中定义静态数组时，元素数目必须是常量错例1intm=4,n=5；intamn；/m,n是变量错例2intp；scanf(”%d”,&p)；intcp；/p是变量,5.1.3数组的操作1.生成一个数组：inta7；/生成静态一维数组(存储结构）2.销毁一个数组3.赋值/修改a1=15；(a1)+；4.取元素的值：a0=a1*2；5.1.4程序设计举例例1main()inti,a10；/生成一维数组afor(i=0；i10；i+)scanf(”%d”,&ai)；/输入元素for(i=0；i10；i+)printf(”%d”,ai*ai)；/输出元素的平方,a,0123456,a,0123456,例2生成动态的10个整数的一维数组int*pa；/指针变量papa=(int*)malloc(10*sizeof(int)；/动态数组pa*main()inti,n,*pa；scanf(”%d”,&n)；/动态输入npa=(int*)malloc(n*sizeof(int)；/生成动态数组*pafor(i=0；in；i+)*(pa+i)=2*i；/指针法引用数组元素,赋值for(i=0；in；i+)printf(“%d,”,*(pa+i)；/输出数组元素0,2,4,6,.for(i=0；in；i+)scanf(“%d”,&pai)；/下标法引用数组元素,输入for(i=0；in；i+)printf(%d,pai)；/输出数组元素free(pa)；/释放(销毁)数组空间,pa,0123456789,5.2数组的顺序表示和实现5.2.1顺序表示(顺序存储结构）1.以行序为主序的顺序存储方式左边的下标后变化，右边的下标先变化2.以列序为主序的顺序存储方式左边的下标先变化，右边的下标后变化例1二维数组a1.3,1.2,b是首地址,s是元素所占的单元数,a11a12a21a22a31a32,序号内存地址,123456,123456,序号内存地址,bb+sb+2*sb+3*sb+4*sb+5*s,bb+sb+2*sb+3*sb+4*sb+5*s,以行序为主序,以列序为主序,逻辑结构,例2三维数组a1.2,1.3,1.2,a111a112a121a122a131a132,序号内存地址,123456789101112,序号内存地址,bb+sb+2*sb+3*sb+4*sb+5*sb+6*sb+11*s,bb+sb+2*sb+3*sb+4*sb+5*sb+6*sb+11*s,以行序为主序,以列序为主序,逻辑结构,a211a212a221a222a231a232,第1页,第2页,123456789101112,5.2.2数组的映象函数数组元素的存储地址例1一维数组a0.n-1设:b为首地址,s为每个元素所占的存储单元数则:元素ai的存储地址：Loc(i)=Loc(0)+i*s=b+i*s0in-1,下标012in-1地址bb+sb+2*sb+i*sb+(n-1)*s,下标123in地址bb+sb+2sb+(i-1)sb+(n-1)s,例2一维数组a1.n,元素ai的存储地址Loc(i)=Loc(1)+(i-1)*s=b+(i-1)*s1in例3二维数组a1.m,1.n,假定无零行零列,a11.a1j.a1n.ai1.aij.ain.am1.amj.amn,Amxn=,(1)以行序为主序，aij的地址为Loc(i,j)=Loc(1,1)+(n*(i-1)+j-1)*s=b+(n*(i-1)+j-1)*s1im,1jn其中：b为首地址，s为每个元素所占的存储单元数n-列数m-行数,共i-1行,共j-1列,例3二维数组a1.m,1.n,假定无零行零列,a11a11.a1j.a1n.ai1ai1.aij.ain.am1am1.amj.amn,Amxn=,(2)以列序为主序，aij的地址为Loc(i,j)=Loc(1,1)+(m*(j-1)+i-1)*s=b+(m*(j-1)+i-1)*s1im,1jn其中：b为首地址，s为每个元素所占的存储单元数n-列数m-行数,共i-1行,共j-1列,例4二维数组a0.m-1,0.n-1（有零行零列）,a00.a0j.a0n-1a10.a1j.a1n-1.ai0.aij.ain-1.am-10.am-1j.am-1n-1,Amxn=,(1)以行序为主序，aij的地址为Loc(i,j)=Loc(0,0)+(n*i+j)*s=b+(n*i+j)*s0im-1,0jn-1其中：b为首地址，s为每个元素所占的存储单元数n-列数m-行数,共i行,共j列,例4二维数组a0.m-1,0.n-1（有零行零列）,a00a01.a0j.a0n-1a10a11.a1j.a1n-1.ai0ai1.aij.ain-1.am-10am-11.am-1j.am-1n-1,Amxn=,(2)以列序为主序，aij的地址为Loc(i,j)=Loc(0,0)+(m*j+i)*s=b+(m*j+i)*s0im-1,0jn-1其中：b为首地址，s为每个元素所占的存储单元数n-列数m-行数,共i行,共j列,例5三维数组a1.p,1.m,1.n,假定无0页0行0列1)以行序为主序，akij的地址为Loc(k,i,j)=Loc(1,1,1)+(m*n*(k-1)+n(i-1)+j-1)*s=b+(m*n*(k-1)+n(i-1)+j-1)*s1kp,1im,1jn其中：b为首地址，s为每个元素所占的存储单元数p-页数n-列数m-行数(2)以列序为主序，akij的地址为Loc(k,i,j)=Loc(1,1,1)+(p*m*(j-1)+p*(i-1)+k-1)*s=b+(p*m*(j-1)+p*(i-1)+k-1)*s1kp,1im,1jn其中：b为首地址，s为每个元素所占的存储单元数p-页数n-列数m-行数,例5三维数组a0.p-1,0.m-1,0.n-1,(1)以行序为主序，akij的地址为Loc(k,i,j)=Loc(0,0,0)+(m*n*k+n*i+j)*s=b+(m*n*k+n*i+j)*s0kp-1,0im-1,0jn-1其中：b为首地址，s为每个元素所占的存储单元数p-页数n-列数m-行数(2)以列序为主序，akij的地址为Loc(k,i,j)=Loc(0,0,0)+(p*m*j+p*i+k)*s=b+(p*m*j+p*i+k)*s0kp-1,0im-1,0jn-1其中：b为首地址，s为每个元素所占的存储单元数p-页数n-列数m-行数,5.3矩阵的压缩存储5.3.1特殊矩阵的压缩存储1.n阶对称矩阵,a11a1najiaijan1ann,Anxn=,上三角,下三角,aij=aji1i,jn,假定以行序为主，顺序存储下三角元素到SA1.maxleng：,k=1234.i(i-1)/2+j.n(n+1)/2,如何求aij在SA中的位置，即序号k？,(1)设aij在下三角，ij第1i-1行共有元素1+2+3+(i-1)=i(i-1)/2(个)ai1aij共有j个元素aij的序号为:k=i(i-1)/2+j(2)设aij在上三角,ij上三角的aij=下三角的aji下三角的aji的序号为k=j(j-1)/2+iij上三角的aij的序号为k=j(j-1)/2+iij由(1)和(2)，任意aij在SA中的序号，为i(i-1)/2+jijj(j-1)/2+ii0其中:e1-LS的表头/首部，记作:Head(LS)=e1(e2,.,en)-LS的表尾/尾部,记作：Tail(LS)=(e2,.,en),例(1)A=()/空表(2)B=(e)Head(B)=eTail(B)=()(3)C=(a,b,c)Head(C)=aTail(C)=(b,c)Head(Tail(C)=bTail(Tail(C)=(c)(4)D=(a,(b,c)Head(D)=aTail(D)=(b,c)D2=(a,b),c)Head(D2)=(a,b)Tail(D2)=(c)(5)E=(a,b),c,(d,e)Head(E)=(a,b)Tail(E)=(c,(d,e)Head(Tail(E)=cTail(Tail(E)=(d,e)(6)F=(A,B,C,d)=(),(e),(a,b,c),d)Head(F)=()Tail(F)=(e),(a,b,c),d),(7)G=(a,G)/递归广义表=(a,(a,G)=(a,(a,(a,G)=(a,(a,(a,(a,.G)Head(G)=aTail(G)=(G)=(a,G)(8)H=(),(),()Head(H)=()Tail(H)=(),()5.4.2广义表的图型表示-树型结构约定-单元素/原子-列表,若有表名,附表名例(1)A=()(2)B=(a),A,B,(3)C=(a,b,c)(4)D=(a,(b,c),C,B,(5)E=(a,b),c,(d,e),(6)F=(A,B,C,d)=(),(e),(a,b,c),d),E,F,B,A,C,(7)G=(a,G)(8)H=(),(),(),H,G,G,G,.,5.4.3广义表的操作1.求长度：Leng(LS)a=()Leng(A)=0G=(a,G)Leng(G)=2H=(),(),()Leng(H)=2F=(A,B,C,d)Leng(F)=4,2.求表头：Head(LS)G=(a,G)Head(G)=aE=(a,b),c,(d,e)Head(E)=(a,b)3.求表尾：Tail(LS)G=(a,G)Tail(G)=(G)=(a,G)E=(a,b),c,(d,e)Tail(E)=(c,(d,e)4.求第i个元素：GetElem(LS,i)=ei1inI=(a,b),c,(),(d)GetElem(I,1)=(a,b)Get(I,2)=CGetE