我是数据结构的新手，一直在尝试实现下面的代码，但无法实现。我不完全理解我在做什么，所以需要一些帮助，我正在使用链表和类创建一个优先级队列。将年龄作为输入，并按降序显示所有年龄值。这是代码。
#include <iostream>
using namespace std;
class Node
{
private:
int age;
Node* next;
public:
int getAge() {
return this->age;
}
void setAge(int age) {
this->age = age;
}
Node* getNext() {
return this->next;
}
Node* setNext(Node* next) {
this->next = next;
}
};
class Priority_Queue
{
private:
Node* front;
Node* rear;
public:
Priority_Queue()
{
front = NULL;
rear = NULL;
}
void enqueue(int x)
{
if (front == NULL && rear == NULL) {
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(NULL);
}
else if (front != NULL && front->getAge() < x) {
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(rear);
front = newNode;
}
else if (front != NULL && front->getAge() > x) {
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(NULL);
rear = newNode;
}
}
void dequeue()
{
if (front == NULL)
cout << "Can't remove from an empty queue!" << endl;
else{
int x = front->getAge();
Node* p = front;
front = front->getNext();
delete p;
cout << "Deleted Age is " << x << endl;
}
}
void display()
{
Node* ptr;
ptr = rear;
if (front == NULL)
cout << "Queue is emptyn";
else
{
cout << "Queue is :n";
while (ptr != NULL)
{
cout << ptr->getAge() << endl;
ptr = ptr->getNext();
}
}
}
};
int main()
{
int c, p;
Priority_Queue pq;
cout << "nWelcome to Patient information system" << endl;
cout << "Enter Your choice of the activity" << endl;
do
{
cout << "1.Insertn";
cout << "2.Deleten";
cout << "3.Displayn";
cout << "4.Exitn";
cout << "Enter your choice : ";
cin >> c;
switch (c)
{
case 1:
cout << "Input the age value to be added in the queue : ";
cin >> p;
pq.enqueue(p);
break;
case 2:
pq.dequeue();
break;
case 3:
pq.display();
break;
case 4:
break;
default:
cout << "Wrong choicen";
}
} while (c != 4);
cout << endl;
return 0;
}
下面是一个快速的代码回顾：
#include <iostream>
using namespace std; // Bad practice; especially in a multi-file project which
// this should be.
// The Node should be an "implementation detail." I care about the queue, not
// the plumbing that makes it work.
class Node {
private:
int age;
Node* next; // A sorted queue using only a singly linked list seems like a
// bad idea.
public:
// Use of this is not needed; it can hurt readability
int getAge() { return this->age; }
void setAge(int age) { this->age = age; }
Node* getNext() { return this->next; }
// Return should be void; you don't return anything
Node* setNext(Node* next) { this->next = next; }
};
class Priority_Queue {
private:
Node* front;
Node* rear;
public:
Priority_Queue() {
front =
NULL; // Prefer default member initialization, then default this ctor
rear = NULL; // Prefer nullptr over NULL, it's been around for a decade now
}
/*
* SUPER BAD: No destructor, copy constructor, or assignment operator
* overload. This class manages heap-allocated resources, and no care is taken
* to ensure that proper copies are made, or that the object is properly
* destroyed.
*
* This is known as the Rule of 3, but has recently been called the Rule of
* 0/3/5. Ideally, you would be adhering to the Rule of 5.
*/
void enqueue(int x) {
if (front == NULL && rear == NULL) { // Unnecessarily redundant
Node* newNode = new Node(); // Why not provide a constructor for this?
newNode->setAge(x);
newNode->setNext(NULL);
}
else if (front != NULL &&
front->getAge() < x) { // Pointers can be directly checked
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(rear);
front = newNode;
}
else if (front != NULL && front->getAge() > x) {
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(NULL);
rear = newNode;
}
}
void dequeue() {
if (front == NULL)
cout << "Can't remove from an empty queue!"
<< endl; // Do nothing, no need for a message
else {
int x = front->getAge();
Node* p = front;
front = front->getNext();
delete p;
cout << "Deleted Age is " << x
<< endl; // Printing in general is a bad idea from within a data
// structure
}
}
void display() {
Node* ptr;
ptr = rear; // Starting at end of list for printing
if (front == NULL)
cout << "Queue is emptyn";
else {
cout << "Queue is :n";
while (ptr != NULL) {
cout << ptr->getAge() << endl;
ptr = ptr->getNext();
}
}
}
};
就学生代码而言，这还不错。当涉及到排序时，我们不会麻烦实际移动节点；考虑到CCD_ 1类的布局，这是不必要的。
我要做的第一件事是将其拆分为多个文件。这实际上让写作变得更容易了。第一个文件是我们的优先级队列头。
优先级队列.hpp
#ifndef PQUEUE_HPP
#define PQUEUE_HPP
class Priority_Queue {
private:
struct Node; // Prevents Nodes from being declared outside of this class
Node* front = nullptr;
Node* rear = nullptr;
// Helper functions
void sort();
void push_front(int x); // Very simple with singly linked list
friend void swap(Priority_Queue& lhs, Priority_Queue& rhs);
public:
Priority_Queue() = default;
// Only going for Rule of 3 for brevity
Priority_Queue(const Priority_Queue& other);
~Priority_Queue();
Priority_Queue& operator=(Priority_Queue other);
void enqueue(int x);
void dequeue();
void display();
};
// Now that we're nested, a struct can be used instead
// Will make things a lot easier
struct Priority_Queue::Node {
int age = 0;
Node* next = nullptr;
Node() = default;
Node(int a);
Node(int a, Node* n);
};
#endif
这声明了类及其包含的函数。最大的单一变化是Node现在是struct，并且在Priority_Queue中被私下声明。我应该不能看到，更不用说在类之外声明Nodes了。它们就是所谓的实现细节。他们帮助我们编写课程，但不需要被看到。
使Node成为一个结构还允许我们删除所有成员函数。我们将让类直接操作数据。
优先级队列.cpp
#include "PriorityQueue.hpp"
#include <algorithm>
#include <iostream>
// This is sloppy, but time contraints won't allow me to make this nicer.
Priority_Queue::Priority_Queue(const Priority_Queue& other) {
Node* otherNode = other.front;
while (otherNode) {
push_front(otherNode->age);
}
sort();
}
Priority_Queue::~Priority_Queue() {
while (front) {
Node* d = front;
front = front->next;
delete d;
}
rear = nullptr;
}
// Untested
Priority_Queue& Priority_Queue::operator=(Priority_Queue other) {
swap(*this, other);
return *this;
}
void Priority_Queue::enqueue(int x) {
if (!front) { // Simpler pointer check
front = new Node(x); // Provided ctor makes this simpler
rear = front;
// Single node, no need to sort
return;
}
push_front(x);
sort();
// Separate your concerns. Enqueue gets a node into the list, we worry about
// sorting elsewhere.
}
// Should be called pop(); not changing so that your main() can be left alone
void Priority_Queue::dequeue() {
if (!front) return;
Node* p = front;
front = front->next;
delete p;
}
void Priority_Queue::display() {
Node* ptr = front;
if (!front)
std::cout << "Queue is emptyn";
else {
std::cout << "Queue is :n";
while (ptr) {
std::cout << ptr->age << 'n';
ptr = ptr->next;
}
}
}
void Priority_Queue::sort() {
// We'll go with a bubble sort
bool madeSwap;
do {
madeSwap = false;
Node* node = front;
while (node->next) {
if (node->age > node->next->age) {
std::swap(node->age, node->next->age);
madeSwap = true;
}
node = node->next;
}
} while (madeSwap);
}
void Priority_Queue::push_front(int x) { front = new Node(x, front); }
// Untested
void swap(Priority_Queue& lhs, Priority_Queue& rhs) {
using std::swap;
swap(lhs.front, rhs.front);
swap(lhs.rear, rhs.rear);
}
// Nested class
Priority_Queue::Node::Node(int a) : age(a) {} // next is automatically nullptr
Priority_Queue::Node::Node(int a, Node* n) : age(a), next(n) {}
你的main.cpp基本上没有受到影响。它现在包括PriorityQueue.hpp，但没有太多不同。
您必须编译这两个cpp文件才能获得一个工作程序。类似g++ -Wall -Wextra -std=c++17 main.cpp PriorityQueue.cpp。您会注意到，我还按升序排序，以避免公然复制/粘贴。这不是一个巨大的威慑，但总比什么都没有好。
要查看它的运行情况，您可以访问此链接。
您的代码有太多问题，您离工作代码太远了，我无法帮助您。
请阅读以下内容：https://www.programiz.com/dsa/priority-queue
C++中还有一个示例，您可以对其进行测试和调试，以准确了解其工作原理。
一些问题：
- setNext应该返回void
- 你从来没有在enque中设置前面(先看看是否在enque(
- 您应该使用std:：vector或std:：list作为底层类型
- 你不需要使用"；这个"；指针(例如"this->age=age"(
- 该算法不会做你认为正在做的事情(不是很接近(……我可以带着这个走很长一段时间