Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 60083
Реклама
Сейчас на сайте
Гостей: 4
На сайте нет зарегистрированных пользователей

Пользователей: 13,113
новичок: SaRdOr0493
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Поиск пути в графе заданном списками инцедентности на Turbo Pascal
Информационная система - транспортный парк на Turbo Pascal (База данных)...
Выбор наилучших альтернатив с использованием методов оптимизации на Delp...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Треугольные массивы
Некоторым программам необходимы значения только половины записей в дву-
мерном массиве. Предположим, что у вас есть карта, на которой 10 городов обозна-
чены цифрами от 0 до 9. При помощи массива можно построить матрицу смежнос-
ти (adjacency matrix), хранящую информацию о наличии между парами городов
благоустроенных дорог. Элемент A[i, j] равен True, если между городами i и j есть
шоссе.
В таком случае значения в одной половине матрицы будут дублировать значе-
ния в другой, потому что A[i, j] = A[j, i]. Таким же образом в программу не будет
включен элемент A[i, i], так как нет смысла строить автостраду от города i в тот же
самый город. Значит, потребуются только элементы A[i, j] в левом нижнем углу,
для которых i > j. Можно с таким же успехом использовать элементы, находящие-
ся в правом верхнем углу. Поскольку все они образуют
треугольник, этот тип массивов называется треугольным
массивом (triangular array).
На рис. 4.1 изображен треугольный массив. Элемен-
ты со значимыми данными обозначены как X, ячейки, со-
ответствующие дублирующимся элементам, оставлены
пустыми. Незначащие диагональные записи A[i, i] обо-
значены тире.
Затраты памяти на хранение таких данных для не-
больших двумерных массивов не слишком существенны.
Если же на карте много городов, то напрасный расход па-
мяти может оказаться значительным. Для N городов будет N*(N- l)/2 дублиро-
ванных элементов и N элементов, подобных A[i, i], которые не являются значи-
мыми. Если карта содержит 1000 городов, то в массиве будет храниться больше
полумиллиона ненужных элементов.
Треугольный массив
Рис. 4.1. Треугольный массив
Вы можете избежать таких потерь памяти, создав одномерный массив В и упа-
ковав в него значимые элементы массива А.
Разместите записи в массиве В построчно, как показано на рис. 4.2. Обратите
внимание, что индексы массива перечисляются, начиная с 0. Это делает следую-
щие формулы немного проще.
Чтобы еще более упростить это представление треугольного массива, можно
написать функции для преобразования индексов массива А в индексы массива
В. Формула для преобразования A[i, j] в В[х] имеет следующий вид:
X := Round(i*(i-l)/2)+j; // Для i>j



Например, если i = 2 и j = 1, то получится х = 2* (2-1) /2 + 1 = 2. Это
означает, что А[2,1] отображается в позицию 2 в массиве В, как показано на рис. 4.2.
Помните, что массивы нумеруются, начиная с 0.
Эта формула справедлива только при i > j. Значения других записей массива А
не передаются в массив В, потому что они избыточны или незначимы.
Упаковка треугольного массива в одномерный массив
Рис. 4.2. Упаковка треугольного массива в одномерный массив
Если нужно получить значение A[i, j], где i < j, вы можете вычислить значение
A[j,i].
Подобные вычисления достаточно сложны. Здесь требуются операции вычи-
тания, сложения, умножения и деления. На выполнение программы будет уходить
намного больше времени, если придется часто прибегать к таким операциям. Это
пример компромисса между пространством и временем. Упаковка треугольного
массива в одномерный экономит память, хранение данных в двумерной матрице
занимает больший объем памяти, но экономит время
Опубликовал Kest October 18 2009 18:28:52 · 1 Комментариев · 10871 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
L May 13 2014 23:09:50
А как сделать распаковку одномерного обратно в треугольный
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Эффект лампы на р...
Borland Delphi 8 ...
Советы от Даниилы...
CoolHints2k v1.03
C++ Builder в за...
Ранги для форума
Пример OpenGL гра...
100 компонентов о...
Иллюстрированный ...
около 291 статьи ...
Прграммирование в...
Модифицированная ...
NetGraph [Исходни...
Профессиональное ...
Запрет гостям ск...
Delphi Быстрый Ст...
PCXReader. Програ...
Delphi Russian Kn...
Flash MP3 Player ...
Голосование для ...

Топ загрузок
Приложение Клие... 100519
Delphi 7 Enterp... 91109
Converter AMR<-... 20098
GPSS World Stud... 15138
Borland C++Buil... 12878
Borland Delphi ... 9073
Turbo Pascal fo... 7105
Калькулятор [Ис... 5156
Visual Studio 2... 5027
FreeSMS v1.3.1 3557
Случайные статьи
HTPC на базе Windows
В среде с постоянн...
Использование прот...
Казино
Введение в создани...
DMZ, настройте вне...
Отсутствует прямой...
Номер улицы IF Sel...
Разработать просто...
— только на объект...
Абстрактные классы
При наследовании а...
Можно ли найти уда...
Написанный вручную...
Создание рабочей к...
NUKE. Факты из ист...
Ваша цель — опреде...
Онлайн-слоты для р...
Чтение сообщения и...
Условия коллектива
Преимущество автом...
7.8. Использован...
Межкомнатные двери...
Продать автомобиль...
Имитационное модел...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?