Навигация
Главная
Поиск
Форум
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
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 65058
Модуль Forms 64835
Пример работы с... 63233
ТЕХНОЛОГИИ ДОСТ... 61548
Имитационное мо... 57389
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

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

Моделирование работы участка термической обработки шестерен на GPSS + По...
Лабораторная работа по динамическим спискам на Turbo Pascal (перемещение...
Файл записей с выводом обратного заголовка на Turbo Pascal

Реклама



Подписывайся на 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 Комментариев · 10506 Прочтений · Для печати

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


Комментарии
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...
Шаблон для новост...

Случайные загрузки
VksButton
Мод "register.php...
C# Учебный курс
начисление процен...
Язык программиров...
Х. М. Дейтел, П. ...
XPmenu
Учебник для продв...
Система баннеро...
Swing. Эффектные...
Аватары в комме...
MPTools
Java в примерах -...
EditNew
CarGame [Исходник...
Tetris 2002
Иллюстрированный ...
Программа предназ...
WAP версия сайта
Delphi 6 программ...

Топ загрузок
Приложение Клие... 100466
Delphi 7 Enterp... 86611
Converter AMR<-... 20077
GPSS World Stud... 12634
Borland C++Buil... 11752
Borland Delphi ... 8555
Turbo Pascal fo... 7037
Visual Studio 2... 4998
Калькулятор [Ис... 4759
FreeSMS v1.3.1 3541
Случайные статьи
Обобщение алгоритм...
Песочные часы
Открыть сетевой до...
Назначение онлайно...
Предоставление сеа...
Новый корпус для д...
Процедура Ваr3D - ...
Применяйте AsyBEUI...
Разработка игр в д...
Как получить досту...
Интернет-магазин ...
Корень дерева упра...
Еще три возможност...
DMZ).• Сервер DNS.
Отсутствует прямой...
Алгоритмы для слож...
Игровой сервер ком...
компьютеры клиенто...
но вместо прав адм...
Иерархия классов о...
«Использование» ша...
Инсталляция библио...
Что подразумевает ...
Копия установочног...
в кадре использует...
Статистика



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


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