c++ - 段。错误调整数组大小 C++

Question

我有一个优先级队列数组，其中填充了“作业”(名称 + 优先级)。如果它已满，除了重新调整大小之外，我已经能够让所有与队列相关的工作。以下是我认为会导致我无法弄清楚的段错误的位。

编辑:

这里还有一些可以编译的代码，我保留了其余的函数，以防它们以任何方式提供帮助。现在初始容量设置为 5，当您尝试将作业添加到完整列表时，它将使阵列容量加倍，并允许您在 SEG 之前添加更多作业。过错。

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

我认为当你执行 ++count 时，下一次使用 count 将超出数组范围。

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

如果数组的容量为 5，而 count 为 4，那么您只需将 count 递增到 5，并尝试访问元素 5，这超出了 -越界。

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

假设 capacity 为 10，因此您有一个包含 10 个元素的数组，范围从元素 0 到 9。count 告诉我们有多少元素被使用。如果 count 恰好是 9，那么当您将 count 递增 1 时，它现在是 10。然后，当您标记为产生段错误的行出现时，您正在尝试访问元素 10，在我们的示例中。长度为 10 的数组中没有元素 10，因此超出范围。

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!

当然，当您继续使用 array[count] 时，该部分之后的所有内容都会导致相同的问题。