Реализация очереди приоритетов с использованием связанного списка - PullRequest
Новая
       103

Реализация очереди приоритетов с использованием связанного списка

0 голосов
/ 01 мая 2020 
#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 ++. В то время как l oop внутри функции-члена enqueue показывает ошибку сегментации.

Я думаю, что указатель *pt на узел, который используется для указания фронта, не указывает правильно. Я пытался решить это, но не мог понять. Что может быть причиной для этого?

1 Ответ

0 голосов
/ 01 мая 2020

Вы инициализируете pt в начале enqueue, но никогда не сбрасываете его в пределах l oop. Поэтому, когда вы добавляете несколько элементов в пустой список, pt начинается с nullptr и не будет обновляться после добавления первого элемента в список. Когда вы пытаетесь добавить второй элемент в список, вы разыменовываете pt->next, что вызывает ошибку сегментации, потому что pt по-прежнему nullptr.

Исправить несложно: переместите Node * pt = front; в в течение в течение l oop.

...