数据结构5数组

《数据结构5数组》由会员分享，可在线阅读，更多相关《数据结构5数组（29页珍藏版）》请在装配图网上搜索。

1、 2006-9华中科技大学计算机学院(5)数据结构 第五章 数组和广义表引言：线性表：L=(a1,a2,.,an)，ai是同类型的元素，1in 数组:A=(a1,a2,.,an)若ai是同类型的元素，A是一维数组，1in 若ai是同类型的定长线性表，A是多维数组，1in 广义表：Ls=(a1,a,.,an)ai可以是同类型的元素或不定长的线性表，1in 5.1 数组及其操作 简单地说，向量和矩阵称为数组。5.1.1 数组的递归定义 1.一维数组是一个定长线性表(a1,a2,.,an)。其中：ai为元素，i为下标/序号，1in (a1,a2,.,an)又称为向量。2.二维数组是一个定长线性表(1

2、,2,.,m)，其中:i=(ai1,ai2,.,ain)为行向量，1im 由m个行向量组成，记作：(a11 a12 .a1n )(a21 a22 .a2n ).(am1 am2 .amn )Am*n=即 Am*n=(a11 a12.a1n),(a21 a22.a2n),.,(am1 am2.amn)或由n个列向量组成，记作：)a11 a12 a1n a21 a22 a2n am1 am2 amn)Amxn=3.三维数组是一个定长线性表(1,2,.,p)。其中:k=(1,2,.,m)为定长二维数组，1kp 例 三维数组A1.3,1.4,1.2,p=3,m=4,n=2a111 a112a121 a

3、122a131 a132a141 a142a211 a212a221 a222a231 a232a241 a242a311 a312a321 a322a331 a332a341 a342第1页第2页第3页5.1.2 数组的类型定义和变量说明：例1 int a10；/10个整数的一维数组 char b45；/4行5列个字符的二维数组 float c342；/3*4*2个实数的三维数组A3*4*2=例2#define m 4 /定义符号常量m#define n 5 /定义符号常量n int am；/m个整数的一维数组 char bmn；/m行n列个字符的二维数组例3#define m 4 /定义符

4、号常量m#define n 5 /定义符号常量n typedef int aram；/一维数组类型ara typedef char arbmn；/二维数组类型arb ara a；/ara类型的变量a arb b；/arb类型的变量b C语言中定义静态数组时，元素数目必须是常量错例1 int m=4,n=5；int amn；/m,n是变量错例2 int p；scanf(”%d”,&p)；int cp；/p是变量5.1.3 数组的操作 1.生成一个数组：int a7；/生成静态一维数组(存储结构）2.销毁一个数组 3.赋值/修改 a1=15；(a1)+；4.取元素的值：a0=a1*2；5.1.4

