第五章数组与广义表

2020-08-09 专业基础►数据结构数据结构 0 评论字数统计: 3.5k(字) 阅读时长: 13(分)

数组与广义表

数组

数组的定义

数组的逻辑结构
- 一维数组：
- 多维数组：
数组的抽象数据类型：
数组的基本操作：
- 数组运算的关键在于找到对应元素的下标。

数组的存储结构

顺序存储结构：数组中的所有元素存储在一块地址连续的内存单元中,使用的是顺序存储结构。（不要把数组与顺序存储结构搞混，顺序存储结构是单指与链式存储结构相对的地址连续的内存单元存储法，只是在c语言中，顺序存储结构由数组来表现）
数组类型的性质
- 数据元素的数目固定；
- 所有数据元素具有相同的数据类型；
- 每个数据元素都有一个（组）唯一的下标；
- 数组是一种随机存储结构，数组中的元素可以随机存取。（随机存取即直接用下标存取矩阵中的元素）

一维数组：

$a_i与a_1$ 之间有i-1个元素，占领了（i-1）*k个存储单元。

多维数组

行优先存储：以行序为主序的存储
列优先存储：以列序为主序的存储
分为这两种存储方式的原因是：虽然在我们的理解中多维数组就像矩阵一样，但实际在计算机中它是连续存储（就像一排排完的）,所以区分行列的优先度就显得很重要。

行优先存储

计算每一个元素前面的元素个数时，先计算前面有多少行，再计算本行前面有多少个元素。

三维数组的行优先存储

三个下标之间的关系可以类比二维数组行优先存储理解：二维数组的a[i][j]中，i是行数，j是列数，在计算机中存储时，相当与每一行看做一个整体（一维数组）然后依标号的顺序存储，一行中包含很多列。三维数组的a[i][j][k]中，i是页数，j是行数，k是列数，在计算机存储中，相当于将一页看做一个整体（二维数组），然后根据标号的顺序存储，一页中包含很多行和列，单独看一页中的存储顺序便相当于又是按照二维数组的存储方式来存储的。
计算公式的理解：先计算前面有多少页i -1,每一页的总元素个数为行列最大数相乘；再计算本页前面有多少行j -1每行的元素个数即为最大的列数，最后计算本行前面有多少列k - 1。

n维数组的行优先存储

第一个元素为a[1][1][1]算：
第一个元素不为a[1][1][1]算：

列优先存储

所有计算公式都与行优先存储的公式结构相同，顺序相反。即行优先存储从第一个下标 $i_1$ 算到第n个下标 $i_n$ ,而列优先存储的公式都是从第n个下标算到第1个下标。

特殊矩阵的压缩存储

特殊矩阵的主要形式
1. 对称矩阵
2. 上三角矩阵/下三角矩阵
3. 对角矩阵（带状矩阵）
特殊矩阵的共性：都是方阵，行数和列数相同。
特殊矩阵压缩存储后，由于它矩阵元素分布的规律，仍然具有随机存取的特性。

对称矩阵的压缩存储

对称矩阵定义
- a[i][j] == a[j][i]
对称矩阵的压缩存储
- 基本思想：
  - 利用其关于主对角线对称的特性，只存储下三角和主对角线上的元素，以节省空间。
  - 下三角和主对角线上的元素的特征是，行标大于或等于列标（i >= j）。
  - 用一维数组存储对称矩阵。
- 压缩前后的对应关系
  - 原矩阵有 $n^2$ 个元素，而压缩后储存在一维数组中的只有 $n(n+1)/2$ 个元素。但是原矩阵中的所有元素都可以在这个一维数组中找到。
  - 原矩阵第i行储存了i个元素在一维数组中，所以第i行第j列元素前有（1 + 2 + 3 + …+i-1）+ j-1个元素。这个个数，也对应着在一维数组中该元素的下标（若非c语言，要在个数后加1）。
  - 若要找到上三角的元素，则根据对称性，只需要将行列的下标对换，代入一维数组的下标计算公式即可。
  - 存储位置计算公式：

三角矩阵的压缩存储

上三角矩阵
- 基本思想
  - 与对称矩阵类似，只是未存储的部分全部为0，需要一维数组在最后留一个位置来储存这个常数。
- 压缩前后的对应关系：
  - 原矩阵第i行存入一维数组的元素个数为n-i+1个元素。
