Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

用C写堆排序

  1. User

    用C写堆排序

  2. 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函数中测试堆排序并打印结果。

  3. User

    定义顺序表L的子表:L 中连续 个元素构成的顺序表称为表长 t 的L的子表。假设一个表长为n的顺序表L. 中有两个分别为长度 s 子表 S 和长度下 子表 R,S 和R不相交。设计算法,实现S 和R在L中的位置互换,并且互换后S 和R的元素均逆序排列。用C语言完成

  4. 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中位置的互换和元素的逆序排列。最后打印交换后的顺序表。