精华内容
下载资源
问答
  • 数据结构,稀疏矩阵快速转置c语言算法,时间复杂性为O(n+t)。
  • c数据结构实验 稀疏矩阵三元压缩存储 稀疏矩阵快速转置
  • 三元组稀疏矩阵快速转置C语言算法徐光联摘要:三元组稀疏矩阵快速转置算法在《数据结构》课程中是一个难点,这里给出三元组稀疏矩阵转置算法详细讲解,并给出C语言算法的源程序。关键词:三元组;稀疏矩阵;...

    1-468-png_6_0_0_454_362_364_183_892.5_1212-918-0-28-918.jpg

    1-84-png_6_0_0_0_0_0_0_892.5_1212-204-0-501-204.jpg

    1-81-png_6_0_0_0_0_0_0_892.5_1212-171-0-590-171.jpg

    三元组稀疏矩阵快速转置C语言算法

    徐光联

    摘要:三元组稀疏矩阵的快速转置算法在《数据结构》课程中是一个难点,这里给出三元组稀疏矩阵的转置算法详细讲解,并给出C语言算法的源程序。

    关键词:三元组;稀疏矩阵;快速转置

    {int m,n,t;              /*  m 表示行数, n 表示列数,t 表示非零元素个数  */

    Mat  data[MAXSIZE];  /*  所存储元素的最大个数 */)Spmatrix;

    Spmatrix a,b;

    要假定结构中data域表示非零元素的三元组是以行为主顺序排列的。(算式1)表示了稀疏矩阵M和N中data域的排列情况。这种表示方法,在矩阵足够稀疏的情况下,对存储空间的需求量比通常的方法少得多。

    一、前 言

    三元组稀疏矩阵的快速转置算法在《数据结构》课程中是一个难点,处理这个知识点很费时间,在教学过程中,往往受课时限制,采取略过不讲的办法,有的教材就干脆把它省去不提。日常生产和科研过程中,数字计算中大量使用了矩阵,为了减少运算量,提高运算效率,这个算法很有用处。这里给出三元组稀疏矩阵的快速转置算法详细过程,并给出C语言描述的实例。

    矩阵转置定义为: m行n列矩阵M(m,n) 转换为n行m列N

    矩阵,即行列互换。例如:(n,m)

    如M(3,4)转置为N(4,3)。如图-1矩阵转置。

    二、数组的三元组表示与稀疏矩阵

    在实际应用中,往往会遇到一种大多数元素的值为零的矩阵,只有少部分为非零元素,这些非零元素在矩阵中的分布又没有一定的规律,我们把它记作“零元素个数>>非零元素个数”,即零元素个数远远大于非零元素个数。这种矩阵称为稀疏矩阵(sparse matrix)。例如,下面所示的矩阵M和它的转置矩阵N,在30个元素中只有8个非零元素,显然是个稀疏矩阵。如图-2,稀疏矩阵M转置成N的示意图。

    为了节省空间,可以

    进行压缩存储,只需存储稀疏矩阵的非零元素。但是,为了实现矩阵的各种运算,除了存储非零元素的值外,还必须同时记下它所在的行和列。可以用一个三元组(i, j, aij)唯一地确定矩阵中的一个非零元素,其中i, j分别表示非零元素的行号和列号,aij表示非零元素的值。

    下面就是(算式1)式中矩阵M的(5行6列共有)8个非零元素的三元组表示:

    { (1,1, 8), (1,3, 9) , (2,2,2) , (3,4,3) , (3,6,7), (4,1,6) , (4,3,4) , (5,4,5)}

    若以某种方式(以行为主或以列为主的顺序)将8个三元组排列起来,再加上一个表示矩阵M的行数,列数及非零元素的个数的特殊的三元组(5,6,8),则所形成的表就能唯一地确定稀疏矩阵。

    三元组表: 假设以顺序存储结构来表示三元组表(tripletable),则得到稀疏矩阵的一种压缩存储方式,即三元组顺序表,简称三元组表。其结构描述如下:

    typedef struct{int I,j;

    ElemType  v;}Mat;

    typedef  struct2008.No592

    1-55-jpg_6_0_______-743-0-0-743.jpg

    例如, 我们所说的5×6的矩阵M,若用三元组表来表示,在每个元素占一个存储单元的情况下,则只需要27个存储单元(包括特殊三元组所占的3个单元,可以使用数组[0]单元);若直接用二维数组,按通常办法表示,则需30个单元。矩阵越大,越稀疏,其优越性越明显。

    三、稀疏矩阵的转置算法。

    矩阵的转置运算是变换元素的位置,把位于(i,  j)的元素换到(j, i)位置上。也就是说,把元素的行和列对换。所以一个m×n的矩阵M,它的转置矩阵是一个n×m的矩阵,且N[i,j]=M[j,i],其中,1≤i≤n,1≤j≤m。例如, (算式1)中的矩阵N就是矩阵M的转置矩阵,矩阵N也是一个稀疏矩阵,其非零元素的排列情况如表-1(b)所示。求矩阵M的转置矩阵N,实际上就是由表-1(a)求表-1(b)。

    从表-1可以看出,对每个非零元素而言,从M转置到N,分两步,第一步,把a.data的第一列数和第二列数对换,得到的b'.data。因为b’.data是按非零元素在N中的列序排列的,又因为我们已约定,b.data中的非零元素应按照在矩阵N中的行序排列。第二步,将b’.data转换成按非零元素在矩阵N中的行序排列的b.data。转换方法如下:

    普通算法分析:按b.data中三元组的次序进行转置。也就是说,按照矩阵M的列序进行转置。显然,为了找到M中的每一列的所有的非零元素,需要对a.data从第1行起整个扫描一遍。由于a.data是以M的行序来存放每一个非零元素的,因此,这样得到的顺序恰好是b.data应有的顺序。其具体算法描述如下:

    #define  MaxSize 100#define  ElemType inttypedef struct{int i,j;ElemType v;}Mat;

    typedef struct

    展开全文
  • #include //栈的顺序存储 #include #include #include #define MAXSIZE 100 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define SElemType int #... printf("转置后的矩阵:\n"); output(&T); return 0; }

    在这里插入图片描述

    #include<stdio.h>          //栈的顺序存储 
    #include<string.h>
    #include<stdlib.h>
    #include<malloc.h>
    #define MAXSIZE   100
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define SElemType int
    #define OK 1
    #define ERROR 0
    #define  TRUE  1
    #define  FALSE 0
    #define  OK    1
    #define  ERROR 0
    #define  INFEASIBLE -1
    #define  OVERFLOW   -2
    #define  STACK_INIT_SIZE  100
    #define  STACKINCREMENT    10
    
    typedef  struct                 //定义三元组
    {
     int hang,lie;
     int zhi;
    }SAN;
    typedef struct
    {
     SAN data[MAXSIZE];
     int mu,nu,tu;
    }SANYUAN;
    void zhuanzhi(SANYUAN M,SANYUAN *T)      //对三元组进行转置
    {
        int col,p,q,t;     
        int num[MAXSIZE],cpot[MAXSIZE];
    
    
        T->mu=M.nu;T->nu=M.mu;T->tu=M.tu;
        if(T->tu)
       {
         for(col=1;col<=M.nu;++col) 
    	   num[col]=0;
         for(t=1;t<=M.tu;++t) 
    	   ++num[M.data[t].lie];     
     cpot[1]=1;
     for(col=2;col<=M.nu;++col)        
     cpot[col]=cpot[col-1]+num[col-1];
     for(p=1;p<=M.tu;++p)       
        { 
    	 col=M.data[p].lie;
         q=cpot[col];
        T->data[q].hang=M.data[p].lie; 
    	T->data[q].lie=M.data[p].hang;
        T->data[q].zhi=M.data[p].zhi;
        ++cpot[col];       
        }
      }
    }
    
    
    void output(SANYUAN *M)           //输出三元组
    {
      int i,j;
      int t=1;
      for(i=1;i<=M->mu;i++)
      {
        for(j=1;j<=M->nu;j++)
    	{
    		if(M->data[t].hang==i&&M->data[t].lie==j)
    		{
    			printf("%d   ",M->data[t].zhi);
    			t++;
    		}
            else printf("0   ");
    	}
        printf("\n");
      }  
    }
    int main()
    {
        SANYUAN  A,T;int k;
        printf("输入矩阵大小\n");
        printf("行:");scanf("%d",&A.mu);
        printf("列:");scanf("%d",&A.nu);
        printf("非零元素个数:");scanf("%d",&A.tu);
        printf("输入三元组表:\n");                       //顺序输入三元组
        for(k=1;k<=A.tu;k++)
    	{
          scanf("%d %d %d",&A.data[k].hang,&A.data[k].lie,&A.data[k].zhi);
        }
        printf("原矩阵\n");
        output(&A);
        zhuanzhi(A,&T);
        printf("转置后的矩阵:\n");
        output(&T);
        return 0;
    }
    
    展开全文
  • 稀疏矩阵快速转置 利用三元组顺序表存放的矩阵M,用快速转置的算法是实现转置得到矩阵T,并将T按照三元组形式输出,每行输出一个元素,注意:矩阵输出顺序按照行号升序输出。其中,行数<20、列数<20。 输入...

    稀疏矩阵快速转置 

    利用三元组顺序表存放的矩阵M,用快速转置的算法是实现转置得到矩阵T,并将T按照三元组形式输出,每行输出一个元素,注意:矩阵输出顺序按照行号升序输出。其中,行数<20、列数<20。

    输入格式:

    第一行输入M的行数mu,M的列数nu,M中非零元个数tu 从第二行开始输入tu行,每行输入一个元素的行号i、列号j和值data。

    输出格式:

    按照T的行号升序输出,每行输出一个元素的行号,列号,元素值,三个值以空格为分隔符

    输入样例:

    在这里给出一组输入。例如:

    3 4 3
    0 1 6
    1 0 -1
    2 2 4

    输出样例:

    在这里给出相应的输出。例如:

    0 1 -1
    1 0 6
    2 2 4

    代码如下: 

    #include<stdio.h>
    typedef int ElemType;
    #define MAXSIZE 12500
    typedef struct {
    	int i, j;       //该非零元的行下标和列下标
    	ElemType e;     //数据域
    }Triple;
    typedef struct {
    	Triple data[MAXSIZE]; //非零元三元组表,data[0]使用了
    	int mu, nu, tu;           //矩阵的行数,列数和非零元个数
    }TSMatrix;
    void GreateSMatrix(TSMatrix* M);
    void TransposeSMatrix(TSMatrix* M, TSMatrix* T);
    void PrintSMatrix(TSMatrix* T);
    int main() {
    	TSMatrix *M=(TSMatrix*)malloc(sizeof(TSMatrix));
    	TSMatrix *T=(TSMatrix*)malloc(sizeof(TSMatrix));
    	GreateSMatrix(M);
    	TransposeSMatrix(M, T);
    	PrintSMatrix(T);
    	return 0;
    }
    void GreateSMatrix(TSMatrix* M) //创建稀疏矩阵M
    {
    	scanf("%d %d %d", &M->mu,&M->nu,&M->tu);
    	if ((M->mu) > 0 &&(M->nu) > 0) {
    		if (M->tu < MAXSIZE)
    		{
    			for (int i = 0; i < M->tu; i++) {
    				scanf("%d %d %d", &M->data[i].i,&M->data[i].j,&M->data[i].e);
    			}
    		}
    	}
    }
    void TransposeSMatrix(TSMatrix* M, TSMatrix* T)//求稀疏矩阵M的转置矩阵T
    {
    	T->mu = M->nu, T->nu = M->mu, T->tu = M->tu;
    	if (T->tu) {
    		int q=0 , p,col;
    		for(col=0;col<M->nu;col++)
    			for(p=0;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;
    				}
    	}
    }
    void PrintSMatrix(TSMatrix* T) //输出矩阵
    {
    	for (int i = 0; i < T->tu; i++) {
    		printf("%d %d %d", T->data[i].i, T->data[i].j, T->data[i].e);
    		printf("\n");
    	}
    }
    

     

    展开全文
  • #######3稀疏矩阵快速转置........
  • 通过下列代码解释: 这么说吧,刚开始我也不是很理解。在经过一段时间研究后才枉然大悟。 1.首先说下,在以三元组表的形式存矩阵元素时。...3.而在快速转置的方法中 cpot【】保存的是正确的行序,所以可以直接行,

    通过下列代码解释:
    这么说吧,刚开始我也不是很理解。在经过一段时间研究后才枉然大悟。
    1.首先说下,在以三元组表的形式存矩阵元素时。如果是以行向量来存的话,在输入与输出时,同一行中的数据,列不一定按顺序来。但行必须从上到下。
    2.所以按照上面的规则,如果按一般思路,之所以不能直接行,列交换是因为直接交换后,行的顺序一般是乱的,在输出时就没有办法输出正确的矩阵。所以一般方法就得从第一列一直遍历到最后一列,每一列都要遍历全部来保证顺序。
    3.而在快速转置的方法中 cpot【】保存的是正确的行序,所以可以直接行,列值交换而不会破坏行序

    TSMatrix* TransTSMatrix_plus(TSMatrix* M)
    {
    	TSMatrix* T;
    	T = (TSMatrix*)malloc(sizeof(TSMatrix));
    	T->tu = M->tu;
    	T->mu = M->nu;
    	T->nu = M->mu;//这三部是矩阵的行,列值交换,不用多说了
    	int num[max] = {};//记住每一列中非零元素个数
    	int cpot[max] = {};//每一列第一个非零元素的正确位置
    	for (int p = 0; p < M->tu; p++)
    		++num[M->data[p].j];//巧妙求非零元素个数
    	for (int p = 1; p < M->tu; p++)
    		cpot[p] = cpot[p - 1] + num[p - 1];
    	for (int p = 0; p < M->tu; p++)
    	{
    		int col = M->data[p].j;
    		int q = cpot[col];
    		T->data[q].i = M->data[p].j;
    		T->data[q].j = M->data[p].i;
    		T->data[q].data = M->data[p].data;
    		++cpot[col];
    	}
    	return T;
    
    }
    
    展开全文
  • 文章目录主类辅助功能类(读入任意规格的矩阵)编写和调试心得 主类 /* * @Description: * @Version: 2.0 * @Author: xuchaoxin * @Date: 2021-03-09 19:27:00 * @LastEditors: xuchaoxin * @LastEditTime: 2021-03-...
  • 稀疏矩阵快速转置

    2019-04-29 15:10:47
    【问题描述】 稀疏矩阵的存储不宜用二维数组存储每个元素,那样的话会浪费很多的存储空间。所以可以使用一个一维数组存储其中的非零...请你实现一个快速的对稀疏矩阵进行转置的算法。 【输入形式】 输入的第一...
  • 稀疏矩阵快速转置算法分析

    千次阅读 2017-10-16 22:41:39
    稀疏矩阵的相关知识 矩阵通常是使用二维数组来进行模拟的,并且可以通过下标快速的访问二维数组里面的元素,但是矩阵里面包含大量重复元素的情况,使用二维数组就很浪费空间的; 对于含有大量重复元素的矩阵,就可以...
  • 南昌航空大学实验报告课程名称: 数据结构 实验名称: 实验五 稀疏矩阵的存储和快速转置 班 级: 学生姓名: 学号: 指导教师评定: 签 名:题目:假设稀疏矩阵A采用三元组表表示,编写程序实现该矩阵的快速转置 要求...
  • 三元组稀疏矩阵快速转置

    千次阅读 2018-05-29 11:52:02
    稀疏矩阵是只存储非零元的行值、列值、元素值 data[0]来存储矩阵的行数、列数、非零元个数 struct Position { int row; int col; int value; }; struct List { Position data[MAX + 1]; }; void Quick_...
  • 稀疏矩阵转置

    2013-01-31 22:46:29
    稀疏矩阵转置的程序及实验报告,数据结构作业。
  • 一个稀疏矩阵A的转置矩阵B,输入使用三元组输入,输出原三元组,原矩阵,转置后三元组,转置后矩阵
  • 稀疏矩阵转置算法

    2017-11-28 10:48:38
    在矩阵中,若数值为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为稀疏矩阵,并用三元组表存储。用C++ 扫描两遍三元组表实现稀疏矩阵转置
  • 稀疏矩阵头文件,宏定义,重命名创建矩阵销毁矩阵输出矩阵普通转置快速转置完整源码 头文件,宏定义,重命名 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR -1 #define OVERFLOW...
  • 稀疏矩阵转置

    2014-04-07 15:12:13
    稀疏矩阵转置: 输入稀疏矩阵中每个元素的行号、列号、值,建立稀疏矩阵的三元组存储结构,并将此矩阵转置,显示转置前后的三元组结构。
  • 稀疏矩阵的转置(矩阵转置快速转置)

    万次阅读 多人点赞 2018-06-23 19:43:52
    那么在对a.data中的三元组一次做转置时,便可直接放到b.data中恰当的位置上去。设两个向量:num和cpotnum[col]表示矩阵M中第col列中的非零元素个数。cpot[col]指M中第col列的第一个非零元在b.data中的恰当位置。有...
  • 本节给大家介绍一种实现矩阵转置更高效的算法,通常称为稀疏矩阵快速转置算法。我们知道,稀疏矩阵的转置需要经历以下 3 步:将矩阵的行数和列数互换;将三元组表(存储矩阵)中的 i 列和 j 列互换,实现矩阵的转置...
  • 实现了从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构(m、n分别表示矩阵行数和列数;i, j为非零元素行号和列号)和十字链表的转置并将转置后的三元组到另一字符文件中
  • 稀疏矩阵快速转置算法理解

    千次阅读 多人点赞 2016-10-02 17:46:16
    稀疏矩阵:绝大多数元素为零的矩阵。 稀疏矩阵的压缩储存:只储存稀疏矩阵中的非零元素,用三元式(row,col,value)唯一表示每...快速转置算法的基本步骤:1. 计算每列非零元素个数,存入num[ ]中;  2. 计算每列第
  • 三元组表压缩存储稀疏矩阵实现稀疏矩阵快速转置(Java语言描述)用经典矩阵转置算法和普通的三元组矩阵转置在时间复杂度上都是不乐观的。快速转置算法在增加适当存储空间后实现快速转置具体原理见代码注释部分,时间...
  • 说明:稀疏矩阵快速转置算法的核心在于,用一个数组num记录原来矩阵中的每列非零元个数,用另一个数组cpos来记录原矩阵每列第一个非零元在新矩阵中的位置,以此来达到快速转置的目的。用这样的方法,主要是希望,...
  • 稀疏矩阵转置算法

    千次阅读 2020-03-29 20:25:18
    数组一般分为一维、二维、三维数组,其中二维数组也称为矩阵,本文主要讲解对于矩阵中稀疏矩阵的相关操作算法。 稀疏矩阵 在矩阵中,当数值为0的元素远远多于非0元素的个数,且非0元素的分布并没有规...
  • } } void Tranverse(SMatrix matrix,SMatrix* tran_res) {//稀疏矩阵转置,一个M*N的稀疏矩阵转置为N*M的矩阵 int cnum[SIZE];//列非零元素的个数 int cpot[SIZE];//列的起始位置 int i,p; for(i=0;i;i++) { ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,974
精华内容 3,189
关键字:

稀疏矩阵快速转置