下三角矩阵：
按列优先存储压缩三角矩阵：
- 将计算公式的行列对换即可；
- 注意：一维数组的初始下标是从0还是1开始。

对角矩阵的压缩存储：

三对角矩阵的定义：
压缩的基本思想：
- 每个元素前有多少个元素是按照每行三个元素计算：3（i-1），之后再减去第一行少的一个元素，加上本行前有多少个:j-i+1
压缩前后的对应关系
- 每个元素前有 $2(i-1)+j-1$ 个元素。

稀疏矩阵

稀疏矩阵的定义：一个阶数较大的矩阵中的非零元素个数相对于总元素个数十分小时，称该矩阵为稀疏矩阵。
稀疏矩阵的压缩存储：
1. 三元组表示法：仍然使用线性表，即顺序存储结构存储；
2. 十字链表表示法：使用链表表示。
稀疏矩阵与特殊矩阵不同，它的非零元素分布并没有规律，所以稀疏矩阵压缩后就丧失了随机存取的特性。

稀疏矩阵的三元组表示

三元组定义

其中i，j存储的是该元素在稀疏矩阵中的行标和下标（与普通矩阵不同的是，它的行标和下标是从0开始算的）,而a[i][j]存储的是该元素具体的值。

三元组线性表的顺序结构存储及算法

创建三元组

基本原理
算法实现：
- 将非零元素按行序扫描到的顺序存储进顺序表中，即可实现三元组中的元素是按行序为主序排列。

三元组的元素赋值

分为两种情况：
- 只是修改非零元素的值
- 增加一个非零元素，即将原来矩阵中的0元素改为非零元素。

算法实现:

bool Value(TSMatrix *t, ElemType  e, int i, int j) //三元组的赋值
{
int k = 0;
if(i > t.Rows || j > t.Cols)
    return false; //坐标不合理  

while(k < t.Terms && i > t.elem[k].row)  //先查找行
    k++;

while(k < t.Terms && i == t.elem[k].row && j > t.elem[k].col) //查列
    k++;

    if(i == t.elem[k].row && j == t.elem[k].col) //判断条件，如果存在这样的一个元素
        t.elem[k].val=e; //那么把这个元素赋值给它


    else //如果不存在的话,此时的k在列标比预期列标大得最少的元素位置上
    {
    for(int k1 = t.Terms-1; k < k1; k1--) //先进行移位操作
    {
        t.elem[k1+1].row=t.elem[k1].row; //行
        t.elem[k1+1].col=t.elem[k1].col; //列
        t.elem[k1+1].val=t.elem[k1].val; //值
    }
        t.elem[k].row=i; //行
        t.elem[k].col=j; //列
        t.elem[k].val=e; //值
        t.Terms++; //个数加1
    }
    return true;
}

前面的算法有严重错误，后面的算法来做参考
若能找到对应的非零元素，则直接修改；
若不能找到对应的非零元素，则将k此时位置及以后的元素后移一位，将新元素值赋给k此时所在的位置。

取出指定位置元素的值

基本原理:在三元组中查找该位置，若能查到，则将该位置的元素值取出，若不能查到，则该位置的元素值应为0。不能直接根据位置取出元素（随机存取），还需经过查找的过程。（类比数组与链表的区别，数组可以直接拿出某一位置的元素值，而链表必须逐次查找）
算法实现：
- 注意：算法有误，查找时的条件应为i > t.data[k].row ;j > t.data[k].col
- 没有找到该位置只是对应着该位置元素为0，不是出错了。

输出三元组

只是输出三元组，不是输出一个矩阵，不用管零元素。

矩阵转置

矩阵转置的定义
直接转置的非高效算法
- 按照列从1到n依次查找，每一个列数都需要将整个三元组扫描一遍，设列数为n,非零元素个数为t,时间复杂度为 $O(nt)$
更加高效的算法：
- 基本原理：
  - 通过记录每个列标号的个数，来确定在新三元组中该列标号的元素出现的位置，然后直接将元素值填入该位置即可。
  - 设置两个数组，分别记录某列标号出现的次数，以及该列标号在新三元组中第一次出现的位置。
    - 此处列标号是从0开始算起。在第二个公式中，1 <= col <= t.n
    - position的计算就是将上一个列标号第一次出现的位置加上该列标号的数目。
