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

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

База данных студентов на Delphi + Microsoft SQL Server
База данных студентов на Delphi (файл записей) + Блок схемы
Игра Sokoban на Delphi + Блок схемы

Реклама



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

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


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

Случайные загрузки
JBlabel3D
XPButtons
Файловый менеджер
Error mod
DFileDeleter
IconCut [Исходник...
Моделирование дви...
DelphiXIsoDemo1
DiskInfo
Размещение элемен...
Borland C++Builde...
FatScrollbar
Mass Photo Upload
Comdrv
Панель Наша Кнопка
FilesInfo
DAlarm
Создание отчетов ...
PHP5. Профессиона...
CoolControls v3.0...

Топ загрузок
Приложение Клие... 100474
Delphi 7 Enterp... 87523
Converter AMR<-... 20081
GPSS World Stud... 13130
Borland C++Buil... 11948
Borland Delphi ... 8639
Turbo Pascal fo... 7042
Visual Studio 2... 5002
Калькулятор [Ис... 4863
FreeSMS v1.3.1 3544
Случайные статьи
Возможности окруже...
Silver Fox - это д...
Простейший пример ...
Назначение физичес...
Этап 5 - использов...
ВВОД ИНФОРМАЦИИ С...
Информационные про...
Конструкторы
ENDIF directive ml...
Работа над языком ...
Часто критически в...
Вставить галерею
Перечислимые свойства
Глава 5
Обновление плагинов
на отдельных учетн...
FVARIABLE (ОПРЕДЕЛ...
Выбор объекта Data...
По поводу отчислен...
Поиск в Гугле
26 шагов к 15 тыс....
Маршалер свободной...
Переработка
Развертывание ЦС п...
Создание атрибутов
Статистика



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


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