C语言程序设计 算法.ppt

《C语言程序设计 算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组和广义表5.1数组的类型定义5.3矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的存储结构学习提要：1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4.掌握广义表的结构特点及其存储表示方法。ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn

2、ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{

3、

4、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:5.1数组的类型定义基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(

5、&A)操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返OK。二维数组的定义:数据对象:D={aij

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

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

8、

9、0≤i≤b1-1,0≤j≤b2-2}二维数组的定义:5.2数组的顺序表示和实现类型特点:（1）只有引用型操作，没有加工型操作；（2）数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:（1）以行序为主序（2）以列序为主序a00a01……a0n-1a10a11……a1n-1am-10am-11…am-1n-1………………….按行序为主序存放am-1n-1……..am-11am-10……….a1n-1……..a11a10a0n-1…….a01a0001n-1m*n-1nLOC(i,j)=LOC(0,0)+(n×i＋j)×L按列序为主序存放

10、01m-1m*n-1mam-1n-1……..a1n-1a0n-1……….am-11……..a11a01am-10…….a10a00a00a01……..a0n-1a10a11……..a1n-1am-10am-11…am-1n-1………………….LOC(i,j)=LOC(0,0)+(m×j＋i)×L称为基地址或基址以“行序为主序”的存储映象:二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(n×i＋j)×L以“列序为主序”的存储映象:二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(m×j＋i)×L推广到一般情况，可得到n维数组数

11、据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1

12、。5.3.1特殊矩阵特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。对称矩阵元素满足条件aij=aji1=