Seg. Array zur Größenänderung von Fehlern C++

Question

Ich habe ein Priority-Queue-Array, das mit "Jobs" (Name + Priorität) gefüllt ist. Ich war in der Lage, alles, was mit der Warteschlange zu tun hat, von der Größenänderung zu entfernen, wenn sie voll ist. Hier sind die Bits, von denen ich denke, dass sie einen Segmentierungsfehler verursachen, den ich nicht herausfinden konnte.

EDIT:

Hier ist ein bisschen mehr Code, verließ ich in den Rest der Funktionen im Fall kompiliert die in irgendeiner Weise helfen könnte. Derzeit ist die anfängliche Kapazität auf 5 eingestellt. Wenn Sie versuchen, einen Job zur vollständigen Liste hinzuzufügen, verdoppelt sich die Kapazität des Arrays und Sie können einige Jobs vor einem SEG hinzufügen. Fehler.

pq.h

#ifndef PQ_H 
#define PQ_H 
#include "interface.h" 
#include <string> 
using namespace std; 

class Job { 
    public: 
     int getPriority(); 
     string getTaskName(); 
     void setPriority(int val); 
     void setTaskName(string tname); 
     Job(); 
    private: 
     int priority; 
     string taskName; 
}; 

class PriorityQueue { 

    public: 
     PriorityQueue(); 
     ~PriorityQueue(); 
     int size(); 
     bool isEmpty(); 
     void clear(); 
     void enqueue(string value, int priority); 
     string dequeue(); 
     string peek(); 
     int peekPriority(); 
     PriorityQueue(const PriorityQueue & src); 
     PriorityQueue & operator=(const PriorityQueue & src); 

    private: 
     static const int INITIAL_CAPACITY = 5; 
     Job *array; 
     int count; 
     int capacity; 

    void expandCapacity() { 
     Job *oldArray = array; 
     capacity *= 2; 
     array = new Job[capacity]; 
     for (int i = 0; i < count; i++) { 
      array[i] = oldArray[i]; 
     } 
     delete[] oldArray; 
    } 
}; 

#endif 

pq.cpp

#include <iostream> 
#include <cstring> 
using namespace std; 
//#include "job.h" 
#include "pq.h" 

Job::Job() // Constructor 
{ 
    priority= 0; 
    taskName = "There are no items in the list."; 
} 

int Job::getPriority(){ // returns the prority of the job 
    return priority; 
} 
string Job::getTaskName(){ // returns the name of the job 
    return taskName; 
} 
void Job::setPriority(int val){ // sets the priority of a newly created job 
    priority = val; 
} 
void Job::setTaskName(string tname){ // sets the name of a new job 
    taskName = tname; 
} 

PriorityQueue::PriorityQueue() // constructor 
    { 
     count = 0; 
     capacity = INITIAL_CAPACITY - 1; 
     array = new Job[INITIAL_CAPACITY]; 
     } 

PriorityQueue::~PriorityQueue() { // destructor 
    delete [] array; 

} 

int PriorityQueue::size() { // returns the number of jobs in the queue 
    return count; 
} 

bool PriorityQueue::isEmpty() { // returns true if queue is empty 
    if (count != 0){ 
     return false; 
    }else{ 
    return true; 
    } 
} 

void PriorityQueue::clear() { // clears queue of all jobs 
    count = 0; 
    // need to make it remove and delete the items 
} 