- 算法实现：
  - 第一步先将矩阵的总行数与列数逆置；
  - 之后通过遍历原三元组，确定每列的非零元的个数，通过++bum[t.data[k].col]来实现对每一列非零元个数的计数，着实秒啊！
  - 第三步，利用num数组，计算出position数组的值；
  - 最后遍历原三元数组，通过每个元素的列标号col来确认它在新三元组中的位置；
  - 值得点赞的是，在每个列标号col对应的元素存入新三元组之后,通过++position[col]的操作，来确定下一个第col列非零元素的位置。

稀疏矩阵的十字链表表示

基本原理：
- 每个非零元素对应一个结点，该结点中储存该元素的行标和列标以及元素值，另外还设有两个分别向右和向下的指针域。
- 每行的所有结点链起来，再设置一个头结点，构成一个带头结点的单链表；
- 每列的所有结点链起来，在设置一个列结点，构成一个带头结点的单链表；
- 将所有行的头结点用一个数组储存起来，将所有列的头结点用一个数组储存起来；

结点的定义

typedef struct OLNode{
int i,j;//元素的行标和列标
int data;//元素的值
struct OLNode * right,*down;//两个指针域
}OLNode, *Olink;

十字链表的定义

typedef struct
{
OLink *rhead, *chead; //存储行和列链表头指针的两个数组
int mu, nu, tu;  //矩阵的行数,列数和非零元的个数
}CrossList;

十字链表的初始化

CrossList CreateMatrix_OL(CrossList M)
{
    int m, n, t; //储存矩阵的行数和列数，以及非零元素个数
    int i, j, e;
    OLNode *p, *q;

    printf("输入矩阵的行数、列数和非0元素个数：");
    scanf("%d%d%d", &m, &n, &t);
    M.mu = m;
    M.nu = n;
    M.tu = t;

    if (!(M.rhead = (OLink*)malloc((m + 1) * sizeof(OLink))) || !(M.chead = (OLink*)malloc((n + 1) * sizeof(OLink)))) //为头结点分配两个顺序储存空间（数组）
    {
        printf("初始化矩阵失败");
        exit(0);
    }

    for (i = 1; i <= m; i++)
    {
        M.rhead[i] = NULL;
    } //初始化所有行的头结点

    for (j = 1; j <= n; j++)
    {
        M.chead[j] = NULL;
    } //初始化所有列的头结点

    for (scanf("%d%d%d", &i, &j, &e); 0 != i; scanf("%d%d%d", &i, &j, &e)) {
        if (!(p = (OLNode*)malloc(sizeof(OLNode))))
        {
            printf("初始化结点失败");
            exit(0);
        }
        p->i = i;
        p->j = j;
        p->e = e;

        //链接到行的指定位置
        if (NULL == M.rhead[i] || M.rhead[i]->j > j)
        {
            p->right = M.rhead[i];
            M.rhead[i] = p;
        } //若原来那一行里第一个数据结点的列标就比新结点大或者没有数据结点，则头插法插入
        else
        {
            for (q = M.rhead[i]; (q->right) && q->right->j < j; q = q->right);
            p->right = q->right;
            q->right = p;
        } //若第一个数据结点比新结点的列标小，则向后找比新结点列标大的，若没有就到最后一个结点，然后插入该结点后面

        //链接到列的指定位置
        if (NULL == M.chead[j] || M.chead[j]->i > i)
        {
            p->down = M.chead[j];
            M.chead[j] = p;
        }
        else
        {
            for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);
            p->down = q->down;
            q->down = p;
        }
    }
    return M;
}

本文链接： http://www.zestaken.top/post/专业基础/数据结构/第五章数组与广义表/index.html

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

Zestaken计算机小白一枚

吾好梦中读书~

第五章 数组与广义表

数组与广义表

数组

数组的定义

数组的存储结构

一维数组：

多维数组

行优先存储

三维数组的行优先存储

n维数组的行优先存储

列优先存储

特殊矩阵的压缩存储

对称矩阵的压缩存储

三角矩阵的压缩存储

对角矩阵的压缩存储：

稀疏矩阵

稀疏矩阵的三元组表示

三元组定义

三元组线性表的顺序结构存储及算法

创建三元组

三元组的元素赋值

取出指定位置元素的值

输出三元组

矩阵转置

稀疏矩阵的十字链表表示

Zestaken计算机小白一枚

第五章数组与广义表