基于 Link 列表的优先级队列

Question

方法,add_by_priority" 给我分段错误，我知道问题出现在,get_prio" 方法中。我试图解决它或搜索它是否在其他任何地方都有效，例如在 ,if" 语句之外它编译得很好。我也不知道我是否正确地执行了整个优先级插入算法（尤其是 2 行之后 while循环）

        #ifndef SNODE_H
        #define SNODE_H
        
        #include <iostream>
        
        template<typename TYPE>
        class SNode
        {
        
        private:
        
        TYPE _elem; //value of element
        
        SNode<TYPE>* _next_elem; //connection to next node
        
        int _prio; //priority
        
        public:
        
        SNode();
        
        SNode(const TYPE & elem, const SNode<TYPE>* next_elem, const int prio);
        
        TYPE &get_elem();
        
        SNode<TYPE>* get_next_elem();
        
        int &get_prio();
        
        void set_elem(const TYPE & elem);
        
        void set_next_elem(SNode<TYPE>& next_elem);
        
        void set_priority(const int & prio);
        
        bool operator<(SNode<TYPE> & Node);
        
        bool operator>(SNode<TYPE> & Node);
        
        };
        
        
        #endif

    #ifndef LINKED_LIST
    #define LINKED_LIST
    
    #include <iostream>
    #include "SNode.h"
    
    
    template<typename TYPE>
    class LinkedList
    {
    private:
    SNode<TYPE>* head;
    public:
    LinkedList(); //konstruktor bezparametryczny
    
    void add_by_priority(const TYPE& Node, const int &prio);
    void removeFront();
    
    void addFront(const TYPE& Node, const int &prio);
    
    const TYPE & front() const;
    bool empty() const;
    void print();
    
    
    
    
    };

    #include "SNode.h"
    
    template<typename TYPE>
    SNode<TYPE>::SNode(){}
    
    template<typename TYPE>
    SNode<TYPE>::SNode(const TYPE & elem, const SNode<TYPE>* next_elem, const int prio)
    {
    _elem=elem;
    
    next_elem= NULL;
    
    _prio = prio;
    }
    
    template<typename TYPE>
    TYPE &SNode<TYPE>::get_elem()
    {
        return _elem;
    }
    
    template<typename TYPE>
    SNode<TYPE>* SNode<TYPE>::get_next_elem()
    {
        return _next_elem;
    }
    
    template<typename TYPE>
    int &SNode<TYPE>::get_prio()
    {
        return _prio;
    
    }
    
    template<typename TYPE>
    void SNode<TYPE>::set_elem(const TYPE & elem)
    {
        _elem=elem;
    }
    
    template<typename TYPE>
    void SNode<TYPE>::set_next_elem( SNode<TYPE>& next_elem)
    {
    _next_elem = &next_elem;
    }
    
    template<typename TYPE>
    void SNode<TYPE>::set_priority(const int & prio)
    {
    _prio = prio;
    }
    
    template<typename TYPE>
    bool SNode<TYPE>::operator<(SNode<TYPE> & Node) 
    {
    if((*this).get_prio() > Node.get_prio())
        return true;
    return false;
    }
    
    template<typename TYPE>
    bool SNode<TYPE>::operator>(SNode<TYPE> & Node)
    {
    return !(*this<Node);
    }

    #include <iostream>
    #include "LinkedList.h"
    
    
    //inicjuje obiekt ktory nie poakzuje na nic (NULL)
    template<typename TYPE>
    LinkedList<TYPE>::LinkedList()
    {
        head = nullptr; 
    }
    
    
    //zwraca 1 element listy
    template<typename TYPE>
    const TYPE & LinkedList<TYPE>::front() const
    {
        return head->get_elem();
    }
    
    
    template<typename TYPE>
    void LinkedList<TYPE>::addFront(const TYPE& Node, const int &prio) 
    {
    
        SNode<TYPE>* temp = new SNode<TYPE>; //tworzymy nowa zmienna do, ktorej przypiszemy wartosc podanego argumentu
        temp->set_elem(Node); //podpisujemy wartosc
        temp->set_priority(prio); //podpisujemy priority
        temp->set_next_elem(*head); //podpisuje pod adres aktualnego poczatku
        head = temp; //nowa inicjalizacja poczatku temp staje sie head
    }
    
    
    template<typename TYPE>
    void LinkedList<TYPE>::removeFront() 
    {
    
        SNode<TYPE>* temp = head; //tworzymy zmienna ktora pokazuje na head zeby nie zgubic pamieci head
        head = head->get_next_elem(); //przestawiamy head na nastepny element
    
    delete temp; //usuwamy pamiec ktora byla pod head
    
    }
    
    
    template<typename TYPE>
    void LinkedList<TYPE>::print()
    {
    SNode<TYPE>* tmp = head; //podpisanie zmiennej pod wartosc i adres head(by od pcozatku printowac liste)
    while(tmp->get_next_elem() !=nullptr ) //jesli lista nie jest pusta
        {
            std::cout << tmp->get_elem() << std::endl;  //print wartosc pod adresem tmp
            tmp = tmp->get_next_elem(); //przestaw na kolejne miejsce
        }
        std::cout << tmp->get_elem() <<std::endl;
    }
    
    
    template<typename TYPE>
    bool LinkedList<TYPE>::empty() const
    {
    if(head == nullptr) //jesli head nie pokazuje na NULL true
        return true;
    else
        return false; //jesli head jest NULL to nie ma elementow bo nic na nic nie pokazuje
    }
    
    
    template<typename TYPE>
    void LinkedList<TYPE>::add_by_priority(const TYPE& Node, const int &prio)
    {
    
    SNode<TYPE>* start_temp; //zmienna pomocnicza by wyszukac odpowiednie miejsce 
    SNode<TYPE>* temp = new SNode<TYPE>; 
    start_temp = head; //ustaw zmienna na head (poczatek listy)
    
    temp->set_elem(Node); //podpisujemy wartosc
    temp->set_priority(prio); //podpisujemy priority
    
    
        if(prio < head->get_prio() || head == nullptr) //jesli head ma wiekszy prio niz nowe podane prio lub lista jest puste
            {

                temp->set_next_elem(*head); // pod temp podpisz head
                head = temp; //temp staje sie head (wstawienie Node) utworzenie i wstawienie nowego node z wyzszym priorytetem
            }
        else
            {

        
                while(start_temp->get_next_elem() != nullptr && start_temp->get_next_elem()->get_prio() < prio) //rob dopoki nie skonczy sie lista 
                {                                                                                     //lub znajdzie priorytet wiekszy od obecnego 
                    start_temp = start_temp->get_next_elem(); //przejdz na kolejny element listy
                }
    
    
        temp->set_next_elem(*start_temp->get_next_elem()); //wez nastepny element(petla zakonczyla sie element wczesniej)
    
        start_temp->set_next_elem(*temp); //ustawia nowy node w poprawnie wybranym miejscu
    
            }
    }

    #include <iostream>
    #include <stdlib.h>
    #include <fstream>
    #include <string.h>
    #include "LinkedList.cpp"
    #include "SNode.h"
    
    /*
    template<typename TYPE>
    struct Mess_prio
    {
    int _key;
    TYPE _mess;
    };
    */
    
    
    int main()
        {
        
    int value,size,prio;
    LinkedList<int> list;
    
    std::cout << " Pass list size: " <<std::endl;
    std::cin >> size;
    std::cout << std::endl;
    for(int i=0; i<size; i++)
    {
    std::cout << "Enter the value: " << std::endl;
    std::cin >> value;
    std::cout << std::endl;
    std::cout << "Enter the priority: " << std::endl;
    std::cin >> prio;
    std::cout << std::endl;
    list.add_by_priority(value,prio);
    
    }
    list.print();
    
        }

