求稀疏矩阵快速转置算法及代码

typedef struct

{ int row /* 行下标 */

int col/* 列下标 */

elemtype value /* 元素值 */

}Triple

typedef struct

{ int rn /* 行数 */

int cn /* 列数 */

int tn /*非0元素个数 */

Triple data[MAX_SIZE]

}TMatrix

快速转置的算法

算法思想：直接按照稀疏矩阵A的三元组表a.data的次序依次顺序转换，并将转换后的三元组放置于三元组表b.data的恰当位置。

前提：若能预先确定原矩阵A中每一列的(即B中每一行)第一个非0元素在b.data中应有的位置，则在作转置时就可直接放在b.data中恰当的位置。因此，应先求得A中每一列的非0元素个数。

附设两个辅助向量num[ ]和cpot[ ] 。

◆ num[col]：统计A中第col列中非0元素的个数；

◆ cpot[col] ：指示A中第一个非0元素在b.data中的恰当位置。

显然有位置对应关系：

cpot[1]=1

cpot[col]=cpot[col-1]+num[col-1] 2≦col≦a.cn

快速转置算法如下：

void FastTransMatrix(TMatrix a, TMatrix b)

{int p , q , col , k

int num[MAX_SIZE] , copt[MAX_SIZE]

b.rn=a.cn b.cn=a.rn b.tn=a.tn

/* 置三元组表b.data的行、列数和非0元素个数 */

if (b.tn==0)printf(“ The Matrix A=0\n” )

else

{ for (col=1 col<=a.cn ++col)num[col]=0

/* 向量num[]初始化为0 */

for (k=1 k<=a.tn ++k)

++num[ a.data[k].col]

/* 求原矩阵中每一列非0元素个数 */

for (cpot[0]=1, col=2 col<=a.cn ++col)

cpot[col]=cpot[col-1]+num[col-1]

/* 求第col列中第一个非0元在b.data中的序号 */

for (p=1 p<=a.tn ++p)

{ col=a.data[p].col q=cpot[col]

b.data[q].row=a.data[p].col

b.data[q].col=a.data[p].row

b.data[q].value=a.data[p].value

++cpot[col] /*至关重要!!当本列中 */

}

}

}

你的程序语言没有错，但是逻辑错了。修改如下

#include"stdio.h"

int main()

{

void swap(int a[3][3],int i,int j)

int i,q,w

int s[3][3]

i=1

for(q=0q<3q++)

{

for(w=0w<3w++)

{s[q][w]=i

i++

printf("%d ",s[q][w])

}

printf("\n")

}

for(q=0q<3q++)

{

for(w=0w<qw++)// 这里不应该是所有列都进行元素交换，到对角线元素就停止，你原来的写法把所有元素交换等于没交换。修改这里你的程序就对了。

swap(s,q,w)

}

for(q=0q<3q++)

{

for(w=0w<3w++)

printf("%d ",s[q][w])

printf("\n")

}

return 0

}

void swap(int a[3][3],int i,int j)

{

int t

t=a[i][j]a[i][j]=a[j][i]a[j][i]=t

}

#include <stdio.h>

#define M 2

#define N 3

void TransMatrix(int source[M][N],int dest[N][M])

{

int i,j

for(i=0i<Mi++)

for(j=0j<Nj++)

dest[j][i]=source[i][j]

}

void main()

{

int i,j

int a[2][3]={1,2,3,4,5,6}

int b[3][2]

printf("orignal array:\n")

for(i=0i<2i++)

{

for(j=0j<3j++)

printf("%d ",a[i][j])

printf("\n")

}

TransMatrix(a,b) /*执行转置*/

printf("convert array:\n")

for(i=0i<3i++)

{

for(j=0j<2j++)

printf("%d ",b[i][j])

printf("\n")

}

}

（1）数组大小定义要用常量

（2）函数定义的时候，参数dest没有定义类型

（3）main函数要有返回值，没返回值就打void

（4）最后输出的应该是b数组

---