在c++ WinAPI中使用HeapSort方法对数组排序时出错

我正在用c++和winapi在visual studio中做一个程序。在程序中，我必须注册人和疫苗的数据以创建疫苗接种卡，所有信息都存储在称为CARNET的双向链表中。
该程序必须具备的功能之一是，在窗口中，它通过QuickSort或HeapSort方法在列表框中组织人员的姓名，对于每种方法，我都有一个按钮。
在每个按钮中，所做的是清理列表框，然后计算列表的大小，创建一个数组，其中复制列表的信息，通过两种方法之一发送排列顺序，最后将排列打印在列表框中。在快速排序方法的情况下，排列是按人名排序的，在堆排序中，它是按标识号（id）排序的。
QuickSort方法已经准备好了，问题是HeapSort方法，当调用这个方法而不是通过HeapSort排序信息时，我通过QuickSort来排序，但到目前为止我不知道为什么。我已经检查了两个按钮都有各自的id，并被它调用。希望你能帮到我，谢谢你提前：）

struct CARDS {

    //Vaccine Data
    wchar_t no_dose[20]{};
    wchar_t price[20]{};
    wchar_t brand[40]{};

    //Person's data
    wchar_t name[60]{};
    wchar_t surname[30]{};
    wchar_t marital_status[40]{};
    wchar_t sex[40]{};
    wchar_t date_birth[40]{};
    wchar_t city[30];
    wchar_t state[30];
    wchar_t tel[20]{};
    

    //Dosage data
    SYSTEMTIME date_dosage{};
    wchar_t no_dosage[10]{};
    wchar_t place_vacc[100]{};
    
    //CARD id
    int id{};

    CARDS* next{};
    CARDS* prev{};
};

CARDS* Lstart = NULL; //Indicates the head of the list
CARDS* Lend = NULL; //Indicates the end of the list
//-----------------------------------------------------
//Quicksort
void change(CARDS* a, CARDS* b) {
    
    //Vaccine Data
    swap(a->no_dose, b->no_dose);
    swap(a->price, b->price);
    swap(a->brand, b->brand);
    
    //Person's data
    swap(a->name, b->name);
    swap(a->surname, b->surname);
    swap(a->marital_status, b->marital_status);
    swap(a->sex, b->sex);
    swap(a->date_birth, b->date_birth);
    swap(a->city, b->city);
    swap(a->state, b->state);
    swap(a->tel, b->tel);
    

    //Dosage data
    swap(a->date_dosage, b->date_dosage);
    swap(a->no_dose, b->no_dose);
    swap(a->place_vacc, b->place_vacc);
    
    //CARD id
    swap(a->id, b->id);
}

int partition(CARDS* arr, int start, int end) {
    wstring pivot = arr[end].name;
    int i = start - 1;

    for (int j = start; j < end; j++) {
        if (arr[j].name<=pivot) {
            i++;
            change(&arr[i], &arr[j]);
        }
    }

    change(&arr[i + 1], &arr[end]);
    return i + 1;
}

void quicksort(CARDS* arr, int start, int end) {
    if (start < end) {
        int index_pivot = partition(arr, start, end);
        quicksort(arr, start, index_pivot - 1);
        quicksort(arr, index_pivot + 1, end);
    }
}

//HeapSort
void heapify(CARDS* arr, int n, int i)
{
    int largest = i; 
    int l = 2 * i + 1; 
    int r = 2 * i + 2; 

    
    if (l<n && arr[l].id>arr[largest].id)
        largest = l;

    
    if (r<n && arr[r].id > arr[largest].id)
        largest = r;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        
        heapify(arr, n, largest);
    }
}

void heapSort(CARDS* arr, int n)
{
    
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    
    for (int i = n - 1; i > 0; i--) {
        
        swap(arr[0], arr[i]);
        
        
        heapify(arr, i, 0);
    }
}

BOOL CALLBACK Quicksort_call(HWND window, UINT message, WPARAM wParam, LPARAM lParam) {
    int select = NULL;
    wchar_t fe[50]{};
    wchar_t idString;
    int id;
    wstring ageString;
    switch (message) {

    case WM_COMMAND: {
        long opc = LOWORD(wParam);
        BAR_MENU(window, opc);
        switch (LOWORD(wParam)) {
        
        case IDC_BUTTON1: {
            SendDlgItemMessage(window, IDC_LIST2, LB_RESETCONTENT, NULL, 0);

            int size = 0;
            for (CARDS* aux = Lstart; aux != nullptr; aux = aux->next) {
                size++;
            }

            CARDS* arr = new CARDS[size];
            int index = 0;
            for (CARDS* aux = Lstart; aux != nullptr; aux = aux->next) {
                arr[index] = *aux;
                index++;
            }
            quicksort(arr, 0, size - 1);
            for (int i = 0; i < size; i++) {

                wchar_t full_name[150] = L"";
                wchar_t idStr[20];
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), arr[i].name);
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), L" ");
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), arr[i].surname);
                swprintf(idStr, sizeof(idStr) / sizeof(wchar_t), L"%d", arr[i].id);
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), L" ");
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), idStr);


                SendDlgItemMessage(window, IDC_LIST2, LB_ADDSTRING, NULL, (LPARAM)full_name);
            }
            delete[]arr;
            break;
        }
        case IDC_BUTTON2: {
            SendDlgItemMessage(window, IDC_LIST2, LB_RESETCONTENT, NULL, 0);

            int size2 = 0;
            for (CARDS* aux = Lstart; aux != nullptr; aux = aux->next) {
                size2++;
            }

            CARDS* arr2 = new CARDS[size2];
            int index = 0;
            for (CARDS* aux = Lstart; aux != nullptr; aux = aux->next) {
                arr2[index] = *aux;
                index++;
            }

            
            
            heapSort(arr2, size2);
            for (int i = 0; i < size2; i++) {

                wchar_t full_name[150] = L"";
                wchar_t idStr[20];
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), arr[i].name);
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), L" ");
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), arr[i].surname);
                swprintf(idStr, sizeof(idStr) / sizeof(wchar_t), L"%d", arr[i].id);
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), L" ");
                wcscat_s(full_name, sizeof(full_name) / sizeof(wchar_t), idStr);

                SendDlgItemMessage(window, IDC_LIST2, LB_ADDSTRING, NULL, (LPARAM)full_name);
            }


            delete[] arr2;
            break;
        }
}

        break;
    }
    case WM_INITDIALOG:
    {
        
        

        break;
    }
    }
    return false;
}

