3 数组和广义表

Wu Jun 2019-12-25 15:59:04
01 数据结构与算法 > 数据结构 > 01 数据结构

1 数组的概念、多维数组的实现

1)数组的概念

2)多维数组的实现

行优先顺序

存储时先按行从小到大的顺序存储,在每一行中按列号从小到大存储。

列优先顺序

存储时先按列从小到大的顺序存储,在每一列中按行号从小到大存储。

2 矩阵的压缩存储

矩阵的压缩存储就是存储数组时,尽量减少存储空间,但数组中每个元素必须存储。

在矩阵中,如果有规律可寻,只要存储其中一部分,而另外一部分的存储地址可以通过相应的算法将它计算出来,从而占有较少的存储空间达到存储整个矩阵的目的。

矩阵的压缩存储仅能针对特殊矩阵使用,对于没有规律可循的二维数组则不能使用。

1)对称矩阵

只需对对称矩阵中n(n+1)/2个元素进行储存表示

2)三角矩阵

以主对角线划分,三角矩阵有上三角和下三角两种。上三角矩阵它的下三角中的元素均为常数。下三角矩阵正好相反,它的主对角线上方均为常数。

3)稀疏矩阵

if 一个 m * n 的矩阵含有 t 个非零元素,且 t 远远小于 m * n,则称这个矩阵为稀疏矩阵

除了记录非零元素的值之外,还必须同时几下它所在的行和列的位置。稀疏矩阵的存储方法一般有三种:三元组法、行逻辑连接顺序表和十字链表法。

三元组法

用三项内容表示稀疏矩阵中的每个非零元素,形式为:(i,j,value)。
其中,i 表示行序号,j 表示列序号,value 表示非零元素的值

3 广义表的基本概念

1)定义

数据元素

广义表的数据元素有两种类型:一个是不可再分的元素(原子元素);一个是可以再分的元素(子表)。

记法

广义表一般记作:LS=(a1,a2,……,an)

常见的广义表为:A=()、B=(())、C=(a,b)、D=(A,B,C)、E=(a,E)

特点

广义表有三个重要的特点:

2)存储方式

广义表的存储方法有很多种,一般采用链表存储。

flag表示标志位。当flag为0时,表示该结点为原子元素,info表示原子元素的值;当flag为1时表示该结点为子表,info表示指针,指向该子表的第一个结点。 link表示指针,指向广义表的下一个元素。