数据结构HW1

数据结构HW1"/>

数据结构HW1

 1.(10分) 编程实现矩阵乘法（源文件命名matrix.c）。函数定义如下：

#include<stdio.h>// 定义矩阵的最大维度
#define MAX_ROWS 100
#define MAX_COLS 100// 矩阵乘法函数
int matmult(int a[][MAX_COLS], int b[][MAX_COLS], int c[][MAX_COLS], int rows_a, int cols_a,int rows_b,  int cols_b) {if (cols_a != rows_b) {printf("矩阵维度不匹配，无法相乘。\n");return 0;}for (int i = 0; i < rows_a; i++) {for (int j = 0; j < cols_b; j++) {c[i][j] = 0;for (int k = 0; k < cols_a; k++) {c[i][j] += a[i][k] * b[k][j];}}}return 1; // 成功执行矩阵乘法
}
int main(){int rows_a, cols_a, rows_b, cols_b;printf("输入矩阵A的行数和列数:");scanf("%d %d",&rows_a, &cols_a);printf("输入矩阵B的行数和列数:");scanf("%d %d",&rows_b, &cols_b);// 检查是否为空矩阵if (cols_a == rows_a == 0 || cols_b == rows_b == 0){printf("输入为空矩阵。\n");return 1;}// 检查维度是否匹配if (cols_a != rows_b) {printf("矩阵维度不匹配，无法相乘。\n");return 1;}// 定义矩阵A,B和结果矩阵Cint matrixA[MAX_ROWS][MAX_COLS];int matrixB[MAX_ROWS][MAX_COLS];int matrixC[MAX_ROWS][MAX_COLS];printf("输入矩阵A的元素:\n");for (int i = 0; i < rows_a; i++) {for (int j = 0; j < cols_a; j++) {scanf("%d", &matrixA[i][j]);}}printf("输入矩阵B的元素:\n");for (int i = 0; i < rows_b; i++) {for (int j = 0; j < cols_b; j++) {scanf("%d", &matrixB[i][j]);}}if (matmult(matrixA, matrixB, matrixC, rows_a, cols_a,rows_b, cols_b)) {printf("矩阵乘法的结果矩阵C为:\n");for (int i = 0; i < rows_a; i++) {for (int j = 0; j < cols_b; j++) {printf("%d ", matrixC[i][j]);}printf("\n");}}return 0;
}

2. (10分) 编程实现二分查找（源文件命名binary_search.c）。函数定义如下：

#include <stdio.h>int b_search(int a[], int x, int left, int right) {// 如果左边界大于右边界，说明目标元素不在数组中if (left > right) {return -1;}// 计算中间索引int mid = left + (right - left) / 2;// 如果中间元素等于目标元素，返回中间索引if (a[mid] == x) {return mid;}// 如果中间元素大于目标元素，在左半边继续搜索if (a[mid] > x) {return b_search(a, x, left, mid - 1);}// 否则，在右半边继续搜索return b_search(a, x, mid + 1, right);
}int main() {int n , i = 0;printf("请输入数组中元素的个数：");scanf("%d",&n);if(n==0){//判断空数组printf("判断为空数组！");return 0;}int a[n];printf("请输入数组的元素：");for(i=0;i<n;i++){scanf("%d",&a[i]);}int x;printf("请输入你想要查找的数：");scanf("%d",&x);int result = b_search(a, x, 0, n - 1);if (result != -1) {printf("目标元素 %d 在数组中的索引位置是 %d\n", x, result);} else {printf("目标元素 %d 未在数组中找到\n", x);}return 0;
}

3. (20分) 编程实现课件《绪论》中的“引例3”，需实现三种方法且进行比较（源文件命名search.c）。问题的输入是两个数组int a[], int x[]，长度分别是n, m；输出int ans[]是一个取值+1或-1的数组，ans[i]=1代表x[i]在a[]中出现过，否则为-1。a[]和x[]数组中的元素自行随机生成（需调用C语言中的随机数生成库）。试生成不同量级的数组长度，比较三种方法的实际运行时间（需调用C语言中的计时库），完成下表：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>// 暴力寻找方法
void brute_force_search(int a[], int x[], int ans[], int n, int m) {for (int i = 0; i < m; i++) {ans[i] = -1;  // 初始化ans数组为-1for (int j = 0; j < n; j++) {if (x[i] == a[j]) {ans[i] = 1;  // 如果找到x[i]，将ans[i]设置为1break;}}}
}// 二分查找方法
int binary_search(int a[], int x, int left, int right) {if (left > right) {return -1;}int mid = left + (right - left) / 2;if (a[mid] == x) {return mid;} else if (a[mid] > x) {return binary_search(a, x, left, mid - 1);} else {return binary_search(a, x, mid + 1, right);}
}// 使用哈希集方法
void hash_set_search(int a[], int x[], int ans[], int n, int m) {// 创建哈希集合int max_element = 0; // 计算a数组中的最大元素for (int i = 0; i < n; i++) {if (a[i] > max_element) {max_element = a[i];}}int *hash_set = (int *)malloc((max_element + 1) * sizeof(int));if (hash_set == NULL) {fprintf(stderr, "内存分配失败\n");exit(1);}for (int i = 0; i < n; i++) {hash_set[a[i]] = 1;}for (int i = 0; i < m; i++) {ans[i] = hash_set[x[i]];}free(hash_set); // 释放哈希集合内存
}int main() {// 随机数种子，用于初始化伪随机数生成器srand(time(NULL));int n = 100; // 数组a的长度int m = 100;  // 数组x的长度// 创建数组a和x，并初始化为随机数int *a = (int *)malloc(n * sizeof(int));int *x = (int *)malloc(m * sizeof(int));if (a == NULL || x == NULL) {fprintf(stderr, "内存分配失败\n");return 1;}for (int i = 0; i < n; i++) {a[i] = rand() % 10000;  // 随机生成0到9999之间的整数}for (int i = 0; i < m; i++) {x[i] = rand() % 10000;  // 随机生成0到9999之间的整数}// 创建用于存储结果的数组ansint *ans = (int *)malloc(m * sizeof(int));if (ans == NULL) {fprintf(stderr, "内存分配失败\n");return 1;}// 测量暴力寻找方法的运行时间clock_t start_time = clock();brute_force_search(a, x, ans, n, m);clock_t end_time = clock();double elapsed_time = (double)(end_time - start_time) / CLOCKS_PER_SEC;printf("暴力寻找方法运行时间: %lf 秒\n", elapsed_time);// 清空ans数组for (int i = 0; i < m; i++) {ans[i] = -1;}// 测量二分查找方法的运行时间start_time = clock();for (int i = 0; i < m; i++) {int result = binary_search(a, x[i], 0, n - 1);if (result != -1) {ans[i] = 1;}}end_time = clock();elapsed_time = (double)(end_time - start_time) / CLOCKS_PER_SEC;printf("二分查找方法运行时间: %lf 秒\n", elapsed_time);// 清空ans数组for (int i = 0; i < m; i++) {ans[i] = -1;}// 测量使用哈希集方法的运行时间start_time = clock();hash_set_search(a, x, ans, n, m);end_time = clock();elapsed_time = (double)(end_time - start_time) / CLOCKS_PER_SEC;printf("使用哈希集方法运行时间: %lf 秒\n", elapsed_time);// 释放动态分配的内存free(a);free(x);free(ans);return 0;
}