首页 > 其他分享 >[数据结构] 数组与特殊矩阵

[数据结构] 数组与特殊矩阵

时间：2024-02-06 16:55:05浏览次数：22  
标签：matrix 元素 矩阵 cdots 数组 数据结构 data

写在前面

偷懒，先写了数组，列表要画图，所以今天就先不写了

数组的定义

数组是由n个相同类型的数据元素构成的有限序列。每个数据元素被称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表，二维数组可视为其元素是定长数组的线性表。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

数组的顺序存储

一维数组

以\(A[0 \dots n-1]\)为例，其存储结构关系式为：

\[LOC(a_i) = LOC(a_0) + i \times L(0 \leq i < n) \]

其中，\(L\)是每个数组元素所占的存储单元。

多维数组

以二维数组为例。设二维数组的行下标与列下标的范围分别为\([0, h_1]\)和\([0,h_2]\)。

按行优先

先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。存储结构关系式为：

\[LOC(a_{i,j}) = LOC(a_{0,0})+[i \times(h_2+1) + j] \times L \]

例如对于数组\(A_{[2][3]}\)。它按行优先方式在内存中的存储形式如下所示：

\[\left[ \begin{matrix} a_{[0][0]} & a_{[0][1]} & a_{[0][2]} \\ a_{[1][0]} & a_{[1][1]} & a_{[1][2]} \\ \end{matrix} \right] \]

\(a_{[0][0]}\) \(a_{[0][1]}\) \(a_{[0][2]}\) \(a_{[1][0]}\) \(a_{[1][1]}\) \(a_{[1][2]}\)

列优先

存储结构关系式为：

\[LOC(a_{i,j}) = LOC(a_{0,0})+[j \times (h_1 + 1) + i] \times L \]

例如对于数组\(A_{[2][3]}\)。它按行优先方式在内存中的存储形式如下所示：

\[\left[ \begin{matrix} a_{[0][0]} & a_{[0][1]} & a_{[0][2]} \\ a_{[1][0]} & a_{[1][1]} & a_{[1][2]} \\ \end{matrix} \right] \]

\(a_{[0][0]}\) \(a_{[1][0]}\) \(a_{[0][1]}\) \(a_{[1][1]}\) \(a_{[0][2]}\) \(a_{[1][2]}\)

特殊矩阵的压缩存储

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间；

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布具有一定规律性的矩阵；

特殊矩阵的压缩存储：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

对称矩阵

对一个n阶矩阵\(A\)中的任意一个元素\(a_{i,j}\)都有\(a_{i, j} = a_{j, i}(1 \leq i, j \leq n)\)，则称其为对称矩阵

