c随机生成两组整数,个数自定,分别采用数组存储和链表存储的方法,对其实现归并排序,输出最后的排序结果
时间: 2023-12-06 11:02:17 浏览: 30
好的,我来为您解答。
首先,我们需要随机生成两组整数,您可以使用 `rand()` 函数来生成随机数。这里以生成 10 个整数为例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 10
// 链表结点
typedef struct node {
int data;
struct node *next;
} Node;
// 生成随机数
void generate_random_nums(int arr[], int len) {
int i;
srand((unsigned) time(NULL));
for (i = 0; i < len; i++) {
arr[i] = rand() % 100;
}
}
// 打印数组
void print_array(int arr[], int len) {
int i;
for (i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// 打印链表
void print_list(Node *head) {
Node *p = head;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 数组归并排序
void merge_sort_array(int arr[], int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
merge_sort_array(arr, left, mid);
merge_sort_array(arr, mid + 1, right);
int i = left, j = mid + 1, k = 0;
int temp[MAXSIZE];
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = 0; i < k; i++) {
arr[left + i] = temp[i];
}
}
// 链表归并排序
Node *merge_sort_list(Node *head) {
if (!head || !head->next) {
return head;
}
Node *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
Node *head2 = slow->next;
slow->next = NULL;
Node *l1 = merge_sort_list(head);
Node *l2 = merge_sort_list(head2);
Node *p1 = l1, *p2 = l2, *p = NULL;
if (p1->data < p2->data) {
p = p1;
p1 = p1->next;
} else {
p = p2;
p2 = p2->next;
}
Node *head3 = p;
while (p1 && p2) {
if (p1->data < p2->data) {
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1) {
p->next = p1;
}
if (p2) {
p->next = p2;
}
return head3;
}
int main() {
int arr1[MAXSIZE], arr2[MAXSIZE];
Node *head1 = NULL, *head2 = NULL;
int i;
generate_random_nums(arr1, MAXSIZE);
generate_random_nums(arr2, MAXSIZE);
printf("数组1:");
print_array(arr1, MAXSIZE);
printf("数组2:");
print_array(arr2, MAXSIZE);
for (i = 0; i < MAXSIZE; i++) {
Node *p1 = (Node *) malloc(sizeof(Node));
Node *p2 = (Node *) malloc(sizeof(Node));
p1->data = arr1[i];
p1->next = head1;
head1 = p1;
p2->data = arr2[i];
p2->next = head2;
head2 = p2;
}
printf("链表1:");
print_list(head1);
printf("链表2:");
print_list(head2);
merge_sort_array(arr1, 0, MAXSIZE - 1);
printf("数组1排序结果:");
print_array(arr1, MAXSIZE);
merge_sort_array(arr2, 0, MAXSIZE - 1);
printf("数组2排序结果:");
print_array(arr2, MAXSIZE);
head1 = merge_sort_list(head1);
printf("链表1排序结果:");
print_list(head1);
head2 = merge_sort_list(head2);
printf("链表2排序结果:");
print_list(head2);
return 0;
}
```
其中,`merge_sort_array()` 函数实现了数组的归并排序,`merge_sort_list()` 函数实现了链表的归并排序。