1. AI技术聚合首页
  2. IT

【数据结构】三元组表的定义以及快速转置

青葱年少 • • IT • 阅读 53

文章目录

  • ⭐️写在前面的话⭐️
  • 三元组顺序表的定义与使用
    • 1、三元组的定义
    • 2、创建稀疏矩阵
    • 3、打印稀疏矩阵
    • 4、将稀疏矩阵转为三元组矩阵
    • 5、打印三元组矩阵
    • 6、将三元组矩阵转为稀疏矩阵并打印
    • 7、转置三元组矩阵
      • 方法一（先按列的次序排序，再交换行列）
      • 方法二（快速转置算法）
    • 主函数
  • 程序源码
        • 运行截图

⭐️写在前面的话⭐️

📒博客主页： 程序员好冰
🎉欢迎 【点赞👍 关注🔎 收藏⭐️ 留言📝】
📌本文由 程序员好冰 原创，CSDN 首发！
📆入站时间： 🌴2022 年 07 月 13 日🌴
✉️ 是非不入松风耳，花落花开只读书。
💭推荐书籍：📚《Java编程思想》，📚《Java 核心技术卷》
💬参考在线编程网站：🌐牛客网🌐力扣
🍭 作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！🍭

三元组顺序表的定义与使用

存在一种矩阵，其非零元较零元少，而且分布没有一定的规律，就是稀疏矩阵；通常认为稀疏矩阵的稀疏因子小于或等于0.05。

然而，在存储稀疏矩阵时，通常不会按照普通的方法，将零元也进行操作，而是会通过三元组将稀疏矩阵进行压缩。

其思想是：只存入非零元，通过行标和列标记录非零元的逻辑上的二维坐标，其余的元素就默认是零元。

传递二维数组参数（固定维度和不固定维度两种）

参考这篇文章

1、三元组的定义

#include <stdio.h>
#include <stdlib.h>

//稀疏矩阵:矩阵中的非零元素比较少

//三元组的结点定义
#define MAX_SIZE 100//表中非零元素个数的最大值

typedef int ElemType;

//三元组结点定义
typedef struct Triple
{
    //三元组中非零元素的行下标和列下标
    int row;
    int col;
    ElemType e;//非零元素对应的值
}Triple;

//三元组顺序表定义
typedef struct TSMatrix
{
    Triple data[MAX_SIZE+1];//多余的一个位置用于存放非零元的个数
    int m_row,m_col,m_num;//矩阵的行数、列数(固定)和非零元的个数
}TSMatrix;

2、创建稀疏矩阵

void creatSMatrix(ElemType *mat,int row,int col)
{
    int i,j;
    printf("请按行依次输入这个矩阵的元素:\n");
    for(i=1;i<=row;i++){
        for(j=1;j<=col;j++){
            scanf("%d",(mat+(i-1)*col+j));
        }
    }
}

3、打印稀疏矩阵

void printSMatrix(ElemType *mat,int row,int col)
{
    printf("原始矩阵为:\n");
    int i,j;
    for(i=1;i<=row;i++){
        for(j=1;j<=col;j++){
            printf("%d\t",*(mat+(i-1)*col+j));
        }
        printf("\n");
    }
    printf("----------------------------------\n");
}

4、将稀疏矩阵转为三元组矩阵

//对三元组进行处理
void initTriple(TSMatrix *M,ElemType *mat,int row,int col)
{
    M->m_row=0;
    M->m_num=0;
    M->m_col=3;//三元组矩阵默认为三列
    int i,j;
    for(i=1;i<=row;i++){
        for(j=1;j<=col;j++){
            if(*(mat+(i-1)*col+j)!=0){
                //非零元数增加一个
                M->m_num++;
                M->m_row++;
                M->data[M->m_num].row=i;
                M->data[M->m_num].col=j;
                M->data[M->m_num].e=*(mat+(i-1)*col+j);
            }
        }
    }
    //第0号位置存放的是原始矩阵的行数和列数，以及非零元的个数
    M->data[0].row=row;
    M->data[0].col=col;
    M->data[0].e=M->m_num;
}

