#include <stdio.h>

#include <stdlib.h>

#include <process.h>

#define MAXSIZE 200 /*矩阵中最大非零元的个数*/

typedef struct triple

{

int i /*行标,本程序中从1开始的*/

int j /*列标，本程序中从1开始的*/

int e /*非零元*/

}Triple/*三元组定义*/

typedef struct tabletype

{

int mu/*矩阵的行数*/

int nu /*列数*/

int tu /*非零元个数*/

Triple data[MAXSIZE] /*非零元的三元组表,本程序中是从data[1]开始使用的*/

}Tabletype /*三元组线性表*/

/*以下为函数声明，注意和书本上的参数类型不同，我用的形参全为指针*/

void CreatSMatrix(Tabletype *)/*生成矩阵*/

void DestroySMatrix(Tabletype *)/*销毁矩阵*/

void out_matrix(Tabletype *) /*打印 矩阵*/

int FastTransposeSMatrix(Tabletype *,Tabletype *)/*快速转置算法*/

int main( void ) /*主函数*/

{

char ch

Tabletype a = {0,0,0,{0,0,0}}/*初始化为0，便于输入数据时的无效检测*/

Tabletype b /*声明矩阵b*/

while(1)

{

printf(" @@@@@@@@@@@@@@本程序的功能是实现稀疏矩阵的快速转置@@@@@@@@@@@@@@@\n")

printf(" @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n")

CreatSMatrix(&a)

printf("The source Matrix:\n")

out_matrix(&a)

if(FastTransposeSMatrix(&a,&b)) /*若a不为零矩阵则转置a，存入b中*/

{ printf("After TransposeSMatrix: \n")

out_matrix(&b)

}

else

{

printf("The matrix is zeros:\n")

out_matrix(&a)

}

/*以下为程序控制*/

printf("Input 'q' to quit and 'c' run again:")

do{

if((ch = getchar()) == 'q' || ch == 'Q')

{

DestroySMatrix(&a)

DestroySMatrix(&b)

exit(0)

}

}while((ch!='C') &&(ch!='c'))

system("cls")

}

return 1

}

void CreatSMatrix(Tabletype *a)

{

int i

printf("请输入矩阵的行数、列数和非零元个数，用空格间隔:")

scanf("%d%d%d",&(a->mu),&(a->nu),&(a->tu))

for(i=1i<= a->tu)

{

printf("请输入矩阵中第%d个非零元（按行标、列标、值的顺序，空格间隔）:",i)

scanf("%d%d%d",&(a->data[i].i),&(a->data[i].j),&(a->data[i].e))

if(a->data[i].i <1 || a->data[i].i >a->mu || a->data[i].j <1 || a->data[i].j >a->nu) /*下标越界*/

{

printf("注意：下标越界输入数据无效!\n请重新输入:行标范围：1--%d,列标范围1--%d!!!\n",a->mu,a->nu)

continue

}

if( ((a->data[i].i) <(a->data[i-1].i)) ||

(((a->data[i].i) == (a->data[i-1].i)) &&((a->data[i].j) <= (a->data[i-1].j)))) /*非按行顺序输入*/

{

printf("注意：输入数据无效!\n请按照按行存储的顺序输入数据!!!\n")

continue

}

i++

}

}

void DestroySMatrix(Tabletype *a)

{ /* 销毁稀疏矩阵a*/

(*a).mu=0

(*a).nu=0

(*a).tu=0

}

void out_matrix(Tabletype *a) /* 打印矩阵*/

{

int i,j,k = 1

for(i = 1 i <= a->mui++)

{

for(j = 1j<= a->nuj++)

{ /*判断是否为非零元*/

if((a->data[k].i == i)&&(a->data[k].j == j))

{

printf("%4d",a->data[k].e)

k++

}

else

printf("%4d",0)

}

printf("\n")

}

}

int FastTransposeSMatrix(Tabletype *a,Tabletype *b)

