【数据结构--二维数组】

二维数组

二维数组定义

二维数组本质上是以数组作为数组元素的数组,即数组的数组。

  • 二维数组就是一个有行和列的矩阵,每一行代表一个数组,即数组的数组;
  • 每一行数组内元素所在的位置可以用行和列号来表示

二维数组的创建

动态二维数组

动态二维数组图示

在这里插入图片描述

elements是动态二维数组变量,其是指向包含两个整型元素数组的指针(即指向二维数组首地址),elements[0]、elements[1]、elements[2]存储的值为一个包含两个整型元素的一维数组的首地址。

代码:

结构体定义

typedef int ElemType;

/* 动态空间分配 */
typedef struct TwoDArry
{
    int rows;
    int columns;
    ElemType** elements; 
} TwoDArray, *TwoDArrayPtr;

初始化

/* 初始化二维数组 */
TwoDArrayPtr initTwoDArray(int tempRows, int tempColumns)
{
    TwoDArrayPtr resultPtr = (TwoDArrayPtr)malloc(sizeof(TwoDArray));
    resultPtr->rows = tempRows;
    resultPtr->columns = tempColumns;
    resultPtr->elements = (ElemType**)malloc(sizeof(ElemType*)*tempRows);
    for(int i = 0; i < tempRows; ++i)
    {
        resultPtr->elements[i] = (ElemType*)malloc(sizeof(ElemType)*tempColumns);
    }
    return resultPtr;
}

静态二维数组

静态二维数组图示

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DYd22BzC-1653384449123)(C:\Users\叶黎曙\AppData\Roaming\Typora\typora-user-images\1653382016725.png)]

  • 静态二维数组实质上就是一个一维数组,其内存空间分配也是连续的
  • elements是静态二维数组变量,指向二维数组首地址
  • elements[0]:指向静态二维数组第一行首地址
  • elements[1]:指向静态二维数组第二行首地址
  • elements[2]:指向静态二维数组第三行首地址

代码:

结构体定义

/* 静态空间分配 */
typedef struct TwoDStaticArray
{
    int rows;
    int columns;
    ElemType elements[ROWS][COLUMNS];
} TwoDStaticArray, *TwoDStaticArrayPtr;

初始化

/* 初始化二维数组(静态) */
TwoDStaticArrayPtr initTwoDStaticArray()
{
    TwoDStaticArrayPtr resultPtr = (TwoDStaticArrayPtr)malloc(sizeof(TwoDStaticArray));
    resultPtr->rows = ROWS;
    resultPtr->columns = COLUMNS;
    for(int i = 0; i < ROWS; ++i)
    {
        for (int j = 0; j < COLUMNS; ++j)
        {
            resultPtr->elements[i][j] = i * 10 + j;
            printf("(%d, %d)地址:%d;",i,j,&(resultPtr->elements[i][j]));
        }
        printf("\n");
    }
    return resultPtr;
}

静态数组地址分配

由测试看出静态二维数组实质上就是一个一维数组,其内存空间分配也是连续的

二维数组的应用

矩阵加法

A = [aij]B = [bij]m * n矩阵。AB 的和是其第(i,j)元素为 aij + bij 的矩阵。

相同大小的两个矩阵的和是将它们对应位置上的元素相加得到的,不同大小的矩阵不能相加。

矩阵加法图示

在这里插入图片描述

代码:

/* 矩阵加法 */
TwoDArrayPtr matrixAddition(TwoDArrayPtr tempPtr1, TwoDArrayPtr tempPtr2)
{
    if((tempPtr1->columns != tempPtr2->columns) ||(tempPtr1->rows != tempPtr2->rows))
    {
        printf("无法相加:两数组行列不同!\n");
        return NULL;
    }
    int sum = 0;
    TwoDArrayPtr resultPtr = initTwoDArray(tempPtr1->rows, tempPtr1->columns);
    for(int i = 0; i < tempPtr1->rows; ++i)
    {
        sum = 0;
        for (int j = 0; j < tempPtr1->columns; ++j)
        {
           resultPtr->elements[i][j] = tempPtr1->elements[i][j] + tempPtr2->elements[i][j];
        }
    }
    return resultPtr;
}

