Если я правильно помню, была статья о том, как Visicalc сделал это, возможно, в журнале Byte в начале 80-х. Я считаю, что это был какой-то редкий массив. Но я думаю, что были ссылки как вверх-вниз, так и влево-вправо, поэтому любая ячейка имела указатель на ячейку над ней (как бы много ячеек не было), под ней, слева от нее. и справа от него.
тим, я работаю над клоном Excel в C #. Моя сетка представлена следующим образом:
private struct CellValue
{
private int column;
private int row;
private string text;
}
private List<CellValue> cellValues = new List<CellValue>();
Каждый раз, когда пользователь добавляет текст, я просто упаковываю его как CellValue и добавляю его в cellValues. Учитывая тип CellValue, я могу определить его строку и столбец за время O (1), и это здорово. Однако, учитывая столбец и строку, мне нужно перебрать все cellValues, чтобы найти, какой текст находится в этом столбце и строке, что очень медленно. Кроме того, учитывая текст, мне тоже нужно перебрать всю вещь. Есть ли какая-либо структура данных, где я могу выполнить все 3 задачи за O (1) время?
Обновлено: просматривая некоторые ответы, я не думаю, что нашел тот, который мне нравится. Могу я:
Не хранить более 2 копий CellValue, чтобы избежать их синхронизации. В мире C я бы неплохо использовал указатели.Строки и столбцы могут быть добавлены динамически (в отличие от Excel).