5、程序设计举例例1 main()int i,a10；/生成一维数组a for(i=0；i10；i+)scanf(”%d”,&ai)；/输入元素 for(i=0；i10；i+)printf(”%d”,ai*ai)；/输出元素的平方 a 0 1 2 3 4 5 6 32 16a 0 1 2 3 4 5 6 例2 生成动态的10个整数的一维数组 int *pa；/指针变量pa pa=(int*)malloc(10*sizeof(int)；/动态数组pa*main()int i,n,*pa；scanf(”%d”,&n)；/动态输入n pa=(int*)malloc(n*sizeof(int)；/生成动态

6、数组*pa for(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 0 1 2 3 4 5 6 7 8 95.2数组的顺序表示和实现 5.2.1顺序表示(顺序存储结构）1.以行序为主序的顺序存储方式 左边的下标后变化，右边的下标先变化 2.以列序为主序的顺序存储方

7、式 左边的下标先变化，右边的下标后变化例1 二维数组a1.3,1.2,b是首地址,s是元素所占的单元数 a11 a12a21 a22a31 a32a11a12a21a22a31a32a11a21a31a12a22a32序号 内存 地址123456123456序号 内存 地址bb+sb+2*sb+3*sb+4*sb+5*sbb+sb+2*sb+3*sb+4*sb+5*s以行序为主序以列序为主序逻辑结构例2 三维数组a1.2,1.3,1.2a111 a112a121 a122a131 a132a111a112a121a122a131a132a211a212a221a222a231a232序号 内存

8、 地址123456789101112序号 内存 地址bb+sb+2*sb+3*sb+4*sb+5*sb+6*sb+11*sbb+sb+2*sb+3*sb+4*sb+5*sb+6*sb+11*s以行序为主序以列序为主序逻辑结构a211 a212a221 a222a231 a232第1页第2页123456789101112a111a211a121a221a131a231a112a212a122a222a132a2325.2.2数组的映象函数 数组元素的存储地址 例1 一维数组a0.n-1 设:b为首地址,s为每个元素所占的存储单元数 则:元素ai的存储地址：Loc(i)=Loc(0)+i*s=b+

9、i*s 0in-1 a0a1a2.ai.a(n-1)下标 0 1 2 i n-1地址 b b+s b+2*s b+i*s b+(n-1)*sa1a2a3.ai.an下标 1 2 3 i n地址 b b+s b+2s b+(i-1)s b+(n-1)s例2 一维数组a1.n 元素ai的存储地址 Loc(i)=Loc(1)+(i-1)*s=b+(i-1)*s 1in 例3 二维数组a1.m,1.n,假定无零行零列a11 .a1j .a1n.ai1 .aij .ain.am1 .amj .amnAmxn=(1)以行序为主序，aij的地址为 Loc(i,j)=Loc(1,1)+(n*(i-1)+j-1

10、)*s =b+(n*(i-1)+j-1)*s 1im,1jn其中：b为首地址，s为每个元素所占的存储单元数 n-列数 m-行数 共i-1行共j-1列例3 二维数组a1.m,1.n,假定无零行零列a11 a11.a1j .a1n.ai1 ai1.aij .ain.am1 am1.amj .amnAmxn=(2)以列序为主序，aij的地址为 Loc(i,j)=Loc(1,1)+(m*(j-1)+i-1)*s =b+(m*(j-1)+i-1)*s 1im,1jn其中：b为首地址，s为每个元素所占的存储单元数 n-列数 m-行数 共i-1行共j-1列例4 二维数组a0.m-1,0.n-1（有零行零列）

11、a00 .a0j .a0n-1a10 .a1j .a1n-1.ai0 .aij .ain-1.am-10.am-1j .am-1n-1Amxn=(1)以行序为主序，aij的地址为 Loc(i,j)=Loc(0,0)+(n*i+j)*s =b+(n*i+j)*s 0im-1,0jn-1其中：b为首地址，s为每个元素所占的存储单元数 n-列数 m-行数 共i行共j列例4 二维数组a0.m-1,0.n-1（有零行零列）a00 a01.a0j .a0n-1a10 a11.a1j .a1n-1.ai0 ai1.aij .ain-1.am-10 am-11.am-1j.am-1n-1Amxn=(2)以列序

12、为主序，aij的地址为 Loc(i,j)=Loc(0,0)+(m*j+i)*s =b+(m*j+i)*s 0im-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)*s 1kp,1im,1jn其中：b为首地址，s为每个元素所占的存储单元数 p-页数 n-列数 m-行数(2)以列序为主序，akij的地址为 Loc(k,

13、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)*s 1kp,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)*s 0kp-1,0im-1,0jn-1其中：b为首地址，s为每个元素所占的存储单元数 p-页数 n-列数 m-行数(2)以列序为主序，akij的地址为 Loc

14、(k,i,j)=Loc(0,0,0)+(p*m*j+p*i+k)*s =b+(p*m*j+p*i+k)*s 0kp-1,0im-1,0jn-1其中：b为首地址，s为每个元素所占的存储单元数 p-页数 n-列数 m-行数 5.3 矩阵的压缩存储5.3.1特殊矩阵的压缩存储 1.n阶对称矩阵a11 a1n aji aij an1 annAnxn=上三角下三角aij=aji1i,jn假定以行序为主，顺序存储下三角元素到SA1.maxleng：a11a21a22a31.ai1.aij.aii.an1.annk=1 2 3 4 .i(i-1)/2+j .n(n+1)/2如何求aij在SA中的位置，即序号

15、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+i ij 上三角的aij的序号为 k=j(j-1)/2+i ij 由(1)和(2)，任意aij在SA中的序号，为 i(i-1)/2+j ij j(j-1)/2+i i0 其中:e1-LS的表头/首部，记作:Head(LS)=e1 (e2,.,en)-LS的表尾/尾部,记作：Tail(LS)=(e2,.,en)例(1)A=(

16、)/空表 (2)B=(e)Head(B)=e Tail(B)=()(3)C=(a,b,c)Head(C)=a Tail(C)=(b,c)Head(Tail(C)=b Tail(Tail(C)=(c)(4)D=(a,(b,c)Head(D)=a Tail(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)=c Tail(Tail(E)=(d,e)(6)F=(A,B,C,d)=(),(e),(a,b,c),d)Head(F)=()Tail(F

17、)=(e),(a,b,c),d)(7)G=(a,G)/递归广义表 =(a,(a,G)=(a,(a,(a,G)=(a,(a,(a,(a,.G)Head(G)=a Tail(G)=(G)=(a,G)(8)H=(),(),()Head(H)=()Tail(H)=(),()5.4.2 广义表的图型表示-树型结构约定 -单元素/原子 -列表,若有表名,附表名例 (1)A=()(2)B=(a)ABa(3)C=(a,b,c)(4)D=(a,(b,c)CbBacabc(5)E=(a,b),c,(d,e)(6)F=(A,B,C,d)=(),(e),(a,b,c),d)EbcaedadecbFBACa(7)G=(

18、a,G)(8)H=(),(),()HGaaGaG.5.4.3 广义表的操作 1.求长度：Leng(LS)a=()Leng(A)=0 G=(a,G)Leng(G)=2 H=(),(),()Leng(H)=2 F=(A,B,C,d)Leng(F)=42.求表头：Head(LS)G=(a,G)Head(G)=a E=(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)=ei 1in I=(a,b),c,(),(d)GetElem(I,1)=(a,b)Get(I,2)=C GetElem(E,3)=()Get(I,4)=(d)5.求深度：Depth(LS)-LS所含括号的层数 (1)A=()Depth(A)=1 (2)E=(a,b),c,(d,e)Depth(E)=2 (3)H=(),(),()Depth(H)=36.插入：InsertFirst(LS,e)-e插入LS的第一个位置 设 A=()执行：InsertFirst(A,a)；得：A=(a)执行：InsertFirst(A,(b,(c)；得：A=(b,(c),a)执行：InsertFirst(A,()；得：A=(),(b,(c),a)7.其它：.