矩阵乘法

Am * k矩阵,Bk * n矩阵。AB 的乘积是一个m * n矩阵,其第(i,j)元素等于 A 的第i行与 B 的第j列对应元素的乘积之和。

矩阵乘法图示

在这里插入图片描述

代码:

/* 矩阵乘法 */
TwoDArrayPtr matrixMultiply(TwoDArrayPtr tempPtr1, TwoDArrayPtr tempPtr2)
{
    if (tempPtr1->columns != tempPtr2->rows)
    {
        printf("无法相乘!\n");
        return NULL;
    }
    int sum = 0;
    TwoDArrayPtr resultPtr = initTwoDArray(tempPtr1->rows,tempPtr2->columns);
    for (int i = 0; i < tempPtr1->rows; ++i)
    {
        for (int j = 0; j < tempPtr2->columns; ++j)
        {
            sum = 0;
            for (int k = 0; k < tempPtr1->columns; ++k)
            {
                sum += tempPtr1->elements[i][k] * tempPtr2->elements[k][j]; 
            }
            resultPtr->elements[i][j] = sum;
        }
    }
    return resultPtr;
}

完整代码

#include <stdio.h>
#include <stdlib.h>

#define ROWS 4
#define COLUMNS 5

typedef int ElemType;

/* 动态空间分配 */
typedef struct TwoDArry
{
    int rows;
    int columns;
    ElemType** elements; 
} TwoDArray, *TwoDArrayPtr;

/* 静态空间分配 */
typedef struct TwoDStaticArray
{
    int rows;
    int columns;
    ElemType elements[ROWS][COLUMNS];
} TwoDStaticArray, *TwoDStaticArrayPtr;

/* 初始化二维数组 (动态)*/
TwoDArrayPtr initTwoDArray(int tempRows, int tempColumns)
{
    TwoDArrayPtr resultPtr = (TwoDArrayPtr)malloc(sizeof(TwoDArray));
    resultPtr->rows = tempRows;
    resultPtr->columns = tempColumns;
    resultPtr->elements = (ElemType**)malloc(sizeof(ElemType*)*tempRows);
    for(int i = 0; i < tempRows; ++i)
    {
        resultPtr->elements[i] = (ElemType*)malloc(sizeof(ElemType)*tempColumns);
    }
    return resultPtr;
}

/* 初始化二维数组(静态) */
TwoDStaticArrayPtr initTwoDStaticArray()
{
    TwoDStaticArrayPtr resultPtr = (TwoDStaticArrayPtr)malloc(sizeof(TwoDStaticArray));
    resultPtr->rows = ROWS;
    resultPtr->columns = COLUMNS;
    for(int i = 0; i < ROWS; ++i)
    {
        for (int j = 0; j < COLUMNS; ++j)
        {
            resultPtr->elements[i][j] = i * 10 + j;
            printf("(%d, %d)地址:%d;",i,j,&(resultPtr->elements[i][j]));
        }
        printf("\n");
    }
    return resultPtr;
}

/* 随机化数组数据 */
void randomizeTwoDArray(TwoDArrayPtr tempPtr, ElemType tempLowerBound, ElemType tempUpperBound)
{
    for(int i = 0; i < tempPtr->rows; ++i)
    {
        for(int j = 0; j < tempPtr->columns; ++j)
        {
            tempPtr->elements[i][j] = rand() % (tempUpperBound - tempLowerBound) + tempLowerBound;
        }
    }
}

/* 打印二维数组 */
void printTwoDArray(TwoDArrayPtr tempPtr)
{
    for(int i = 0; i < tempPtr->rows; ++i)
    {
        for(int j = 0; j < tempPtr->columns; ++j)
        {
            printf("% d,",tempPtr->elements[i][j]);
        }
        printf("\n");
    }
}