5、打印三元组矩阵

void printTriple(TSMatrix M)
{
    //打印三元组
    printf("三元组矩阵为:\n");
    printf("行\t列\t值\n");
    int i;
    for(i=0;i<=M.m_row;i++){
        printf("%d\t%d\t%d\n",M.data[i].row,M.data[i].col,M.data[i].e);
    }
    printf("----------------------------------\n");
}

6、将三元组矩阵转为稀疏矩阵并打印

//将三元组表还原为稀疏矩阵
void printSMatrix2(TSMatrix M)
{
    int i,j;
    int row=M.data[0].row;
    int col=M.data[0].col;
    ElemType mat2[row][col];
    //写法一（比较常规）
    //写法二(数组中的每个元素默认值都为0)
    for(i=1;i<=M.m_num;i++){
        mat2[M.data[i].row][M.data[i].col]=M.data[i].e;
    }
    printf("原始矩阵为:\n");
    for(i=1;i<=row;i++){
        for(j=1;j<=col;j++){
            printf("%d\t",mat2[i][j]);
        }
        printf("\n");
    }
    printf("----------------------------------\n");
}

7、转置三元组矩阵

我们知道，稀疏矩阵的转置需要经历以下 3 步：

  1. 将矩阵的行数和列数互换；
  2. 将三元组表（存储矩阵）中的 i 列和 j 列互换，实现矩阵的转置；
  3. 以 j 列为序，重新排列三元组表中存储各三元组的先后顺序。
  • 由于三元组表的第0行存放的是稀疏矩阵的信息，所以只进行交换，不进行重排。

image-20230423180003784

方法一（先按列的次序排序，再交换行列）

对矩阵M的col的值进行冒泡排序，由于M是以行序为主序排列的，说明对col的相同值来说，已经是排好序的了，因此不必再对row的值进行冒泡排序。

操作过程中，将col列中的最小值提出，放到转置矩阵T的第一行，注意行列交换，值value不改变。

image-20230423180244705

同样的思路：先交换行列，再进行行排序

//普通转置思路
//参数中M指原三元组表，值传递
//参数中T指转置后的三元组表，引用传递
void TransposeSMatrix(TSMatrix M,TSMatrix *T)
{
    int T_index;用于遍历T的非0行，共遍历t_num次
    int M_col;//记录三元组表M的列的数值，应该从1递增
    int M_index;//用于遍历M的非0行，共遍历m_num次
    //先将M的一些初始信息赋值为T
    T->m_row=M.m_row;
    T->m_col=M.m_col;
    T->m_num=M.m_num;
    T->data[0].row=M.data[0].col;
    T->data[0].col=M.data[0].row;
    T->data[0].e=M.data[0].e;//这相当于处理完了三元组表的第0行
    if(T->m_num>0){
        T_index=1;
        for(M_col=1;M_col<=M.m_col;M_col++){
            //这里的M_index从1开始，是因为我们上面已经处理好的第0行
            for(M_index=1;M_index<=M.m_num;M_index++){
                if(M.data[M_index].col==M_col){
                    T->data[T_index].row=M.data[M_index].col;
                    T->data[T_index].col=M.data[M_index].row;
                    T->data[T_index].e=M.data[M_index].e;
                    T_index++;
                }
            }
        }
    }
}

方法二（快速转置算法）

可以参考一下这个文章

稀疏矩阵快速转置算法和普通算法的区别仅在于第 3 步，快速转置能够做到遍历一次三元组表即可完成第 3 步的工作。

初步思路：统计M矩阵列中小于col值的个数，加上1就是转置后T矩阵中所对应的行数。

​ 若col值存在相同的，则进行累加。

可以发现这种思路的时间复杂度同样挺高的，甚至和方法一的思路类似。

实际算法:

注意：

这里通过两个数组来缩短算法的时间复杂度

  • 记录稀疏矩阵每一列非零元素的个数a[col]，第1列有1个非零元，第2列有2个非零元。

