北京网络营销推广公司,某个网站seo分析实例,wordpress友链审核插件,网站建设公司推来客网站系统怎么样4.2数组
数组#xff1a;按一定格式排列起来的#xff0c;具有相同类型的数据元素的集合。
**一维数组#xff1a;**若线性表中的数据元素为非结果的简单元素#xff0c;则称为一维数组。
**一维数组的逻辑结构#xff1a;**线性结构#xff0c;定长的线性表。
**声明…4.2数组
数组按一定格式排列起来的具有相同类型的数据元素的集合。
**一维数组**若线性表中的数据元素为非结果的简单元素则称为一维数组。
**一维数组的逻辑结构**线性结构定长的线性表。
**声明格式**数据类型 变量名称 [长度] 例如int num[5] {0,1,2,3,4} **二维数组**若一维数组中的数据元素又是一维数组结构则称为二维数组。
二维数组的逻辑结构
非线性结构每一个数据元素既在一个行表中又在一个列表中。线性结构定长的线性表该线性表的每个数据元素也是一个定长的线性表。
**声明格式**数据类型 变量名称 [行数] [列数] 例如int num [5] [8]; 在C语言中一个二维数组类型也可以定义为一维数组类型其分量类型为一维数组类型即 typedef int array2[m][n];
等价于typedef int array1[n];typedef array1 array2[m];**三维数组**若二维数组中的元素又是一个一维数组则称作三维数组。
**n维数组**若 n - 1 维数组中的元素又是一个一维数组结构则称作 n 维数组。
**结论**线性表结构是数组结构的一个特例而数组结构又是线性表结构的扩展。
**数组特点**结构固定——定义后维数和维界不再改变。
**数组基本操作**除了结构的初始化和销毁之外只有取元素和修改元素值的操作。
4.2.1数组的顺序存储结构
数组特点结构固定——维数和维界不变。
一般都是采用顺序存储结构来表示数组。 **注意**数组可以是多维的但存储数据元素的内存单元地址是一维的因此在存储数组结构之前需要解决将多维关系映射到一维关系的问题。 一维数组 例有数组定义int a[5] 每个元素占用4字节假设a[0]存储在2000单元a[3]地址是多少 LOC(0) a 2000 L4 LOC(3) 3*42000 LOC(i) i*L 首地址 存储单元是一维结构而数组是个多维结构则用一组连续存储单元存放数组的数据元素就有个次序约定问题。
二维数组可有两种存储方式 以行序为主序 设数组开始存储位置LOC(0,0)存储每个元素需要L个存储单元 数组元素a[i] [j]的存储位置是LOC(i,j)LOC(0,0) (n * i j) * L 以列序为主序。
**三维数组**按页/行/列存放页优先的顺序存储。
4.2.2特殊矩阵的压缩存储
**矩阵**一个由 m*n 个元素排成的 m 行 n 列的表。
**矩阵的常规存储**将矩阵描述为一个二维数组。
矩阵的常规存储的特点
可以对其元素进行随机存取。矩阵运算非常简单存储的密度为1.
**不适宜常规存储的矩阵**值相同的元素很多且呈某种规律分布零元素多。
**矩阵的压缩存储**为多个相同的非零元素只分配一个存储空间对零元素不分配空间。 1、什么是压缩存储
若多个数据元素的值都相同则只分配一个元素值的存储空间且零元素不占存储空间。
2、什么样的矩阵能够压缩
一些特殊矩阵如对称矩阵对角矩阵三角矩阵稀疏矩阵等。
3、什么叫稀疏矩阵
矩阵中非零元素的个数较少一般小于5%
1.对称矩阵 **【特点】**在 n*n 的矩阵 a 中满足如下性质aijaji1≤i , j≤n
**【存储方法】**只存储下或者上三角包括主对角线的数据元素。共占用 n(n1)/2个元素空间。
**【存储结构】**对称矩阵上下三角中的元素数均为n(n1)/2
可以以行序为主序将元素存放在一个一维数组 sa[ n(n1)/2 ]中。
2.三角矩阵
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6FofxLkg-1690537372616)(https://tse1-mm.cn.bing.net/th?idOIF-C.uHr%2bn0jNJ2j8NRD2iircPApidImgDetrs1)]
**【特点】**对角线以下或者以上的数据元素不包括对角线全部为常数c。
**【存储方法】**重复元素c共享一个元素存储空间共占用n(n1)/21个元素空间[1…n(n1)/21]
上三角矩阵 下三角矩阵 3.对角矩阵带状矩阵 **【特点】**在n*n的方阵中所有非零元素都集中在以主对角线为中心的带状区域中区域外的值全为0则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。 4.稀疏矩阵
**稀疏矩阵**设在 m*n 的矩阵中有 t 个非零元素。
令 δ t / (m*n)
当 δ ≤ 0.05 时称为稀疏矩阵。 **压缩存储原则**存各非零元素的值行列位置和矩阵的行列数。
4.1三元组顺序表 注意为更可靠描述通常再加一个“总体”信息即总行数、总列数、非零元素总个数。
三元组顺序表又称有序的双下标法。
三元组顺序表的优点非零元素在表中按行序有序存储因此便于进行依行顺序处理的矩阵运算。
三元组顺序表的缺点不能随机存取。若按行号存取某一行中的非零元素则需从头开始进行查找。
4.2十字链表 **优点**它能够灵活地插入因运算而产生的新的非零元素删除因运算而产生的新的零元素实现矩阵的各种运算。 在十字链表中矩阵的每一个非零元素用一个结点表示该结点除了(rowcolvalue)以外还要有两个域 right用于链接同一行中的下一个非零元素。down用以链接同一列中的下一个非零元素。 十字链表中结点的结构示意图
4.3广义表
4.3.1广义表定义
广义表又称列表Lists是n≥0个元素 a0a1…an-1的有限序列其中每一个ai或者是原子或者是一个广义表。 例如中国举办的国际足球邀请赛参赛队伍名单可表示如下 阿根廷巴西德国法国西班牙意大利英国国家队山东鲁能广州恒大 在这个表中叙利亚队应排在法国队的后面但未能参加成为空表。国家队山东鲁队广州恒大均作为东道主的参赛队参加构成一个小的线性表成为原线性表的一个数据元素。这种拓宽了的线性表就是广义表。 广义表通常记作LS( a1a2…an 习惯上一般用大写字母表示广义表小写字母表示原子。 **表头**若LS非空n≥1则其第一个元素a1就是表头。记作headLSa1. 注意表头可以是原子也可以是子表。 表尾除表头之外的其他元素组成的表。记作tailLSa2…an 注意表尾不是最后一个元素而是一个子表。 例如1 A() 空表长度为0 2B(( )) 长度为1表头、表尾均为。 3C(a,(b,c)) 长度为2由原子a和子表bc构成。表头为a表尾为((bc)) 4D(x,y,z) 长度为3每一项都是原子。表头为x表尾为yz 5E(C,D) 长度为2每一项都是子表。表头为C表尾为D 6F(a,F) 长度为2第一项为原子第二项为它本身。表头为a表尾为F。F(a(a(a…)))
4.3.2广义表的性质 广义表的数据元素有相对应次序一个直接前驱和一个直接后继。 广义表的长度定义为最外层所包括元素的个数如C(a,(b,c))是长度为2的广义表。 广义表的深度定义为该广义表展开后所含括号的重数。 注意“原子”的深度为0“空表”的深度为1。 广义表可以为其他广义表共享如广义表B就共享表A。在B中不必列出A的值而是通过名称来引用。B(A) 广义表可以是一个递归的表。 注意递归表的深度是无穷值长度是有限值。 广义表是一个多层次结构广义表的元素可以是单元数也可以是子表而子表的元素还可以是子表。
4.3.3广义表和线性表的区别
广义表可以看成是线性表的推广线性表是广义表的特例。
广义表的结构相当灵活在某种前提下它可以兼容线性表、数组、数和有向图等各种常见的数据结构。
当二维数组的每行或每列作为子表处理时二维数组即为一个广义表。
另外数和有向图也可以用广义表来表示。
由于广义表不仅集中了线性表数组数和有向图等常见数据结构的特点而且可有效地利用存储空间因此在计算机的许多应用领域都有成功使用广义表的实例。
4.3.4广义表的基本运算
求表头GetHead(L)非空广义表的第一个元素可以是一个单一元素也可以是一个子表。求表尾GetTail(L)非空广义表除去表头元素以外其他元素所构成的表表尾一定是一个表。
