数据结构11：二维数组与矩阵乘法

摘要：二维数组在我们学习c语言的时候遇到过，现在我们来试试用数据结构对二维数组进行操作，并且顺便看看c语言是如何给二维数组分配空间的
一.代码块
1）创建

这里分为了静态和动态两个写法，由于静态操作比较简单，我们后续的函数用的动态。

#define ROWS 4
#define COLUMNS 5

 
typedef struct twoDArray
{
	int rows;
	int columns;
	int **elements;
}*towDArrayPtr;

//这种静态分配不用单独给数组malloc,由于这种比较简单，我们后续的都用的第一种 
typedef struct twoDStaticArray
{
	int rows;
	int columns;
	int elements[ROWS][COLUMNS];
}*twoDStaticArrayPtr;

2）初始化

在开始初始化函数之前，我们要知道一件事情：对于c语言来说，二维数组其实就是一个一维数组，只不过这个一维数组的每个元素又分别是一个一维数组。同理推广到三维数组甚至更高维。其次，c语言的的二维数组是以行序为主序的，即相当于二维数组的每一行单独是一个大的元素，第一行为第一个元素，第二行为第二个元素。

towDArrayPtr twoDArrayInit(int paraRows,int paraColumns)
{
	int i;
	//首先先给结构体 malloc 
	towDArrayPtr resultTwoDArray = (towDArrayPtr)malloc(sizeof(struct twoDArray));
	resultTwoDArray->rows = paraRows;
	resultTwoDArray->columns = paraColumns;
	
	//对于二维数组，先给最外层malloc
	resultTwoDArray->elements = (int**)malloc(paraRows * sizeof(int*));
	
	//然后，在对我们说的每一行的大元素malloc，空间就是每一行元素的个数，即列数
	for(i = 0;i < resultTwoDArray->rows;i ++)
	{
		
		resultTwoDArray->elements[i] = (int*)malloc(paraColumns * sizeof(int));
	}
	
	return  resultTwoDArray;
	 
}

3）打印

void outputTwoDArray(towDArrayPtr paraPtr)
{
	int i,j;
	for(i = 0;i < paraPtr->rows;i ++)
	{
		for(j = 0;j < paraPtr->columns;j ++)
		{
			printf("%d ",paraPtr->elements[i][j]);
		} 
		
		printf("n");
	}
	
	printf("rn");
}

4）随机赋值

void randomizeTwoDArray(towDArrayPtr paraPtr, int paraLowerBound, int paraUpperBound)
{
	int i, j;	
	//这里就是一个随机函数，在stdlib头文件里面，给定上下界然后给每个元素赋随机值 
	for (i = 0; i < paraPtr->rows; i ++)
	{
		for (j = 0; j < paraPtr->columns; j ++) 
		{
			paraPtr->elements[i][j] = rand() % (paraUpperBound - paraLowerBound) + paraLowerBound;
		}
	}
}

5）矩阵的乘法

我们要先知道矩阵相乘是怎么算的，然后解读一下这个三重循环

首先，前两重循环就是遍历我们要的矩阵，给每一个矩阵赋值。
第三重循环就是执行我们每一个位置的元素是如何得到的，就是
第一个矩阵的第i行每个位置的元素乘以第二个矩阵的第j列每个位置
的元素，再把他们加起来。读者需要自行画个矩阵跟踪一下就会明朗很多

towDArrayPtr matrixMultiply(towDArrayPtr paraPtr1,towDArrayPtr paraPtr2)
{
	int i,j,k,sum;
	if(paraPtr1->columns != paraPtr2->rows)
	{
		printf("这个两个矩阵不能相乘哦0.0n");
		return ; 
	}
	towDArrayPtr resultPtr;
	resultPtr = twoDArrayInit(paraPtr1->rows,paraPtr2->columns);
	
	for(i = 0;i < paraPtr1->rows;i ++)
		for(j = 0;j < paraPtr2->columns;j ++)
		{
			sum = 0;
			for(k = 0;k < paraPtr1->columns;k ++)
			{
				sum += paraPtr1->elements[i][k] * paraPtr2->elements[k][j]; 
			}
			resultPtr->elements[i][j] = sum; 
		}
		
	return resultPtr; 
}

6）静态版的初始化并且打印其地址

这里简单的给静态数组赋值输出一下，重点是地址的打印让我们直到c语言是怎么看待二维数组的

twoDStaticArrayPtr initTwoDStaticArray()
{
	int i, j;
	twoDStaticArrayPtr resultPtr = (twoDStaticArrayPtr)malloc(sizeof(struct twoDStaticArray));
	resultPtr->rows = ROWS;
	resultPtr->columns = COLUMNS;
	for (i = 0; i < ROWS; i ++)
	{
		for (j = 0; j < COLUMNS; j ++) 
		{
			resultPtr->elements[i][j] = i * 10 + j;
			printf("(%d, %d): %d; n", i, j, &(resultPtr->elements[i][j]));
		}
	}
	
	return resultPtr;
}

7）测试函数

void twoDArrayTest()
{
	towDArrayPtr tempPtr1, tempPtr2, tempPtr3;
	tempPtr1 = twoDArrayInit(3, 2);
	randomizeTwoDArray(tempPtr1, 1, 5);
	printf("The first matrix:rn");
	outputTwoDArray(tempPtr1);

	tempPtr2 = twoDArrayInit(2, 4);
	randomizeTwoDArray(tempPtr2, 4, 9);
	printf("The second matrix:rn");
	outputTwoDArray(tempPtr2);

	tempPtr3 = matrixMultiply(tempPtr1, tempPtr2);
	printf("The result:rn");
	outputTwoDArray(tempPtr3);
}

