-1
저는이 링크 된 목록 우선 순위 큐에서 4 시간에서 5 시간 정도 더 잘 작업했습니다. 그리고 저의 삶에서이 seg fault의 근원을 찾을 수 없습니다. 나를 미치게 만들었다.내 기본 PriorityQueue 정렬 알고리즘이 seg fault를 일으키는 이유는 무엇입니까?
나는이 호출 될 때까지 목록이 위대한을 작동하기 때문에 문제의 근본은, (우선 순위에 따라 두 노드의 위치를 교환) 내 swapUp() 함수에 있음을 알고있다. seg 오류는 실제로 swapUp()에 의해 발생 된 것이 아니며 노드의 위치 n에있는 요소를 반환하는 peekAt()에 의해 발생합니다. 하지만 swapUp()이 먼저 호출되지 않으면 오류가 발생하지 않으므로 문제가있는 부분이됩니다 (생각합니다).
또한 내가() swapUp에서 같은 근본 원인이있을 수 있습니다 생각 소멸자에서 발생되는 독방 감금 잘못이있다.
나는 반복해서 코드를 통해 갔다 나는 밤새 디버깅 봤는데 난 그냥 잘못된 것입니다 정확히 알아낼 수 없습니다. 정말이 점에 대해 약간의 도움을 주시면 감사하겠습니다.
우선 순위 큐 :
#ifndef JMF_PriorityQueue
#define JMF_PriorityQueue
#include <iostream>
#include <string>
template <typename T>
class PriorityQueue{
public:
struct Node{
T data;
int priority;
Node * next;
Node * prev;
};
PriorityQueue();
PriorityQueue & operator=(const PriorityQueue &rhs);
bool isEmpty(); //Returns true if queue is empty
int getLength(); //Returns length of queue
void enqueue(T data, int p); //Enqueues data T with priority p
void enqueue(T data); //Enqueues data T with priority 1
T dequeue(); //Dequeues and returns data at head of queue
void clearQueue(); //Empties queue
T peek(); //Returns data at head of queue without dequeing it
T peekAt(int n); //Returns data element n without dequeuing it
int getPriority(int n); //Returns priority of item at position n
void display(); //Prints list of data elements to screen
void revDisplay();
void swapUp(Node * target); //Swaps target node with it's neighbor next in line
bool contains(T data); //Returns true if data exists as an element anywhere on the queue
~PriorityQueue();
private:
int size;
Node * head, *tail;
};
template <typename T>
PriorityQueue<T>::PriorityQueue(){
size = 0;
head = 0;
tail = 0;
}
template <typename T>
PriorityQueue<T> & PriorityQueue<T>::operator=(const PriorityQueue &rhs){
clearQueue();
for(int n = 0; n < rhs.size(); n++)
enqueue(rhs.peekAt(n));
return *this;
}
template <typename T>
int PriorityQueue<T>::getLength(){
return size;
}
template <typename T>
bool PriorityQueue<T>::isEmpty(){
return(!size);
}
template <typename T>
void PriorityQueue<T>::enqueue(T data){
enqueue(data, 1);
}
template <typename T>
void PriorityQueue<T>::enqueue(T data, int p){
Node * newNode = new Node();
newNode -> data = data;
newNode -> priority = p;
if(isEmpty()){
head = newNode;
tail = newNode;
} else {
newNode -> next = tail;
tail -> prev = newNode;
tail = newNode;
//WHEN THIS WHILE LOOP IS COMMENTED OUT (IE NO SORTING), NO SEG FAULT ISSUES
while(newNode != head && newNode->priority < newNode->next->priority)
swapUp(newNode);
std::cout << "\n";
}
tail->prev = 0;
head->next = 0;
size++;
}
template <typename T>
T PriorityQueue<T>::dequeue(){
if(isEmpty()){
std::cout << "\n\nWARNING: Trying to dequeue empty queue\n\n";
throw 3;
} else {
Node * frontNode = head;
T result = frontNode -> data;
if(size == 1){
head = 0;
tail = 0;
} else {
head = frontNode -> prev;
head -> next = 0;
}
delete frontNode;
size--;
return result;
}
}
template <typename T>
void PriorityQueue<T>::clearQueue(){
while(!isEmpty())
dequeue();
}
template <typename T>
T PriorityQueue<T>::peek(){
return peekAt(0);
}
template <typename T>
T PriorityQueue<T>::peekAt(int n){
T result;
Node * thisNode;
if(isEmpty()){
std::cout << "\n\nWARNING: Trying to peek empty queue\n\n";
throw 3;
} else if(n < 0 || n > size){
std::cout << "\n\nWARNING: Trying to peek queue at non-existent index " << n << "\n\n";
throw 3;
} else {
thisNode = head;
if(thisNode->prev == 0)
for(int k = 0; k < n; k++)
thisNode = thisNode -> prev;
result = thisNode -> data; //Crashes program if swapUp() is ever called
}
return result;
}
template <typename T>
int PriorityQueue<T>::getPriority(int n){
int result;
if(isEmpty()){
std::cout << "\n\nWARNING: Trying to get priority from empty queue\n\n";
result = -1;
} else if(n < 0 || n > size){
std::cout << "\n\nWARNING: Trying to get priority from non-existent index " << n << "\n\n";
result = -1;
} else{
Node * thisNode = head;
for(int k = 0; k < n; k++)
thisNode = thisNode -> prev;
result = thisNode -> priority;
}
return result;
}
template <typename T>
void PriorityQueue<T>::display(){
if(isEmpty()){
std::cout << "\nQueue is empty\n";
} else {
std::cout << "\nINDEX\tDATA\tPRIORITY\n";
std::cout << "-----------------------\n";
Node * thisNode = head;
for(int n = 0; n < size; n++){
std::cout << n << "\t" << thisNode->data << "\t" << thisNode->priority << "\n";
thisNode = thisNode -> prev;
}
std::cout << "\n";
}
}
template <typename T>
void PriorityQueue<T>::revDisplay(){
if(isEmpty()){
std::cout << "\nQueue is empty\n";
} else {
std::cout << "\nINDEX\tDATA\tPRIORITY\n";
std::cout << "-----------------------\n";
Node * thisNode = tail;
for(int n = 0; n < size; n++){
std::cout << n << "\t" << thisNode->data << "\t" << thisNode->priority << "\n";
thisNode = thisNode -> next;
}
std::cout << "\n";
}
}
template <typename T>
void PriorityQueue<T>::swapUp(Node * target){
if(target == head)
return;
Node * partner = target->next;
if(partner == head){
head = target;
target->next = 0;
} else
target->next = partner->next;
if(target == tail){
tail = partner;
partner->prev = 0;
} else
partner->prev = target->prev;
}
template <typename T>
bool PriorityQueue<T>::contains(T data){
bool result = false;
if(!isEmpty()){
Node * thisNode = head;
for(int n = 0; n < size; n++){
if(thisNode->data == data){
result = true;
break;
}
thisNode = thisNode -> prev;
}
}
return result;
}
template <typename T>
PriorityQueue<T>::~PriorityQueue(){
clearQueue();
}
#endif
테스트 프로그램 :
#include <iostream>
#include <string>
#include <ctype.h>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include "PriorityQueue.hpp"
int main(){
PriorityQueue<char> test;
test.enqueue('c',1);
test.enqueue('a',2);
test.enqueue('t',3);
test.display();
std::cout <<"\nREVERSE:\n";
test.revDisplay();
std::cout<<"\nWITH SORTING:\n";
test.enqueue('d',5);
test.enqueue('s',9);
test.enqueue('g',7);
test.enqueue('o',6);
test.enqueue('&',4);
test.display();
std::cout <<"\n\nALL DONE\n\n";
return 0;
}
좋아, 나는 아직도 나에게 오류를주는 둘 다 서로 다른 두 가지 새로운 방법에 SwapUp()를 구현하는 시도했습니다.
실패 시도 # 1 :
template <typename T>
void PriorityQueue<T>::swapUp(Node * target){
Node * partner = target->next; //Partner = target next
Node * temp = new Node; // temp spot to hold partner neighbors
temp->next = partner->next;
temp->prev = partner->prev;
partner->next = target->next;
partner->prev = target->prev;
target->next = temp->next;
target->prev = temp->prev;
if(target == tail)
tail = partner;
if(partner == head)
head = target;
delete temp;
}
실패 시도 # 2 :
template <typename T>
void PriorityQueue<T>::swapUp(Node * target){
Node * partner = target->next; //Partner = target next
target->next = partner->next; //Target next = partner next
partner->prev = target->prev; //Partner prev = target prev
partner->next = target; //Partner next = target
target->prev = partner; //Target prev = partner
if(target == tail)
tail = partner;
if(partner == head)
head = target;
}
이 나를 절대적으로 미친 운전. 이것은 내가 왜 그렇게 많은 문제를 겪고 있는지 모르는 초등 논리 문제입니다. 어떤 도움이라도 크게 대단히 감사하겠습니다!