Лінійне уявлення з покажчиком нерегулярних масивів

Один спосіб уникнення порожнього витрати пам’яті – упакувати дані в одно-
мірному масиві В. На відміну від трикутних непостійні масиви не можна опи-
сать за допомогою формул для обчислення відповідності елементів в різних масивів
вах. Щоб вирішити цю проблему, можна створити інший масив, який містить
значення зміщення кожного рядка в одновимірному масиві В.
Якщо додати мітку в кінці масиву В, яка вказує точку відразу за по-
следние елементом, в ньому буде простіше визначати положення точок, відповід-
ціалу кожному рядку. Потім точки, які складають багатокутник i,
займуть в масиві В позиції від A [i] до A [i + 1] – 1. Наприклад, програма може
перерахувати елементи, які складають рядок i, використовуючи наступний код:
for j := A[i] to A[i+l]-l do
/ / Вивід записи B [j].

Цей метод називається нумерацією зв’язків (forward star). На рис. 4.4 показано
уявлення непостійного масиву, зображеного на рис. 4.3, за допомогою ну-
нумерації зв’язків. Мітка зафарбована сірим кольором.
Рис. 4.4. Подання непостійного масиву за допомогою нумерації зв’язків
Цей метод підходить і для створення багатовимірних нерегулярних масивів.
Можна використовувати тривимірне представлення нумерації зв’язків для зберігання
набору малюнків, кожний з яких складається з різного числа багатокутників.
На рис. 4.5 схематично показана тривимірна структура даних, представлений-
ная за допомогою нумерації зв’язків. Мітки зафарбовані сірим кольором. Вони вказу-
ють на позицію позаду значущих даних
наступного масиву.
Подання нерегулярних масивів
вов в лінійному вигляді вимагає мінімаль-
них витрат пам’яті. “Впустити” витраті-
ється тільки пам’ять, займана мітками.
За допомогою подібної структури дан-
вих можна швидко і легко перерахувати
вершини багатокутника. Так само просто
зберігати ці дані на диску і завантажувати
жати їх назад в пам’ять. Але модифікувати масиви з нумерацією зв’язків до-
статочно складно. Припустимо, ви хочете додати нову вершину до першого
многоугольнику, зображеному на рис. 4.4. Для цього знадобиться зрушити всі
точки праворуч від нової на одну позицію, звільняючи місце для вводиться еле-
мента. Потім потрібно додати одиницю до всіх елементів, наступним після пер-
вого в масиві, щоб вирахувати новий покажчик. Нарешті, слід вставити но-
вий елемент. Такі ж труднощі виникають при видаленні точки з першого
багатокутника.
Рис. 4.5. Тривимірний нерегулярний масив
На рис. 4.6 показано виставу у вигляді нумерації зв’язків масиву з рис. 4.4
після додавання однієї точки до першого багатокутника. Змінені елементи
зафарбовані сірим кольором. Як видно з малюнка, такими є майже всі еле-
менти обох масивів.
Рис. 4.6. Додавання точки при лінійному представленні

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*