在C++中編寫一個具有最大堆結構的優先級隊列

Question

我正在寫一個具有最大堆結構的優先級隊列作爲學校的分配。我可以將它寫成數組，也可以使用矢量。我選擇了一個矢量。所以分配是這樣的，用戶從他想要添加，打印或查看元素的菜單中選擇選項。當用戶選擇添加時，他會詢問誰想要添加，教師，學生或TA。他可以輸入我，我，t，T，S，s。教師具有最高的優先級，如果用戶選擇打印選項並且隊列中有一位教練，他將首先進入。電訊局長具有第二高的優先權，如果隊列中有助教和學生，電訊局長會先走。如果有多於一個教師，則該隊列將作爲普通隊列。我寫了大部分，或嘗試過。我從我的教科書中獲得了我的最大堆實現，因爲它們提供了一個。現在的問題是，當我在優先級隊列中有多個項目，並且我選擇打印時，它崩潰並給我一個向量下標超出範圍的異常。我一直試圖解決它，沒有運氣。另外，當我嘗試打印隊列中的元素或打印它們時，它需要用作者的姓名說出作業＃。有人可以幫助我找到一種方法來實現這一點。

#pragma once 
#include <vector> 

struct Heap 
{ 
    std::vector<int> m_elements; 

    void ReHeapDown(int, int); 
    void ReHeapUp(int, int); 
    void Swap(int& a, int& b); 
}; 

    #include "heap.h" 

void Heap::ReHeapDown(int index, int bottom) 
{ 
    int maxChild, rightChild, leftChild; 

    leftChild = index * 2 + 1; 
    rightChild = index * 2 + 2; 

    if (leftChild <= bottom) 
    { 
     if (leftChild == bottom) 
      maxChild = leftChild; 
     else 
     { 
      if (m_elements[leftChild] <= m_elements[rightChild]) 
       maxChild = rightChild; 
      else 
       maxChild = leftChild; 
     } 
     if (m_elements[index] < m_elements[maxChild]) 
     { 
      Swap(m_elements[index], m_elements[maxChild]); 
      ReHeapDown(maxChild, bottom); 
     } 
    } 
} 

void Heap::ReHeapUp(int index, int bottom) 
{ 
    int parent; 

    if (bottom > index) 
    { 
     parent = (bottom - 1)/2; 
     if (m_elements[parent] < m_elements[bottom]) 
     { 
      Swap(m_elements[parent], m_elements[bottom]); 
      ReHeapUp(index, parent); 
     } 
    } 
} 

void Heap::Swap(int& a, int& b) 
{ 
    int temp; 
    temp = a; 
    a = b; 
    b = temp; 
} 

    #include <iostream> 
#include "heap.h" 
#pragma once 

class PQTYPE 
{ 

private: 
    Heap m_Items; 

public: 
    bool isEmpty() const; 
    void Enqueue(int, std::string); 
    void Dequeue(int, std::string); 
    void printElements(); 
}; 



#include "pqtype.h" 

bool PQTYPE::isEmpty() const 
{ 
    return m_Items.m_elements.empty(); 
} 

void PQTYPE::Enqueue(int newItem, std::string lName) 
{ 

    if (lName == "Student") 
    { 
     m_Items.m_elements.push_back(newItem); 
     m_Items.ReHeapUp(0, m_Items.m_elements.size() - 1); 
    } 
    else if (lName == "TA") 
    { 
     m_Items.m_elements.push_back(newItem); 
     m_Items.ReHeapUp(0, m_Items.m_elements.size() - 1); 
    } 
    else if (lName == "Instructor") 
    { 
     m_Items.m_elements.push_back(newItem); 
     m_Items.ReHeapUp(0, m_Items.m_elements.size() - 1); 
    } 
} 

void PQTYPE::Dequeue(int item, std::string lName) 
{ 
    if (isEmpty()) 
     std::cout << "No jobs to print\n"; 
    else 
    { 
     m_Items.m_elements[0] = m_Items.m_elements.back(); 
     std::cout << "Now printing Job#" << m_Items.m_elements[item - 1] << " " << lName.c_str() << std::endl; 
     m_Items.m_elements.pop_back(); 
     m_Items.ReHeapDown(0, item - 1); 
    } 
} 

void PQTYPE::printElements() 
{ 
    if (isEmpty()) 
     std::cout << "No jobs to print\n"; 
    else 
    { 
     for (int i = 0; i < m_Items.m_elements.size(); i++) 
     { 
      std::cout << "Job#" << m_Items.m_elements[i] << std::endl; 
     } 
    } 
} 


#include"pqtype.h" 

