数据结构：压缩矩阵的转置（压缩矩阵的2种转置运算）

落日映苍穹つ 2022-12-22 04:53 166阅读 0赞

## 实验6、压缩矩阵的2种转置运算 ##

**（1）实验目的**  
通过该实验，让学生理解矩阵压缩存储的概念、方法等相关知识，掌握用三元组表的方式如何进行矩阵的压缩存储，并在此基础上进行转置操作，理解转置和快速转置两种矩阵转置算法的思想。  
**（2）实验内容**  
用三元组表压缩存储矩阵，实现创建矩阵、显示以及教材中介绍的两种转置算法。  
**（3）参考界面**  
1.创建矩阵  
2.销毁矩阵  
3.输出矩阵  
4.转置矩阵  
5.快速转置矩阵  
*具体要求*：请认真查看测试用例  
**（4）验收/测试用例**

*  **创建矩阵：**

*注意*：检查非零元素个数是否小于等于行数乘列数；检查是否能拦截元素下标重复输入；检查是否能控制输入的非零元素的下标是递增的（即按照行序输入，先输入小的下标，再输入较大的下标）。  
*注意*：输入的过程中如果有一个输入错了，不要让用户从头再把所有的输入一次，只需把刚才输入错误的，重新输入正确即可。

1.  输入：4（行数） 4（列数） 25（非零元个数），会提示：输入错误，非零元素个数要小于等于行数乘列数，请从新输入。
2.  输入：4（行数） 4（列数） 5（非零元个数）
3.  先输入：（1,1,1） （2,3,2）
4.  再输入（2,3,6），会提示：输入错误，输入的下标重复，请重新输入！
5.  再输入（1,1,6），会提示：输入错误，输入的下标重复，请重新输入！
6.  继续输入（3,1,3） （3,4,5）
7.  再输入（3,2,9），会提示：输入错误，下标输入时要递增输入，请重新输入！
8.  再输入（2,3,8），会提示：输入错误，下标输入时要递增输入，请重新输入！
9.  最后输入（4,2,4）

*  **显示：**

屏幕上输出

>     1  0  0  0
>              0  0  2  0
>              3  0  0  5
>              0  4  0  0

*  **转置：**  
    屏幕上输出

>     1  0  3  0
>              0  0  0  4
>              0  2  0  0
>              0  0  5  0

**效果图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70_pic_center]

## 代码 ##