/* 矩阵加法 */
TwoDArrayPtr matrixAddition(TwoDArrayPtr tempPtr1, TwoDArrayPtr tempPtr2)
{
    if((tempPtr1->columns != tempPtr2->columns) ||(tempPtr1->rows != tempPtr2->rows))
    {
        printf("无法相加:两数组行列不同!\n");
        return NULL;
    }
    int sum = 0;
    TwoDArrayPtr resultPtr = initTwoDArray(tempPtr1->rows, tempPtr1->columns);
    for(int i = 0; i < tempPtr1->rows; ++i)
    {
        sum = 0;
        for (int j = 0; j < tempPtr1->columns; ++j)
        {
           resultPtr->elements[i][j] = tempPtr1->elements[i][j] + tempPtr2->elements[i][j];
        }
    }
    return resultPtr;
}

/* 矩阵乘法 */
TwoDArrayPtr matrixMultiply(TwoDArrayPtr tempPtr1, TwoDArrayPtr tempPtr2)
{
    if (tempPtr1->columns != tempPtr2->rows)
    {
        printf("无法相乘!\n");
        return NULL;
    }
    int sum = 0;
    TwoDArrayPtr resultPtr = initTwoDArray(tempPtr1->rows,tempPtr2->columns);
    for (int i = 0; i < tempPtr1->rows; ++i)
    {
        for (int j = 0; j < tempPtr2->columns; ++j)
        {
            sum = 0;
            for (int k = 0; k < tempPtr1->columns; ++k)
            {
                sum += tempPtr1->elements[i][k] * tempPtr2->elements[k][j]; 
            }
            resultPtr->elements[i][j] = sum;
        }
    }
    return resultPtr;
}

/* 测试 */
void test()
{
    TwoDArrayPtr tempPtr1,tempPtr2,tempPtr3,tempPtr4,tempPtr5;
    tempPtr1 = initTwoDArray(3,2);
    randomizeTwoDArray(tempPtr1,1,5);
    printf("第一个矩阵:\n");
    printTwoDArray(tempPtr1);

    tempPtr2 = initTwoDArray(2,4);
    randomizeTwoDArray(tempPtr2,4,9);
    printf("第二个矩阵:\n");
    printTwoDArray(tempPtr2);

    tempPtr3 = matrixMultiply(tempPtr1,tempPtr2);
    printf("相乘结果为:\n");
    printTwoDArray(tempPtr3);

    tempPtr4 = initTwoDArray(3,2);
    randomizeTwoDArray(tempPtr4,4,9);
    printf("第四个矩阵:\n");
    printTwoDArray(tempPtr4);

    printf("第一个矩阵:\n");
    printTwoDArray(tempPtr1);

    tempPtr5 = matrixAddition(tempPtr1,tempPtr4);
    printf("相加结果为:\n");
    printTwoDArray(tempPtr5);
}

int main()
{
	test();
	TwoDStaticArrayPtr tempPtr = initTwoDStaticArray();
    return 0;
}

测试结果

第一个矩阵:
 2, 4,
 3, 1,
 2, 1,
第二个矩阵:
 7, 7, 6, 8,
 4, 4, 5, 6,
相乘结果为:
 30, 30, 32, 40,
 25, 25, 23, 30,
 18, 18, 17, 22,
第四个矩阵:
 5, 5,
 4, 6,
 6, 5,
第一个矩阵:
 2, 4,
 3, 1,
 2, 1,
相加结果为:
 7, 9,
 7, 7,
 8, 6,
(0, 0)地址:7302856;(0, 1)地址:7302860;(0, 2)地址:7302864;(0, 3)地址:7302868;(0, 4)地址:7302872;
(1, 0)地址:7302876;(1, 1)地址:7302880;(1, 2)地址:7302884;(1, 3)地址:7302888;(1, 4)地址:7302892;
(2, 0)地址:7302896;(2, 1)地址:7302900;(2, 2)地址:7302904;(2, 3)地址:7302908;(2, 4)地址:7302912;
(3, 0)地址:7302916;(3, 1)地址:7302920;(3, 2)地址:7302924;(3, 3)地址:7302928;(3, 4)地址:7302932;