数组、矩阵、广义表思维导图

生杀予夺

2023-11-02

浏览量: 11

随机存取功能

数组

递归

数组、矩阵、广义表介绍

树图思维导图提供《数组、矩阵、广义表》在线思维导图免费制作，点击“编辑”按钮，可对《数组、矩阵、广义表》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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]则上述相加

注意点

一定一定要注意所求是在哪个范围！

第八章 90年代小说思维导图

U466224422

0.98

树图思维导图提供《第八章 90年代小说》在线思维导图免费制作，点击“编辑”按钮，可对《第八章 90年代小说》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：8ffc25c9b9bbbfb800a54224dbc7f0dd

现代主义设计思维导图

U666074772

0.89

树图思维导图提供《现代主义设计思维导图》在线思维导图免费制作，点击“编辑”按钮，可对《现代主义设计思维导图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0bc83385bf2c89d90fef1becf2437650

思维导图模板

基础教育

数学

正文

相似思维导图模版

人教版九年级数学下册第二十九章：投影与视图思维导图

2022-11-08 15:46:52

中考数学复习重点：易错点解析（四）思维导图

2023-04-11 15:56:28

初中数学全等三角形思维导图

2022-08-05 17:55:05

初三数学复习要点：等式与变量和一元一次方程2023思维导图

2023-04-11 15:36:20

思维导图模版推荐

首页

我的文件

我的团队

个人中心