数据结构（C语言描述）第5章数组

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第5章 数组,数组的根本概念和存储结构,稀疏矩阵的定义、表示方法、存储结构及根本操作的实现算法,特殊矩阵的存储,广义表的定义、链式存储结构，以及相应操作的实现算法。,第5章 数组,5.1,数组,5.2,数学中的应用,5.3,广义表,本章总结,5.1,数组,5.1.1,一维数组,5.1.2,多维数组,5.1.1,一维数组,一维数组在数组结构中可以看成是一个线性表或一个向量，通常分配一块连续的存储单元。,在C语言中，一维数组a n 的存储单元是从a 0 至an1的一块连续的存储空间，设a 0 的存储地址LOCa 0，数据元素所占的存储单元为k个字节，那么任一元素a i 的首字节地址LOCa i：,LOCa i=LOCa 0+i*k (0in),5.1.2,多维数组,多维数组的定义：,1 行向量形式,Amn=A，那么A=a0，a1，ai，am1一维数组,其中，aj=aj,0，aj,1，aj,n-10jm是一个行向量形式的线性表。就是以行序为主序的存储方式。,2 列向量形式,Amn=A，那么A=a0，a1，ai，an1，其中，ap=a0,p，a1,p，am-1,p(0pn)是一个列向量形式的线性表，如式子5-3所示。是以列序为主序的存储结构。,数组的存储结构,对于二维数组来说，设数组的第一个元素a0,0的地址LOCa0,0，每个元素所占的存储单元为k，那么二维数组中任一元素ai，j的存储地址：,LOCai,j=LOCa0,0+i*nj*k n为列数,n,维数组,ad1d2 dn,的数据元素存储位置的,计算公式,：,5.2,数学中的应用,5.2.1,稀疏矩阵,5.2.2,特殊矩阵,5.2.1,稀疏矩阵,稀疏矩阵的概念,稀疏矩阵的三元组线性表表示,稀疏矩阵的顺序存储方式,稀疏矩阵的链式存储方式,稀疏矩阵各种操作的实现,稀疏矩阵的概念：,在一个阶数较大的矩阵中非零元素个数s相对于矩阵元素的总个数t非常小，即 s sublist)+1 其它情况,实现算法：略,时间复杂度为On，其中n为广义表中所有结点的个数。该算法的空间复杂度为Om，m为广义表的深度。,建立广义表,分析：建立广义表过程可以通过递归实现。将广义表分解成表头和表尾，而表头和表尾假设仍是广义表，那么继续分解为表头和表尾。创立过程就是建立表头和建立表尾。,区分表头和表尾中的元素是单元素还是表元素的方法：,1如果 i为“，表示这是一个空的表元素，字符串长度为2；,2如果 i长度为1，说明它是一个单元素；,3如果长度1，这是一个表元素。,前两种情况就可作为递归过程的结束条件。,实现算法：略,时间复杂度和空间复杂度：0n，n广义表中字符个数,输出广义表,分析：设GL为表头指针，那么输出时，需要对子表进行递归调用。当GL结点为表结点时，应首先输出作为一个表的起始符号“。然后再输出以sublist为表头指针的表；当GL结点为原子结点时，那么应输出该元素的值。当以sublist为表头指针的表输出结束后，应在其最后输出一个作为表终止符的“。当GL结点输出结束后，假设存在后继结点，那么应首先输出一个逗号作为分隔符，然后再递归输出由next指针所指向的后继表。,实现算法：略,时间复杂度和空间复杂度：0n，n广义表中结点个数。,本章总结：,一维数组在内存中开辟一块连续的存储单元存储数据，适合于随机查找。多维数组可以看成是一维数组的推广，也是一个线性表，表中的每个数据元素本身也是一个线性表。,稀疏矩阵是指非零元素个数相对于矩阵元素的总个数十分小的矩阵。稀疏矩阵的存储方法有三种：第一种是三元组表示法，第二种是行逻辑链式存储，第三种是十字链式存储。稀疏矩阵的根本操作有五种，都采用了顺序存储方式。,特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。为了节省存储空间可以对特殊矩阵进行压缩存储。,广义表的元素分为原子和子表，是一种递归结构。表中所含元素的个数称为长度。表中括号嵌套的最大次数称为深度。常用的根本操作有求广义表的长度、深度、创立和输出广义表等，操作的共同点是都通过递归实现。,