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

文章目录

二维数组

二维数组定义

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

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

二维数组的创建

动态二维数组

动态二维数组图示

在这里插入图片描述

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 = [a_ij] 和 B = [b_ij] 为m * n矩阵。A 和 B 的和是其第(i,j)元素为 a_ij + b_ij 的矩阵。

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

矩阵加法图示

在这里插入图片描述

代码：

/* 矩阵加法 */
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;
}

矩阵乘法

令 A 为m * k矩阵，B 为k * n矩阵。A 和 B 的乘积是一个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;