\[\left[ \begin{matrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \end{matrix} \right] \]

很显然，对于n阶对称矩阵，上三角区所有元素和下三角区的对应元素相同，采用二维数组存放，会造成大范围的空间浪费，因此我们把其存放在一维数组\(B[\frac{n(n+1)}{2}]\)中。

比如只存放下三角部分的元素：

在数组\(B\)中，位于元素\(a_{i, j}\)前的元素个数为：

第1行：1个（\(a_{1,1}\)）

第2行：2个（\(a_{2,1},a_{2,2}\)）

\(\dots\)

第\(i-1\)行：\(i-1\)个（\(a_{i-1,1},a_{i-1,2} \dots ,a_{i-1,i-1}\)）

第\(i\)行：\(j-1\)个（\(a_{i,1},a_{i,2}, \dots , a_{i,j-1}\)）

因此，元素\(a_{i,j}\)在数组\(B\)中的下标\(k = 1 + 2 + \dots + (i - 1) + j - 1 = \frac{i(i - 1)}{2} + j - 1\)

因此，元素下标之间对应关系如下：

\[k = \begin{cases} \frac{i(i-1)}{2} + j - 1&, \qquad i \geq j \\ \frac{j(j-1)}{2} + i - 1&, \qquad i < j \end{cases} \]

三角矩阵

下三角矩阵

\[\left[ \begin{matrix} a_{1,1} \\ a_{2,1} & a_{2,2} \\ \vdots & \vdots & \ddots \\ a_{n,1} & a_{n,2} & \cdots a_{n,n} \end{matrix} \right] \]

上三角区为统一常量。元素下标之间的对应关系为：

\[k = \begin{cases} \frac{i(i-1)}{2} + j - 1 &, \qquad i \geq j \\ \frac{n(n-1)}{2} &, \qquad i < j \end{cases} \]

下标 0 1 2 3 4 5 \(\cdots\) \(\frac{n(n+1)}{2}\)
元素 \(a_{1,1}\) \(a_{2,1}\) \(a_{2,2}\) \(a_{3,1}\) \(a_{3,2}\) \(a_{3,3}\) \(\cdots\) \(a_{n,1}\) \(a_{n,2}\) \(\cdots\) \(a_{n,n}\) \(c\)
行号 第一行 第二行 第二行 第三行 第三行 第三行 \(\cdots\) 第n行 第n行 \(\cdots\) 第n行 常数项

上三角矩阵

\[\left[ \begin{matrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ & a_{2,2} & \cdots & a_{2,n} \\ & & \ddots & \vdots \\ & & & a_{n,n} \end{matrix} \right] \]

与上文类似地，位于元素\(a_{i,j}(i \leq j)\)前面的元素个数为：

第1行：\(n\)个

第2行：\(n-1\)个

\(\dots\)

第\(i-1\)行：\(n - i + 2\)个

第\(i\)行：\(j-1\)个

因此，元素\(a_{i,j}\)在数组\(B\)中的下标\(k = n + (n - 1) + \dots + (n - i + 2) + (j - i + 1) - 1\)

因此，元素下标之间对应关系如下：

\[k = \begin{cases} \frac{(i-1)(2n - i + 2)}{2} + j - i &, \qquad i \leq j \\ \frac{n(n+1)}{2} &, \qquad i > j \end{cases} \]

下标 0 1 \(\cdots\) \(\frac{n(n+1)}{2}\)
元素 \(a_{1,1}\) \(a_{1,2}\) \(\cdots\) \(a_{1,n}\) \(a_{2,2}\) \(a_{2,3}\) \(\cdots\) \(a_{2,n}\) \(\cdots\) \(a_{n,n}\) \(c\)
行号 第一行 第一行 第一行 第一行 第二行 第二行 第二行 第二行 \(\cdots\) 第n行 常数

三对角矩阵

对n阶矩阵\(A\)中的任意元素\(a_{i,j}\)，都有当\(|i-j| >1\)时，\(a_{i,j} = 0\)。

\[\left[ \begin{matrix} a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} & a_{2,3} & & 0 \\ & a_{3,2} & a_{3,3} & a_{3,4} \\ & & \ddots & \ddots & \ddots \\ & 0 & & a_{n-1,n-2} & a_{n-1,n-1} & a_{n-1,n} \\ & & & & a_{n,n-1} & a_{n, n} \end{matrix} \right] \]

稀疏矩阵

矩阵中非零元素的个数t，相对于矩阵元素的个数s来说非常少，即\(s >> t\)的矩阵称为稀疏矩阵

我们可以用对应的三元组线性表来存储稀疏矩阵，如下例：

\[M = \left[ \begin{matrix} 4 & 0 & 0 & 0 \\ 0 & 0 & 6 & 0 \\ 0 & 9 & 0 & 0 \\ 0 & 23 &0 & 0 \end{matrix} \right] \]

对应的三元组为：

\[\left( \begin{matrix} i & j & a_{i,j} \\ 0 & 0 & 4 \\ 1 & 2 & 6 \\ 2 & 1 & 9 \\ 3 & 1 & 23 \end{matrix} \right) \]

下面，上代码，可以实现稀疏矩阵的输入、输出，稀疏矩阵对应三元组的加法、乘法、转置：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10000

typedef int ElemType;

typedef struct {

    int i, j;
    ElemType e;

}Triple;


typedef struct {

    Triple data[MAXSIZE + 1];
    int mu, nu, tu;          //矩阵行数，列数和非0元个数

}TSMatrix;



//输入稀疏矩阵数据
void InPutM(TSMatrix& M) {
    printf("输入稀疏矩阵的 行数, 列数, 非0元个数 :\n");
    scanf_s("%d %d %d", &M.nu, &M.mu, &M.tu);
    printf("输入矩阵非0元素的 所在行i, 所在列j, 值e:\n");
    for (int k = 1; k <= M.tu; k++) {
        scanf_s("%d %d %d", &M.data[k].i, &M.data[k].j, &M.data[k].e);
    }
}



//打印稀疏矩阵三元组数据
void PrintM(TSMatrix T) {
    printf("  %d    %d    %d\n", T.mu, T.nu, T.tu);
    printf("  ------------\n");
    for (int k = 1; k <= T.tu; k++) {
        printf("  %d    %d    %d\n", T.data[k].i, T.data[k].j, T.data[k].e);
    }
}



//稀疏矩阵三元组加法
void AddSMatrix(TSMatrix a, TSMatrix b, TSMatrix& c) {
    int i = 0, j = 0, k = 0;
    ElemType v;                            //用于计算和
    if (a.mu != b.mu || a.nu != b.nu)       //两矩阵无法相加
        return;

    c.mu = a.mu;
    c.nu = a.nu;
    while (i < a.tu || j < b.tu)
    {
        //若行相等，看列
        if (a.data[i + 1].i == b.data[j + 1].i)
        {
            //行相同时的第一种情况
            if (a.data[i + 1].j < b.data[j + 1].j)
            {
                c.data[k + 1].i = a.data[i + 1].i;
                c.data[k + 1].j = a.data[i + 1].j;
                c.data[k + 1].e = a.data[i + 1].e;
                k++;
                i++;        //前往下一个a中的非0元
            }
            //行相同时的第二种情况
            else if (a.data[i + 1].j > b.data[j + 1].j)
            {
                c.data[k + 1].i = b.data[j + 1].i;
                c.data[k + 1].j = b.data[j + 1].j;
                c.data[k + 1].e = b.data[j + 1].e;
                k++;
                j++;        //前往下一个b中的非0元
            }
            //行相同的第三种情况
            else
            {
                v = a.data[i + 1].e + b.data[j + 1].e;
                if (v != 0)
                {
                    c.data[k + 1].i = a.data[i + 1].i;
                    c.data[k + 1].j = a.data[i + 1].j;
                    c.data[k + 1].e = v;
                    k++;
                }
                i++;
                j++;
            }
        }
        //若行不相同 的两种情况
        else if (i == a.tu || a.data[i + 1].i > b.data[j + 1].i && j != b.tu)
        {
            c.data[k + 1].i = b.data[j + 1].i;
            c.data[k + 1].j = b.data[j + 1].j;
            c.data[k + 1].e = b.data[j + 1].e;
            k++;
            j++;      //前往下一个b的非0元
        }
        else if (j == b.tu || a.data[i + 1].i < b.data[j + 1].i && i != a.tu)
        {
            c.data[k + 1].i = a.data[i + 1].i;
            c.data[k + 1].j = a.data[i + 1].j;
            c.data[k + 1].e = a.data[i + 1].e;
            k++;
            i++;      //前往下一个a的非0元
        }
    }
    c.tu = k;
}



//乘法辅助函数
int Getval(TSMatrix a, int i, int j) {
    int k = 1;
    while (k <= a.tu && (a.data[k].i != i || a.data[k].j != j))
        k++;
    if (k <= a.tu)
        return a.data[k].e;
    else
        return 0;
}



//稀疏矩阵三元组乘法
void MultSMatrix(TSMatrix a, TSMatrix b, TSMatrix& c) {
    int p = 0;
    ElemType s;
    if (a.nu != b.mu)
        return;

    for (int i = 1; i <= a.mu; i++) {
        for (int j = 1; j <= b.nu; j++) {
            s = 0;
            for (int k = 1; k <= a.nu; k++)
                s += Getval(a, i, k) * Getval(b, k, j);
            if (s != 0) {
                c.data[p + 1].i = i;
                c.data[p + 1].j = j;
                c.data[p + 1].e = s;
                p++;
            }
        }
    }
    c.mu = a.mu;
    c.nu = b.nu;
    c.tu = p;
}



//稀疏矩阵转置   （适用于 tu << mu × nu 的情况）
void TransposeSMatrix(TSMatrix M, TSMatrix& T) {
    T.mu = M.nu;                           //T行数等于原矩阵列数
    T.nu = M.mu;                           //T列数等于原矩阵行数
    T.tu = M.tu;
    if (!T.tu)
        return;

    int q = 1;                             //从列数小的开始，一一对应赋值
    for (int col = 1; col <= M.nu; ++col) {
        for (int p = 1; p <= M.tu; ++p) {
            if (M.data[p].j == col) {
                T.data[q].i = M.data[p].j;
                T.data[q].j = M.data[p].i;
                T.data[q].e = M.data[p].e;
                q++;
            }
        }
    }
}



//稀疏矩阵的快速转置算法
int cpot[MAXSIZE + 1], num[MAXSIZE + 1];   //辅助数组  
//cpot[col] 表示M中第col列第一个非0元在T.data中的位置
//num[col]  表示M中第col列中非0元的个数
void FastTransposeSMatrix(TSMatrix M, TSMatrix& T) {
    T.mu = M.nu;
    T.nu = M.mu;
    T.tu = M.tu;
    if (!T.tu)
        return;

    for (int col = 1; col <= M.mu; col++)
        num[col] = 0;                      //初始化为0

    for (int k = 1; k <= M.tu; k++)
        num[M.data[k].j]++;                //记录M.data[k].j列中非0元个数 （简易哈希表）

    cpot[1] = 1;                           //初始化第一个非0元的序号
    for (int col = 2; col <= M.mu; col++)   //求第col列中第一个非零元在T.data中的序号   
        cpot[col] = cpot[col - 1] + num[col - 1];

    for (int p = 1; p <= M.tu; p++) {
        int col = M.data[p].j;             //此时M对应三元组中的非0元的所在列
        int q = cpot[col];                  //q为当前非0元的应当放置的序号位置
        T.data[q].i = M.data[p].j;
        T.data[q].j = M.data[p].i;
        T.data[q].e = M.data[p].e;
        cpot[col]++;                       //cpot[col]++,对应下一个此列中非0元的序号
        //cpot[col]最后一直加到等于cpot[col + 1],第col列也就不会有更多的非0元了
    }
}




int main() {
    TSMatrix A, B, C, D;
    printf("输入稀疏矩阵A的三元组:\n");
    InPutM(A);
    PrintM(A);
    printf("\n输入稀疏矩阵B的三元组:\n");
    InPutM(B);
    PrintM(B);
    //printf("\n矩阵A与B相加得到矩阵C:\n");
    //AddSMatrix(A, B, C);
    //PrintM(C);
    printf("\n矩阵A与B相乘得到矩阵D:\n");
    MultSMatrix(A, B, D);
    PrintM(D);
    printf("\n");
    system("pause");
    system("cls");



    TSMatrix M, T, FT;
    printf("————稀疏矩阵转置测试————\n\n");
    InPutM(M);
    printf("\n稀疏矩阵转置前三元组: \n");
    PrintM(M);

    printf("\n稀疏矩阵转置结果: \n");
    TransposeSMatrix(M, T);
    PrintM(T);

    printf("\n稀疏矩阵的快速转置结果: \n");
    FastTransposeSMatrix(M, FT);
    PrintM(FT);
}

标签：matrix,元素,矩阵,cdots,数组,数据结构,data
From： https://www.cnblogs.com/wanyy-home/p/18009990

相关文章

  • JavaScript 实现类似SQL 左联接式的对象数组合并
    在JavaScript中，你可以使用对象合并（Objectmerging）来模拟数据库的左联接操作。左联接操作会将两个对象的特定属性进行合并，类似于SQL中的LEFTJOIN操作。假设你有两个对象，每个对象代表一个表：consttable1=[{id:1,age:30},{id:3,age:25},];consttable2......
  • Java 中的哈希表数据结构
    哈希表数据结构HashMap集合：在JDK8之后，如果单向链表中的元素超过8个，单向链表数据结构就会变成红黑树数据结构，当红黑树上的节点数量小于6时，会重新把红黑树变成单向链表数据结构。HashMap集合底层是哈希表/散列表的数据结构哈希表是一个怎样的数据结构？哈希表是一个数组和单向链......
  • 【CPL-2023】W4 W5笔记-循环、多维数组
    编码练习选择排序冒泡排序二分法 循环多维数组标量：保存单一数据项聚合变量：存储成组的数据：数组，结构体数组检查下标是否越界地址消除器--检查地址取值时是否合法在同一个表达式中对i同时有取值操作和++操作，不同编译器有可能行为不一致，所以不建议这么写i......
  • 【CPL-2023】W3笔记-条件、循环、数组
    分支结构程序的生存期if();等价于if(){  ;}级联ifif(){}elseif(){}elseif(){}else{}关系运算符优先级低于算术运算符判等运算符优先级低于关系运算符多出口程序不容易调试(if多个分支中多个pritf类似这种程序)可以调整多出口程序为单出口......
  • 代码随想录算法训练营第十三天 | 59.螺旋矩阵II 209.长度最小的子数组 977.有序数
    977.有序数组的平方 已解答简单 相关标签相关企业 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。 示例1：输入：nums=[-4,-1,0,3,10]输出：[0,1,9,16,100]解释：平方后，数组变为[16......
  • [数据结构] 栈
    栈的定义及特点栈（Stack）是只允许在一端进行插入或删除操作的线性表，如图所示：栈顶（top）：线性表允许进行插入、删除的一端；栈底（bottom）：不允许进行插入和删除的一端；空栈：不含任何元素的空表。如上图所示，设某个栈\(S=(a_1,a_2,a_3,a_4,a_5)\)，则\(a_1\)为栈底元素，\(a_5\)为栈顶元素。......
  • JS数组添加元素的三种方式
    JS数组添加元素的三种方式1、push()结尾添加数组.push(元素)参数描述newelement1必需。要添加到数组的第一个元素。newelement2可选。要添加到数组的第二个元素。newelementX可选。可添加多个元素。2、unshift()头部添加数组.unshift(元素)参数描述newelement1必......
  • 经典数据结构题目-图
    图200.岛屿数量思路遍历二维数组，遇到等于1的进行计算。同时修改同岛的位置为0，避免重复计算遍历同岛的位置，可以采用dfs深度优先搜索代码char[][]g;publicintnumIslands(char[][]grid){intsum=0;g=grid;for(inti=0;......
  • 有关各种数据结构模板
    FHQ-Treap模板题-普通平衡树#include<bits/stdc++.h>#definelstr[u].l#definerstr[u].rusingnamespacestd;constintN=3e5+10;structNode{intl,r;intkey,v;intsize;}tr[N];introot,idx;intn,m;voidpushup(intu){tr[u].size......
  • R语言逻辑回归、决策树、随机森林、神经网络预测患者心脏病数据混淆矩阵可视化
    全文链接:https://tecdat.cn/?p=33760原文出处：拓端数据部落公众号概述：众所周知，心脏疾病是目前全球最主要的死因。开发一个能够预测患者心脏疾病存在的计算系统将显著降低死亡率并大幅降低医疗保健成本。机器学习在全球许多领域中被广泛应用，尤其在医疗行业中越来越受欢迎。机器......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99