数据结构-数组(详细讲解)

文章目录

- 数组
- - 数组的概述
  - 数组的图示
  - - 一维数组
    - 二维数组
  - 数组的定义
  - - 一维数组的定义
    - 二维数组的定义
  - 数组的取值赋值
  - - 一维数组
    - 二维数组
  - 数组的操作
  - - 一维数组的操作
    - - 索引实现
      - 指针实现
    - 二位数组的操作
    - - 矩阵转三元组
      - 矩阵的乘法

数组

数组的概述

概述：数组是一种线性数据结构，它由一组按顺序排列的元素组成。每个元素都有一个唯一的索引，用于访问和操作该元素。数组可以包含任意类型的数据，如整数、浮点数、字符串等
注意：数组是只能存储一种数据类型，且数组一旦创建，大小就固定的容器。
优缺点：
- 数组的优点，快速访问和搜索速度，因为元素的位置是固定的，可以通过索引直接访问
- 数组的缺点，插入和删除操作可能会导致大量元素的移动，从而影响性能，并且数组的大小一旦创建就是固定的
种类：
- 一维数组
- 二维数组(二维数组其实就是多维数组，像一个表格一样)
- 多维数组

数组的图示

一维数组

二维数组

二维数组可以看成一个表格，下边就是一个4行3列的二维数组

二维数组也可以看成一维数组中嵌套一维数组的样式，下边图也是一个 4行3列的二维数组

数组的定义

一维数组的定义

格式

// 格式一
数据类型 数组名[长度];
// 格式二
数据类型 数组名[长度] = {值1,值2...值n};
// 格式三
数据类型 数组名[] = {值1,值2...值n};

示例

// 定义一个长度为 5 的整型数组
int a[5];
// 定义一个长度为 5 的整型数组，并初始化(初始化就是赋值的意思)
int b[5] = {1,2,3,4,5};
// 定义一个整型数组，并初始化，可以看到方括号中并无长度，是因为初始化列表自动推断数组的大小
int c[] = {1,2,3,4,5};

二维数组的定义

格式

// 格式一
数据类型 数组名[行数][列数];
// 格式二
数据类型 数组名[行数][列数] = {{值1,值2...值n},{值1,值2...值n},...,{值1,值2...值n}};
// 格式三
数据类型 数组名[][列数] = {{值1,值2...值n},{值1,值2...值n},...,{值1,值2...值n}};

示例

// 定义一个3行4列的整型二维数组
int a[3][4];
// 定义一个3行4列的整型二维数组，并初始化
int b[3][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
// 初始化列表自动推断数组是多少行
int c[][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};

数组的取值赋值

一维数组

#include <stdio.h>					// 打印需要靠这个 标准输入输出库int main() {// 定义一个一维数组int arr[] = {1, 2, 3, 4, 5};// 访问数组中的元素printf("%d\n", arr[0]);  // 输出：1printf("%d\n", arr[2]);  // 输出：3// 修改数组中的元素arr[3] = 6;for (int i = 0; i < 5; i++) {printf("%d ", arr[i]);  // 输出：1 2 3 6 5}// 获取数组的长度int length = sizeof(arr) / sizeof(arr[0]);printf("\n%d\n", length);  // 输出：5return 0;
}

二维数组

#include <stdio.h>int main() {// 定义一个二维数组int arr2d[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};// 访问二维数组中的元素printf("%d\n", arr2d[0][0]);  // 输出：1printf("%d\n", arr2d[1][2]);  // 输出：6// 修改二维数组中的元素arr2d[2][1] = 10;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {printf("%d ", arr2d[i][j]);  // 输出：1 2 3 4 5 6 7 10 9}}// 获取二维数组的行数和列数int rows = sizeof(arr2d) / sizeof(arr2d[0]);int cols = sizeof(arr2d[0]) / sizeof(arr2d[0][0]);printf("\n%d %d\n", rows, cols);  // 输出：3 3return 0;
}

数组的操作

一维数组的操作

索引实现

#include <stdio.h>// 使用索引进行操作
void arrayOperationsWithIndex(int arr[], int size) {// 插入操作，insertIndex 是要插入的位置，insertValue 是要插入的值int insertIndex = 2;int insertValue = 10;// 将插入位置之后的元素依次向后移动for (int i = size - 1; i >= insertIndex; i--) {arr[i + 1] = arr[i];}// 插入元素arr[insertIndex] = insertValue;// 改变数组长度size++;// 删除操作int deleteIndex = 3;// 将 deleteIndex 之后的元素依次前移，覆盖for (int i = deleteIndex; i < size - 1; i++) {arr[i] = arr[i + 1];}size--;// 修改操作int modifyIndex = 1;int newValue = 20;arr[modifyIndex] = newValue;// 查找操作int target = 20;int found = 0;for (int i = 0; i < size; i++) {if (arr[i] == target) {printf("元素 %d 找到了，索引为 %d\n", target, i);found = 1;break;}}if (!found) {printf("未找到元素 %d\n", target);}
}
int main() {int arr1[10] = {1, 2, 3, 4, 5};int size1 = 5;// 使用索引进行操作arrayOperationsWithIndex(arr1, size1);return 0;
}

