使用链表C++数组的优先级队列

Question

所以我正在尝试使用 C++ 中的链表数组创建优先级队列。我还没有完成，但如果我能修复构造函数，我想我可以自己完成剩下的工作。我有一个数据文件，第一行是文件中的项目数。此后的下一行将有一个字符，然后是从 0 到 9 的优先级。所以我正在对有 26 个字母（项目）的字母表进行排序。每个字母都有一个优先级。前任。 Q 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

class 只分配指向 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;
}

应该link编辑的不是数组中的指针。

每个指针都是指向 linked 列表的 HEAD 的指针，即 10 个独立的 linked 列表。所以不要link他们。

最后 - 在 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 个 linked 列表中的所有元素。

使用链表C++数组的优先级队列

Priority Queue using array of linked list C++

c++

arrays

linked-list

priority-queue