#include <stdio.h>
    #include <stdlib.h>
    
    #define OK 1
    #define ERROR -1
    #define OVERFLOW -2
    //--------------压缩矩阵的顺序存储表示-------------
    typedef int status;     //status是函数的类型，其值是函数结果状态代码。
    typedef int Elem;       //自定
    
    #define MAXSIZE 100 //非零元个数的最大值为100
    
    typedef struct { 
    	/*定义矩阵中一个非零元素的结构 i为行下标，j为列下标，e为该元素的值 */
    	int i,j;
    	Elem e;	
    }Triple; 
    
    typedef struct { 
    	/*定义整个矩阵的结构 data为压缩矩阵，data[0]未被使用 mu为行数，nu为列数，tu为非零元个数 */
    	Triple data[MAXSIZE+1];
    	int mu,nu,tu;
    }TMatrix; 
    
    //---------------基本操作的函数原型说明------------ 
    status CreateTMatrix(TMatrix &M);
           //创建矩阵 
    status DestoryTMatrix(TMatrix &M);       
           //销毁矩阵 
    status PrintTMatrix(TMatrix M);       
           //输出矩阵 
    status TransposeTMatrix(TMatrix M,TMatrix &T);
           //转置矩阵 
    status FastTransposeTMatrix(TMatrix M,TMatrix &T);
           //快速转置矩阵 
    //---------------主函数---------------------------- 
    int main() { 
    	//初始化 
    	int i = 0;
    	TMatrix M ;
    	TMatrix T ;
    	
    	int choice;
    	while (1){ 
    		//菜单
    		printf("\t\t\t 1---创建矩阵\n");
    		printf("\t\t\t 2---销毁矩阵\n");
    		printf("\t\t\t 3---输出矩阵\n");
    		printf("\t\t\t 4---转置矩阵\n");
    		printf("\t\t\t 5---快速转置矩阵\n");	
    		printf("\t\t\t 退出，输入一个负数！");
    		printf("\n");
    		printf("\t\t----------------------------------------------\n");
    		printf("\n");
    		printf("请输入你需要的操作：\n");
    		//退出
    		scanf("%d",&choice);
    		if(choice<=0){ 
    			printf("已退出\n");
    			return 0;
    		} 
    		switch (choice){ 
    			case 1:
    				i = CreateTMatrix(M);
    				if(i == 1){ 
    					printf("创建成功\n");
    				}
    				break;
    			case 2:
    				i = DestoryTMatrix(M);
    				if(i == 1){ 
    					printf("销毁成功\n");
    				}
    				break;
    			case 3:
    				i = PrintTMatrix(M);				
    			 	break;
    			case 4:
    				printf("转置前\n");
    				i = PrintTMatrix(M);	
    				i = TransposeTMatrix(M,T);
    				printf("转置后\n");
    				i = PrintTMatrix(T);				
    			 	break;
    			case 5:
    				printf("转置前\n");
    				i = PrintTMatrix(M);
    				i = FastTransposeTMatrix(M,T);
    				printf("快速转置后\n");
    				i = PrintTMatrix(T);
    			 	break;
    			default:
    				printf("选择失败！请重新选择！\n");
    				break; 	 	 	 			
    		}
    		system("pause");   //请按任意键结束 
    		system("cls");     //清屏 
    	}
    	return 0;
    }
    //---------------基本操作的算法描述----------------
    status CreateTMatrix(TMatrix &M){ 
    	//创建矩阵 
    	M.data[0].i = M.data[0].j = 0;//方便比较 
    	int num = 1;
    
    	while(1){ 
    		//检查非零元素个数是否小于等于行数乘列数；
    		printf("请输入矩阵的行数，列数和非零元个数:");
    		scanf("%d%d%d",&M.mu,&M.nu,&M.tu);
    		if(M.nu*M.mu < M.tu){ 
    		    printf("输入错误，非零元素个数要小于等于行数乘列数，请从新输入。\n");
    		    continue;
    		}else{ 
    			break;
    		}
    	}
    	//输入数据 
    	while(num <= M.tu){ 
    		printf("请输入第%d个元素的行下标，列下标和元素值（按行序输入，且下标递增）：",num);
    		scanf("%d%d%d",&M.data[num].i,&M.data[num].j,&M.data[num].e);	
    		if(M.data[num].i < M.data[num-1].i){ 
    			//行下标递减,报错 
    			printf("该元素行下标输入错误，请重新输入\n");
    		}else if(M.data[num].i == M.data[num-1].i){ 
    			//行下标相等,则列下标不可小于或等于上一个元素的列下标 
    			if(M.data[num].j <= M.data[num-1].j || M.data[num].j > M.nu){ 
    				//列下标递减或重复,或者列下标超出列数范围，都报错 
    				printf("该元素列下标输入错误，请重新输入\n"); 
    			}else{ 
    				//列下标递增,输入成功 
    				num++; 
    			}
    		}else if(M.data[num].i > M.mu){ 
    			//行下标超出行数范围
    			printf("该元素行下标输入错误，请重新输入\n"); 
    		}else{ 
    			//行下标递增，则只需控制列下标不超纲即可 
    			if(M.data[num].j >=1 && M.data[num].j <=M.nu){ 
    				//输入成功 
    				num++;	
    			}else{ 
    				printf("该元素列下标输入错误，请重新输入\n"); 
    			} 
    		} 
    	}
    	return OK;
    }
    
    status DestoryTMatrix(TMatrix &M){ 
    	//销毁矩阵 
    	M.mu = 0;
    	M.nu = 0;
    	M.tu = 0;
    	return OK;
    }      
      
    status PrintTMatrix(TMatrix M){ 
    	//输出矩阵 
    	int num = 1;
    	for(int col = 1;col <= M.mu;col++){ 
    		for(int rol = 1;rol <= M.nu;rol++){ 
    			if(col == M.data[num].i && rol == M.data[num].j){ 
    				//输出数据 
    				printf("%d",M.data[num].e);
    				num++;				
    			}else{ 
    				printf("0");
    			}
    			printf("\t");
    			if(rol == M.nu){ 
    				//一列输出后换行 
    				printf("\n");
    			}
    		}
    	} 
    }       
             
    status TransposeTMatrix(TMatrix M,TMatrix &T){ 
    	//转置矩阵
    	int num = 1;	
    	T.mu = M.nu;
    	T.nu = M.mu;
    	T.tu = M.tu;
    	if(T.tu){ 
    		for(int col = 1;col <= M.nu; col++){ 
    			//每行 
    			for(int sum = 1;sum <= M.tu;sum++){ 
    				//遍历所有的数据 
    				if(M.data[sum].j == col){ 
    					T.data[num].i = M.data[sum].j;
    					T.data[num].j = M.data[sum].i;
    					T.data[num].e = M.data[sum].e; 
    					num++;
    				}
    			}
    		}
    	}
    	return OK;
    }
           
    status FastTransposeTMatrix(TMatrix M,TMatrix &T){ 
    	//快速转置矩阵
    	T.mu = M.nu;
    	T.nu = M.mu;
    	T.tu = M.tu;
    	int q = 0;
    	int col = 0;
    	int num[MAXSIZE + 1];
    	int cpot[MAXSIZE + 1];
    	for(int col = 1;col <= M.mu; col++){ 
    		//清空num 
    		num[col] = 0;
    	}
    	for(int t = 1;t <= M.tu; t++){ 
    		//求M中每一列含非零元个数
    		 num[M.data[t].j]++;
    	}
    	cpot[1] = 1;
    	for(int col = 2;col <= M.nu; col++){ 
    		//求第col列中第一个非零元在T.data中的序号 
    		cpot[col] = cpot[col - 1] + num[col - 1];
    	}
    	for(int 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]++;
    	}
    	return OK;
    }

**号外**  
在检验创建矩阵中的输入时，我发现了一个本实验要求中没有提及的一种更加极端的情况：输入的数据过靠后，导致后面的数据没有位置存储。就是说假设输入一个4行4列4个元素的矩阵时，若第3个数据输入的时候为（4,4，\*），则最后一个数据将无法输入(极端情况)。我想到的想法便是在输入后再加一段判断，控制每一个输入的数据都可以使后面的数据有位置输入，当然这种情况的判断还需考虑所输入矩阵的列数，故没有在代码中实现，默认不会出现这种情况。  
有兴趣的可以去实现以下，也不难，奈何博主太懒  
╮(╯▽╰)╭

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6c1575d52199460888495543f20762f4.png