数据结构：二维数组和压缩矩阵

二维数组的定义：类型 数组名[行号][列号]

矩阵相乘需要前面矩阵的行数与后面矩阵的列数相同方可相乘。将前面矩阵的每一行分别与后面矩阵的列相乘作为结果矩阵的行列。
第一个的列数等于第二个的行数，如：2X3与3X2 的结果为2X2

二维数组和矩阵乘法

#include
#include
#include

#define ROWS 4
#define COLUMNS 5



typedef struct TwoDArray{
	int rows;
	int columns;
	int** elements;
}TwoDArray,*TwoDArrayPtr;



typedef struct TwoDStaticArray{
	int rows;
	int columns;
	int elements[ROWS][COLUMNS];
}TwoDStaticArray,*TwoDStaticArrayPtr;


TwoDArrayPtr initTwoDArray(int paraRows,int paraColumns){
	int i;
	TwoDArrayPtr resultPtr = (TwoDArrayPtr)malloc(sizeof(struct TwoDArray));
	resultPtr->rows = paraRows;
	resultPtr->columns = paraColumns;
	resultPtr->elements = (int**)malloc(paraRows*sizeof(int*));
	for(i=0;ielements[i]=(int*)malloc(paraRows*sizeof(int));
	}//of for it
	
	return resultPtr;
}//of initTwoDArray



void randomizeTwoDArray(TwoDArrayPtr paraPtr,int paraLowerBound,int paraUpperBound){
	int i,j;
	for(i=0;irows;i++){
		for(j=0;jcolumns;j++){
			paraPtr->elements[i][j] = rand()%(paraUpperBound-paraLowerBound)+paraLowerBound;
		}//of for j
	}//of for i
}//of randomizetwodarray


void printTwoDArray(TwoDArrayPtr paraPtr)
{
	int i,j;
	for(i=0;irows;i++){
		for(j=0;jcolumns;j++){
			printf("%d, ",paraPtr->elements[i][j]);
		}//of for j
		printf("rn");
	}//of for i
}//of inittwodarray



TwoDArrayPtr matrixMultiply(TwoDArrayPtr paraPtr1,TwoDArrayPtr paraPtr2){
	int i,j,k,sum;
	if(paraPtr1->columns != paraPtr2->rows){
		printf("matrices cannot be multiplied.rn");
		return NULL;
	}//of if
	
	TwoDArrayPtr resultPtr = initTwoDArray(paraPtr1->rows,paraPtr2->columns);
	for(i=0;irows;i++){
		for(j=0;jcolumns;j++){
			sum=0;
			for(k=0;kcolumns;k++){
				sum+=paraPtr1->elements[i][j]*paraPtr2->elements[k][j];
			} //of for k
			resultPtr->elements[i][j]=sum;
			printf("sum= %d, ",sum);
		}//of for j
	}//of for i
	
	return resultPtr;
}



void twoDArrayTest(){
	TwoDArrayPtr tempPtr1,tempPtr2,tempPtr3;
	tempPtr1 = initTwoDArray(3,2);
	randomizeTwoDArray(tempPtr1,1,5);
	printf("the first matrix:rn");
	printTwoDArray(tempPtr1);
	
	tempPtr2 = initTwoDArray(2,4);
	randomizeTwoDArray(tempPtr2,4,9);
	printf("the first matrix:rn");
	printTwoDArray(tempPtr2);
	
	tempPtr3 = matrixMultiply(tempPtr1,tempPtr2);
	printf("the result:rn");
	printTwoDArray(tempPtr3);
	
}
TwoDStaticArrayPtr initTwoDStaticArray(){
	int i,j;
	TwoDStaticArrayPtr resultPtr = (TwoDStaticArrayPtr)malloc(sizeof(struct TwoDStaticArray));
	resultPtr->rows = ROWS;
	resultPtr->columns = COLUMNS;
	for(i=0;ielements[i][j]= i*10+j;
			printf("(%d,%d):%d;",i,j,&(resultPtr->elements[i][j]));
		}//of for j
	}//of for i
	
	return resultPtr;
}

int main(){
	twoDArrayTest();
	TwoDStaticArrayPtr tempPtr = initTwoDStaticArray();
	
	return 1;
}//of main

运行结果

 压缩矩阵

指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。

#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;ielements[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;inumElements;i++){
		printf("(%d,%d):%drn",paraPtr->elements[i].i,paraPtr->elements[i].j,paraPtr->elements[i].e);
	}	
}//of printCompressedMatrix

CompressedMatrixPtr transposeCompressedMatrix(CompressedMatrixPtr paraPtr){
	//step1 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;icolumns;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));
	//step2.one scan to calculate offsets
	for(i=0;inumElements;i++){
		tempColumnCounts[paraPtr->elements[i].j]++;
	}
	tempOffsets[0]=0;
	for(i=1;icolumns;i++){
		tempOffsets[i]=tempOffsets[i-1]+tempColumnCounts[i-1];
		printf("tempOffsets[%d] = %drn",i,tempOffsets[i]);
	}
	//step3
	for(i=0;inumElements;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]++;
	}
	
	return resultPtr;
	
}

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

运行结果