作业：13数据结构压缩矩阵的转置

提示：此blog仅为完成作业，大佬请绕路

• 老师的代码
• 我的代码

#include 
#include 

typedef int elem;


typedef struct Triple{
    int i;
    int j;
    elem e;
} Triple, *TriplePtr;


typedef struct CompressedMatrix{
    int rows,columns,numElements;
    Triple* elements;
} CompressedMatrix, *CompressedMatrixPtr;


CompressedMatrixPtr initCompressedMatrix(int paraRows, int paraColumns, int paraElements, int** paraData){
	int i;
	CompressedMatrixPtr resultPtr = (CompressedMatrixPtr)malloc(sizeof(struct CompressedMatrix));
	resultPtr->rows = paraRows;
	resultPtr->columns = paraColumns;
	resultPtr->numElements = paraElements;
	resultPtr->elements = (TriplePtr)malloc(paraElements * sizeof(struct Triple));

	for(i = 0; i < paraElements; i ++){
		resultPtr->elements[i].i = paraData[i][0];
		resultPtr->elements[i].j = paraData[i][1];
		resultPtr->elements[i].e = paraData[i][2];
	}//Of for i

	return resultPtr;
}// Of initCompressedMatrix


void printCompressedMatrix(CompressedMatrixPtr paraPtr){
	int i;
	for(i = 0; i < paraPtr->numElements; i ++){
		printf("(%d, %d): %drn", paraPtr->elements[i].i, paraPtr->elements[i].j, paraPtr->elements[i].e);
	}//Of for i
}// Of printCompressedMatrix


CompressedMatrixPtr transposeCompressedMatrix(CompressedMatrixPtr paraPtr){
	//Step 1. Allocate space.
	int i, tempColumn, tempPosition;
	int *tempColumnCounts = (int*)malloc(paraPtr->columns * sizeof(int));
	int *tempOffsets = (int*)malloc(paraPtr->columns * sizeof(int));
	for(i = 0; i < paraPtr->columns; i ++){
		tempColumnCounts[i] = 0;
	}//Of for i

	CompressedMatrixPtr resultPtr = (CompressedMatrixPtr)malloc(sizeof(struct CompressedMatrix));
	resultPtr->rows = paraPtr->columns;
	resultPtr->columns = paraPtr->rows;
	resultPtr->numElements = paraPtr->numElements;

	resultPtr->elements = (TriplePtr)malloc(paraPtr->numElements * sizeof(struct Triple));
	
	//Step 2. One scan to calculate offsets.
	for(i = 0; i < paraPtr->numElements; i ++) {
		tempColumnCounts[paraPtr->elements[i].j] ++;
	}//Of for i
	tempOffsets[0] = 0;
	for(i = 1; i < paraPtr->columns; i ++){
		tempOffsets[i] = tempOffsets[i - 1] + tempColumnCounts[i - 1];
		printf("tempOffsets[%d] = %d rn", i, tempOffsets[i]);
	}//Of for i

	//Step 3. Another scan to fill data.
	for(i = 0; i < paraPtr->numElements; i ++) {
		tempColumn = paraPtr->elements[i].j;
		tempPosition = tempOffsets[tempColumn];
		resultPtr->elements[tempPosition].i = paraPtr->elements[i].j;
		resultPtr->elements[tempPosition].j = paraPtr->elements[i].i;
		resultPtr->elements[tempPosition].e = paraPtr->elements[i].e;

		tempOffsets[tempColumn]++;
	}//Of for i

	return resultPtr;
}//Of transposeCompressedMatrix


void compressedMatrixTest(){
	CompressedMatrixPtr tempPtr1, tempPtr2;
	int i, j, tempElements;

	//Construct the first sample matrix.
	tempElements = 4;
	int** tempMatrix1 = (int**)malloc(tempElements * sizeof(int*));
	for(i = 0; i < tempElements; i ++){
		tempMatrix1[i] = (int*)malloc(3 * sizeof(int));
	}//Of for i

	int tempMatrix2[4][3] = {{0, 0, 2}, {0, 2, 3}, {2, 0, 5}, {2, 1, 6}};
	for(i = 0; i < tempElements; i ++){
		for(j = 0; j < 3; j ++) {
			tempMatrix1[i][j] = tempMatrix2[i][j];
		}//Of for j
	}//Of for i
	
	tempPtr1 = initCompressedMatrix(2, 3, 4, tempMatrix1);

	printf("After initialization.rn");
	printCompressedMatrix(tempPtr1);

	tempPtr2 = transposeCompressedMatrix(tempPtr1);
	printf("After transpose.rn");
	printCompressedMatrix(tempPtr2);
}// Of main


int main(){
	compressedMatrixTest();

	return 1;
}// Of main

#include 
#include 

#define OK 1
#define ERROR -1
#define OVERFLOW -2
//--------------压缩矩阵的顺序存储表示-------------
typedef int status;     //status是函数的类型，其值是函数结果状态代码。
typedef int Elem;       //自定

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

typedef struct {
	
	int i,j;
	Elem e;	
}Triple; 

typedef struct {
	
	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("ttt 1---创建矩阵n");
		printf("ttt 2---销毁矩阵n");
		printf("ttt 3---输出矩阵n");
		printf("ttt 4---转置矩阵n");
		printf("ttt 5---快速转置矩阵n");	
		printf("ttt 退出，输入一个负数！");
		printf("n");
		printf("tt----------------------------------------------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;
}