数组、矩阵、广义表思维导图
数组、矩阵、广义表介绍
树图思维导图提供 数组、矩阵、广义表 在线思维导图免费制作，点击“编辑”按钮，可对 数组、矩阵、广义表 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：1495534bfea066edd50ffd2066f86e23
思维导图大纲
数组、矩阵、广义表思维导图模板大纲
数组的存储结构
一维数组的存储结构
a[i]地址 = LOC + i * sizeof(elemtype)
二维数组b[M][N]的存储结构
行优先存储
b[i][j]的地址 = LOC + （i * N + j) * sizeof(elemtype)
列优先存储
上式改为j * M + i
多维数组，不从0开始
先数一下从哪到哪，确定大小为A[M][N][P]
要求给定元素地址
先判断优先，以高位优先（行优先）为例，要求A[i][j][k]
无论行列，只看前面有几个，如i只看在m1,m2……中它前面有几个，设t个
再×下一维度的总长度（即t*N*P），每一维度都这么算
最后×每个元素大小，再+首地址
三角矩阵压缩存储
类似对称矩阵存储，只是最后多了一个位置存储相同的常量，故数组大小为n*(n+1)/2 + 1
三对角矩阵压缩存储
三对角矩阵压缩存储，这个建议记，如果都是从0开始就是2i+j
三对角矩阵反推i和k的关系
稀疏矩阵压缩存储
非零元很少且分布无规律
链式存储法：十字链表法
顺序存储：三元组法
三元组法转置矩阵
矩阵的行数列数值交换
每个三元组的i和j交换
重排三元组的次序，按照行序（置换前的列序）进行排序
三者缺一不可！尤其最后一个
无论哪种方法，一定失去了随机存取功能！
对称矩阵压缩存储
策略：只存主对角线 + 上（下）三角区
对称矩阵存储坐标转换
广义表（列表）
概念
L(e1,e2,e3,……,en)，其中，L为表名，ei为表元素，n为表长，n=0为空表：()。左右括号不计入长度
表头：第1个元素，可以是原子可以是子表
表尾：除了第一个元素外的其余元素组成的表！一定是广义表。求法：把表头删了，算上外面括号，就是表尾。
原子：广义表中的单个元素
子表：广义表中的广义表元素
难以用顺序存储结构表示，通常用链式存储结构
结论
列表的元素可以是子表，而子表的元素还可以是子表
列表可以为其他列表所共享
列表可以是递归的表
空表一定没有表头表尾
广义表唯一对应二叉树的条件：空表 or 只有一个元素 or 各个子表长度为0 or 2
二维及以上的数组就是一种特殊的广义表
广义表的表头为空，并不代表该广义表为空表；广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为1的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表。
广义表深度
空表：1
原子：0
最大嵌套层数，表现为括弧的重数
矩阵压缩存储问题（三步走）
求前 i- 1行有多少个
一般做法为前i-1行是[0]~[i-1]这么多行，看看每行多少个
求是本行第几个
一般做法是看本行前面有几个，注意不一定是从[0]开始，本行前有i个---->本行第i+1个
看是b[0]还是b[1]
b[0]则上述相加-1，b[1]则上述相加
注意点
一定一定要注意所求是在哪个范围！
相关思维导图模板
树图思维导图提供 Python基本语法与数据类型思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 Python基本语法与数据类型思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：350489608220fa38c9d889c5e984fea7
树图思维导图提供 万象汇自我时间安排表 在线思维导图免费制作，点击“编辑”按钮，可对 万象汇自我时间安排表 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：7dfe807d3adbe59f88d8c425e2511995
沪公网安备 31011502019485号
上海工商