首页 文章

如何合并排序结构数组

提问于
浏览 709
1

我有一个结构数组

typedef struct BinaryTreeNode {
    BSTElementType userID;
    BSTElementType count;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
}BinaryTreeNode;

typedef BinaryTreeNode BSTNode;

我希望按升序合并排序数组 . 但是,当我执行合并时,没有任何变化 . 这是我用来创建struct数组的代码,以及 MergeSort 的函数调用 . maxUsers 是我从转换二叉树中的节点数得到的int,它应该是数组的最大数量 .

BSTNode *arr = (BSTNode *)malloc(maxUsers * sizeof(BSTNode));

MergeSort(arr, 0, maxUsers);

void Merge(BSTNode *arr, int low, int mid, int high) {
    int mergedSize = high - low + 1;
    BSTNode *temp = (BSTNode *)malloc(mergedSize * sizeof(BSTNode));
    int mergePos = 0;
    int leftPos = 0;
    int rightPos = 0;

    leftPos = low;
    rightPos = mid + 1;

    //printf("Starting Merge\n");

    while (leftPos <= high && rightPos <= mid) {
        if (arr[leftPos].count < arr[rightPos].count) {
            temp[mergePos].userID = arr[leftPos].userID;
            temp[mergePos].count = arr[leftPos].count;
            ++leftPos;
        }
        else {
            temp[mergePos].userID = arr[rightPos].userID;
            temp[mergePos].count = arr[rightPos].count;
            ++rightPos;
        }
        ++mergePos;
    }

    while (leftPos <= mid) {
        temp[mergePos].userID = arr[leftPos].userID;
        temp[mergePos].count = arr[leftPos].count;
        ++leftPos;
        ++mergePos;
    }

    while (rightPos <= high) {
        temp[mergePos].userID = arr[rightPos].userID;
        temp[mergePos].count = arr[rightPos].count;
        ++rightPos;
        ++mergePos;
    }

    for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
        arr[low + mergePos].userID = temp[mergePos].userID;
        arr[low + mergePos].count = temp[mergePos].count;
    }
}

void MergeSort(BSTNode *arr, int low, int high) {
    int mid = 0;

    if (low < high) {
        mid = (low + high) / 2;

        MergeSort(arr, low, mid);
        MergeSort(arr, mid + 1, high);

        Merge(arr, low, mid, high);
    }
}

任何提示或提示将不胜感激!

编辑:当我尝试编写一些printf语句时,我注意到这些值是负面的 . 但是存储在结构中的值是正数 . 出现此错误的原因是什么?

