数据结构（c语言描述） 教学课件 作者 库波 第5章 数组和广义表.ppt

《数据结构（c语言描述） 教学课件 作者 库波 第5章 数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构(C#)主编：库波第5章数组和广义表5.1数组5.2多维数组及其存储结构5.3特殊矩阵及其压缩存储5.4稀疏矩阵5.5广义表5.1数组数组可以看作是线性表的推广，特点是结构中的数据元素可以是具有某种结构的数据，甚至可以是数组，但属于同一数据类型。数组在许多高级语言里面都被作为固定类型来使用。数组的逻辑结构数组是n(n≥1)个相同数据类型的数据元素的有限序列。一维数组可以看作是一个线性表，二维数组可以看作是“数据元素是一维数组”的一维数组，三维数组可以看作是“数据元素是二维数组”的一维数组，依次类推。数组是一个具有固定格式和数量的数据有序集，每一个数据元素通过下标来标识和访问

2、。一个数组一经定义，每一维的大小及上下界都不能改变。所以，在数组上不能进行插入、删除数据元素等操作。数组上的操作一般有：取值操作：给定一组下标，读其对应的数据元素。赋值操作：给定一组下标，存储或修改与其对应的数据元素。清空操作：将数组中的所有数据元素清除。复制操作：将一个数组的数据元素赋给另外一个数组。排序操作：对数组中的数据元素进行排序。反转操作：反转数组中数据元素的顺序。5.2多维数组及其存储结构二维数组二维数组可以看成是向量的推广。例如，设A是一个有m行n列的二维数组，则A可以表示为：数组的内存映象采用顺序存储结构来存储数组中的数据元素。计算机的内存是一个一维数组，内存地址就

3、是数组的下标。所以，可根据一维数组元素的下标得到它的存储地址及访问一维数组中的元素。对于多维数组，需要把多维的下标表达式转换成一维的下标表达式。两种存储方式：一种是以行序为主序（先行后列）的顺序存放，另一种是以列序为主序（先列后行）的顺序存放。a11a12…a1na21a22…a2n…am1am2…amn(a)以行为主序a11a21…Am1a12a22…am2…a1na2n…amn(b)以列为主序按元素的下标求地址当以行序为主序进行存储：Loc(aij)=Loc(a11)+((i-1)*n+j-1)*w数组元素aij的前面有i-1行，每一行有n个数据元素，在第i行中aij的前面还有

4、j-1个元素。当以列序为主序进行存储：Loc(aij)=Loc(a11)+((j-1)*m+i-1)*w数组元素aij的前面有j-1列，每一列有m个数据元素，在第j列中aij的前面还有i-1个元素。数组是一种随机存储结构。5.3特殊矩阵及其压缩存储特殊矩阵(RegularMatrix)的存储稀疏矩阵(SparseMatrix)的存储具有一定规律的矩阵，如对称矩阵，三角矩阵等很多元素是0（或者同一个值）,只有少量元素具有特定值压缩存储(compressedstorage)：使用少于二维数组的空间存储矩阵对称矩阵的存储n阶对称矩阵：aij=aji0i,jn-1不需存储所有n2个元素

5、，只需存储n(n+1)/2个元素方法是将下三角元素线性化后用一维数组存储a00a01….a0n-1a10a11….a1n-1an-1,0an-1,1….an-1,n-1…aij….….….….aij(i

6、元素，i(i+1)/2+j+1存放aij(ij)5.4稀疏矩阵6行,7列,非零元素8个稀疏因子=稀疏因子0.2稀疏矩阵:非零元素数<

7、aijElemTypei=1,2,…,m;j=1,2,…,n}数据关系：R={Row,Col}Row={(ai,j,ai,j+1)1im,1jn-1}Col={(ai,j,ai+1,j)1im-1,1jn}基本操作：…}ADTSparseMatrix基本操作包括：创建、输出、转置

8、和加、减、乘等运算。稀疏矩阵的存储稀疏矩阵可以用所有的非零元素和它们的下标来唯一表示；每个非零元素可用一个三元组（行下标，列下标，值）表示；任务：如何存储这些三元组，并实现稀疏矩阵上的运算；顺序结构—三元组顺序表：按照行优先或者列优先的方法把非零元素视为一个线性表；链式存储—十字链：给每个非零元素附上它所在行和列的下一个非零元素的地址；稀疏矩阵的顺序存储使用顺序结构存储行优先的三元组表称为三元组顺序表其结构定义如下：structtupletype{publici