Блоковый список. C++ ошибка в коде
Программа использует блоки для хранение массива данных. В самой функции всё сделано по методическим указаниям, но всё равно компилятор ругается на else if строчку функции, когда мы сдвигаем текущий блок вправо
Структуры данных:
struct record //запись с данными
{
float key; //ключ
vector<int> intData; //должен быть массивом
vector<char> charData; // должен быть массивом
float floatData; //инфа
};
struct block //блок
{
size_t cnt; //кол-во записей в блоке
record cells[blockSize]; //ячейки блока
block* prev = nullptr; //предыдущий элемент
block* next = nullptr; //следующий элемент
};
struct blockList //список блоков
{
block* head = nullptr; //указатель на голову списка
block* tail = nullptr; //указатель на хвост списка
};
Функция вставки элемента на нулеове место первого блока: (l - блоклист, b - Блок, r - запись)
void blockList_add_begin(blockList* l, record* r)
{
if (!l || !r)
return;
//Если список пуст (указатель на голову == nullptr)
if (!l->head) {
//Создаем новый блок c этой записью и задаем head
l->head = new block{ 1, *r };
//выходим
return;
}
//Если сюда попали, значит список не пуст
//Если блок в начале (head) может вместить данные
if (l->head->cnt < blockSize) //блок содержит свободные ячейки(т.е.cnt < blockSize), то вставить элемент(возможно, со сдвигом содержимого блока на одну позицию); увеличить счетчик;
{
//сдвигаем блоки на 1, освобождая 0 место
for (size_t i = l->head->cnt; i > 0; i--)
{
l->head->cells[i] = l->head->cells[i - 1];
}
//на освободившееся записываем данные
l->head->cells[0] = *r;
//увеличиваем счетчик записей
l->head->cnt++;
//выходим
return;
}
else if (l->head->next->cnt < blockSize) //иначе, т.е блок заполнен до конца; если следующий блок содержит свободные ячейки, то сдвинуть содержимое следующего блока на одну позицию вправо, поместить в нулевую позицию последний элемент текущего блока; увеличить счетчик следующего блока; сдвинуть содержимое текущего блока на одну позицию вправо начиная с позиции вставки, разместить новый элемент;
{
for (size_t i = l->head->next->cnt; i > 0; i--)
{
l->head->next->cells[i] = l->head->next->cells[i - 1]; //сдвигаем содержимое след. блока на 1 вправо
}
l->head->next->cells[0] = l->head->cells[blockSize - 1]; // помещаем в нулевую позицию последний элемент текущего блока
l->head->next->cnt++; //увеличиваем счетчик следующего блока
for (size_t j = l->head->cnt; j > 0; j--)
{
l->head->cells[j] = l->head->cells[j - 1]; //сдвигаем содержимое текущего блока на 1 вправо
}
l->head->cells[0] = *r; // размещаем новый элемент
return;
}
else // следующий блок тоже заполнен до конца создать новый блок и вставить его как узел в двусвязном списке, настроив указатели previous и next там, где необходимо. Осуществить сдвиг в старом блоке, хвостовой элемент поместить в нулевой позиции нового блока, добавляемый элемент - в освободившуюся позицию, счетчику нового блока присвоить единицу;
{
//Если сюда попали, значит список не пуст и нет мест в head
//создаем новый блок с записью
block* p = new block{ 1, *r };
//связываем блоки
p->next = l->head;
l->head = p;
return;
}
}
Ответы (1 шт):
Ну вот смотрите:
if (l->head->cnt < blockSize)
у вас НЕ выполняется. Значит,
l->head->cnt >= blockSize
Но далее вы делаете
for (size_t j = l->head->cnt; j > 0; j--)
{
l->head->cells[j] = l->head->cells[j - 1];
Итак, что получается при первой итерации? l->head->cells[j] то же, что и l->head->cells[l->head->cnt], т.е. l->head->cells[blockSize] (или даже больший индекс). Выход за границы массива? несомненный.
Думаю, компилятор оказался достаточно умным, чтобы это обнаружить...
У меня ощущение, что вы просто при copy-paste забыли дописать ->next, нет?