Ошибки метода реализации очереди массива C ++

Question

Я пытаюсь реализовать очередь, используя массив в C ++. Я не могу понять, почему некоторые из моих методов не работают должным образом. Мой существующий метод не находит значение, которое находится в очереди, и мой дублирующий метод дублирует заднюю часть моей очереди вместо передней. Метод duplicate должен взять все, что находится в начале очереди (если он не пустой или полный), скопировать это значение и поместить его в начало очереди. Мой примет заднее значение, скопирует его и поместит в одну позицию сзади. Кроме того, метод Enqueue неправильно вставляет значения.

#include <iostream>
#include "queue.h"

using namespace std;

static int nums[10];
int front = 0, rear = 0, sizeOfArray = 0;
int initialCapacity = 10;


int Enqueue(int num) {
    if (sizeOfArray == initialCapacity) {
        return -58;
    }
        for (int i = 0; i < initialCapacity; i++) {
            if (nums[i] == num) {
                return -62;
            }
            else {
                nums[rear] = num;
                rear = (rear + 1);
                sizeOfArray++;
                return 0;
            }   
    }
}

int Dequeue(int& num) {
    if (sizeOfArray == 0) {
        return -64;
    }
    front = (front + 1);
    sizeOfArray--;
    return 0;
}

int isEmpty() {
    if (sizeOfArray == 0) {
        return 1;
    }
    else {
        return 0;
    }
}

int Exists(int num) {
    for (int i = 0; i < sizeOfArray; i++) {
        int index = (front + i);
        if (nums[index] == num) {
            return 1;
        }
        else {
            return 0;
        }

    }
    return 0;
}

void Clear(void) {
    front = rear = sizeOfArray = 0;
}

void Print(void) {
    for (int i = 0; i < sizeOfArray; i++) {
        cout << nums[i] << " ";

    }
    cout << endl;
}


int Duplicate(void) {
    if (sizeOfArray == 0) {
        return -78;
    } 
    if (sizeOfArray == initialCapacity) {
        return -81;
    }
    int dupeNum;
    dupeNum = nums[front];

    nums[front + 1] = dupeNum;
    sizeOfArray++;
    return 0;
}

Всякий раз, когда я выполняю следующие методы в тестовом драйвере: ставить в очередь 4 ставить в очередь 5 существует 5 дубликата печати

Я получаю этот вывод:

тест 1 0 - 0 указывает на успех

Тест 2 0 - 0 указывает на успех

Тест 3 0 - 0 указывает на сбой

Тест 4 0 - указывает на успех

4 4 0

Answer 1

Для начала, если front не равен всегда нулю, этот код не будет делать то, что вы ожидаете:

int index = (front + i);
if (nums[index] == num) ...

Это потому, что вы попытаетесь прочитать массив за его конец. Вам нужно обернуть в верхнем конце массива что-то вроде:

int index = (front + i) % initialCapacity;

---

Другие проблемы:

• ваша функция очереди проверяет наличие дубликата в все элементы массива, даже те, которые технически не заполнены. Вы должны проверять только заполненные значения (от front до front + sizeOfArray, с переносом, как описано выше).
• также неправильно обрабатывает перенос при добавлении элемента. Следующее значение rear должно быть перенесено на ноль после вставки элемента в последний элемент массива: rear = (rear + 1) % initialCapacity.
• То же самое для функций удаления и дублирования при настройке front.
• использование magi c кодов возврата - плохая идея, лучше было бы использовать перечисление (см. Мой код ниже).
• ваша очередь никогда на самом деле никогда не будет помещает искомое значение в передаваемый вами ссылочный параметр, что означает, что оно никогда не изменится. Прежде чем увеличивать front (убедившись, что вы исправили перенос), вы можете просто сделать num = nums[front].

---

Там могут быть другие проблемы, но Самое важное, что, несмотря на использование определенных вещей на C ++, на самом деле это не код C ++. Самая большая ошибка, которую может сделать кодер C ++, - это кодер C +, эта странная порода потерялась на полпути между мирами C и C ++: -)

Ваша очередь должна действительно быть классом, а не автономной функции. Таким образом, вы можете должным образом инкапсулировать его и защитить данные от внешнего вмешательства.

Я не скажу вам , как сделать это, поскольку это сделало бы этот ответ невыносимо долгим, но чем раньше вы начинаете идти таким путем, тем лучше вы станете программистом на C ++.

---

Например, следующая полная программа показывает один из способов сделать это. Я бы не стал воспринимать это как вашу собственную работу, но полезно получить представление о том, как программист C ++ может это сделать:

#include <cstdlib>
#include <memory>

template<class T>
class MyQ {
private:
    size_t m_sz, m_first, m_next, m_used;
    T *m_data;

public:
    enum RetCode { OK, FULL, EMPTY };

    MyQ(size_t sz = 10) : m_sz(sz), m_first(0), m_next(0), m_used(0), m_data(new T[sz]) {}
    ~MyQ() { delete [] m_data; }

    enum RetCode Enqueue(T item) {
        if (m_used == m_sz) return FULL;
        m_data[m_next] = item;
        m_next = (m_next + 1) % m_sz;
        ++m_used;
        return OK;
    }

    enum RetCode Dequeue(T &item) {
        if (m_used == 0) return EMPTY;
        item = m_data[m_first];
        m_first = (m_first + 1) % m_sz;
        --m_used;
        return OK;
    }
};

// The class proper is above, the following is just a test harness.

#include <iostream>

int main() {
    MyQ<int> x(6);
    for (int i = 0; i < 7; i++) {
        std::cout << "Enqueueing " << i << " returns " << x.Enqueue(i) << '\n';
    }
    std::cout << '\n';

    int val;
    for (int i = 0; i < 4; i++) {
        MyQ<int>::RetCode rc = x.Dequeue(val);
        if (rc == MyQ<int>::OK) {
            std::cout << "Dequeueing returns " << rc << ", value was " << val << '\n';
        } else {
            std::cout << "Dequeueing returns " << rc << '\n';
        }

        std::cout << "Enqueueing " << (i + 7) << " returns " << x.Enqueue(i + 7) << '\n';
    }
    std::cout << '\n';

    for (int i = 0; i < 7; i++) {
        MyQ<int>::RetCode rc = x.Dequeue(val);
        if (rc == MyQ<int>::OK) {
            std::cout << "Dequeueing returns " << rc << ", value was " << val << '\n';
        } else {
            std::cout << "Dequeueing returns " << rc << '\n';
        }
    }
    std::cout << '\n';
}

---

Выходные данные показывают различные действия и условия ошибки:

Enqueueing 0 returns 0
Enqueueing 1 returns 0
Enqueueing 2 returns 0
Enqueueing 3 returns 0
Enqueueing 4 returns 0
Enqueueing 5 returns 0
Enqueueing 6 returns 1

Dequeueing returns 0, value was 0
Enqueueing 7 returns 0
Dequeueing returns 0, value was 1
Enqueueing 8 returns 0
Dequeueing returns 0, value was 2
Enqueueing 9 returns 0
Dequeueing returns 0, value was 3
Enqueueing 10 returns 0

Dequeueing returns 0, value was 4
Dequeueing returns 0, value was 5
Dequeueing returns 0, value was 7
Dequeueing returns 0, value was 8
Dequeueing returns 0, value was 9
Dequeueing returns 0, value was 10
Dequeueing returns 2