​ a[1]=1;a[2]=2;

  • 记录稀疏矩阵中每一列第1个非零元素在转置后的三元表中的位置b[col],由转置的性质我们可以知道，转置相当于将原先按行展开的形式按列展开；故第1列的首非零元会放到转置后的三元表的第1个位置上（第0个位置上有其它信息）。

​ b[1]=1；b[2]=2。

b[col]=b[col-1]+a[col-2]

解释一下：由于我们的稀疏矩阵是从第0行第0列开始的，所以这里的a[col-2]是减2，而不是减1。

后一列首个非 0 元素存放的位置等于前一列首个非 0 元素的存放位置加上该列非 0 元素的个数。

image-20230423200002035
//三元组表的快速转置
/*
思路:
    按列查找每一列中的首非零元以及非零元的个数，并使用两个数组存储起来
    有cpot[n]=cpot[n-1]+num[n-1]
    并规定cpot[1]=1
    注意：这里不考虑稀疏矩阵或是三元组表的0行0列
*/
void FastTransposeSMatrix(TSMatrix M,TSMatrix *T2)
{
    int T2_index;用于遍历T的非0行，共遍历t_num次
    int M_col;//记录三元组表M的列的数值，应该从1递增
    int M_index;//用于遍历M的非0行，共遍历m_num次

    int num[MAX_SIZE];//用于记录M中每一列的非零元素
    int cpot[MAX_SIZE];//用于记录M中每一列的首非零元素应该在T中的index(从1开始)

    //首先，分别从表结构和非零元两个方面赋值T2
    T2->m_row=M.m_row;
    T2->m_col=M.m_col;
    T2->m_num=M.m_num;
    T2->data[0].row=M.data[0].col;
    T2->data[0].col=M.data[0].row;
    T2->data[0].e=M.data[0].e;

    if(T2->m_num>0){
        //将数组num中的每个元素置0，防止默认值
        for(M_col=1;M_col<=M.m_col;M_col++){
            num[M_col]=0;
        }
        //遍历稀疏矩阵每一列，统计非零元的数量
        for(M_index=1;M_index<=M.m_num;M_index++){
            num[M.data[M_index].col]++;
        }

        //由于转置后相当于按列展开
        //默认（稀疏矩阵从第1行第1列开始）
        cpot[1]=1;

        for(M_col=2;M_col<=M.m_col;M_col++){
            cpot[M_col]=cpot[M_col-1]+num[M_col-1];
        }
        //遍历M的每一行
        for(M_index=1;M_index<=M.m_num;M_index++){
            //取每一行的列下标
            M_col=M.data[M_index].col;
            //带入cpot[]数组中，找到在T中的下标
            //cpot中存有所有非零元的位置信息
            T2_index=cpot[M_col];
            //互换信息
            T2->data[T2_index].row=M.data[M_index].col;
            T2->data[T2_index].col=M.data[M_index].row;
            T2->data[T2_index].e=M.data[M_index].e;
            //这个值是根据列来自增的
            //即每一列中除了首非零元，还剩下几个非零元就加几次
            cpot[M_col]++;
        }
    }
}

主函数

int main()
{
    printf("初始化稀疏矩阵...\n");
    int row,col;
    printf("请输入矩阵的行数和列数(row,col):");
    scanf("%d,%d",&row,&col);
    printf("\n");
    ElemType mat[row][col];
    TSMatrix M;
    TSMatrix T;
    TSMatrix T2;

    //创建稀疏矩阵
    creatSMatrix(*mat,row,col);
    printf("----------------------------------\n");
    //打印稀疏矩阵
    printSMatrix(*mat,row,col);
    //将稀疏矩阵转为三元组
    initTriple(&M,*mat,row,col);
    //打印三元组
    printTriple(M);
    //将三元组还原，并打印
    printf("还原后的");

    printSMatrix2(M);

    //转置三元组

    /*方法一*/
    TransposeSMatrix(M,&T);
    printf("普通转置后的");
    printTriple(T);
    /*方法二*/
    FastTransposeSMatrix(M,&T2);
    printf("快速转置后的");
    printTriple(T2);
    printf("Hello world!\n");
    return 0;
}

程序源码

运行截图

