Вопрос, собственно, не сколько по алгоритмам, столько по структурам данных.

Есть объекты-таблицы, по своей сути похожие на те таблицы, которые создаются в MS Word, например. А именно: таблица состоит из прямоугольных ячеек (их содержимое для простоты пока игнорируем), но она не просто двумерный массив, т.к. одна ячейка может быть растянута на несколько строк, столбцов или строк/столбцов. (Однако, при этом ни одна ячейка не пересекается с другой.)

Как представить такую таблицу в виде структур данных какого-нибудь языка высокого уровня (пусть, для определенности, будет C или C++, но можно и LISP)? Бинарное или N-арное дерево, например, отпадают (очень легко нарисовать таблицу, которая таким способом непредставима). Желательно также, чтобы выбранный способ представления был компактен и эффективен (как по памяти, так и по времени обработки). Особенно хочется найти *изящное* решение этой задачи (топорных я могу понапридумывать много, но меня они не устраивают )

Всем заранее спасибо за помощь.

Я не очень понял, что значит "ячейка может быть растянута"? Ты имеешь в виду, что в какой-то момент времени пользователь растягивает таблицу?
Если ты имеешь в виду что-то типа таблиц 1С (когда кликнув на ячейку ты получаешь доступ к подтаблице), то думаю это легко реализуется:
Создаешь структуру/класс, в которой есть поле (по мимо всего остального) - значение (допустим, строка). Каждая ячейка - это ссылка на другую таблицу. Если у таблицы размеры нулевые, то она должна считаться не таблицей, а значением ячейки, которая на нее ссылается.
Например:
Если это не подходит, приведи пример той таблицы, которую нельзя будет представить в таком виде.

Может быть, я не совсем точно выразился -- я имею в виду то, что одна ячейка может прилегать к нескольким соседним (по ширине, или по высоте, или и то и другое.)



В принципе, то, что вы предлагаете, и есть N-арное дерево (точнее, N*M-арное, если можно так сказать). Однако, привести пример таблицы, которую нельзя так представить, просто (sorry за ASCII-art):


    +---+---+---+
    |       |   |
    +---+---+   +
    |   |   |   |
    +   +---+---+
    |   |       |
    +---+---+---+


Думаю, что это простейший пример таблицы, которая не разбивается на подтаблицы, т.к. любое разбиение разрежет пополам минимум одну ячейку. Поэтому представить ее в виде дерева нельзя.
 

Это сообщение отредактировал(а) regis - 17.4.2006, 10:34

Возможно, Вы слишком ограниченно понимаете представление таблицы в виде иерархии подтаблиц.

А что, если так:


 

Для объединения ячеек по горизонтали или вертикали вполне сойдут флаги. Например, вводим флаги HOR_GROUP/VRT_GROUP. Певая ячейка, у которой есть такой флаг, начинает группу, первая, у которой он отсутствует - уже не в группе. 
Данные хранить только в первой ячейке.
Это если таблица представлена плотным 2-мерным контейнером.

Вариант 2 - для разреженной таблицы. Объединенные ячейки не храним, а в первую ячейку записываем, скажем, индекс последней ячейки или размер группы.
Делов-то. 
Главное - хорошо продумать и реализовать интерфейс класса таблицы.  

Не совсем понятно, что именно хочет автор. Можно ли в участок 2x2 клетки помещать таблицу, скажем, 1x3 клетки? 

Если несколько клеток объединено, то левая верхняя хранит описАтель спана вправо и вниз, а все с ней объединенные - только признак объединения.

Например:

Struct SPAN
Vert as integer default=1
Hor as integer default=1
end struct

Если клетка объединена - заполняется соотв. спан, а всем кто с ней объединен, присваивается спан = 0 в направлении объединения (один или оба, смотря где). 

Спасибо всем за предложенные идеи.
Я бы обобщая все предложенное, сделал бы так: к каждой клетке (вдобавок ко всему прочему) добавляется описатель ее положения внутри "спана" -- что-нибудь вроде:

int span_left, span_right;            // сколько клеток в спане справа/слева
int span_up, span_down;     // то же, сверху/снизу

Если клетка "нормальная", т.е. размеров 1x1, все эти элементы будут равны нулю.