数据结构中的数组：概念、操作与实战
第一部分 数组分类及常见形式
数组是最基本的数据结构之一，它是由相同类型的元素按一定顺序排列的集合，在内存中占据连续的空间。数组可以分为以下几类：
1. 一维数组
最基本的数组形式，元素线性排列。
// 声明并初始化一个一维数组
int numbers[5] = {1, 2, 3, 4, 5};
2. 多维数组
常见的是二维数组（矩阵），可以看作数组的数组。
// 声明并初始化一个二维数组
int matrix[3][3] = {{1, 2, 3},{4, 5, 6},{7, 8, 9}
};
3. 动态数组
大小可以在运行时确定的数组，通常需要手动管理内存。
// 动态数组示例
int size = 10;
int *dynamicArray = (int*)malloc(size * sizeof(int));
// 使用后不要忘记释放内存
free(dynamicArray);
4. 字符数组
C语言中用字符数组表示字符串。
char str[] = "Hello, World!";
第二部分 数组常见操作
1. 遍历数组
// 遍历一维数组
for(int i = 0; i < 5; i++) {printf("%d ", numbers[i]);
}// 遍历二维数组
for(int i = 0; i < 3; i++) {for(int j = 0; j < 3; j++) {printf("%d ", matrix[i][j]);}printf("\n");
}
2. 插入元素
// 在指定位置插入元素
void insertElement(int arr[], int size, int pos, int value) {for(int i = size - 1; i > pos; i--) {arr[i] = arr[i-1];}arr[pos] = value;
}
3. 删除元素
// 删除指定位置的元素
void deleteElement(int arr[], int size, int pos) {for(int i = pos; i < size - 1; i++) {arr[i] = arr[i+1];}arr[size-1] = 0; // 可选，将最后一个元素置0
}
4. 查找元素
// 线性查找
int linearSearch(int arr[], int size, int target) {for(int i = 0; i < size; i++) {if(arr[i] == target) {return i;}}return -1; // 未找到
}// 二分查找（要求数组已排序）
int binarySearch(int arr[], int size, int target) {int left = 0, right = size - 1;while(left <= right) {int mid = left + (right - left) / 2;if(arr[mid] == target) return mid;if(arr[mid] < target) left = mid + 1;else right = mid - 1;}return -1;
}
5. 排序数组
// 冒泡排序
void bubbleSort(int arr[], int size) {for(int i = 0; i < size - 1; i++) {for(int j = 0; j < size - i - 1; j++) {if(arr[j] > arr[j+1]) {// 交换int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}
第三部分 数组编程题例子
1. 寻找数组中的最大值和最小值
void findMinMax(int arr[], int size, int *min, int *max) {*min = *max = arr[0];for(int i = 1; i < size; i++) {if(arr[i] < *min) *min = arr[i];if(arr[i] > *max) *max = arr[i];}
}
2. 数组反转
void reverseArray(int arr[], int size) {for(int i = 0; i < size/2; i++) {int temp = arr[i];arr[i] = arr[size - i - 1];arr[size - i - 1] = temp;}
}
3. 移除数组中的重复元素
int removeDuplicates(int arr[], int size) {if(size == 0) return 0;int index = 0;for(int i = 1; i < size; i++) {if(arr[i] != arr[index]) {index++;arr[index] = arr[i];}}return index + 1;
}
4. 两数之和（找出数组中相加等于目标值的两个数）
void twoSum(int arr[], int size, int target) {for(int i = 0; i < size - 1; i++) {for(int j = i + 1; j < size; j++) {if(arr[i] + arr[j] == target) {printf("找到两数: %d 和 %d\n", arr[i], arr[j]);return;}}}printf("未找到符合条件的两个数\n");
}
5. 旋转数组
void rotateArray(int arr[], int size, int k) {k = k % size; // 处理k大于数组长度的情况// 反转整个数组reverseArray(arr, size);// 反转前k个元素reverseArray(arr, k);// 反转剩余元素reverseArray(arr + k, size - k);
}
6. 合并两个有序数组
void mergeSortedArrays(int arr1[], int size1, int arr2[], int size2, int result[]) {int i = 0, j = 0, k = 0;while(i < size1 && j < size2) {if(arr1[i] < arr2[j]) {result[k++] = arr1[i++];} else {result[k++] = arr2[j++];}}// 复制剩余元素while(i < size1) result[k++] = arr1[i++];while(j < size2) result[k++] = arr2[j++];
}
数组是编程中最基础也是最重要的数据结构之一，掌握数组的操作和常见算法对提升编程能力至关重要。通过不断练习这些基础题目，可以加深对数组特性的理解，并为学习更复杂的数据结构打下坚实基础。
