使用數組鏈表C++的優先級隊列

Question

所以我試圖創建一個優先級隊列使用C++中的鏈接列表數組。我還沒有完成，但如果我能修復構造函數，我想我可以自己完成剩下的工作。 我有一個數據文件，第一行有文件中的項目數。 之後的下一行將有一個字符，然後是從0開始到9的優先級。 因此，我正在對包含26個字母（項目）的字母進行排序。每封信都有一個優先級。例如，問題5（字母Q的優先級爲5） 當我運行它時，它說程序停止工作，然後開始尋找解決方案。就像一個無限循環的錯誤，我想。

#include <iostream> 
#include <fstream> 
using namespace std; 

class Queue 
{ 
private: 
    struct linkedList 
    { 
     char data; 
     linkedList *next; 
    }; 
    linkedList* PQ[10]; 

public: 
    //bool empty; 
    //bool empty(int priority); 
    void add(char info, int lvl); 
    //void remove(); 
    Queue(); 
}; 

int main() 
{ 
    int size; 
    char Info; 
    int Lvl; 
    Queue Q; 
    ifstream dataIn; 
    dataIn.open("charQueueInput.txt"); 
    if (dataIn.fail()) 
    { 
     cout << "File does not exist." << endl; 
     exit(1); 
    } 
    dataIn >> size; 
    dataIn.get(); 
    cout << size; 
    /*for (int i = 0; i < size; i++) 
    { 
     dataIn >> Info; 
     dataIn >> Lvl; 
     dataIn.get(); 
     Q.add(Info, Lvl); 
    }*/ 
    system("pause"); 
    return 0; 
} 

Queue::Queue() 
{ 
    for (int i = 0; i < 10; i++) 
    { 
     PQ[i] = NULL; 
    } 
    for (int i = 0; i < 9; i++) 
    {  
     PQ[i]->next = PQ[i + 1]; 
    } 
    PQ[9]->next = NULL; 
} 

void Queue::add(char info, int lvl) 
{ 
    if (lvl == 0) 
    { 
     PQ[0]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = PQ[1]; 
     PQ[0]->next = temp; 
    } 
    else if (lvl == 1) 
    { 
     PQ[1]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = PQ[2]; 
     PQ[1]->next = temp; 
    } 
    else if (lvl == 2) 
    { 
     PQ[2]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = PQ[3]; 
     PQ[2]->next = temp; 
    } 
    else if (lvl == 3) 
    { 
     PQ[3]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = PQ[4]; 
     PQ[3]->next = temp; 
    } 
    else if (lvl == 4) 
    { 
     PQ[4]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = PQ[5]; 
     PQ[4]->next = temp; 
    } 
    else if (lvl == 5) 
    { 
     PQ[5]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = PQ[6]; 
     PQ[5]->next = temp; 
    } 
    else if (lvl == 6) 
    { 
     PQ[6]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = PQ[7]; 
     PQ[6]->next = temp; 
    } 
    else if (lvl == 7) 
    { 
     PQ[7]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = PQ[8]; 
     PQ[7]->next = temp; 
    } 
    else if (lvl == 8) 
    { 
     PQ[8]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = PQ[9]; 
     PQ[8]->next = temp; 
    } 
    else if (lvl == 9) 
    { 
     PQ[9]->data = info; 
     linkedList *temp = new linkedList; 
     temp->next = NULL; 
     PQ[1]->next = temp; 
    } 
} 

這裏會是對數據文件的例子：

7 
Q 5 
W 3 
T 0 
Y 4 
A 9 
B 5 
U 0 

你將它讀成：

0: T -> U 
1. 
2. 
3. W 
4. Y 
5. Q -> B 
6. 
7. 
8. 
9. A 

T，U，W，Y，Q，B， A

Answer 1

問題是您在分配內存之前訪問PQ。

class Queue 
{ 
private: 
    struct linkedList 
    { 
     char data; 
     linkedList *next; 
    }; 
    linkedList* PQ[10]; // Allocates pointer only 

該類只分配指向linkenList的指針，但不分配任何實例。

以後你：

// In constructor 
Queue::Queue() 
{ 
    for (int i = 0; i < 10; i++) 
    { 
     PQ[i] = NULL; 
    } 
    for (int i = 0; i < 9; i++) 
    {  
     PQ[i]->next = PQ[i + 1]; // PQ[i] is NULL so run time error 
    } 

也是後來

void Queue::add(char info, int lvl) 
{ 
    if (lvl == 0) 
    { 
     PQ[0]->data = info; // Access to non-allocated element! 
     linkedList *temp = new linkedList; 
     temp->next = PQ[1]; 

，你訪問PQ

[0] - >數據。但是元素還沒有被分配，所以你會遇到運行時問題。

而不是

if (lvl == 0) 
{ 
    PQ[0]->data = info; 
    linkedList *temp = new linkedList; 
    temp->next = PQ[1]; 
    PQ[0]->next = temp; 
} 

你需要的東西，如：

if (lvl == 0) 
{ 
    if (PQ[0] == nullptr) 
    { 
     PQ[0] = new linkedList; // If head of queue is null, allocate 
            // new element for head 
     PQ[0]->next = nullptr; 
    } 


    linkedList *temp2 = PQ[0]; 
    while(temp2->next != nullptr) // Search the linked list 
    {        // to find last element 
     temp2 = temp2->next; 
    } 
    // Now temp2 points to the last element in the list 

    temp2->next = new linkedList; // Allocate new element and add it 
            // to the list after temp2 
            // to get a linked list 

    temp2 = temp2->next;   // Make temp2 point to the new element 
    temp2->next = nullptr;   // Remember to initialize next of new element 

    temp2->data = info;    // Save info 
} 

並在構造函數：

Queue::Queue() 
{ 
    for (int i = 0; i < 10; i++) 
    { 
     PQ[i] = nullptr; // Use nullptr instead of NULL 
    } 

// Remove this block 
//  for (int i = 0; i < 9; i++) 
//  {  
//   PQ[i]->next = PQ[i + 1]; 
//  } 
//  PQ[9]->next = NULL; 
} 

它不是應該掛在數組中的指針。

每個指針是指向鏈接列表HEAD的指針，即10個獨立鏈接列表。所以不要鏈接它們。

最後 - 在add（）函數中使用數組！不要做大的if語句。

void Queue::add(char info, int lvl) // Tip: Consider making lvl an unsigned int 
{ 
    if ((lvl >= 10) || (lvl < 0)) return; // Ignore if lvl is out of range 

    if (PQ[lvl] == nullptr) // <---- USE lvl to index array 
    { 
     PQ[lvl] = new linkedList; // If head of queue is null, allocate 
            // new element for head 
     PQ[lvl]->next = nullptr; 
    } 


    linkedList *temp2 = PQ[lvl]; 
    while(temp2->next != nullptr) // Search the linked list 
    {        // to find last element 
     temp2 = temp2->next; 
    } 
    // Now temp2 points to the last element in the list 

    temp2->next = new linkedList; // Allocate new element and add it 
            // to the list after temp2 
            // to get a linked list 

    temp2 = temp2->next;   // Make temp2 point to the new element 
    temp2->next = nullptr;   // Remember to initialize next of new element 

    temp2->data = info;    // Save info 
} 

順便說一句 - 記得創建一個析構函數，它刪除10個鏈表中的所有元素。