struct Person 
{ 
    int m_priority; 
    std::string m_name; 

    Person() 
    { 
     m_priority = 0; 
     m_name = " "; 
    } 
}; 

int showMenu(); 
void addJobs(PQTYPE&, Person&); 
void printJobs(PQTYPE&, Person&); 
void viewJobs(PQTYPE&); 

int main() 
{ 

    int option; 
    Person p; 
    PQTYPE pq; 

    do 
    { 
     option = showMenu(); 

     switch (option) 
     { 
     case 1: addJobs(pq, p); 
     break; 
     case 2: printJobs(pq, p); 
     break; 
     case 3: viewJobs(pq); 
     break; 
     case 4: 
     break; 
     default: std::cout << "Wrong input\n"; 
     break; 
     } 

    } while (option != 4); 


    return 0; 
} 

int showMenu() 
{ 
    int choice; 
    std::cout << " 1.)Add Job\n"; 
    std::cout << " 2.)Print Job\n"; 
    std::cout << " 3.)View Jobs\n"; 
    std::cout << " 4.)Exit\n"; 
    std::cout << " Enter Choice: "; 
    std::cin >> choice; 

    return choice; 
} 

void addJobs(PQTYPE& pq, Person& per) 
{ 
    char jobChoice; 

    std::cout << "Who is the job for (Instructor(i or I), TA(t or T), Student(s or S) :"; 
    std::cin >> jobChoice; 

    if (jobChoice == 'S' || jobChoice == 's') 
    { 
     per.m_priority++; 
     per.m_name = "Student"; 
     pq.Enqueue(per.m_priority, per.m_name); 
    } 
    else if (jobChoice == 'T' || jobChoice == 't') 
    { 
     per.m_priority++; 
     per.m_name = "TA"; 
     pq.Enqueue(per.m_priority, per.m_name); 
    } 
    if (jobChoice == 'I' || jobChoice == 'i') 
    { 
     per.m_priority++; 
     per.m_name = "Instructor"; 
     pq.Enqueue(per.m_priority, per.m_name); 
    } 
} 

void printJobs(PQTYPE& pq, Person& p) 
{ 
    pq.Dequeue(p.m_priority, p.m_name); 
} 

void viewJobs(PQTYPE& pq) 
{ 
    pq.printElements(); 
} 

Answer 1

在您的原始代碼中，在Dequeue（）中用於訪問該向量的索引似乎沒有以正確的方式初始化。假設您已將兩個條目添加到列表中。在這種情況下，main（）中的P.m_priority的值爲2.現在您第一次調用printJobs（）。 printJobs（）調用pq.Dequeue（p.m_priority，p.m_name），所以Dequeue（）獲取p.m_priority作爲其參數item。請記住，項目有2

m_Items.m_elements[0] = m_Items.m_elements.back(); 
std::cout << "Now printing Job#" << m_Items.m_elements[item - 1] << " " << lName.c_str() << std::endl; 
m_Items.m_elements.pop_back(); 

您使用項目的索引訪問您的std ::矢量值 - 1。這是第一次，因爲你的列表中有兩個元素。在這個調用中，還有一個pop_back（）在你的列表中完成，它將它的大小減1。下一次調用printJobs（）時，給定的參數項目不會更改，它仍然具有值2.當您訪問您的Itemlist時，不再有索引1，並且下標超出範圍異常將被拋出。

在原始版本中沒有固定的優先級分配給三種入口類型，所以我添加了這些（請參閱addJobs（））。

因此，一個可能的解決方案來存儲人的名字看起來是這樣的：

struct Person 
{ 
    int m_priority; 
    std::string m_name; 

    Person() 
    { 
     m_priority = 0; 
     m_name = " "; 
    } 
}; 

struct Heap 
{ 
    std::vector<Person> m_elements; 

    void ReHeapDown(int, int); 
    void ReHeapUp(int, int); 
    void Swap(Person& a, Person& b); 
}; 

void Heap::ReHeapDown(int index, int bottom) 
{ 
    int maxChild, rightChild, leftChild; 

    leftChild = index * 2 + 1; 
    rightChild = index * 2 + 2; 

    if (leftChild <= bottom) 
    { 
     if (leftChild == bottom) 
      maxChild = leftChild; 
     else 
     { 
      if (m_elements[leftChild].m_priority <= m_elements[rightChild].m_priority) 
       maxChild = rightChild; 
      else 
       maxChild = leftChild; 
     } 
     if (m_elements[index].m_priority < m_elements[maxChild].m_priority) 
     { 
      Swap(m_elements[index], m_elements[maxChild]); 
      ReHeapDown(maxChild, bottom); 
     } 
    } 
} 

