C++ 具有链表的优先级队列类

Question

我的 c++ 代码有两个问题（测试文件如下）：

我似乎无法弄清楚为什么它没有突破 while 循环，在运行时，它卡在循环"7 对 325"上。

因此，它应该进入 temp 的下一个节点，该节点将为 null，然后跳转到将其添加到队列末尾的部分。 但它只是循环往复。

我的第二个问题是我注释掉的函数 queue1.back，每当运行它时，它都会出错并给出似乎是地址的内容，但 .front（） 函数工作得很好。

我正在使用的测试文件是这样的：

89 Alex

325 Rob

72 Joy

91 Bob

using namespace std;
class Person
{
    friend class Pqueue;
    public:
        int priority;
        string name;
    };

    class PQueue
    {
        friend class Person;
        private:
        //Structure for my linked list.
        typedef struct node {
            Person data;
            struct node *next;
        }Node, *NodePtr;
        Node *head, *tail;
        public:
        //Prototype Functions
        PQueue(void);              //Initializer function
        bool empty(void);          //Test if empty
        int size(void);            //Return size
        void enqueue(Person *);    //Insert Node
        void dequeue(void);        //Remove Node
        Person* front(void);       //Access Next Node
        Person* back(void);        //Access last node
    };

    PQueue::PQueue()
   {
       head = NULL;
       tail = NULL;
   }

    bool PQueue::empty(){
        return (head == NULL);
    }

    void PQueue::enqueue(Person *myPerson){
        NodePtr np = (NodePtr) malloc(sizeof(Node));
        np->data = *myPerson;
        np->next = NULL;
        if(empty())
        {
             cout << "Making into creating the first node, of the linked list" <<endl;
             head = np;
             tail = np;
         }
         else { //Queue has more the one node
               Node* temp = head;
               if(np->data.priority > temp->data.priority) //If the priority is greater then the rest.
               {
                   head = temp;                            //Saving my head pointer
                   head->data = np->data;                  //Assigning new Data to the head pointer
                   head->next = temp;                      //Assigning the rest of the linked list back into head.
                   cout << "Making into creating the first node again, having to reassign." <<endl;
               }
               else{
                    //Searching where to place the node.
                    while(temp->data.priority > np->data.priority) //Searching if the next priority is higher then the passed.
                    {
                        cout << "Inside the while loop: " << np->data.priority << " versus "<<temp->data.priority <<endl;
                        if(temp->next == NULL)
                            break;
                        temp = temp->next;
                     }
            if(temp->next == NULL && np->data.priority < temp->data.priority) //Inserting at the end.
            {
                cout << "Making into creating the last node" <<endl;
                tail->next = np;
                cout << "Passing the function of creating the last node" <<endl;
            }
            else   //Inserting into the middle of the function.
            {
                cout << "Inserting in the middle of the queue" <<endl;
                np->next = temp->next;
                temp->next = np;
            }
        }
    }
}

void PQueue::dequeue(){
    if(empty()){
        cout << "nAttempt to remove from an empty list." << endl;
        exit(1);
    }
    Person hold = head->data;
    NodePtr temp = head;
    head=head->next;
    if (head == NULL) tail = NULL;
    free(temp);
}
Person* PQueue::front(){
    //Person &temp = head->next->data;
    //Person &temp = head->data;
    Person &temp = head->data;
    return &temp;
}
Person* PQueue::back(){
    if(empty()){
        cout << "nNo entries in list." << endl;
        exit(1);
    }
    Person &temp = tail->data;
    return &temp;
}
int main() {
    cout << "Starting main" << endl;
    PQueue queue1; //Creating my queue.
    cout << "Created Queue" << endl;
    Person tempPerson;
    ifstream inFile;
    inFile.open("/tmp/temp");
    cout << "going into while loop" << endl;
    while (inFile >> tempPerson.priority >> tempPerson.name){
        cout << "The priority is " <<  tempPerson.priority << " the name is " << tempPerson.name <<endl;
        queue1.enqueue(&tempPerson);
    }

    //Testing Section, trying to get .front and .back to work.
    Person *testPerson;
    testPerson = queue1.front();
    cout << "The TEST priority is " <<  testPerson->priority << " the TEST name is " << testPerson->name <<endl;
    /**
    Person *tailPerson;
    testPerson = queue1.back();
    cout << "The TEST priority is " <<  tailPerson->priority << " the TEST  name is " << tailPerson->name <<endl;
    **/
    queue1.dequeue();
    queue1.dequeue();
    queue1.dequeue();

    return 0;
}

Answer 1

当您将新的头条目添加到非空列表中时，您错误地将下一个指针设置为直接指向它所在的节点，而不是将其设置为指向链表的其余部分，就像您预期的那样。

head = temp;                            //Saving my head pointer
head->next = temp;                      //Assigning the rest of the linked list back into head.