Сортированный индексированный список с использованием связанного списка в массиве

Question

У меня есть проект для реализации отсортированного индексированного списка с использованием односвязного списка в массиве. И у меня есть некоторые проблемы, когда я пытаюсь сделать функцию добавления. Вот так выглядит мой конструктор:

SortedIndexedList::SortedIndexedList(Relation r) {
    this->cap = 10;
    this->elems = new TComp[this->cap];
    this->next = new TComp[this->cap];
    this->head = -1;
    for (int i = 0; i < this->cap - 1; i++)
        this->next[i] = i + 1;
    this->next[this->cap] = -1;
    this->firstEmpty = 0;
    this->size_elems = 0;
    this->rel = r;
}

И это моя функция добавления:

void SortedIndexedList::add(TComp e) {
    if (this->size() == this->cap)
        this->resize();
    if (this->size() == 0)
    {
        int newPosition = this->firstEmpty;
        this->elems[newPosition] = e;
        this->firstEmpty = this->next[this->firstEmpty];
        this->next[newPosition] = this->head;
        this->head = newPosition;
    }
    else
    {
        int current = this->head;
        int currentPosition = 0;
        while (current != -1 && currentPosition < this->size() && rel(this->elems[current], e))
        {
            current = this->next[current];
            currentPosition++;
        }
        if (current != -1)
        {
            int nextPos = this->firstEmpty;
            this->firstEmpty = this->next[firstEmpty];
            this->elems[current] = e;
            this->next[nextPos] = this->next[current];
            this->next[current] = nextPos;
        }
    }
    this->size_elems++;
}

Я хотел убедиться, что это работает, и я попытался добавить 1, затем 2, затем 3 и выведите в каждой строке элементы, но I 2 и 3 не будут добавлены (отношение было <=). Может ли кто-нибудь помочь мне, пожалуйста? Я не мог понять, что я сделал не так. </p>

Answer 1

Я думаю, что вы пропустили индекс при инициализации массива next:

for (int i = 0; i < this->cap - 1; i++)
        this->next[i] = i + 1;
this->next[this->cap] = -1;

Вы получите this->cap - 2 в for-l oop (i < this->cap - 1), поэтому this->cap - 1 никогда не присваивается значение.