void Heap::ReHeapUp(int index, int bottom) 
{ 
    int parent; 

    if (bottom > index) 
    { 
     parent = (bottom - 1)/2; 
     if (m_elements[parent].m_priority < m_elements[bottom].m_priority) 
     { 
      Swap(m_elements[parent], m_elements[bottom]); 
      ReHeapUp(index, parent); 
     } 
    } 
} 

void Heap::Swap(Person& a, Person& b) 
{ 
    Person temp; 
    temp = a; 
    a = b; 
    b = temp; 
} 

#include <iostream> 

class PQTYPE 
{ 

private: 
    Heap m_Items; 

public: 
    bool isEmpty() const; 
    void Enqueue(Person); 
    void Dequeue(); 
    void printElements(); 
}; 

bool PQTYPE::isEmpty() const 
{ 
    return m_Items.m_elements.empty(); 
} 

void PQTYPE::Enqueue(Person newItem) 
{ 

    if (!newItem.m_name.compare("Student")) 
    { 
     m_Items.m_elements.push_back(newItem); 
     m_Items.ReHeapUp(0, m_Items.m_elements.size() - 1); 
    } 
    else if (!newItem.m_name.compare("TA")) 
    { 
     m_Items.m_elements.push_back(newItem); 
     m_Items.ReHeapUp(0, m_Items.m_elements.size() - 1); 
    } 
    else if (!newItem.m_name.compare("Instructor")) 
    { 
     m_Items.m_elements.push_back(newItem); 
     m_Items.ReHeapUp(0, m_Items.m_elements.size() - 1); 
    } 
} 

void PQTYPE::Dequeue() 
{ 
    if (isEmpty()) 
     std::cout << "No jobs to print\n"; 
    else 
    { 
     Person front = m_Items.m_elements.front(); 
     std::cout << "Now printing Job#" << front.m_priority << " " << front.m_name.c_str() << std::endl; 
     m_Items.m_elements.erase(m_Items.m_elements.begin()); 
     m_Items.ReHeapDown(0, m_Items.m_elements.size() - 1); 
    } 
} 


void PQTYPE::printElements() 
{ 
    if (isEmpty()) 
     std::cout << "No jobs to print\n"; 
    else 
    { 
     for (int i = 0; i < m_Items.m_elements.size(); i++) 
     { 
      std::cout << "Job#" << m_Items.m_elements[i].m_priority << " " << m_Items.m_elements[i].m_name.c_str() << std::endl; 
     } 
    } 
} 

int showMenu(); 
void addJobs(PQTYPE&, Person&); 
void printJobs(PQTYPE&, Person&); 
void viewJobs(PQTYPE&); 

int showMenu() 
{ 
    int choice; 
    std::cout << " 1.)Add Job\n"; 
    std::cout << " 2.)Print Job\n"; 
    std::cout << " 3.)View Jobs\n"; 
    std::cout << " 4.)Exit\n"; 
    std::cout << " Enter Choice: "; 
    std::cin >> choice; 

    return choice; 
} 

void addJobs(PQTYPE& pq, Person& per) 
{ 
    char jobChoice; 

    std::cout << "Who is the job for (Instructor(i or I), TA(t or T), Student(s or S) :"; 
    std::cin >> jobChoice; 

    if (jobChoice == 'S' || jobChoice == 's') 
    { 
     per.m_priority = 0; 
     per.m_name = "Student"; 
     pq.Enqueue(per); 
    } 
    else if (jobChoice == 'T' || jobChoice == 't') 
    { 
     per.m_priority = 1; 
     per.m_name = "TA"; 
     pq.Enqueue(per); 
    } 
    if (jobChoice == 'I' || jobChoice == 'i') 
    { 
     per.m_priority = 2; 
     per.m_name = "Instructor"; 
     pq.Enqueue(per); 
    } 
} 

void printJobs(PQTYPE& pq) 
{ 
    pq.Dequeue(); 
} 

void viewJobs(PQTYPE& pq) 
{ 
    pq.printElements(); 
} 

int main() 
int option; 
    Person p; 
    PQTYPE pq; 

    do 
    { 
     option = showMenu(); 

     switch (option) 
     { 
     case 1: addJobs(pq, p); 
     break; 
     case 2: printJobs(pq); 
     break; 
     case 3: viewJobs(pq); 
     break; 
     case 4: 
     break; 
     default: std::cout << "Wrong input\n"; 
     break; 
     } 

    } while (option != 4); 

    return 0 
} 

你確定方法ReHeapUp和ReHeapDown滿足您的要求？不應該在工作號碼和優先級之間進行區分嗎？