{

int p,q,col

int *num

int *cpot

b->mu = a->nu/*原矩阵的行数为新矩阵的列数，原列数为新行数，非零元个数不变*/

b->nu = a->mu

b->tu = a->tu

num=(int *)malloc((b->nu+1)*sizeof(int)) /* 生成两个辅助数组*/

cpot=(int *)malloc((b->nu+1)*sizeof(int))

if(b->tu) /*若a不为零矩阵*/

{

for(col = 0col <a->nucol++) /*初始化矩阵a的每列中非零元的个数均为0*/

num[col] = 0

for(col = 0col <=a->tu col++)/*统计每列中非零元的个数*/

num[a->data[col].j]++

cpot[1] = 1 /*确定每列中第一个非零元的位置*/

for(col = 2col <= a->nucol++)

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

for(p = 1p <= a->tup++) /*p为a-data的下标*/

{

col = a->data[p].j/*交换元素*/

q = cpot[col]

b->data[q].i = a->data[p].j

b->data[q].j = a->data[p].i

b->data[q].e = a->data[p].e

q++

cpot[col]++

}

free(num) /*释放两个辅助数组*/

free(cpot)

return 1 /*转置成功*/

}

else /*a为零矩阵*/

return 0

#include<ctype.h>

#include<malloc.h>// malloc()等

#include<limits.h>// INT_MAX等

#include<stdio.h>// EOF(=^Z或F6),NULL

#include<stdlib.h>// atoi()

#include<io.h>// eof()

#include<math.h>// floor(),ceil(),abs()

#include<process.h>// exit()

#include<iostream.h>// cout,cin

// 函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行

typedef int Status// Status是函数的类型,其值是函数结果状态代码，如OK等

typedef int Boolean// Boolean是布尔类型,其值是TRUE或FALSE

typedef int ElemType

// c5-2.h 稀疏矩阵的三元组顺序表存储表示

#define MAXSIZE 100 // 非零元个数的最大值

struct Triple

{

int i,j// 行下标,列下标

ElemType e// 非零元素值

}

struct TSMatrix

{

Triple data[MAXSIZE+1]// 非零元三元组表,data[0]未用

int mu,nu,tu// 矩阵的行数、列数和非零元个数

}

// bo5-2.cpp 三元组稀疏矩阵的基本操作,包括算法5.1(9个)

Status CreateSMatrix(TSMatrix &M)

{ // 创建稀疏矩阵M

int i,m,n

ElemType e

Status k

printf("请输入矩阵的行数,列数,非零元素数：")

scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu)

M.data[0].i=0// 为以下比较顺序做准备

for(i=1i<=M.tui++)

{

do

{

printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值：",i,M.mu,M.nu)

scanf("%d,%d,%d",&m,&n,&e)

k=0

if(m<1||m>M.mu||n<1||n>M.nu) // 行或列超出范围

k=1

if(m<M.data[i-1].i||m==M.data[i-1].i&&n<=M.data[i-1].j) // 行或列的顺序有错

k=1

}while(k)

M.data[i].i=m

M.data[i].j=n

M.data[i].e=e

}

return OK

}

void DestroySMatrix(TSMatrix &M)

{ // 销毁稀疏矩阵M

M.mu=0

M.nu=0

M.tu=0

}

void PrintSMatrix(TSMatrix M)

{ // 输出稀疏矩阵M

int i

printf("%d行%d列%d个非零元素。\n",M.mu,M.nu,M.tu)

printf("行 列 元素值\n")

for(i=1i<=M.tui++)

printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e)

}

Status CopySMatrix(TSMatrix M,TSMatrix &T)

{ // 由稀疏矩阵M复制得到T

T=M

return OK

}

int comp(int c1,int c2) // 另加

{ // AddSMatrix函数要用到

int i

if(c1<c2)

i=1

else if(c1==c2)

i=0

else

i=-1

return i

}

Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)

