数组和广义表

在各种各样的数据结构的实现里

数组通常是最底层的基本数据类型

以至于我们完全没有意识到它本身其实就是一个数据存储结构

要知道,数组不仅可以存储不可分的数据元素(数字、字符)

还可以存储数据结构(作为底层实现可以存储顺序表链表等)

就是套娃(数组里面继续存储数组)

根据数组中存储数据之间逻辑结构的不同

数组可细分为一维数组、二维数组、…、n 维数组

一维数组,指的是存储不可再分数据元素的数组

二维数组,指的存储一维数组的一维数组

在这里可以把第一行理解为这个二维数组

第一列到最后一列理解为这个二维数组存储的一维数组

行和列对换也是一样

由此我们可以推出

n 维数组,指的是存储 n-1 维数组的一维数组

当然不管有多少维数组中的数据类型必须是一致的


一维数组的存储结构

对于一个一维数组按照元素顺序存储到一块地址连续的内存单元中

假设第一个元素a1的地址用LOC(a1)表示

每个元素占用k个存储单元

则任意元素ai的地址LOC(ai)= LOC(a1)+ (i-1)*k   (2<=i && i<=n)

说明了一维数组的任意元素地址可由计算直接得到

也就是说可以直接存取,所以说一维数组具有随机存储特性


二维数组的存储结构

可以推广到多维数组,多维数组一般采用的是按行优先

二维数组按行优先存放

二维数组按列优先存放


特殊矩阵的压缩存储

都是些线性代数相关

线代里讲了不少特殊的矩阵

当然这些特殊矩阵的主要形式大多是方阵

也就是行数=列数

对称矩阵的压缩存储

沿着主对角线对称的位置上的元素相等

也就是说我们可以只用一维数组来存储对角线一侧的元素

就可以推出整个对称矩阵了

如果存储下三角的元素,元素在数组的位置k可以通过下面的公式计算得出

行标i列标j 下同

如果要存储上三角的元素如下

那么上图的元素存储到一维数组就如下skr数组

上、下三角矩阵的压缩存储

和上面的操作基本差不多

0不用存储然后按照公式来选择上三角和下三角存储

对角矩阵的压缩存储

所有的非零元素集中在以主对角线为中心的带状区域中,即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外,其余元素皆为零的矩阵为对角矩阵。


稀疏矩阵

如果矩阵中分布有大量的元素 0,即非 0 元素非常少,这类矩阵称为稀疏矩阵

所以存储的话只需要存储非0元素就可以了

你需要存储元素值,元素的行标和列标三个值

除了元素以外还需要记得存储矩阵的行列上限

下面介绍了稀疏矩阵的存储方式

稀疏矩阵的三元组表示

如图是一个稀疏矩阵,里面的三个元素按照上面提到的方式存储就是这样

(行标,列标,元素值)这样的构成就称为一个三元组(三部分组成的集合)

typedef struct {
    int i,j;//行标i,列标j
    int data;//元素值
}triple;

还需要在类或者另外一个结构体对三元组来封装

#define number 20
//矩阵的结构表示
typedef struct {
    triple data[number];//存储该矩阵中所有非0元素的三元组
    int n,m,num;//n和m分别记录矩阵的行数和列数,num记录矩阵中所有的非0元素的个数
}TSMatrix;

三元组的基本运算

待补充

稀疏矩阵的十字链表表示

一种链表加数组的存储方式

chead和rhead分别代表了矩阵的行和列

他们两个同时分别对应着元素的表头

里面的元素同样具有三元组的特性

但是多出来两个指针分别指向所在行/列的下一个元素

所以链表中的结点就是这个样子的


广义表

广义表是线性表的推广,是有限个元素的序列

其逻辑结构采用括号表示法

它是一种非连续性的数据结构

简单理解就是一个既可以存储不可分的数据元素

同时又可以存储数据结构的存储结构

存储的单个元素被称为原子

存储的广义表被称为子表

如果广义表啥都没存就叫空表

如果广义表不是空表,那通常第一个元素被叫做表头

剩下的元素构成的新广义表统称为表尾

广义表的长度为最外层包含元素的个数

广义表的深度为所含括弧的重数,原子为0,空表的深度为1

广义表可以共享,一个广义表可以被其它广义表共享

这种共享广义表被称为再入表

广义表也可以是一个递归的表,一个广义表可以是自己的子表

所以被称为递归表,递归表的深度是无穷的,长度是有限的


广义表的存储结构

广义表的定义决定了它很难被顺序存储结构来存储

通常我们是用链表来实现的

因为元素的类型有两种

所以链表的结点也有两种

tag是用来区别结点的,0为原子结点,1为表结点

atom存放值

hp指针是连接自己结点存放的数据结构

tp指针是连接下一个结点的数据结构


广义表的基本运算

待补充


关于head和tail

head就是取出首元素,同时可以消去一层括号

tail取出来的是除首元素以外剩下的元素,但取出来后需要加一层括号(取出表)

例如LS=((a,b,c),(d,e,f))

tail(LS) = ((d,e,f))//去除首元素abc,括号要加一层

head(tail(LS)) = (d,e,f)//去了一层括号

tail(head(tail(LS))) = (e,f)//去除d,加一层括号

head(tail(head(tail(LS)))) = e//head取单个元素

发表评论

您的电子邮箱地址不会被公开。