三.全部代码

#include 
#include 
#include 

#define ROWS 4
#define COLUMNS 5

 
typedef struct twoDArray
{
	int rows;
	int columns;
	int **elements;
}*towDArrayPtr;

//这种静态分配不用单独给数组malloc,由于这种比较简单，我们后续的都用的第一种 
typedef struct twoDStaticArray
{
	int rows;
	int columns;
	int elements[ROWS][COLUMNS];
}*twoDStaticArrayPtr;


towDArrayPtr twoDArrayInit(int paraRows,int paraColumns)
{
	int i;
	//首先先给结构体 malloc 
	towDArrayPtr resultTwoDArray = (towDArrayPtr)malloc(sizeof(struct twoDArray));
	resultTwoDArray->rows = paraRows;
	resultTwoDArray->columns = paraColumns;
	
	//对于二维数组，先给最外层malloc
	resultTwoDArray->elements = (int**)malloc(sizeof(int*));
	
	//然后，在对我们说的每一行的大元素malloc，空间就是每一行元素的个数，即列数
	for(i = 0;i < resultTwoDArray->rows;i ++)
	{
		
		resultTwoDArray->elements[i] = (int*)malloc(sizeof(int));
	}
	
	return  resultTwoDArray;
	 
}

void randomizeTwoDArray(towDArrayPtr paraPtr, int paraLowerBound, int paraUpperBound)
{
	int i, j;	
	//这里就是一个随机函数，在stdlib头文件里面，给定上下界然后给每个元素赋随机值 
	for (i = 0; i < paraPtr->rows; i ++)
	{
		for (j = 0; j < paraPtr->columns; j ++) 
		{
			paraPtr->elements[i][j] = rand() % (paraUpperBound - paraLowerBound) + paraLowerBound;
		}
	}
}

void outputTwoDArray(towDArrayPtr paraPtr)
{
	int i,j;
	for(i = 0;i < paraPtr->rows;i ++)
	{
		for(j = 0;j < paraPtr->columns;j ++)
		{
			printf("%d ",paraPtr->elements[i][j]);
		} 
		
		printf("n");
	}
	
	printf("rn");
}

towDArrayPtr matrixMultiply(towDArrayPtr paraPtr1,towDArrayPtr paraPtr2)
{
	int i,j,k,sum;
	if(paraPtr1->columns != paraPtr2->rows)
	{
		printf("这个两个矩阵不能相乘哦0.0n");
		return ; 
	}
	towDArrayPtr resultPtr;
	resultPtr = twoDArrayInit(paraPtr1->rows,paraPtr2->columns);
	
	for(i = 0;i < paraPtr1->rows;i ++)
		for(j = 0;j < paraPtr2->columns;j ++)
		{
			sum = 0;
			for(k = 0;k < paraPtr1->columns;k ++)
			{
				sum += paraPtr1->elements[i][k] * paraPtr2->elements[k][j]; 
			}
			resultPtr->elements[i][j] = sum; 
		}
		
	return resultPtr; 
}

twoDStaticArrayPtr initTwoDStaticArray()
{
	int i, j;
	twoDStaticArrayPtr resultPtr = (twoDStaticArrayPtr)malloc(sizeof(struct twoDStaticArray));
	resultPtr->rows = ROWS;
	resultPtr->columns = COLUMNS;
	for (i = 0; i < ROWS; i ++)
	{
		for (j = 0; j < COLUMNS; j ++) 
		{
			resultPtr->elements[i][j] = i * 10 + j;
			printf("(%d, %d): %d; n", i, j, &(resultPtr->elements[i][j]));
		}
	}
	
	return resultPtr;
}

void twoDArrayTest()
{
	towDArrayPtr tempPtr1, tempPtr2, tempPtr3;
	tempPtr1 = twoDArrayInit(3, 2);
	randomizeTwoDArray(tempPtr1, 1, 5);
	printf("The first matrix:rn");
	outputTwoDArray(tempPtr1);

	tempPtr2 = twoDArrayInit(2, 4);
	randomizeTwoDArray(tempPtr2, 4, 9);
	printf("The second matrix:rn");
	outputTwoDArray(tempPtr2);

	tempPtr3 = matrixMultiply(tempPtr1, tempPtr2);
	printf("The result:rn");
	outputTwoDArray(tempPtr3);
}

int main()
{
	twoDArrayTest();
	twoDStaticArrayPtr tempPtr = initTwoDStaticArray();
}

四.运行结果

矩阵运行结果

The first matrix:
2 4
3 1
2 1

The second matrix:
7 7 6 8
4 4 5 6

The result:
30 30 32 40
25 25 23 30
18 18 17 22

打印地址结果

(0, 0): 11408888;
(0, 1): 11408892;
(0, 2): 11408896;
(0, 3): 11408900;
(0, 4): 11408904;
(1, 0): 11408908;
(1, 1): 11408912;
(1, 2): 11408916;
(1, 3): 11408920;
(1, 4): 11408924;
(2, 0): 11408928;
(2, 1): 11408932;
(2, 2): 11408936;
(2, 3): 11408940;
(2, 4): 11408944;
(3, 0): 11408948;
(3, 1): 11408952;
(3, 2): 11408956;
(3, 3): 11408960;
(3, 4): 11408964;

可以很明显的看到，c语言是以行序为主序的。

数据结构11：二维数组与矩阵乘法

C/C++/C#相关栏目本月热门文章