第5章数组和广义表ppt课件.ppt

《第5章数组和广义表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组和广义表元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即线性表的推广）。数组和广义表的特点：特殊的线性表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构第5章数组和广义表5.1数组的定义数组：由一组名字相同、下标不同的同类型的元素组成数组特点数组结构固定,下标一般具有固定的上界和下界数据元素具有统一的类型数组运算给定一组下标，取相应的数据元素.给定一组下标，修改数据元素的值.数组的处理比其它复杂的结构要简单与高级语言中数组的区别：1、本章所讨论的数组是一种数据结构，而高级语言中数组是一种数据

2、类型。2、高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。二维数组的特点：一维数组的特点：1个下标，ai是ai+1的直接前驱2个下标，每个元素aij受到两个关系（行关系和列关系）的约束：一个m×n的二维数组可以看成是由m行的一维数组组成或由n列的一维数组组成。A0A1..Am-1Ai=(ai0,ai1,…,ai,n-1)i=0,1,2…,m-15.1数组的定义B0B1…Bn-1二维数组是一个数据元素为线性表的线性表j=0,1,…,n-1aij(1≤i≤m-2，1≤j≤n-2)有两个前驱结点ai,j-1和ai-1,j两个后

3、继结点ai,j+1和ai+1,ja00没有前驱结点,称之为开始结点.am-1,n-1没有后继结点,称之为终端结点.第0行的元素a0j(j=1,…,n-1)第0列的元素ai0(i=1,…,m-1)只有一个前驱只有一个后继我们可以把二维数组中的元素aij看成是属于两个线性表:即第i行的线性表Ai和第j列的线性表Bj第m-1行的元素am-1,j(j=1,…,n-2)第n-1列的元素ai,n-1(i=1,…,m-2)同理，三维数组Am×n×l中每个元素属于三个线性表，每个元素最多有三个前驱和三个后继。ai1,i2,i3前驱：ai1-1,i2,i3，ai1,i2-1,i3，a

4、i1,i2,i3-1后继：ai1+1,i2,i3，ai1,i2+1,i3，ai1,i2,i3+1推而广之，一个n维数组可以看成是由若干个n－1维数组组成的线性表，在n维数组Ab1×b2×…×bn中,每个元素ai1,i2,…,in(0≤ij≤bi-1,j=1,2,…,n)属于n个线性表,每个元素最多有n个前驱和n个后继。ai1,i2,…,in前驱：ai1-1,i2,…,in，ai1,i2-1,…,in，…,，ai1,i2,…,in-1后继：ai1+1,i2,…,in，ai1,i2+1,…,in，…，ai1,i2,…,in+1数据对象:D={aij

5、aijElemSe

6、t，0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={

7、0≤i≤b1-1,0≤j≤b2-2}COL={

8、0≤i≤b1-2,0≤j≤b2-1}二维数组的定义:InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。基本操作：DestroyArray(&A)操作结果：销毁数组A。Value(A,&e,index1,...,indexn)//取数组元素初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若

9、各下标不超界，则e赋值为所指定的A的元素值，并返回OK。基本操作：Assign(&A,e,index1,...,indexn)//修改数组元素初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。5.2数组的顺序存储表示和实现问题：计算机的存储结构一般是一维的，而n维数组(n≥2)一般是多维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一序列，然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。若规定好了次序，则数组中任意一个元素的存放地址便有

10、规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。按行序为主序存放am-1,n-1……..am-1,1am-1,0……….a1n-1……..a11a10a0,n-1…….a01a00a00a01……..a0,n-1a10a11……..a1,n-1am-1,0am-1,1…am-1,n-1………………….01n-1m*n-1nam-1,n-1……..a1,n-1a0,n-1……….am-1,1……..a11a01am-1,0…….a10a00a00a01……..a0n-1a