[计算机软件及应用]结构体 数组 结构体数组

《[计算机软件及应用]结构体 数组 结构体数组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章数组4.1数组定义及基本操作4.2数组的存储结构4.3特殊矩阵的压缩存储4.4稀疏矩阵的压缩存储4.5数组的运算7/20/20211数组是我们最常用的一种数据结构，各种计算机语言均有此类型。例如：顺序表、顺序栈、循环队列等。１．数组的定义：数组：是ｎ（ｎ＞１）个相同数据类型的数据元素a0,a1…an-1,构成的占用一块连续的内存单元的有限序列。数组特点：1.有限个元素的集合；2.所有元素具有相同的特性；3.元素名由数组名和下标组成；4.下标值与元素对应（代表元素的位置）。4.1数组的定义及操作7/20/20212数组与线性表:相同

2、之处:由若干个相同数据类型的数据元素组成.不同之处:1.存储单元连续与否2.数据元素在逻辑意义上可分与否3.操作不同。7/20/20213２.数组的逻辑结构一维数组（a0,a1,a2,a3,…an-1）满足线性关系；二维或二维以上数组：（以二维为例）Amxn=aa…..aa00a02…….a0n-110111n-1……...aaam-10m-12m-1n-1看元素a11有两个直接前趋a10和a02两个直接后继a21和a12三维数组:每个元素有三个直接前趋和三个直接后继.可见:数组(除一维数组外)是一种复杂的非线性数据结构.7/20/20

3、214但是:1)可将Amxn看成由m个行向量组成的向量,即Amn={(a00,a01,……a0n-1),(a10,a11,……a1n-1),……(am-10,am-11,……am-1n-1)}2)将Amxn看成由n个列向量组成的向量,即Amn=((a00,a10,……am-10),(a01,a11,……am-11)……(a0n-1,a1n-1,……am-1n-1))列向量为线性.元素1元素2元素m看(ai0,ai1,…..ain-1),除ai0,ain-1外只有一个直接前趋和一个直接后继.元素1元素2元素n7/20/20215据此数组可

4、看成是线性表的扩展:即线性表中的数据元素本身也是一个数据结构.数组可表示成两类线性表:1.以行向量做线性表的一个元素;2.以列向量做线性表的一个元素.7/20/20216３．数组抽象数据类型：数据集合：数组的数据集合可表示为a0,a1…an-1,每个数据元素的类型为抽象数据类型:DataType．（限定顺序存储）数据关系:线性关系.操作集合：各种高级程序设计语言的操作各不相同，必备的操作有：（1）求数组元素个数（2）随机取（3）随机存（4）矩阵运算7/20/20217一般数组:(以二维数组为例)多采用顺序存储:(1).按行优先顺序存储假

5、设：Am×n=a00a01a02…a0n-1a10…a00a01a02a03…a0n-1a10a11a12a13…a1n-1…am-10am-11am-12am-13…am-1n-1即a00,a01,a02……a0n-1,a10,a11,…...a1n-1……aij的存储地址:am-1,04.2数组的存储结构:7/20/20218L:为每个元素所占存储单元.Pascal和C语言中数组存储为此方式.Loc(aij)=Loc(a00)+(i*n+j)*L(2).列优先顺序存储,即a00,a10,a20……am-10,a01,a11,…...

6、am-11……aij存储地址:Loc(aij)=Loc(a00)+(j*m+i)*LFortran语言采用此方法.a00a10a20…am-10a01…可见:数组是一种随机存储结构.存取任意元素的时间相等7/20/20219推广:假设:A[c1--d1][c2--d2]例：二维数组floata[4][3].计算（1）数组元素数目？（2）若数组Loc(a00)=1000,且L=4,数组元素a[3][2]的地址?(按行优先存储)4*3=12Loc(a32)=Loc(a00)+(i*n+j)*L=1000+(3*3+2)*4=1044Loc(

7、aij)=Loc(ac1c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L按行优先顺序存储：Loc(aij)=Loc(ac1c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*L按列优先顺序存储：7/20/202110特殊矩阵：指有一定量的零元素（或相同元素），并且其分布（非零元素的位置）有一定的规律。采用压缩顺序存储方式:只存非零元素,节省空间.1.下三角矩阵:存放形式:{a00,a10,a11,a20,a21,…an-10,an-11,…an-1n-1}4.3特殊矩阵的压缩存储a0000……..0a10a110…

8、….0……………….0an-10an-11…..an-1n-1Ann=可以是0和常数C第1行：1个第2行：2个第3行：3个……第n行：n个1+2+3+4+5+…+n=n(n+1)/27/20/2