Answer 1

您的代码中有几个错误：

// OP CODE
template<typename TYPE>
    SNode<TYPE>::SNode(){}

不初始化 _next_elem，使其处于无效状态。此构造函数运行后不一定为null

// OP CODE
template<typename TYPE>
SNode<TYPE>::SNode(const TYPE & elem, const SNode<TYPE>* next_elem, const int prio)
{
    _elem=elem;
    next_elem= NULL;
    _prio = prio;
}

在这里你做将它设置为 null 但你设置的是函数参数，而不是成员，而且你从未从函数参数中读取。 _next_elem 在此构造函数之后也未初始化。

// OP CODE
template<typename TYPE>
void SNode<TYPE>::set_next_elem( SNode<TYPE>& next_elem)
{
    _next_elem = &next_elem;
}

此处您存储的是一个对象的地址，您只知道调用该函数时该对象还处于活动状态。没有简单的方法来检测所提供的 next_elem 的生命周期是否已结束，并且您的指针是否悬空。但假设这是一种可能性。

// OP CODE
template<typename TYPE>
bool SNode<TYPE>::operator<(SNode<TYPE> & Node) 
{
    if((*this).get_prio() > Node.get_prio())
        return true;
    return false;
}

更“自然”的写法是：

// suggestion
template<typename TYPE>
bool SNode<TYPE>::operator<(SNode<TYPE> & Node) 
{
    return this->get_prio() > Node.get_prio();
}

LinkedList 代码中的另一个问题

// OP CODE
template<typename TYPE>
LinkedList<TYPE>::LinkedList()
{
    head = nullptr; 
}

// OP CODE
template<typename TYPE>
void LinkedList<TYPE>::addFront(const TYPE& Node, const int &prio) 
{
...
    temp->set_next_elem(*head);
}

在这里，如果你创建一个 LinkedList，head 是 nullptr，但是如果你尝试在这个列表上添加 addFront，突然你取消引用 null。

我就到此为止了。请注意您的地址、指针、生命周期等。

基于 Link 列表的优先级队列

Priority Queue based on Link List

c++

linked-list

priority-queue