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

数组、矩阵、广义表

---

目录

数组、矩阵、广义表

  一、数组

        二.矩阵

三、广义表

---

---

  一、数组

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

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

二、矩阵

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

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

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

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

1.三元组表示法

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

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

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

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

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

2.伪地址存储

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

稀疏矩阵的链式存储

1.邻接表法。

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

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

2.十字链表

三、广义表

广义表时线性表的推广，不是线性表，而是层次结构，树。

每个广义表用（）括住，广义表里面可以套广义表，每个广义表是一个小整体。广义表里面，可以由原子元素（单个值），可以是广义表。

广义表的深度，长度和表头表尾

深度：最多的层数，即广义表包含几个，查括号。化成树的话，为最底下的那个广义表。

长度：第一层元素个数，化成树的话，是第二层结点.

表头：广义表非空时，第一个元素。即表头为取第一个元素的值。

表尾：实际上是除了表头以外，其他构成的新的广义表。是个广义表。

例如：（（a）,(b,f),(v)）

表头为：（a）//只包含a的广义表，  不是a，a是原子元素。

表尾：（（b，f）(v)），新构成的广义表.

再对表尾求

表头：（b,f），广义表。   不是（（b，f）），表头为取第一个元素

表尾：( (v) ),是个广义表，由广义表（v）构成，即删除表头，剩下组成的新的广义表，

---

广义表的链式存储

有两个结点，第一个为广义表结点，包含标记域，表头，表尾指针，第二个是原子元素结点，包含标记域，和具体值。其中标记域为1，表示广义表，标记域为0表示原子元素。

一般，先画出第一个广义表结点，然后头节点指向出来，尾指针指向尾结点，以此类推。

扩展的线性表存储结构

跟链式存储差不多，只不过后面的指针变成了，左孩子又兄弟了，头指针指向最左边的孩子，之后孩子的尾指针，指向同级的右兄弟。（这种一般先画成树的形式，好判断）