这不是一个真实的的答案，但更多的是一个例子，说明你的代码在当前的C中可能是什么样子：另一个提示：首先在一个单独的C静态库中编写这样的函数（不包括任何窗口头文件）。为该库编写一些测试。当它工作时，开始使用windows代码中的函数。

#include <algorithm>
#include <chrono>
#include <vector>
#include <string>
#include <iostream>

struct card_t
{
    std::uint64_t no_dose;  // be typesafe number of doses is not a string
    double price;           // be typesafe a price is not a string (consider using some currency type)
    std::string brand;      // replace all your wchar_t with std::wstring
    std::chrono::system_clock::time_point date_dosage{}; // use C++ time type
    std::size_t id;

    // never mix data with datastructures
    // so no next/prev. 
};

// no need to write change or swap function
// rely on copy assigment/copy construction for cards_t
// if needed you can use std::swap
// using pointers as much as you do is also not recommended.

//HeapSort
// CARDS* arr, int n -> std::vector<cards_t>&
// int i -> std::size_t i (integers can be negative which will 
// always be incorrect indices, use std::size_t for 
// datastructure sizes)
// variable naming, name variables according to WHAT they represent
// not HOW they are implemented
void heapify(std::vector<card_t>& cards, std::size_t i)
{
    std::size_t largest = i;
    std::size_t left = 2 * i + 1; // nothing wrong with writing 'left' 
    std::size_t right = 2 * i + 2;

    // add some extra '(' and ')' for readability
    // and to avoid typos causing bugs
    if ((left < cards.size()) && (cards[left].id > cards[largest].id))
    {
        largest = left;
    }

    if ((right < cards.size()) && (cards[right].id > cards[largest].id))
    {
        largest = right;
    }

    if (largest != i) 
    {
        // use C++ build in swap function
        // note this will be slow (even in your implementation)
        // since you are swapping full structs. Not pointers.
        std::swap(cards[i], cards[largest]);
        heapify(cards, largest);
    }
}

void heapSort(std::vector<card_t>& arr)
{
    if (arr.size() < 2ul) return; // never trust input, too small array cannot be sorted

    for (std::size_t i = arr.size() / 2 - 1; i >= 0; i--)
    {
        heapify(arr, i);
    }

    for (std::size_t i = arr.size() - 1; i > 0; i--) 
    {
        std::swap(arr[0], arr[i]);
        heapify(arr, 0);
    }
}

auto load_cards()
{
    using namespace std::string_literals; // for ""s std::string creation

    auto time = std::chrono::system_clock::now();

    // note a std::vector of std::unique_ptr<card_t> would be 
    // more efficient since sorting would then only have to swap
    // pointers to card_t not the whole card_t structure
    // but thats another refactor excercise for you

    std::vector<card_t> cards
    {
        { 1, 1.0, "brand1"s, time, 1ul}, // initialize structs members
        { 4, 4.0, "brand4"s, time, 4ul},
        { 3, 3.0, "brand3"s, time, 3ul},
        { 5, 5.0, "brand2"s, time, 5ul},
    };

    return cards;
}

std::ostream& operator<<(std::ostream& os, const std::vector<card_t>& cards)
{
    for (const auto& card : cards)
    {
        os << card.id << ":" << card.brand << "\n";
    }

    return os;
}

bool compare_cards_by_id(const card_t& lhs, const card_t& rhs)
{
    return lhs.id < rhs.id;
}

int main()
{
    // Note your heap algorithm does not terminate,
    // so still buggy. Consider using :
    // https://en.cppreference.com/w/cpp/algorithm/make_heap
    std::cout << "heap sort\n";
    auto cards = load_cards();
    heapSort(cards);
    std::cout << cards << "\n";

    // quicksort, by passing a predicate it is so
    // easy to sort by different 
    std::cout << "quick sort\n";
    cards = load_cards();
    std::sort(cards.begin(), cards.end(), compare_cards_by_id);

    return 0;
}

在c++ WinAPI中使用HeapSort方法对数组排序时出错

1条答案

相关问题

热门标签

最新问答