image-20230425202934182

#include <stdio.h>
#include <stdlib.h>

//稀疏矩阵:矩阵中的非零元素比较少

//三元组的结点定义
#define MAX_SIZE 100//表中非零元素个数的最大值

typedef int ElemType;

//三元组结点定义
typedef struct Triple
{
    //三元组中非零元素的行下标和列下标
    int row;
    int col;
    ElemType e;//非零元素对应的值
}Triple;

//三元组顺序表定义
typedef struct TSMatrix
{
    Triple data[MAX_SIZE+1];//多余的一个位置用于存放非零元的个数
    int m_row,m_col,m_num;//矩阵的行数、列数(固定)和非零元的个数
}TSMatrix;

void creatSMatrix(ElemType *mat,int row,int col)
{
    int i,j;
    printf("请按行依次输入这个矩阵的元素:\n");
    for(i=1;i<=row;i++){
        for(j=1;j<=col;j++){
            scanf("%d",(mat+(i-1)*col+j));
        }
    }
}

void printSMatrix(ElemType *mat,int row,int col)
{
    printf("原始矩阵为:\n");
    int i,j;
    for(i=1;i<=row;i++){
        for(j=1;j<=col;j++){
            printf("%d\t",*(mat+(i-1)*col+j));
        }
        printf("\n");
    }
    printf("----------------------------------\n");
}

//对三元组进行处理
void initTriple(TSMatrix *M,ElemType *mat,int row,int col)
{
    M->m_row=0;
    M->m_num=0;
    M->m_col=3;//三元组矩阵默认为三列
    int i,j;
    for(i=1;i<=row;i++){
        for(j=1;j<=col;j++){
            if(*(mat+(i-1)*col+j)!=0){
                //非零元数增加一个
                M->m_num++;
                M->m_row++;
                M->data[M->m_num].row=i;
                M->data[M->m_num].col=j;
                M->data[M->m_num].e=*(mat+(i-1)*col+j);
            }
        }
    }
    //第0号位置存放的是原始矩阵的行数和列数，以及非零元的个数
    M->data[0].row=row;
    M->data[0].col=col;
    M->data[0].e=M->m_num;
}


void printTriple(TSMatrix M)
{
    //打印三元组
    printf("三元组矩阵为:\n");
    printf("行\t列\t值\n");
    int i;
    for(i=0;i<=M.m_row;i++){
        printf("%d\t%d\t%d\n",M.data[i].row,M.data[i].col,M.data[i].e);
    }
    printf("----------------------------------\n");
}

//将三元组表还原为稀疏矩阵
void printSMatrix2(TSMatrix M)
{
    int i,j;
    int row=M.data[0].row;
    int col=M.data[0].col;
    ElemType mat2[row][col];
    //写法一（比较常规）
    //写法二(数组中的每个元素默认值都为0)
    for(i=1;i<=M.m_num;i++){
        mat2[M.data[i].row][M.data[i].col]=M.data[i].e;
    }
    printf("原始矩阵为:\n");
    for(i=1;i<=row;i++){
        for(j=1;j<=col;j++){
            printf("%d\t",mat2[i][j]);
        }
        printf("\n");
    }
    printf("----------------------------------\n");
}

//普通转置思路
//参数中M指原三元组表，值传递
//参数中T指转置后的三元组表，引用传递
void TransposeSMatrix(TSMatrix M,TSMatrix *T)
{
    int T_index;用于遍历T的非0行，共遍历t_num次
    int M_col;//记录三元组表M的列的数值，应该从1递增
    int M_index;//用于遍历M的非0行，共遍历m_num次
    //先将M的一些初始信息赋值为T
    T->m_row=M.m_row;
    T->m_col=M.m_col;
    T->m_num=M.m_num;
    T->data[0].row=M.data[0].col;
    T->data[0].col=M.data[0].row;
    T->data[0].e=M.data[0].e;//这相当于处理完了三元组表的第0行
    if(T->m_num>0){
        T_index=1;
        for(M_col=1;M_col<=M.m_col;M_col++){
            //这里的M_index从1开始，是因为我们上面已经处理好的第0行
            for(M_index=1;M_index<=M.m_num;M_index++){
                if(M.data[M_index].col==M_col){
                    T->data[T_index].row=M.data[M_index].col;
                    T->data[T_index].col=M.data[M_index].row;
                    T->data[T_index].e=M.data[M_index].e;
                    T_index++;
                }
            }
        }
    }
}

