#include <stdio.h> #include <stdlib.h> #include <string.h> void merge(char** arr, int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; char** leftArr = (char**)malloc(n1 * sizeof(char*)); char** rightArr = (char**)malloc(n2 * sizeof(char*)); for (i = 0; i < n1; i++) leftArr[i] = arr[left + i]; for (j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j]; i = 0; j = 0; k = left; while (i < n1 && j < n2) { if (strlen(leftArr[i]) <= strlen(rightArr[j])) { arr[k] = leftArr[i]; i++; } else { arr[k] = rightArr[j]; j++; } k++; } while (i < n1) { arr[k] = leftArr[i]; i++; k++; } while (j < n2) { arr[k] = rightArr[j]; j++; k++; } free(leftArr); free(rightArr); } void mergeSort(char** arr, int n) { int currSize; int leftStart; for (currSize = 1; currSize <= n - 1; currSize = 2 * currSize) { for (leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) { int mid = leftStart + currSize - 1; int rightEnd = (leftStart + 2 * currSize - 1) < (n - 1) ? (leftStart + 2 * currSize - 1) : (n - 1); merge(arr, leftStart, mid, rightEnd); } } } int main() { char inputFileName[100]; char outputFileName[100]; printf("請輸入輸入檔案名稱:"); scanf("%s", inputFileName); printf("請輸入輸出檔案名稱:"); scanf("%s", outputFileName); FILE* inputFile = fopen(inputFileName, "r"); FILE* outputFile = fopen(outputFileName, "w"); if (inputFile == NULL) { printf("無法開啟輸入檔案。\n"); return 1; } if (outputFile == NULL) { printf("無法建立輸出檔案。\n"); return 1; } char** strings = NULL; char buffer[100]; int count = 0; while (fgets(buffer, sizeof(buffer), inputFile) != NULL) { buffer[strcspn(buffer, "\n")] = '\0'; strings = (char**)realloc(strings, (count + 1) * sizeof(char*)); strings[count] = (char*)malloc((strlen(buffer) + 1) * sizeof(char)); strcpy(strings[count], buffer); count++; } mergeSort(strings, count); for (int i = 0; i < count; i++) { fprintf(outputFile, "%s\n", strings[i]); } for (int i = 0; i < count; i++) { free(strings[i]); } free(strings); fclose(inputFile); fclose(outputFile); printf("排序完成並將結果寫入輸出檔案。\n"); return 0; }
时间: 2024-01-14 11:02:19 浏览: 29
这是一个使用归并排序对字符串数组进行排序的程序,主要包括merge函数和mergeSort函数。merge函数用于将两个有序的子数组合并成一个有序数组,mergeSort函数则通过递归地将数组划分成两个子数组,直到子数组中只有一个元素,然后再逐层合并子数组,最终得到完整的有序数组。程序中还包括从文件中读取字符串数组、输出有序字符串数组到文件中以及动态分配内存等操作,使得程序具有较好的可扩展性和灵活性。
相关问题
#include <stdio.h>#include <stdlib.h>void merge_sort(int *arr, int l, int r);void merge(int *arr, int l, int mid, int r);int main() { int n; scanf("%d", &n); int *arr = (int *) malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } merge_sort(arr, 0, n - 1); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } free(arr); return 0;}void merge_sort(int *arr, int l, int r) { if (l >= r) { return; } int mid = (l + r) / 2; merge_sort(arr, l, mid); merge_sort(arr, mid + 1, r); merge(arr, l, mid, r);}void merge(int *arr, int l, int mid, int r) { int i = l; int j = mid + 1; int k = 0; int *tmp = (int *) malloc((r - l + 1) * sizeof(int)); while (i <= mid && j <= r) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } while (i <= mid) { tmp[k++] = arr[i++]; } while (j <= r) { tmp[k++] = arr[j++]; } for (int p = 0; p < k; p++) { arr[l + p] = tmp[p]; } free(tmp);}输出格式错误,第一行为自然数n,第二行开始为n个自然数。 输出格式: 输出n个自然数的归并分类结果。 输入样例1: 5 9 6 2 6 3 输出样例1: 在这里给出相应的输出。例如: 2 3 6 6 9
你需要在输出样例的最后加上一个换行符,即在最后一个数字后面输出一个空格和一个换行符,代码如下:
```c
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n"); // 注意这里需要加上一个换行符
```
这样就能满足题目所要求的输出格式了。
改进以下代码:#include <stdio.h> #include <stdlib.h> #include <mpi.h> #define N 4000 #define TAG 0 void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[4000], R[4000]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } int main(int argc, char** argv) { int rank, size; int i, j, k; int A[N], B[N]; int block_size, start, end; double start_time, end_time; MPI_Status status; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); block_size = N / size; start = rank * block_size; end = start + block_size - 1; if (rank == size - 1) { end = N - 1; } if (rank == 0) { printf("Generating random array...\n"); for (i = 0; i < N; i++) { A[i] = rand() % 100000; } printf("Sorting array...\n"); } MPI_Barrier(MPI_COMM_WORLD); start_time = MPI_Wtime(); MPI_Scatter(A, block_size, MPI_INT, &B[start], block_size, MPI_INT, 0, MPI_COMM_WORLD); mergeSort(B, start, end); for (i = 0; i < size; i++) { if (rank == i) { MPI_Send(&B[start], block_size, MPI_INT, (rank + 1) % size, TAG, MPI_COMM_WORLD); } else if (rank == (i + 1) % size) { MPI_Recv(&B[start], block_size, MPI_INT, i, TAG, MPI_COMM_WORLD, &status); } } MPI_Barrier(MPI_COMM_WORLD); end_time = MPI_Wtime(); if (rank == 0) { printf("Writing result to file...\n"); FILE* fp; errno_t err; err = fopen_s(&fp, "sorted_array.txt", "w"); for (i = 0; i < N; i++) { fprintf(fp, "%d\n", B[i]); } fclose(fp); printf("Done!\n"); printf("Time used: %.6f seconds\n", end_time - start_time); } MPI_Finalize(); return 0; }
以下是改进后的代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#define N 4000
#define TAG 0
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int *L = (int*)malloc(n1 * sizeof(int));
int *R = (int*)malloc(n2 * sizeof(int));
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
free(L);
free(R);
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main(int argc, char** argv) {
int rank, size;
int i, j, k;
int *A, *B;
int block_size, start, end;
double start_time, end_time;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
block_size = N / size;
start = rank * block_size;
end = start + block_size - 1;
if (rank == size - 1) {
end = N - 1;
}
if (rank == 0) {
printf("Generating random array...\n");
A = (int*)malloc(N * sizeof(int));
for (i = 0; i < N; i++) {
A[i] = rand() % 100000;
}
printf("Sorting array...\n");
}
B = (int*)malloc(block_size * sizeof(int));
MPI_Barrier(MPI_COMM_WORLD);
start_time = MPI_Wtime();
MPI_Scatter(A, block_size, MPI_INT, B, block_size, MPI_INT, 0, MPI_COMM_WORLD);
mergeSort(B, 0, block_size - 1);
for (i = 0; i < size; i++) {
if (rank == i) {
MPI_Send(B, block_size, MPI_INT, (rank + 1) % size, TAG, MPI_COMM_WORLD);
}
else if (rank == (i + 1) % size) {
MPI_Recv(B, block_size, MPI_INT, i, TAG, MPI_COMM_WORLD, &status);
}
}
MPI_Barrier(MPI_COMM_WORLD);
end_time = MPI_Wtime();
if (rank == 0) {
printf("Writing result to file...\n");
FILE* fp;
errno_t err;
err = fopen_s(&fp, "sorted_array.txt", "w");
for (i = 0; i < N; i++) {
fprintf(fp, "%d\n", B[i]);
}
fclose(fp);
free(A);
printf("Done!\n");
printf("Time used: %.6f seconds\n", end_time - start_time);
}
free(B);
MPI_Finalize();
return 0;
}
```
改进点如下:
1. 在 `merge` 函数中使用动态内存分配,避免了栈溢出的问题。
2. 在 `main` 函数中使用动态内存分配,避免了数组过大时栈溢出的问题。
3. 在 `MPI_Scatter` 函数中直接传递数组指针,避免了在发送和接收数据时进行复制的问题。
4. 在 `MPI_Send` 和 `MPI_Recv` 函数中,发送和接收的数据都是 `B` 数组中的一段,因此直接传递 `B` 数组的指针即可。同时,在发送和接收数据时,将 `TAG` 设为 0,以避免与其他消息混淆。
5. 在结束程序前,释放 `A` 和 `B` 数组占用的内存。
相关推荐
![image/gif](https://img-home.csdnimg.cn/images/20210720083352.png)
![exe](https://img-home.csdnimg.cn/images/20210720083343.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)