{ // 求稀疏矩阵的和Q=M+N

Triple *Mp,*Me,*Np,*Ne,*Qh,*Qe

if(M.mu!=N.mu)

return ERROR

if(M.nu!=N.nu)

return ERROR

Q.mu=M.mu

Q.nu=M.nu

Mp=&M.data[1]// Mp的初值指向矩阵M的非零元素首地址

Np=&N.data[1]// Np的初值指向矩阵N的非零元素首地址

Me=&M.data[M.tu]// Me指向矩阵M的非零元素尾地址

Ne=&N.data[N.tu]// Ne指向矩阵N的非零元素尾地址

Qh=Qe=Q.data// Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址

while(Mp<=Me&&Np<=Ne)

{

Qe++

switch(comp(Mp->i,Np->i))

{

case 1: *Qe=*Mp

Mp++

break

case 0: switch(comp(Mp->j,Np->j)) // M、N矩阵当前非零元素的行相等,继续比较列

{

case 1: *Qe=*Mp

Mp++

break

case 0: *Qe=*Mp

Qe->e+=Np->e

if(!Qe->e) // 元素值为0，不存入压缩矩阵

Qe--

Mp++

Np++

break

case -1: *Qe=*Np

Np++

}

break

case -1: *Qe=*Np

Np++

}

}

if(Mp>Me) // 矩阵M的元素全部处理完毕

while(Np<=Ne)

{

Qe++

*Qe=*Np

Np++

}

if(Np>Ne) // 矩阵N的元素全部处理完毕

while(Mp<=Me)

{

Qe++

*Qe=*Mp

Mp++

}

Q.tu=Qe-Qh// 矩阵Q的非零元素个数

return OK

}

Status SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)

{ // 求稀疏矩阵的差Q=M-N

int i

for(i=1i<=N.tui++)

N.data[i].e*=-1

AddSMatrix(M,N,Q)

return OK

}

Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)

{ // 求稀疏矩阵的乘积Q=M*N

int i,j,h=M.mu,l=N.nu,Qn=0

// h,l分别为矩阵Q的行、列值,Qn为矩阵Q的非零元素个数，初值为0

ElemType *Qe

if(M.nu!=N.mu)

return ERROR

Q.mu=M.mu

Q.nu=N.nu

Qe=(ElemType *)malloc(h*l*sizeof(ElemType))// Qe为矩阵Q的临时数组

// 矩阵Q的第i行j列的元素值存于*(Qe+(i-1)*l+j-1)中，初值为0

for(i=0i<h*li++)

*(Qe+i)=0// 赋初值0

for(i=1i<=M.tui++) // 矩阵元素相乘，结果累加到Qe

for(j=1j<=N.tuj++)

if(M.data[i].j==N.data[j].i)

*(Qe+(M.data[i].i-1)*l+N.data[j].j-1)+=M.data[i].e*N.data[j].e

for(i=1i<=M.mui++)

for(j=1j<=N.nuj++)

if(*(Qe+(i-1)*l+j-1)!=0)

{

Qn++

Q.data[Qn].e=*(Qe+(i-1)*l+j-1)

Q.data[Qn].i=i

Q.data[Qn].j=j

}

free(Qe)

Q.tu=Qn

return OK

}

Status TransposeSMatrix(TSMatrix M,TSMatrix &T)

{ // 求稀疏矩阵M的转置矩阵T。算法5.1

int p,q,col

T.mu=M.nu

T.nu=M.mu

T.tu=M.tu

if(T.tu)

{

q=1

for(col=1col<=M.nu++col)

for(p=1p<=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

}

}

return OK

}

Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)

{ // 快速求稀疏矩阵M的转置矩阵T。算法5.2

int p,q,t,col,*num,*cpot

num=(int *)malloc((M.nu+1)*sizeof(int))// 生成数组（[0]不用）

cpot=(int *)malloc((M.nu+1)*sizeof(int))// 生成数组（[0]不用）

T.mu=M.nu

T.nu=M.mu

T.tu=M.tu

if(T.tu)

{

for(col=1col<=M.nu++col)

num[col]=0// 设初值

for(t=1t<=M.tu++t) // 求M中每一列含非零元素个数

++num[M.data[t].j]

cpot[1]=1

for(col=2col<=M.nu++col) // 求第col列中第一个非零元在T.data中的序号

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

for(p=1p<=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]

}

}

free(num)

free(cpot)

return OK

}

void main()

{

TSMatrix A,B

printf("创建矩阵A: ")

CreateSMatrix(A)

PrintSMatrix(A)

FastTransposeSMatrix(A,B)

printf("矩阵B(A的快速转置): ")

PrintSMatrix(B)

DestroySMatrix(A)

DestroySMatrix(B)

}

稀疏矩阵三元组转置，你参考下