@Mercury13
Программист на «си с крестами» и не только

Существует ли структура данных «расширяемая 2D-таблица»?

Хочу такую структуру данных: расширяемая/сужаемая двухмерная таблица.

То есть: у нас, например, таблица 5×5, и мы к ней сверху добавляем строку, и стала 6×5. А потом справа добавляем два столбца, и стала 6×7. А потом снизу убираем две строки, и стала 4×7.

Расширение и сужение возможно только с краёв — то есть нельзя убрать строку или столбец из середины, и нельзя добавить ничего в середину.

Подскажите, в каком направлении двигаться?
  • Вопрос задан
  • 140 просмотров
Решения вопроса 1
@Mercury13 Автор вопроса
Программист на «си с крестами» и не только
Пока остановился на таком механизме.
Есть два одномерных массива — оглавление строк и оглавление столбцов, два одномерных массива — задействованность строк/столбцов, а также двухмерный массив — буфер.

a[i,j] := buffer[rowIndex[i−i0], colIndex[j−j0]]

Если в rowIndex[i−i0] замечен маркер незадействованности, находим незадействованную строку и прописываем её в оглавлении.
Чтобы меньше перевыделять памяти, перевыделение идёт импульсами и с запасом. Например, хотим 20 строк, а выделяем сразу на 30.
Такой массив способен только расширяться, но этого мне хватает.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 4
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
можно не ограничиваться 2D
Как вариант — подсмотреть реализацию ndarray в Numpy.
Частично описано здесь (на англ.)
Данные хранятся в буфере – типа массива в C. И есть метаданные, описывающие "вид" на этот буфер.
Когда меняется форма, создаётся новый объект метаданных, без изменений в самих данных.
Но тут не раскрывается тема вставки, как это изменяет размер буфера – создают новый или расширяют старый. В конце или распихивают по строкам.
Ответ написан
Комментировать
mayton2019
@mayton2019
Bigdata Engineer
Коробочное решение это хеш-табличка. Где ключ - координаты ячейки а значение это то что вы положите в ячейку.
Ответ написан
Комментировать
WinPooh32
@WinPooh32
Stack Overflow answer searching expert
Нет, в стандартных библиотеках такого нет, по крайней мере я не знаю про такие.

Вы можете реализовать сами:
1) С помощью связного списка;
2) На массиве, с заранее выделенной памятью, с добавлением элементов в центр. Далее расширять в ту сторону, которая требуется.
Ответ написан
@AlexSku
не буду отвечать из-за модератора
Матлаб для матрицы это делает автоматически (можно даже переставлять строки или столбцы в любом порядке). Он на базе Java.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы