数据结构实验——压缩矩阵的转置-创新互联

Spraing※boy该实验中的难点是创建矩阵时，按照行序递增的输入顺序的控制，以及矩阵的快速转置，重点是掌握矩阵转置的算法。在做这次实验中，我也参照了很多代码，根据自己的理解和补充，我在代码部分加了很多的注释，希望各位学习的友友们可以借鉴学习❀❀。

创新互联，为您提供重庆网站建设公司、成都网站制作、网站营销推广、网站开发设计，对服务成都户外休闲椅等多个行业拥有丰富的网站建设及推广经验。创新互联网站建设公司成立于2013年,提供专业网站制作报价服务,我们深知市场的竞争激烈，认真对待每位客户，为客户提供赏心悦目的作品。 与客户共同发展进步，是我们永远的责任！

实验题目：

用三元组表压缩存储矩阵，实现创建矩阵、显示以及两种转置算法。

（1）参考界面：

1.创建矩阵

2.销毁矩阵

3.输出矩阵

4.转置矩阵

5.快速转置矩阵

（2）验收/测试用例

1. 创建矩阵：

注意：检查非零元素个数是否小于等于行数乘列数；检查是否能拦截元素下标重复输入；检查是否能控制输入的非零元素的下标是递增的（即按照行序输入，先输入小的下标，再输入较大的下标）。

注意：输入的过程中如果有一个输入错了，不要让用户从头再把所有的输入一次，只需把刚才输入错误的，重新输入正确即可。

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. 显示

屏幕上输出

  1  0  0  0

  0  0  2  0

  3  0  0  5

  0  4  0  0

1. 转置

屏幕上输出

  1  0  3  0

  0  0  0  4

  0  2  0  0

  0  0  5  0

#define MAXSIZE 12500 //假设非零元个数大值为12500 
typedef struct {
 	int i, j;         //非零元的行下标和列下标
 	ElemType e;
 } Triple; 
 
 typedef struct {
 	Triple data[MAXSIZE+1];  /非零元三元组表，data[0]未使用
	int rows, cols, numbers; //矩阵的行数、列数、非零元个数 
 } TSMatrix;

代码实现：

#includeusing namespace std;

#define MAXSIZE 12500 //表示非零元个数大值 
typedef int ElemType; //存储元素的数据类型
bool isInit = false; //矩阵是否已经被创建的标记 
 
//三元组定义区
 typedef struct {
 	int i, j;
 	ElemType e;
 } Triple; 
 
 typedef struct {
 	Triple data[MAXSIZE+1];
	int rows, cols, numbers; //矩阵的行数、列数、非零元个数 
 } TSMatrix; 
 
//函数声明区 
void menu(); //功能菜单 
void CreateMatrix (TSMatrix &T); //创建矩阵 
void DestoryMatrix (TSMatrix T); //销毁矩阵 
void OutputMatrix (TSMatrix T); //输出矩阵 
void TransposeMatrix (TSMatrix T, TSMatrix &M); //矩阵的转置 
void FastTransposeMatrix (TSMatrix T, TSMatrix &M); //快速转置矩阵 
 
int main(){
	TSMatrix TSM, M; 
	int option = 0;
	menu();
	while (option >= 0){
		cout<< "请输入你的选择:"<< endl;
		cin >>option;
		if (option != 1 && option >0 && isInit == false){
			cout<< "你还未创建矩阵，请先创建矩阵"<< endl;
			continue;
		} 
		switch(option) {
			case 1:
				CreateMatrix(TSM);
				break;
			case 2:
				DestoryMatrix(TSM);
				break; 
			case 3:
				cout<< "输出矩阵："<< endl; 
				OutputMatrix(TSM);
				break;
			case 4:
				TransposeMatrix(TSM,M);
				cout<< "转置之后的矩阵是："<< endl; 
				OutputMatrix(M); 
				break; 
			case 5:
				FastTransposeMatrix (TSM, M);
				cout<< "快速转置之后的矩阵为："<< endl;
				OutputMatrix(M); 
				break;	
			default:
				cout<< "成功退出，欢迎你下次使用！"<< endl; 
				break;	
		}
	}
} 

//功能菜单 
void menu(){
	cout<< "~~~~~~Spraing※boy~~~~~~~"<< endl;
	cout<< "**     1.创建矩阵      **"<< endl;
	cout<< "**     2.销毁矩阵      **"<< endl;
	cout<< "**     3.输出矩阵      **"<< endl;
	cout<< "**     4.转置矩阵      **"<< endl;
	cout<< "**     5.快速转置矩阵  **"<< endl;
	cout<< "**  ->退出输入一个负数 **"<< endl; 
	cout<< "~~~~~~~~~~~~~~~~~~~~~~~~~"<< endl; 
} 

//创建矩阵
void CreateMatrix (TSMatrix &T){
	while (true){
		cout<< "请输入总行数："<< endl;
		cin >>T.rows;
		if (T.rows<= 0){
			cout<< "你的输入有误，请重新输入"<< endl; 
		} else {
			break;
		}
	} 
	while (true){
		cout<< "请输入总列数："<< endl;
		cin >>T.cols;
		if (T.cols<= 0){
			cout<< "你的输入有误，请重新输入"<< endl; 
		} else {
			break;
		}
	} 
	//矩阵输入的合法性的检查
	while (true){
		cout<< "请输入总元素个数："<< endl;
		cin >>T.numbers;
		if (T.numbers<= 0){
			cout<< "元素个数输入有误，请重新输入"<< endl;
		}
		if (T.numbers >T.rows*T.cols){
			cout<< "输入错误，非零元素个数要小于等于行数乘列数，请重新输入"<< endl; 
		} else {
			break;
		} 	
	} 
	cout<< "矩阵的行数为："<< T.rows<< " 矩阵的列数为："<< T.cols<< " 矩阵的非零元的个数为："<< T.numbers<< endl; 
	int cnt = 1; //记录已插入的合法元素的个数 
	//定义三个变量分别代表输入的行，列，非零元素的值,如果在下面非法性的判断的过程中，结果合法，在对三元组相应属性赋值存储，如果非法让用户重新输入 
	int m, n, t; 
	while (cnt<= T.numbers){
		bool flag = true; //插入元素的合法性标记,必须放到while循环里面，不然会影响元素的存储，导致一些合法元素无法存入 
		cout<< "请输入元素的行，列和非零元的值：(元素下标不能重复，且下标需要递增)"<< endl;
		cin >>m >>n >>t;
		for (int b = 1; b<= cnt; ++b){
			//非法条件1：输入下标重复 
			if (T.data[b].i == m && T.data[b].j == n){
				cout<< "输入错误，你输入的下标重复"<< endl;
				flag = false;
				break;
			} else if (m<= 0 || n<= 0 || m >T.rows || n >T.cols){ //非法错误2：输入下标越界 
				cout<< "输入错误，你输入的下标越界"<< endl;
				flag = false;
				break;
			} else if (t == 0){ //非法错误3：输入元素为0 
				cout<< "输入错误，你输入的非零元的值为0"<< endl; 
				flag = false; 
				break;
			//非法错误4：输入下标行的时候不递增(只在输入非第一个元素的时候出现)
			//这里只需要判断上一个输入的行下表是否小于该次输入的下标，而上一个元素的行标已经储存到三元组对应位置中 
			} else if (cnt >1 && T.data[cnt-1].i >m){ 
				cout<< "输入错误，你输入时行的下标要逐渐递增"<< endl;
				flag = false; 
				break;
			} else if (cnt >1 && T.data[cnt-1].j >n && T.data[cnt-1].i == m){ //非法错误5：输入下标列的时候不递增 
				cout<< "输入错误，你输入时列的下标要逐渐递增"<< endl;
				flag = false; 
				break;
			}
		} 
		//输入合法元素 
		if (flag == true) {
			T.data[cnt].i = m;
			T.data[cnt].j = n;
			T.data[cnt].e = t;
			cout<< "成功输入第"<< cnt<< "个元素，"<< "还有"<< T.numbers-cnt<< "个等待你的输入!"<< endl;  
			cnt++; 
		} 
	}
	isInit  = true;
} 

//销毁矩阵 
void DestoryMatrix (TSMatrix T){
	for (int i = 0; i< T.numbers; ++i){
		T.data[i].e = 0; 
	}
	T.rows = T.cols = T.numbers = 0;
	cout<< "矩阵销毁成功！"<< endl;
	isInit = false;
} 

//输出矩阵
void OutputMatrix (TSMatrix T) {
	for (int i = 1; i<= T.rows; ++i){
		for (int j = 1; j<= T.cols; ++j){
			bool flag_isZero = true; //判断遍历矩阵时，是否为非零元,该标记必须放到循环体里面，每次判断结束都要初始化 
			for (int m = 1; m<= T.numbers; ++m){ //该层循环是为了遍历矩阵中非零元的所有下标 
				if (T.data[m].i == i && T.data[m].j == j){
					cout<< T.data[m].e<< "  ";
					flag_isZero = false;  
					break; 
				}
			}
			if (flag_isZero) {
				cout<< "0"<< "  "; 
			}
		}
		cout<< endl; //一行元素输出完成之后换行 
	}
} 

//转置矩阵
void TransposeMatrix (TSMatrix T, TSMatrix &M) {
	M.rows = T.cols;
	M.cols = T.rows;
	M.numbers = T.numbers;
	if (M.numbers != 0){
		int cnt = 1; //通过cnt对三元组进行遍历 
		for (int i = 1; i<= T.cols; ++i){ //控制列数 
			for (int j = 1; j<= T.numbers; ++j){ //遍历T中的非零元 
				if (T.data[j].j == i){
					M.data[cnt].i = T.data[j].j;
					M.data[cnt].j = T.data[j].i;
					M.data[cnt].e = T.data[j].e;
					cnt++; 
				} 
			} 
		}
	}
} 

//矩阵的快速转置
void FastTransposeMatrix (TSMatrix T, TSMatrix &M){
	M.rows = T.cols;
	M.cols = T.rows;
	M.numbers = T.numbers;
	int num[100]; //num[n]表示矩阵T中第n列中非零元的个数
	int cpot[100]; //cpot[n]表示矩阵T中第n列中第一个非零元素在M中的位置 
	if (M.numbers != 0) {
		int col, t, p, q;
		for (col = 1; col<= T.cols; ++col){ //初始化T中各列元素个数为0 
			num[col] = 0;
		}
		for (t = 1; t<= T.numbers; ++t){
			++num[T.data[t].j];
		} 
		cpot[1] = 1;
		//求第col列中第一个非零元在b.dataa中的序号
		for (col = 2; col< T.rows; ++col){
			cpot[col] = cpot[col-1] + num[col-1];
		} 
		for (p = 1; p<= T.numbers; ++p){
			col = T.data[p].j;
			q = cpot[col];
			M.data[q].i = T.data[p].j;
			M.data[q].j = T.data[p].i;
			M.data[q].e = T.data[p].e;
			++cpot[col];
		}
	} 
}

实验用例测试：

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