指针实现

#include <stdio.h>
// 使用指针进行操作
void arrayOperationsWithPointer(int *arr, int *size) {// 插入操作int insertIndex = 2;int insertValue = 10;for (int i = *size - 1; i >= insertIndex; i--) {*(arr + i + 1) = *(arr + i);}*(arr + insertIndex) = insertValue;(*size)++;// 删除操作int deleteIndex = 3;for (int i = deleteIndex; i < *size - 1; i++) {*(arr + i) = *(arr + i + 1);}(*size)--;// 修改操作int modifyIndex = 1;int newValue = 20;*(arr + modifyIndex) = newValue;// 查找操作int target = 20;int found = 0;for (int i = 0; i < *size; i++) {if (*(arr + i) == target) {printf("元素 %d 找到了，索引为 %d\n", target, i);found = 1;break;}}if (!found) {printf("未找到元素 %d\n", target);}
}
int main() {int arr2[10] = {1, 2, 3, 4, 5};int size2 = 5;// 使用指针进行操作arrayOperationsWithPointer(arr2, &size2);return 0;
}

二位数组的操作

矩阵转三元组

#include <stdio.h>// 定义矩阵的行数和列数
#define ROWS 3
#define COLS 3// 定义矩阵转换为三元组的结构体
typedef struct Triple {int row;				// 行int col;				// 列int value;				// 值
}Triple;/* 定义矩阵转换为三元组的函数参数：matrix[ROWS][COLS]		矩阵，用二维数组实现rows					矩阵行数cols					矩阵列数triple[]				三元组数组
*/
int convertToTriple(int matrix[ROWS][COLS], int rows, int cols, Triple triple[]) {int count = 0;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (matrix[i][j] != 0) {/*下边四行代码释义：1、将不等于0元素的行值存到三元组中2、将不等于0元素的列值存到三元组中3、将不等于0元素的值存到三元组中4、行数加1*/triple[count].row = i;triple[count].col = j;triple[count].value = matrix[i][j];count++;}}}return count;
}int main() {// 定义一个矩阵int matrix[ROWS][COLS] = {{1, 0, 0},{0, 2, 0},{0, 0, 3}};// 打印原始矩阵printf("原始矩阵：\n");for (int i = 0; i < ROWS; i++) {for (int j = 0; j < COLS; j++) {printf("%d ", matrix[i][j]);}printf("\n");}// 将矩阵转换为三元组Triple triple[ROWS * COLS];int count = convertToTriple(matrix, ROWS, COLS, triple);// 打印三元组printf("转换后的三元组：\n");for (int i = 0; i < count; i++) {printf("(%d, %d, %d)\n", triple[i].row, triple[i].col, triple[i].value);}return 0;
}

三元组，就是将矩阵压缩的一种形式，将非零元素值的位置和值存到三元组数组中，零元素值不存储

矩阵的乘法

#include <stdio.h>#define ROWS1 2
#define COLS1 3
#define ROWS2 3
#define COLS2 2/*矩阵乘法函数参数：mat1[ROWS1][COLS1]					矩阵1mat2[ROWS2][COLS2]					矩阵2result[ROWS1][COLS2]				结果矩阵
*/ 
void matrixMultiply(int mat1[ROWS1][COLS1], int mat2[ROWS2][COLS2], int result[ROWS1][COLS2]) {// 遍历矩阵1的行for (int i = 0; i < ROWS1; i++) {// 遍历矩阵2的列for (int j = 0; j < COLS2; j++) {// 首先将这个位置初始化为 0result[i][j] = 0;// k 作为矩阵1 的列，矩阵2 的行for (int k = 0; k < COLS1; k++) {// 矩阵1的i行上的每个值 乘以 矩阵2 j列上的每个值相加之和，就是 i,j 位置的乘积result[i][j] += mat1[i][k] * mat2[k][j];}}}
}int main() {int mat1[ROWS1][COLS1] = {{1, 2, 3}, {4, 5, 6}};int mat2[ROWS2][COLS2] = {{7, 8}, {9, 10}, {11, 12}};int result[ROWS1][COLS2];// 打印原始矩阵1printf("矩阵1：\n");for (int i = 0; i < ROWS1; i++) {for (int j = 0; j < COLS1; j++) {printf("%d ", mat1[i][j]);}printf("\n");}// 打印原始矩阵2printf("矩阵2：\n");for (int i = 0; i < ROWS2; i++) {for (int j = 0; j < COLS2; j++) {printf("%d ", mat2[i][j]);}printf("\n");}// 对矩阵进行相乘matrixMultiply(mat1, mat2, result);// 打印相乘后的结果矩阵printf("相乘后的结果矩阵：\n");for (int i = 0; i < ROWS1; i++) {for (int j = 0; j < COLS2; j++) {printf("%d ", result[i][j]);}printf("\n");}return 0;
}