《返回主目录》ppt课件

《《返回主目录》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、返回主目录本章说明5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存贮结构本章小结学习目标理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”、“以列为主”的存储表示中的地址计算方法。掌握特殊矩阵的存储压缩表示方法。理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。本章说明重点和难点重点是学习数组类型的定义及其存储表示。知识点数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表

2、示方法、随机稀疏矩阵的压缩存储表示方法。本章说明5.1数组的定义数组是线性表的推广数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。列向量行向量数组的抽象数据类型定义ADTArray{数据对象：ji=0,...,bi-1,i=1,2,..,nD＝{aj1,j2,...jn

3、n(>0)为数组的维数，bi为数组第i维的长度，ji为数组元素的第i维下标，aj1,j2,...jn∈ElemSet}数据关系：R＝{R1,R2,...,Rn}Ri＝{

4、,…,jn>

5、0≤jk≤bk-1,1≤k≤n且ki,0≤ji≤bi-2,aj1,…，ji,…,jn,aj1,…，ji+1,…,jn∈D,i=2,...,n}5.1数组的定义基本操作:InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A。DestroyArray(&A)初始条件：数组A已经存在。操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若

6、各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给A中指定下标的元素。}ADTArray5.1数组的定义5.2数组的顺序表示和实现用一组连续的存储单元来表示数组。有两种映象方法：“以行(序)为主(序)”：对二维数组进行“按行切分”，即将数组中的数据元素“按行依次排放”在存储器中“以列(序)为主(序)”对二维数组进行“按列切分”，即将数组中的数据元素"

7、按列依次排放"在存储器中。按行序为主序存放am-1,n-1……..am-1,1am-1,0………a1,n-1……..a11a10a0,n-1…….a01a0001n-1m*n-1n5.2数组的顺序表示和实现按列序为主序存放am-1,n-1……..a1,n-1a0,n-1……….am-1,1……..a11a01am-1,1…….a10a0001m-1m*n-1m5.2数组的顺序表示和实现按行序为主序存放am-1,n-1……..am-1,1am-1,0………a1,n-1……..a11a10a0,n-1…….a01

8、a0001n-1m*n-1n每个数据元素占L个存储单元;LOC(0,0)表示数据元素a00的存储地址是数组的起始地址（基地址）;LOC(i,j)表示下标为(i,j)的数据元素aij的存储地址LOC(i,j)=LOC(0,0)+(i*n+j)*L5.2数组的顺序表示和实现按列序为主序存放am-1,n-1……..a1,n-1a0,n-1……….am-1,1……..a11a01am-1,1…….a10a0001m-1m*n-1m每个数据元素占L个存储单元;LOC(0,0)表示数据元素a00的存储地址，是数组的起

9、始地址（基地址）LOC(i,j)表示下标为(i,j)的数据元素aij的存储地址LOC(i,j)=LOC(0,0)+(j*m+i)*L5.2数组的顺序表示和实现5.3矩阵的压缩存储压缩存储为多个值相同的矩阵元只分配一个存储空间；对零元不分配空间。5.3.1特殊矩阵特殊矩阵值相同的元素或者零元素在矩阵中的分布有一定规律对称矩阵n阶矩阵；aij=aji1i,jn5.3矩阵的压缩存储特殊矩阵值相同的元素或者零元素在矩阵中的分布有一定规律三角矩阵n阶矩阵；下（上）三角矩阵：矩阵的上（下）三角（不包括对角线）中的元均

10、为常数c或零。5.3矩阵的压缩存储特殊矩阵值相同的元素或者零元素在矩阵中的分布有一定规律对角矩阵n阶矩阵所有的非零元都集中在以主对角线为中心的带状区域中5.3矩阵的压缩存储压缩存储——对称矩阵按行序为主序：仅存储下三角a11a12….……..a1na21a22……..…….a2nan1an2……..ann………………….ann…an1a32…a31a22a21a114321k=05.3矩阵的压缩存储