//三元组表的快速转置
/*
思路:
    按列查找每一列中的首非零元以及非零元的个数，并使用两个数组存储起来
    有cpot[n]=cpot[n-1]+num[n-1]
    并规定cpot[1]=1
    注意：这里不考虑稀疏矩阵或是三元组表的0行0列
*/
void FastTransposeSMatrix(TSMatrix M,TSMatrix *T2)
{
    int T2_index;用于遍历T的非0行，共遍历t_num次
    int M_col;//记录三元组表M的列的数值，应该从1递增
    int M_index;//用于遍历M的非0行，共遍历m_num次

    int num[MAX_SIZE];//用于记录M中每一列的非零元素
    int cpot[MAX_SIZE];//用于记录M中每一列的首非零元素应该在T中的index(从1开始)

    //首先，分别从表结构和非零元两个方面赋值T2
    T2->m_row=M.m_row;
    T2->m_col=M.m_col;
    T2->m_num=M.m_num;
    T2->data[0].row=M.data[0].col;
    T2->data[0].col=M.data[0].row;
    T2->data[0].e=M.data[0].e;

    if(T2->m_num>0){
        //将数组num中的每个元素置0，防止默认值
        for(M_col=1;M_col<=M.m_col;M_col++){
            num[M_col]=0;
        }
        //遍历稀疏矩阵每一列，统计非零元的数量
        for(M_index=1;M_index<=M.m_num;M_index++){
            num[M.data[M_index].col]++;
        }

        //由于转置后相当于按列展开
        //默认（稀疏矩阵从第1行第1列开始）
        cpot[1]=1;

        for(M_col=2;M_col<=M.m_col;M_col++){
            cpot[M_col]=cpot[M_col-1]+num[M_col-1];
        }
        //遍历M的每一行
        for(M_index=1;M_index<=M.m_num;M_index++){
            //取每一行的列下标
            M_col=M.data[M_index].col;
            //带入cpot[]数组中，找到在T中的下标
            //cpot中存有所有非零元的位置信息
            T2_index=cpot[M_col];
            //互换信息
            T2->data[T2_index].row=M.data[M_index].col;
            T2->data[T2_index].col=M.data[M_index].row;
            T2->data[T2_index].e=M.data[M_index].e;
            //这个值是根据列来自增的
            //即每一列中除了首非零元，还剩下几个非零元就加几次
            cpot[M_col]++;
        }
    }
}

int main()
{
    printf("初始化稀疏矩阵...\n");
    int row,col;
    printf("请输入矩阵的行数和列数(row,col):");
    scanf("%d,%d",&row,&col);
    printf("\n");
    ElemType mat[row][col];
    TSMatrix M;
    TSMatrix T;
    TSMatrix T2;

    //创建稀疏矩阵
    creatSMatrix(*mat,row,col);
    printf("----------------------------------\n");
    //打印稀疏矩阵
    printSMatrix(*mat,row,col);
    //将稀疏矩阵转为三元组
    initTriple(&M,*mat,row,col);
    //打印三元组
    printTriple(M);
    //将三元组还原，并打印
    printf("还原后的");

    printSMatrix2(M);

    //转置三元组

    /*方法一*/
    TransposeSMatrix(M,&T);
    printf("普通转置后的");
    printTriple(T);
    /*方法二*/
    FastTransposeSMatrix(M,&T2);
    printf("快速转置后的");
    printTriple(T2);
    printf("Hello world!\n");
    return 0;
}

🚀先看后赞，养成习惯！🚀

🚀 先看后赞，养成习惯！🚀

🎈觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！🎈

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
青葱年少的头像青葱年少普通用户
0
上一篇 2023年12月11日
下一篇 2023年12月11日

相关推荐