c++ - 使用链表实现优先级队列
问题描述
#include<iostream>
using namespace std;
//template<class T>
class Node
{
public:
// T data;
int data;
Node *next;
int priority;
};
//template<class T>
class Que
{
Node *front , *rear;
public:
Que(){front = rear = NULL;}
// void enqueue(T x);
// T dequeue();
void enqueue(int *x, int l);
int dequeue();
void display();
};
//template<class T>
//void Que<T>::enqueue(T x)
void Que::enqueue(int *x, int l)
{
Node * pt = front;
for(int i=0; i<l; i++){
Node *t = NULL;
t = new Node;
if(t==NULL)
cout<<"Queue is full"<<endl;
else
{
t->next = NULL;
t->data = x[i];
t->priority = x[i];
if(front==NULL)
front = rear =t;
else
{
if(front->priority <= t->priority)
{
t->next = front;
front = t;
}
else
{
while(pt->next!= NULL && pt->next->priority <= x[i])
pt = pt->next;
t->next = pt->next;
pt->next = t;
}
}
}
}
}
//template<class T>
//T Que<T>::dequeue()
int Que::dequeue()
{
// T x = -1;
int x = -1;
Node *t = NULL;
if(front == NULL)
cout<<"Queue is empty"<<endl;
else
{
x = front->data;
t = front;
front = front->next;
delete t;
}
return x;
}
//template<class T>
//void Que<T>::display()
void Que::display()
{
Node *t = front;
while(t)
{
cout<<t->data<<" ";
t = t->next;
}
cout<<endl;
}
int main()
{
// Que <int> q();
Que q;
int a [] = {6, 1, 2, 5, 4, 3};
q.enqueue(a, sizeof(a)/sizeof(a[0]));
// q.dequeue();
q.display();
return 0;
}
这是在 C++ 中使用链表的优先级队列代码。入队成员函数内的 while 循环显示分段错误。
我认为指向*pt
用于指向前面的节点的指针未正确指向。我一直在尝试解决它,但不知道。这可能是什么原因?
解决方案
您pt
在开始时进行初始化,enqueue
但从不在循环中重置它。因此,当您将多个元素添加到空列表时,pt
将以 开头nullptr
,并且在将第一个元素添加到列表后不会更新。当您尝试将第二个元素添加到您取消引用的列表中时pt->next
,这会导致您的分段错误,因为pt
is still nullptr
。
修复很简单:移到Node * pt = front;
for循环内。
推荐阅读
- python - NameError:未定义名称“LoginView”
- python - 根据条件创建具有新列名的熊猫数据透视表
- sql-server - 从 0001 开始在现有表中添加新列
- java - 如何在 Java 中使用多行 lambda 表达式对 int[] 进行排序
- c# - 控制台窗口切换开关
- c++ - 如何配置 Codeblocks 在程序完成后不关闭控制台?
- c# - 即使从 NUGet 包管理器安装了最新版本,system.runtime DLL 仍指向旧版本的问题
- html - enctype="multipart/form-data" 编码错误
- php - 使用自定义价格 woocommerce 添加到购物车
- php - 在 laravel 7 中通过用户名进行身份验证