void PriorityQueue::enqueue(string value, int priority) { 
    // tests size to see if Queue is a max capacity 
    if(count == capacity){ 
     expandCapacity(); 
     cout << "\tList was full and has been expanded\n"; 
    } 
    array[++count].setPriority(priority); 
    array[count].setTaskName(value); 

    // upheap operations 
    Job v = array[count]; 
    int tempcount = count; 
    while (array[tempcount/2].getPriority() >= v.getPriority()){ 
     array[tempcount] = array[tempcount/2]; 
     tempcount = tempcount/2; 
    array[tempcount] = v; 
    } 

} 
string PriorityQueue::dequeue() { 
    // removes the job with the highest priority from the queue and returns the name 

    if(this->isEmpty()){ // make sure the queue isnt empty 
     string empty = "The queue is empty"; 
     return empty; 
    }else{ 
    Job remove = array[1]; 
    array[1] = array[count--]; 

    int j; 
    Job v; 
    int k = 1; 
    v = array[k]; 
    while(k <= count/2){ 
     cout << "dequeuewhile"; // test 
     j = k + k; 
     if(j < count && array[j].getPriority() > array[j+1].getPriority()){ 
      j++; 
      cout << "dequeueloop if1"; // test 
     } 
     if(v.getPriority() <= array[j].getPriority()){ 
      cout << "dequeueloop if2"; //test 
      break; 
     } 
     array[k] = array[j]; 
     k = j; 
    } 
    array[k] = v; 

    return remove.getTaskName(); // returns the name of the removed job 
    } 
} 
string PriorityQueue::peek() { // returns the name of the highest priority job without removing it from the queue 
    if(count == 0){ 
     return array[0].getTaskName(); 
    } 
    return array[1].getTaskName(); 
} 

int PriorityQueue::peekPriority() { // returns the priority from the highest priority job without removing it from the queue 
     if(count == 0){ 
     cout << "\tThere are no items in the list.\n"; 
     return array[0].getPriority(); 
    } 
    return array[1].getPriority(); 
} 

Answer 1

Ihr ursprünglicher Code entsprach exakt der vorherigen Antwort von @antiHUMAN.

Das Problem, das Sie haben, ist Mischen oder falsch mit 0-basierten und 1-basierten Konzepten.

Ihr erster Fehler ist capacity eine 0-basierte Nummer zu machen. Die capacity sollte die maximale Anzahl der Elemente in einem Array bezeichnen, daher sollten Sie nicht 1 davon subtrahieren. Wenn das Array 5 Gegenstände halten kann, dann sollte capacity 5, nicht 4.

PriorityQueue::PriorityQueue() // constructor 
{ 
    count = 0; 
    capacity = INITIAL_CAPACITY; // this remains 1-based. 
    array = new Job[INITIAL_CAPACITY]; 
} 

oder mit der Initialisierer-Liste:

PriorityQueue::PriorityQueue() : count(0), 
           capacity(INITIAL_CAPACITY), 
           array(new Job[INITIAL_CAPACITY]) {} 

---

Die 0-basierte Nummer in Ihrer Situation sollten sei count, nicht capacity.Da, da count 0-basiert, und capacity ist 1-basiert, Ihren Test in enqueue geändert werden muss:

if(count + 1 == capacity){ 
     expandCapacity(); 
     cout << "\tList was full and has been expanded\n"; 
    } 

Beachten Sie, dass 1 wird zählen für die Tatsache zu berücksichtigen, dass count 0- ist basiert und capacity ist 1 basiert.

Answer 2

Ich glaube, dass, wenn Sie ++count tun, wird die nächste Verwendung von count für die Anordnung außerhalb der Grenzen sein.

array[++count].setPriority(priority); 
// SEGMENTATION FAULT HERE 
array[count].setTaskName(value); 

Wenn die Kapazität des Arrays ist 5, und count betrug 4, dann nur Sie count auf 5 erhöht, und versuchten 5 zuzugreifen Element, das außerhalb der Grenzen liegt.

array = new Job[capacity]; 
for (int i = 0; i < count; i++) { 
    array[i] = oldArray[i]; 
} 

Nehmen wir an, capacity 10 ist, so haben Sie eine Reihe von 10 Elementen erhalten, die von Elementen 0 bis 9 count sagt uns, wie viele Elemente verwendet werden. Wenn count zufällig 9 ist, dann wenn Sie count um eins erhöhen, ist es jetzt 10. Wenn dann die Zeile kommt, die als produzierender Segmentfehler markiert ist, versuchen Sie in unserem Beispiel auf das Element 10 zuzugreifen. Es gibt kein Element 10 in einem Array der Länge 10, so dass Sie außerhalb der Grenzen sind.

array[++count].setPriority(priority); // array[10], but last element is 9! 
// SEGMENTATION FAULT HERE 
array[count].setTaskName(value); // array[10], but last element is 9! 

Und natürlich, alles nach diesem Teil verursacht das gleiche Problem, wie Sie array[count] halten verwenden.