gpt-3.5-turbo-0613· OpenAI
WildChat-4.8M (AI2)
用C写堆排序
- User
用C写堆排序
- Assistant
下面是用C语言实现堆排序的示例代码:
#include <stdio.h> void heapify(int arr[], int n, int i) { int largest = i; // 初始化最大元素为根节点 int left = 2*i + 1; // 左子节点索引 int right = 2*i + 2; // 右子节点索引 // 如果左子节点比根节点大,则更新最大元素索引 if (left < n && arr[left] > arr[largest]) largest = left; // 如果右子节点比根节点大,则更新最大元素索引 if (right < n && arr[right] > arr[largest]) largest = right; // 如果最大元素不是根节点,则交换根节点和最大元素 if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; // 递归调用堆化,直到堆化完成 heapify(arr, n, largest); } } void heapSort(int arr[], int n) { // 建立最大堆 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 一个个取出最大元素并放到数组末尾 for (int i=n-1; i>=0; i--) { // 将当前根节点与最后一个元素交换 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 重新堆化剩余的元素 heapify(arr, i, 0); } } // 打印数组元素 void printArray(int arr[], int n) { for (int i=0; i < n; ++i) printf("%d ", arr[i]); printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]); heapSort(arr, n); printf("排序后的数组:\n"); printArray(arr, n); }该代码实现了堆排序算法。首先,通过
heapify函数构建最大堆,然后利用heapify函数对堆进行排序。printArray函数用于打印排序后的数组。最后在main函数中测试堆排序并打印结果。 - User
定义顺序表L的子表:L 中连续 个元素构成的顺序表称为表长 t 的L的子表。假设一个表长为n的顺序表L. 中有两个分别为长度 s 子表 S 和长度下 子表 R,S 和R不相交。设计算法,实现S 和R在L中的位置互换,并且互换后S 和R的元素均逆序排列。用C语言完成
- Assistant
下面是用C语言实现题目要求的算法代码:
#include <stdio.h> typedef struct { int *data; // 存储数据的数组指针 int length; // 顺序表的长度 } SeqList; // 初始化顺序表 void InitList(SeqList *L, int length) { L->data = (int *)malloc(length * sizeof(int)); L->length = length; } // 交换数组中两个元素的位置 void Swap(SeqList *L, int i, int j) { int temp = L->data[i]; L->data[i] = L->data[j]; L->data[j] = temp; } // 将子表S和R在L中的位置互换,并且互换后S和R的元素均逆序排列 void ReverseSwap(SeqList *L, int start, int s, int r) { int i, j; // 交换S和R的位置 for (i = 0; i < s/2; i++) { Swap(L, start + i, start + s - 1 - i); } for (i = 0; i < r/2; i++) { Swap(L, start + s + i, start + s + r - 1 - i); } // 再次交换S和R各自内部的元素位置 for (i = 0; i < s/2; i++) { Swap(L, start + i, start + s - 1 - i); } for (i = 0; i < r/2; i++) { Swap(L, start + s + i, start + s + r - 1 - i); } } // 打印顺序表 void PrintList(SeqList *L) { int i; for (i = 0; i < L->length; i++) { printf("%d ", L->data[i]); } printf("\n"); } int main() { SeqList L; int n = 10; // 顺序表长度 int s = 3; // 子表S的长度 int r = 4; // 子表R的长度 int start = 3; // 子表S的起始位置 InitList(&L, n); // 初始化顺序表L的元素 for (int i = 0; i < n; i++) { L.data[i] = i + 1; } printf("交换前的顺序表: "); PrintList(&L); ReverseSwap(&L, start, s, r); printf("交换后的顺序表: "); PrintList(&L); return 0; }这段代码中,我们首先定义了一个顺序表的结构体
SeqList,其中包括一个指向存储数据的数组的指针data和顺序表的长度length。然后是初始化顺序表函数
InitList,用于为顺序表分配内存空间和初始化相关变量。接着是交换数组中两个元素的位置的函数
Swap。然后是核心的互换位置并逆序排列的函数
ReverseSwap,它首先通过循环交换S和R的位置,然后再次循环交换S和R各自内部的元素位置。最后是打印顺序表函数
PrintList,用于输出顺序表中的元素。在主函数中,我们根据题目给定的条件初始化顺序表L,并通过调用
ReverseSwap函数来实现S和R在L中位置的互换和元素的逆序排列。最后打印交换后的顺序表。