12-数据结构-数组、矩阵、广义表

数组、矩阵、广义表

一、数组

二.矩阵

三、广义表

一、数组

这一章节理解基本概念即可。数组要看清其实下标是多少，并且二维数组，存取数据，要先看清楚是按照行存还是按列存，按行则是正常一行一行的去读写，按列则是，从左至右，一列一列的弄。

此外，数组中具体坐标的空间大小要会计算，每块存储单元，算到该数组坐标的前一位的数组大小：如A[5][3]，起始位A[0][0]，则计算A[5][3]的时候，先计算0-4行的空间大小，再计算第5行的大小，第五行的时候，是计算0-2列即0，1，2，三列，所以第五行空间个数为3，将其加上即可。

二、矩阵

则是掌握基本矩阵的代码，矩阵相加，相乘，转置。

其次要会压缩矩阵，压缩矩阵的目的是减少存储单元
方法是，给矩阵中的有效数据，存进一维数组中去。
这个时候就需要压缩矩阵的计算了，一般计算特殊矩阵：
对称阵，上三角下三角，画一个简单的矩阵，然后根据按行存或者按列存，进行存储，然后计算，一般是等差数列，然后加上最后一行或最后一列的有效数据，这个就看具体是多少了。一般遇到选择题，让求规律的，在看清矩阵和一维数组起始下标的前提下，找具体坐标试一下，如A[0][0]---0,在一维数组里面是第0个，给（行）i=0,（列）j=0，代入试一下即可。如果遇到算具体数值的，则是画一个大概矩阵，然后找规律。按行排列，则先计算0到i-1行的个数（一般为等差数列，第0行有1个，第1行有2个第i-1行有i个，则共0到i-1，总个数为i个，a1=1,an=i所以等差数列为( $\frac{i*(i+1)}{2}$ ）,这是第0到i-1行的总个数，再计算第i行的个数，按列算，j+1个，所以总个数为 $\frac{i*(i+1)}{2}$ +j+1，但存进数组的话，若数组下标为1，则 $\frac{i*(i+1)}{2}$ +j+1+1，要看具体矩阵和数组的起始下标。
对三角矩阵，则是待定系数法，为了省事直接k=ai+bj+c，其中k为存进一维数组的下标，i为矩阵的行，j为矩阵的列，c为常数，然后再去带具体坐标去解方程组即可。但上面设的公式，还要看具体情况去设置，如果有的个数为等差数列，则肯定有行的平方或者列的平方。
之后是稀疏矩阵：矩阵中大部分都是0的矩阵。

稀疏矩阵的压缩，就是给矩阵中非零元素，存起来。

稀疏矩阵的顺序存储（设成结构体，里面包含各种变量）

1.三元组表示法

按行优先存储，所以稀疏矩阵三元组，不好逆置，逆置的话，需要按列重新搞一下。

三元组，就是数组结构体里定义三个变量，分别是行，列，以及坐标值。其中数组结构体，第一个里面存的是，矩阵信息，即共几行几列，有几个非零元素。因此如果题中有5个非零元素，则三元组数组，要5+1个数组空间。

稀疏矩阵转化三元组步骤：

1.先计算矩阵中非零元素个数。即二维数组遍历，非零的，count（计数器）+1。最后返回count。

2.之后定义一个三元组数组，然后开始写转换函数，返回类型为三元组指针类型，即返回三元组。先存储矩阵信息，再三元组数组第一个位置，随后定义个记录器，index=1，表示实际非零元素个数的下标，随后开始遍历，当矩阵元素不等于零的时候，存进index坐标下，随后行和列也记录，之后，index+1，后移动，直到遍历结束。

2.伪地址存储

数据结构体，里面变量为伪地址变量以及具体值。伪地址计算方法，可直接查，按照行或者列，从1开始，哪个位置非零，就记录。

稀疏矩阵的链式存储

1.邻接表法。

用一维数组（矩阵行）去索引，索引内容，坐标值，列下标，以及同行下一个非零元。

即同一行，串成一个链，只串同行非零元素。

2.十字链表