Помогите с функцией удаления записи из блочного списка!

Question

Я вполне мог что-нибудь напутать, потому что функция не работает корректно! Если в текущем блоке остаются элементы (т.е. cnt > 1), то сдвинуть содержимое блока на одну позицию влево, начиная с последней заполненной ячейки, до позиции удаляемого элемента; уменьшить счетчик на единицу иначе // удаляется последний элемент исключить опустевший блок полностью, удалив узел в двусвязном списке, настроив указатели previous и next, где необходимо

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;     //указатель на хвост списка
};

   void blockList_delete_custom(blockList* l, size_t indexBlock, const size_t indexCell) //Удаление строчки
    {
        block* temp = l->head;
        /*считаем блоки, не доходя до последнего.
        Если это последний блок, проверяем не превышало значение indexBlock фактическому
        количеству блоков. Если нет, тогда удаляем из массива записей этого блока переданные в функцию
        номер блока->номер строчки, при условии, что indexCell < blockSize*/
        while (indexBlock != 0 && temp != l->tail) // перемещаемся по блоклисту в поиске нужного юзерблока
        {
            temp = temp->next;
            indexBlock--;
        }
        if (temp->cnt > 1) // если в текущем блоке остаются элементы (т.е. cnt > 1), то сдвинуть содержимое
            //блока на одну позицию влево, начиная с последней заполненной ячейки,
            //до позиции удаляемого элемента; уменьшить счетчик на единицу
        {
            for (size_t i = temp->cnt; i > indexCell; i--) // Сдвигаем влево
            {
                temp->cells[i + 1] = temp->cells[i];
            }
            //Удаляем ячейку
            temp->cnt--;
            //выходим
            return;
        }
        else //исключить опустевший блок полностью, удалив узел в двусвязном списке, настроив указатели previous и next, где необходимо
        {
            block* tmp = temp;
            temp = temp->next;
            delete tmp;
    
            temp->prev = l->tail;
            temp->next = l->head;
            return;
        }
    }

Answer 1

Если я правильно понял то исходные условия:
indexBlock - номер блока, в котором нужно удалить строку
indexCell - номер строки, которую нужно удалить
У вас в программе есть проблемы с логикой:

Список не хранит свой размер, заранее проверить что indexBlock меньше или равен размеру списка невозможно. И при движении по списку не проверяется, что дошли до нужного номера блока:

while (indexBlock != 0 && temp != l->tail) // перемещаемся по блоклисту в поиске нужного юзерблока
{
   temp = temp->next;
   indexBlock--;
}

Т.е. если список состоит из 2 блоков, а нужно удалить строчку из 3 блока indexBlock == 3 , то при проходе по блокам остановитесь на втором и удалится строчка из 2 блока.

Проблемы с удалением строки:

if (temp->cnt > 1) // если в текущем блоке остаются элементы (т.е. cnt > 1), то сдвинуть содержимое
          //блока на одну позицию влево, начиная с последней заполненной ячейки,

{
   for (size_t i = temp->cnt; i > indexCell; i--) // Сдвигаем влево
   {
      temp->cells[i + 1] = temp->cells[i];
   }
   temp->cnt--;  //Удаляем ячейку
   return;
        }

если количество строк cnt в блоке равно 5 то при попытке доступа или записи чего-то в 6 элемент массива состоящего из 5 элементов будет крах программы или неопределенное поведение (undefined behavior) temp->cells[i + 1] = temp->cells[i];
поскольку индексация массивов начинается с 0, то последний элемент массива будет cells[4]. А размер == 5. При попытке доступа к cells[i] когда cnt == 5 а i = cnt опять получится доступ за пределы массива cells[5] и крах программы или неопределенное поведение
нигде не проверяется, правильность индекса строчки на удаление. Если у вас в блоке 3 строки а нужно удалить 5-ю, то в блоке просто уменьшается счетчик, т.е. удаляется последняя строка - это возможно нормальное поведение, но оговорить нужно. Также нужно для себя поставить логическое ограничение - indexCell считается от 0 или от 1, чтобы правильно отсчитывать строчку.
в комментариях пишете что сдвигаете влево, а на самом деле сдвигаете вправо
сдвиг влево это первому элементу cells[1] присвоить значение второго элемента cells[2], а здесь всё наоборот
при сдвиге влево начинать нужно не с последнего элемента, а с элемента следующего за удаляемым, иначе просто затираются данные
допустим в массиве было 1 2 3 4 и нужно удалить 1
сначала 4 скопируется в 3 - 1 2 4 4
потом 4 из позиции где была 3 скопируется в 2 - 1 4 4 4
потом 4 из позиции где была 2 скопируется в 1 - 4 4 4 4
затем последняя 4 удалится - 4 4 4
А должно было быть 2 3 4

Проблемы с удалением блока

//исключить опустевший блок полностью, удалив узел в двусвязном списке, настроив указатели previous и next, где необходимо
{
   block* tmp = temp;
   temp = temp->next; // а если этот блок был последним? 
   delete tmp;
   
   // здесь элемент закольцовывается с началом и концом списка
   // абсолютно бессмысленное действо
   temp->prev = l->tail;
   temp->next = l->head;
   return;
}

если блок был последним, то указатель temp->next == nullptr, и temp становится nullptr и дальше обращение по нулевому указателю приводит к краху программы
после удаления блока, указатель next предыдущего блока и указатель prev следующего блока по-прежнему указывают на этот удаленный блок и при следующем проходе по списку будет обращение в чужую память что приведет к неопределенному поведению программы, в лучшем случае - краху
указатели блока, следующего за удаленным просто выставляются предыдущий на конец списка, следующий на начало списка - в результате блок закольцовывается на начало и конец списка. видимо подразумевалось:

    if(temp == l->tail) // если блок последний в списке
    {
        l->tail = temp->prev; // конец списка устанавливаем на предыдущий блок
        (temp->prev)->next = nullptr; // указатель next предыдущего блока обнуляем
    } else
    if(temp == l->head) // если блок первый в списке
    {
        l->head = temp->next; // начало списка устанавливаем на следующий блок
        (temp->next)->prev = nullptr; // указатель prev следующего блока обнуляем
    }
    else // блок в середине списка - до него и после него есть блоки
    {
      (temp->prev)->next = temp->next;
      (temp->next)->prev = temp->prev;
    }
    delete temp;

БЛОГ НА HUSL

Помогите с функцией удаления записи из блочного списка!

Ответы (1 шт):