printf("Left Pos: %d, Right Pos: %d\n", leftPos, rightPos);
    while (leftPos <= mid && rightPos <= high) {
        printf("Left Pos count: %d, Right Pos count: %d\n", arr[leftPos].count, arr[rightPos].count);
        if (arr[leftPos].count < arr[rightPos].count) {
            temp[mergePos].userID = arr[leftPos].userID;
            temp[mergePos].count = arr[leftPos].count;
            ++leftPos;
        }

1 回答

  • 1

    需要做出两个重要的变化:

    • Merge 中,您有 while (leftPos <= high && rightPos <= mid) 但是您需要 while (leftPos <= mid && rightPos <= high) (反转左/右比较值) .

    • main() 中 - 或者至少是调用 MergeSort() 的代码,你有 MergeSort(arr, 0, maxUsers); 但是你需要 MergeSort(arr, 0, maxUsers-1); 因为传递的值必须是 arr[lo]arr[hi] 都是数组中的有效条目,当你传递 maxUsers 时你就是在告诉它 arr[maxUsers] 在没有的情况下有效 .

    第三个重要的变化是在退出 MergeSort() 之前添加 free(temp) .

    我还选择用简单的单行结构分配来替换你的多行分配 .

    这是代码的调试版本,但调试打印全部被注释掉了 . 当我解决问题时,一切都很活跃 . 在我调试时,即使我使用 rand() 生成数据,我也没有故意使用 srand() ,所以我在每次运行时都使用相同的数据 . 当我确信代码是干净的,那么我使用 srand(time(0)); 并改变了数组的大小,但在调试时,稳定性很重要 .

    #include <assert.h>
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <time.h>
    
    typedef int BSTElementType;
    
    typedef struct BinaryTreeNode
    {
        BSTElementType userID;
        BSTElementType count;
        struct BinaryTreeNode *left;
        struct BinaryTreeNode *right;
    } BinaryTreeNode;
    
    typedef BinaryTreeNode BSTNode;
    
    static void PrintArray(const char *tag, int n, BSTNode *array)
    {
        printf("%s:\n", tag);
        for (int i = 0; i < n; i++)
            printf("%2d: u = %4d, c = %2d\n", i, array[i].userID, array[i].count);
        putchar('\n');
        fflush(stdout);
    }
    
    static
    void Merge(BSTNode *arr, int low, int mid, int high)
    {
        int mergedSize = high - low + 1;
        BSTNode *temp = (BSTNode *)malloc(mergedSize * sizeof(BSTNode));
        int mergePos = 0;
        int leftPos = low;
        int rightPos = mid + 1;
    
        //printf("-->> %s: lo = %d, md = %d, hi = %d, sz = %d\n", __func__, low, mid, high, mergedSize);
    
        //printf("L = %d, M = %d; R = %d, H = %d\n", leftPos, mid, rightPos, high);
        while (leftPos <= mid && rightPos <= high)      // Key change
        {
            //printf("a[%d].c = %d <=> a[%d].c = %d\n", leftPos, arr[leftPos].count,
            //       rightPos, arr[rightPos].count);
            if (arr[leftPos].count < arr[rightPos].count)
            {
                //printf("L1: a[%d].c = %d\n", leftPos, arr[leftPos].count);
                temp[mergePos++] = arr[leftPos++];
            }
            else
            {
                //printf("R1: a[%d].c = %d\n", rightPos, arr[rightPos].count);
                temp[mergePos++] = arr[rightPos++];
            }
            //printf("L = %d, M = %d; R = %d, H = %d\n", leftPos, mid, rightPos, high);
        }
    
        while (leftPos <= mid)
        {
            //printf("L2: a[%d].c = %d\n", leftPos, arr[leftPos].count);
            temp[mergePos++] = arr[leftPos++];
        }
    
        while (rightPos <= high)
        {
            //printf("R2: a[%d].c = %d\n", rightPos, arr[rightPos].count);
            temp[mergePos++] = arr[rightPos++];
        }
    
        assert(mergePos == mergedSize);
    
        //PrintArray("merged", mergedSize, temp);
    
        for (mergePos = 0; mergePos < mergedSize; ++mergePos)
            arr[low + mergePos] = temp[mergePos];
    
        free(temp);         // Key change
        //printf("<<-- %s: lo = %d, md = %d, hi = %d, sz = %d\n", __func__, low, mid, high, mergedSize);
    }
    
    static
    void MergeSort(BSTNode *arr, int low, int high)
    {
        if (low < high)
        {
            int mid = (low + high) / 2;
            //printf("-->> %s: lo = %d, md = %d, hi = %d\n", __func__, low, mid, high);
    
            MergeSort(arr, low, mid);
            MergeSort(arr, mid + 1, high);
    
            Merge(arr, low, mid, high);
            //printf("<<-- %s: lo = %d, md = %d, hi = %d\n", __func__, low, mid, high);
        }
    }
    
    int main(void)
    {
        /* Unstable when testing */
        //srand(time(0));
        //int maxUsers = rand() % 20 + 5;
        /* Stable while debugging */
        int maxUsers = 10;
    
        BSTNode *arr = (BSTNode *)malloc(maxUsers * sizeof(BSTNode));
    
        for (int i = 0; i < maxUsers; i++)
        {
            arr[i].userID = rand() % 100 * 100;
            arr[i].count = rand() % 10;
            arr[i].left = 0;
            arr[i].right = 0;
        }
    
        PrintArray("Before", maxUsers, arr);
        MergeSort(arr, 0, maxUsers - 1);        // Key change
        PrintArray("After", maxUsers, arr);
    
        free(arr);
    
        return 0;
    }
    

    其中一个关键的调试观察是 Merge() 中的主循环从未进入过;这是对第一个问题的强烈暗示 . Oddball数据是第二个问题的强烈暗示 . 主要数据都在很好的范围内控制 .

    样本输出(YMMV,因为您可能没有使用完全相同的PRNG):

    Before:
     0: u = 7900, c =  9
     1: u = 3900, c =  5
     2: u = 5500, c =  3
     3: u = 4300, c =  4
     4: u = 3600, c =  6
     5: u =  900, c =  2
     6: u = 5300, c =  9
     7: u = 6300, c =  1
     8: u = 7900, c =  8
     9: u = 4400, c =  3
    10: u = 9400, c =  0
    
    After:
     0: u = 9400, c =  0
     1: u = 6300, c =  1
     2: u =  900, c =  2
     3: u = 4400, c =  3
     4: u = 5500, c =  3
     5: u = 4300, c =  4
     6: u = 3900, c =  5
     7: u = 3600, c =  6
     8: u = 7900, c =  8
     9: u = 5300, c =  9
    10: u = 7900, c =  9
    

    样本运行(随机数据量):

    Before:
     0: u = 3300, c =  1
     1: u =  200, c =  8
     2: u = 7500, c =  6
     3: u = 2700, c =  8
     4: u = 8300, c =  3
     5: u = 6900, c =  3
     6: u =  400, c =  3
     7: u = 1100, c =  6
     8: u = 3600, c =  5
     9: u = 2100, c =  7
    10: u = 9400, c =  9
    11: u = 7300, c =  0
    12: u = 1800, c =  4
    13: u = 8200, c =  9
    14: u = 8400, c =  4
    15: u = 9600, c =  0
    16: u = 4400, c =  7
    17: u = 2900, c =  0
    18: u = 4300, c =  4
    19: u = 6500, c =  9
    20: u = 6800, c =  6
    21: u = 8000, c =  2
    22: u = 6000, c =  5
    
    After:
     0: u = 2900, c =  0
     1: u = 9600, c =  0
     2: u = 7300, c =  0
     3: u = 3300, c =  1
     4: u = 8000, c =  2
     5: u =  400, c =  3
     6: u = 6900, c =  3
     7: u = 8300, c =  3
     8: u = 4300, c =  4
     9: u = 8400, c =  4
    10: u = 1800, c =  4
    11: u = 6000, c =  5
    12: u = 3600, c =  5
    13: u = 6800, c =  6
    14: u = 1100, c =  6
    15: u = 7500, c =  6
    16: u = 4400, c =  7
    17: u = 2100, c =  7
    18: u = 2700, c =  8
    19: u =  200, c =  8
    20: u = 6500, c =  9
    21: u = 8200, c =  9
    22: u = 9400, c =  9
    

    启用调试,固定大小的运行:

    Before:
     0: u =  700, c =  9
     1: u = 7300, c =  8
     2: u = 3000, c =  2
     3: u = 4400, c =  8
     4: u = 2300, c =  9
     5: u = 4000, c =  5
     6: u = 9200, c =  2
     7: u = 8700, c =  3
     8: u = 2700, c =  9
     9: u = 4000, c =  2
    
    -->> MergeSort: lo = 0, md = 4, hi = 9
    -->> MergeSort: lo = 0, md = 2, hi = 4
    -->> MergeSort: lo = 0, md = 1, hi = 2
    -->> MergeSort: lo = 0, md = 0, hi = 1
    -->> Merge: lo = 0, md = 0, hi = 1, sz = 2
    L = 0, M = 0; R = 1, H = 1
    a[0].c = 9 <=> a[1].c = 8
    R1: a[1].c = 8
    L = 0, M = 0; R = 2, H = 1
    L2: a[0].c = 9
    <<-- Merge: lo = 0, md = 0, hi = 1, sz = 2
    <<-- MergeSort: lo = 0, md = 0, hi = 1
    -->> Merge: lo = 0, md = 1, hi = 2, sz = 3
    L = 0, M = 1; R = 2, H = 2
    a[0].c = 8 <=> a[2].c = 2
    R1: a[2].c = 2
    L = 0, M = 1; R = 3, H = 2
    L2: a[0].c = 8
    L2: a[1].c = 9
    <<-- Merge: lo = 0, md = 1, hi = 2, sz = 3
    <<-- MergeSort: lo = 0, md = 1, hi = 2
    -->> MergeSort: lo = 3, md = 3, hi = 4
    -->> Merge: lo = 3, md = 3, hi = 4, sz = 2
    L = 3, M = 3; R = 4, H = 4
    a[3].c = 8 <=> a[4].c = 9
    L1: a[3].c = 8
    L = 4, M = 3; R = 4, H = 4
    R2: a[4].c = 9
    <<-- Merge: lo = 3, md = 3, hi = 4, sz = 2
    <<-- MergeSort: lo = 3, md = 3, hi = 4
    -->> Merge: lo = 0, md = 2, hi = 4, sz = 5
    L = 0, M = 2; R = 3, H = 4
    a[0].c = 2 <=> a[3].c = 8
    L1: a[0].c = 2
    L = 1, M = 2; R = 3, H = 4
    a[1].c = 8 <=> a[3].c = 8
    R1: a[3].c = 8
    L = 1, M = 2; R = 4, H = 4
    a[1].c = 8 <=> a[4].c = 9
    L1: a[1].c = 8
    L = 2, M = 2; R = 4, H = 4
    a[2].c = 9 <=> a[4].c = 9
    R1: a[4].c = 9
    L = 2, M = 2; R = 5, H = 4
    L2: a[2].c = 9
    <<-- Merge: lo = 0, md = 2, hi = 4, sz = 5
    <<-- MergeSort: lo = 0, md = 2, hi = 4
    -->> MergeSort: lo = 5, md = 7, hi = 9
    -->> MergeSort: lo = 5, md = 6, hi = 7
    -->> MergeSort: lo = 5, md = 5, hi = 6
    -->> Merge: lo = 5, md = 5, hi = 6, sz = 2
    L = 5, M = 5; R = 6, H = 6
    a[5].c = 5 <=> a[6].c = 2
    R1: a[6].c = 2
    L = 5, M = 5; R = 7, H = 6
    L2: a[5].c = 5
    <<-- Merge: lo = 5, md = 5, hi = 6, sz = 2
    <<-- MergeSort: lo = 5, md = 5, hi = 6
    -->> Merge: lo = 5, md = 6, hi = 7, sz = 3
    L = 5, M = 6; R = 7, H = 7
    a[5].c = 2 <=> a[7].c = 3
    L1: a[5].c = 2
    L = 6, M = 6; R = 7, H = 7
    a[6].c = 5 <=> a[7].c = 3
    R1: a[7].c = 3
    L = 6, M = 6; R = 8, H = 7
    L2: a[6].c = 5
    <<-- Merge: lo = 5, md = 6, hi = 7, sz = 3
    <<-- MergeSort: lo = 5, md = 6, hi = 7
    -->> MergeSort: lo = 8, md = 8, hi = 9
    -->> Merge: lo = 8, md = 8, hi = 9, sz = 2
    L = 8, M = 8; R = 9, H = 9
    a[8].c = 9 <=> a[9].c = 2
    R1: a[9].c = 2
    L = 8, M = 8; R = 10, H = 9
    L2: a[8].c = 9
    <<-- Merge: lo = 8, md = 8, hi = 9, sz = 2
    <<-- MergeSort: lo = 8, md = 8, hi = 9
    -->> Merge: lo = 5, md = 7, hi = 9, sz = 5
    L = 5, M = 7; R = 8, H = 9
    a[5].c = 2 <=> a[8].c = 2
    R1: a[8].c = 2
    L = 5, M = 7; R = 9, H = 9
    a[5].c = 2 <=> a[9].c = 9
    L1: a[5].c = 2
    L = 6, M = 7; R = 9, H = 9
    a[6].c = 3 <=> a[9].c = 9
    L1: a[6].c = 3
    L = 7, M = 7; R = 9, H = 9
    a[7].c = 5 <=> a[9].c = 9
    L1: a[7].c = 5
    L = 8, M = 7; R = 9, H = 9
    R2: a[9].c = 9
    <<-- Merge: lo = 5, md = 7, hi = 9, sz = 5
    <<-- MergeSort: lo = 5, md = 7, hi = 9
    -->> Merge: lo = 0, md = 4, hi = 9, sz = 10
    L = 0, M = 4; R = 5, H = 9
    a[0].c = 2 <=> a[5].c = 2
    R1: a[5].c = 2
    L = 0, M = 4; R = 6, H = 9
    a[0].c = 2 <=> a[6].c = 2
    R1: a[6].c = 2
    L = 0, M = 4; R = 7, H = 9
    a[0].c = 2 <=> a[7].c = 3
    L1: a[0].c = 2
    L = 1, M = 4; R = 7, H = 9
    a[1].c = 8 <=> a[7].c = 3
    R1: a[7].c = 3
    L = 1, M = 4; R = 8, H = 9
    a[1].c = 8 <=> a[8].c = 5
    R1: a[8].c = 5
    L = 1, M = 4; R = 9, H = 9
    a[1].c = 8 <=> a[9].c = 9
    L1: a[1].c = 8
    L = 2, M = 4; R = 9, H = 9
    a[2].c = 8 <=> a[9].c = 9
    L1: a[2].c = 8
    L = 3, M = 4; R = 9, H = 9
    a[3].c = 9 <=> a[9].c = 9
    R1: a[9].c = 9
    L = 3, M = 4; R = 10, H = 9
    L2: a[3].c = 9
    L2: a[4].c = 9
    <<-- Merge: lo = 0, md = 4, hi = 9, sz = 10
    <<-- MergeSort: lo = 0, md = 4, hi = 9
    After:
     0: u = 4000, c =  2
     1: u = 9200, c =  2
     2: u = 3000, c =  2
     3: u = 8700, c =  3
     4: u = 4000, c =  5
     5: u = 4400, c =  8
     6: u = 7300, c =  8
     7: u = 2700, c =  9
     8: u = 2300, c =  9
     9: u =  700, c =  9
    

    该代码在Mac OS X 10.11.6上的GCC 6.1.0和Valgrind 3.12-SVN下编译和运行 .

相关问题