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

数据结构(C#)主编: ,特点是结构中的数据元素可以是具有某种结构的数据,甚至可以是数组,但属于同一数据类型。数组在许多高级语言里面都被作为固定类型来使用。数组的逻辑结构数组是n(n≥1)个相同数据类型的数据元素的有限序列。一维数组可以看作是一个线性表,二维数组可以看作是“数据元素是一维数组”的一维数组,三维数组可以看作是“数据元素是二维数组”的一维数组,依次类推。数组是一个具有固定格式和数量的数据有序集,每一个数据元素通过下标来标识和访问。一个数组一经定义,每一维的大小及上下界都不能改变。所以,在数组上不能进行插入、删除数据元素等操作。数组上的操作一般有:取值操作:给定一组下标,读其对应的数据元素。赋值操作:给定一组下标,存储或修改与其对应的数据元素。清空操作:将数组中的所有数据元素清除。复制操作:将一个数组的数据元素赋给另外一个数组。排序操作:对数组中的数据元素进行排序。反转操作:反转数组中数据元素的顺序。。例如,设A是一个有m行n列的二维数组,则A可以表示为:数组的内存映象采用顺序存储结构来存储数组中的数据元素。计算机的内存是一个一维数组,内存地址就是数组的下标。所以,可根据一维数组元素的下标得到它的存储地址及访问一维数组中的元素。对于多维数组,需要把多维的下标表达式转换成一维的下标表达式。两种存储方式:一种是以行序为主序(先行后列)的顺序存放,另一种是以列序为主序(先列后行)的顺序存放。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的前面还有j-1个元素。当以列序为主序进行存储:Loc(aij)=Loc(a11)+((j-1)*m+i-1)*w数组元素aij的前面有j-1列,每一列有m个数据元素,在第j列中aij的前面还有i-1个元素。数组是一种随机存储结构。(RegularMatrix)的存储稀疏矩阵(SparseMatrix)的存储具有一定规律的矩阵,如对称矩阵,三角矩阵等很多元素是0(或者同一个值),pressedstorage):使用少于二维数组的空间存储矩阵