数值我们都应该很熟悉，也是一种很常见的数据类型，不只是C语言，其他很多高级语言也支持这样的数据结构，系统在为数组分配内存时，会分配一组连续的内存，因此从逻辑结构上来看，数组可以看成是线性表的一种扩充，二维数组可以看成是线性表的线性表。而广义表，也是线性表的一种推广，它广泛的应用在人工智能等领域的表处理语言LISP中，因此要想自己开发能力提升，掌握这一部分的内容还是很重要的，今天这篇我们先介绍数据结构中的数组，当然也会涉及到矩阵的简单知识，如矩阵的转置，与相乘，下面就开始今天的任务。

一、数组

该数据类型很常见，至于多维数组，我们只讨论二维数组，首先我们看一下示意图：

示意图

上图所示，可以看成是二维数组，上面的第一个A可以看成是线性表，元素有希腊字母α表示，其也可以看成是一个线性表，可称为列向量表，βi称为行向量。由上面分析二维数组是线性表的线性表，三维数组及多维数组也是如此，还有由上面看到a后面有两个标号，分别表示行号跟列号，用以定位数据元素，当然三维数组有三个，n为数组有n个下标，来定位数据元素。当然还有一个表示该元素的数值。

我们知道数组是由固定数据元素的集合，一旦定义了一个数组，那么数组中的元素就会固定，如上面A由m*n个数据元素组成，本于此，不能像线性表那样随意插入跟删除，一般是取元素，修改元素。

二、数组的顺序存储。

我们知道内部存储器是一维的，但是需要存储多维数组时就必须按某种方式来存储，一般以向量来作为数组的顺序存储结构，我们一般以行序存储，与列续存储，上图所示，第一个A是以列为主，B是以行为主，一般情况下我们选择以行序为主存储，不同的高级语言他们所选择的有所不同，有的选择以行序为主，有的以列序为主。如上图的B，我们在内存中，先把第一行存到内存中，然后在把第二行存入内存中，依次如此，

三、稀疏矩阵：

稀疏矩阵，其实没有特定的界限，如上图所示，如果非零元素有a个，其余都是0，如果非零元素与总元素的比值0.2到0.3时（或低于该数时），称为稀疏矩阵，稀疏矩阵存储我们一般只存储非零值，省略掉0值，但是非零元素在矩阵中是杂乱的，但是由他们得行列标号，可以唯一确定，因此我们在内存中可以存储三个值，元素的行下表与列下表，当然还要包括元素本身值，存储形式如下：

三元组

因此上面可以成为三元组，下面看示意图：

示意图

上面是三元组定义的结构体，下面是在内存中的形式，该是以行的形式存储的。

要想用三元组方式来表示稀疏矩阵，我们只存储非零元素不至于确定矩阵A的大小，因此还需要确定A的长宽以及非零元素的个数。

四、用三元组方法实现稀疏矩阵的转置：

何为转置运算，也就是将原矩阵的非零元素的行列互换，就可以了，如98在原矩阵中，位置为1行2列，转置后就变成，2行1列。

下面介绍算法1：

并不难，思路，从原矩阵第一列开始，依次转换，这样直接转换后，在内存中就直接是以以行为主方式存储的，因为原矩阵第一列转置后就变成第一行，一列中的第一个元素就是转换后的第一行元素，首先我们定义一个结构体，用以表示三元组，如下：

三元组结构体

结构体

上面两个结构体，一个是三元组结构体，另一个是用以确定矩阵的结构体。

下面就为第一种算法写出矩阵转置函数：

转置运算算法1

一列一列的转置，最后转置后的新矩阵，也是按行方式存储的。

该算法中有两层循环，第一层为次数为t.n，第二次为t.len，因此该算法的时间复杂度为O(t.n*t.len)，当然要是考虑最坏情况，就是需要转置的矩阵都是非零元素（t.n*t.m=t.len），那么其复杂度就变为O(t.m*t.n*t.n)。

算法2：

该算法采用两个数组，其一保存每列非零元素的个数，其二保存每一列第一个非零元素在转置后的数值中的正确位置，其方法是直接定位，每转置一个数据元素，就直接将其放到正确位置上，该算法的思想是，先定位每一列第一个数据元素，将其插入到转置后的正确位置上，如何定位呢，首先我们先确定每一列元素的个数，第一列第一个非零数据元素，因为是行方式存储，转置后必定位于位置1，然后要想确定第二列第一个非零数据在转置后的正确位置，因为第一列非零元素在转置后必定是在转置后矩阵的第一行，因此，把第一行第一个非零元素在转置后的正确位置加上非零元素的个数，就得到第二行第一个非零元素在转置后矩阵在内存中的正确位置了，依次类推。第二、当第一列第二个元素怎么正确插入呢？其实也简单，我们用数组如p[1]，代表第一列第一个非零数据元素在转置后的正确位置，p[1]=1；那么改变p[1]的值，加上1，也就指向了第二个正确位置，因此我们得到下面的转置函数：

转置

上面就是转置矩阵的算法，当然还有矩阵乘法，后面将会介绍。当然后面也会继续介绍广义表。今天这篇可能并没有说的很清楚，毕竟在忙中写出这一篇，希望能对你们有所帮助。