土方法快速转置.cpp

稀疏矩阵快速转置 数据结构初学者可以参考使用

// 土方法快速转置.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <malloc.h>
#include <string.h>

#define MAXSIZE 12500
#define OK 0

using namespace std;

typedef struct
{
	int i,j;
	int e;
}Triple;

typedef struct
{
	Triple data[MAXSIZE+1];
    int mu,nu,tu;
}TSMatrix;

int Input(TSMatrix &M)                //输入稀疏矩阵
{
	int i;
	cout  <<"input mu nu tu"<<endl;
	cin  >>M.mu>>M.nu>>M.tu;
	for(i=1;i<=M.tu;i++)
	{
		cout<<"input the contents"<<endl;
		cin>>M.data[i].i>>M.data[i].j>>M.data[i].e;
	}
	return OK;
}

int  FastTransposeSMatrix(TSMatrix M, TSMatrix &T) {  // 算法5.2
  // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T
  int col, t, p, q;
  int num[20], cpot[20];
  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) // 求 M 中每一列所含非零元的个数
       ++num[M.data[t].j];
    cpot[1] = 1;         
    // 求 M 中每一列的第一个非零元在 b.data 中的序号
	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].j;   q = cpot[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;  ++cpot[col]; 
    } // for
  } // if
  return OK;
} // FastTransposeSMatrix

int PrintSmatrix(TSMatrix &T)     //打印稀疏矩阵
{
	int i;
	cout<<"the result is:"<<endl;
	for(i=1;i<=T.tu;i++)
	{
		cout<<T.data[i].i<<" "<<T.data[i].j<<" "<<T.data[i].e<<endl;
	}
	return OK;
}

int _tmain(int argc, _TCHAR* argv[])
{
    TSMatrix M;
    TSMatrix T;
    Input(M);
    FastTransposeSMatrix(M,T);
	PrintSmatrix(T);
	return 0;
}