内容:

        编写程序用三元组表示稀疏矩阵的案列转置操作。本设计使用三元组表来实现。

算法分析

        本题要完成的是三元组表实现稀疏矩阵按列转置操作。首先就是要设立三个函数。函数InitSPNode()用来建立一个稀疏矩阵的三元组表，就是要输入行数、列数和非零元的值，最后要用（-1，-1，-1）来结束输入；第二函数showMatrix()用来输出稀疏矩阵，算法中按矩阵a的列进行循环处理，对a的每一列扫描三元组，找出相应的元素，若找到了，则交换其行号与列号，并存储到矩阵b的三元组中。最后用函数TransposeSMatrix()用来完成稀疏矩阵的转置算法。算法主要的工作是在配合col的两重循环中完成，时间复杂度为（n*t）。如果非零元素个数t和m*n同数量级，则算法的时间复杂度变为O（m*n²）

概要设计

用三元组表实现系数矩阵的基本操作

程序运行流程图如下：

#include<stdio.h>
#include<string.h>
#define Ok 1
#define MAX 10//用户自定义三元组表最大长度
typedef struct//定义三元组表
{
	int i, j;//行，列
	int v;//非0数组中的值
}SPNode;
typedef struct//定义三元组表
{
	int m;//矩阵行
	int n;//矩阵列
	int t;//矩阵中的非零元素（三元组表的长度）
	SPNode date[MAX];
}SPMatrix;
void InitSPMatrix(SPMatrix* a)//输入三元列表
{
	int i, j, k, val, maxrow, maxcol;
	maxrow = 0;
	maxcol = 0;
	i = j = 0;
	k = 0;
	while (i != -1 && j != -1)//rol=-1&&col=-1结束输入
	{
		printf("输入（行 列 值）");
		scanf_s("%d,%d,%d", &i, &j, &val);
		a->date[k].i = i;
		a->date[k].j = j;
		a->date[k].v = val;
		if (maxrow < i) maxrow = i;//获得最大的列和行，以便于得到矩阵的列和行
		if (maxcol < j) maxcol = j;
		k++;
	}
	a->m = maxrow;
	a->n = maxcol;
	a->t = k-1;//矩阵中非零元素的数
}
void showMatrix(SPMatrix *a)
{
	int p, q;
	int t = 0;
	for (p = 0; p <= a->m; p++)//这个是行循环，p代表p+1行
	{
		for (q = 0; q <= a->n; q++)//这个是列循环，q代表q+1列
		{
			if (a->date[t].i== p && a->date[t].j == q)//遍历循环输出有v的元素
			{
					printf("%d", a->date[t].v);
					t++;
			}
			else printf("0");//if不成立说明该位置没有输入元素，则输出0
		}
		printf("\n");//一行结束以后进行换行处理
	}
}
void TransposeSMatrix(SPMatrix* a, SPMatrix* b)
{
	int q, col, p;
	b->m = a->n;//行列转换
	b->n = a->m;
	b->t = a->t;
	if (b->t)
	{
		q = 0;
		for(col=0;col<=a->n;++col)//遍历整个矩阵进行置换
			for(p=0;p<a->t;++p)
				if (a->date[p].j == col)
				{
					b->date[q].i = a->date[p].j;
					b->date[q].j = a->date[p].i;
					b->date[q].v = a->date[p].v;
					++q;
				}
	}
}
void main()
{
	SPMatrix a, b;
	printf("\n结束请输入（-1，-1，-1）\n");
	InitSPMatrix(&a);
	printf("输入矩阵为：\n");
	showMatrix(&a);
	TransposeSMatrix(&a, &b);
	printf("输出矩阵为：\n");
	showMatrix(&b);//转置后
}