数据结构实验题目：

稀疏矩阵A、B均采用三元组顺序表表示，验证实现矩阵A快速转置算法，并设计、验证矩阵A、B相加得到矩阵C的算法。

(1)从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。
(2) 设计算法将随机生成的稀疏矩阵转换成三元组顺序表形式存储。
(3) 设计算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。
(4) 输出随机生成的稀疏矩阵A、B及其三元组顺序表、快速转置得到的与相加得到的三元组顺序表及其矩阵形式。

  1. 从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。（老师要求不能用二维数组去贮存矩阵）
    也就是说直接生成三元组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    //动态随机生成三元组
    TSMatrix Romand(int m,int n){
    	TSMatrix M;
    	int t=1;
    	int num[100]={0};//记录数组位置是否是非0元
    	M.mu=m;
        M.nu=n;
        M.tu=(int)(m*n*factor)+1;//factor为稀疏因子
    	srand((unsigned)time(0));
    	while(t!=M.tu+1){
    		M.data[t].i = rand() % m+1;
    		M.data[t].j = rand() % n+1;
    		if(num[(M.data[t].i-1)*n+M.data[t].j] == 0){//如果该位置没有数据，属于0元
    			M.data[t].v = rand() % 10+1;
    			t++;
    			num[(M.data[t].i-1)*n+M.data[t].j] = 1;
    		}  
    	}
    	//对三元组排序
    	for(int i=1;i<=M.tu;i++){
    		for(int j = i+1;j<=M.tu;j++){
    			if((M.data[i].i > M.data[j].i)||(M.data[i].i == M.data[j].i&&M.data[i].j > M.data[j].j)){
    				Triple a;
    				a = M.data[i];
    				M.data[i] = M.data[j] ;
    				M.data[j] = a;
    			}
    		}
    	} 
    	return M;
    }

  2. 算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。
    这一步呢我们就按照矩阵形式输出就行了，不用实际转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//打印矩阵 
void printMatrix(TSMatrix M,int m,int n){
	int t=1,k=0;
	for(int i= 1; i<=m;i++){
		for(int j=1; j<=n;j++){
			if(M.data[t].i == i&&M.data[t].j == j){
				printf("%d\t", M.data[t].v );
				t++;
			}else{
				printf("0\t"); 
			}
		}
		printf("\n"); 
	}
}

3.快速转置算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/快速转置
void fastTSMatrix(TSMatrix M,TSMatrix *T){
	//初始化T（行数、列数、元素个数）
	int q,p,col;
	int num[100];
	int cpot[100];
	T->mu=M.nu;
	T->nu=M.mu;
	T->tu=M.tu; 
	if(T->tu>0){
		for(col=1;col<=M.nu;col++) num[col]=0;//初始化求num[] 为0 
			for(p=1;p<=M.tu;p++)	num[M.data[p].j]++;//求每一列的num[]，即求出每一列的有值元素的个数 
		//求cpot[]
		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].j;
			q=cpot[col];
			T->data[q].i=M.data[p].j;
			T->data[q].j=M.data[p].i;
			T->data[q].v=M.data[p].v;
			cpot[col]++;//把当前一列元素的位置后移一个单位 
		}
	}
}

4.三元组相加
三元组相加是行与列相同既相加，不同则就不用相加，自己把其赋值给新数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
int cmp(Triple c1,Triple c2){
	if(c1.i==c2.i){
		if(c1.j==c2.j){//位置相同 
			return 0;
		} 
		else if(c1.j<c2.j){
				return -1;//A在B的前 
			}	
			 else{
			 	return 1;//B在A的前
			 }
	}
	else if(c1.i<c2.i){
			return -1;//A在B的前 
		} 
		else{
			return 1;//B在A的前
		} 		
}
//三元组相加 
int addTSMatrix(TSMatrix A,TSMatrix B,TSMatrix *C){
	int i,j;
	int p=1,q=1;
	C->tu=1;
	while((p<=A.tu)&&(q<=B.tu)){
		if(cmp(A.data[p],B.data[q])==-1){//A在B的前 
			C->data[C->tu].i=A.data[p].i;
			C->data[C->tu].j=A.data[p].j;
			C->data[C->tu++].v=A.data[p].v;
			p++;
		}
		if(cmp(A.data[p],B.data[q])==1){//B在A的前 
				C->data[C->tu].i=B.data[q].i;//
				C->data[C->tu].j=B.data[q].j;//
				C->data[C->tu++].v=B.data[q].v;
				q++;
		}
		if(cmp(A.data[p],B.data[q])==0){//i，j 相同 
			if(A.data[p].v+B.data[q].v != 0){
				C->data[C->tu].i=A.data[p].i;
				C->data[C->tu].j=A.data[p].j;
				C->data[C->tu++].v=A.data[p].v+B.data[q].v;
			}
			p++;
			q++;
		} 
	}
	//将剩下的三元组的合并 
	C->mu=A.mu;
	C->nu=A.nu;
	while((p<=A.tu)){
		C->data[C->tu].i=A.data[p].i;
		C->data[C->tu].j=A.data[p].j;
		C->data[C->tu++].v=A.data[p].v;
		p++;
		C->mu=A.mu;
		C->nu=A.nu;
	} 
	while((q<=B.tu)){
		C->data[C->tu].i=B.data[q].i;
		C->data[C->tu].j=B.data[q].j;
		C->data[C->tu++].v=B.data[q].v;
		q++;
		C->mu=B.mu;
		C->nu=B.nu;
	}
	C->tu--;
	return 0;
}

5.三元组的数据结构：

1
2
3
4
5
6
7
8
9
10
11
#define maxsize 1250
typedef struct{
    int i;//元素的行下标 
    int j;//元素的列下标 
    int v;//元素的值 
}Triple;
//定义三元组
typedef struct{
    Triple  data[maxsize+1];  // data[0]未用
    int  mu,nu,tu;//元素的总行数，总列数，不为0元素个数 
}TSMatrix;

6.测试结果：
请输入A矩阵的行数，列数
2
2
A矩阵为：
0 5
0 0
三元组顺序表形式A为：
1 2 5
请输入B矩阵的行数，列数
2
2
B矩阵为：
0 0
0 5
三元组顺序表形式B为：
2 2 5
转置后的TA:
2 1 5
转置后的TA的矩阵形式:
0 0
5 0
A+B矩阵三元组表示:
1 2 5
2 1 5
TC的矩阵形式：
0 5
5 0