c随机生成两组整数,,两个数组的内容不同,个数自定,分别采用数组存储和链表存储的方法,对其实现归并排序,输出最后的排序结果
时间: 2023-11-27 21:03:24 浏览: 42
好的,我来解答你的问题。
首先,针对你的问题,我需要说明的是,CSDN开发的ChitGPT并不是一个可以直接用来进行编程的工具或软件,它是一个AI模型,能够进行自然语言处理和生成自然语言回复。因此,我无法为你提供编程环境或代码编辑器。
不过,我可以给你提供一些思路和代码示例,以帮助你解决你的问题。
下面是使用数组存储实现归并排序的示例代码:
```
#include <stdio.h>
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[n1], R[n2];
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);
}
}
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
```
接下来是使用链表存储实现归并排序的示例代码:
```
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void moveNode(struct Node** destRef, struct Node** sourceRef) {
struct Node* newNode = *sourceRef;
*sourceRef = newNode->next;
newNode->next = *destRef;
*destRef = newNode;
}
struct Node* sortedMerge(struct Node* a, struct Node* b) {
struct Node dummyNode;
struct Node* tail = &dummyNode;
dummyNode.next = NULL;
while (1) {
if (a == NULL) {
tail->next = b;
break;
}
else if (b == NULL) {
tail->next = a;
break;
}
if (a->data <= b->data)
moveNode(&(tail->next), &a);
else
moveNode(&(tail->next), &b);
tail = tail->next;
}
return (dummyNode.next);
}
void frontBackSplit(struct Node* source,
struct Node** frontRef, struct Node** backRef) {
struct Node* fast;
struct Node* slow;
if (source == NULL || source->next == NULL) {
*frontRef = source;
*backRef = NULL;
}
else {
slow = source;
fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}
void mergeSort(struct Node** headRef) {
struct Node* head = *headRef;
struct Node* a;
struct Node* b;
if (head == NULL || head->next == NULL) {
return;
}
frontBackSplit(head, &a, &b);
mergeSort(&a);
mergeSort(&b);
*headRef = sortedMerge(a, b);
}
void push(struct Node** head_ref, int new_data) {
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int main() {
struct Node* head = NULL;
push(&head, 15);
push(&head, 10);
push(&head, 5);
push(&head, 20);
push(&head, 3);
push(&head, 2);
printf("Linked List before sorting \n");
printList(head);
mergeSort(&head);
printf("\nLinked List after sorting \n");
printList(head);
return 0;
}
```
希望这些示例代码能够对你有所帮助。如果你在使用中遇到了问题,可以随时向我提问。
阅读全文