Подання структур у пам’яті ЕОМ - Студопедія
Як реально уявити у пам'яті структуру даних тієї чи іншої типу? Зазвичай для однорідних масивів постійної довжини використовують послідовне уявлення. У цьому випадку логічно суміжні елементи масиву розміщуються у фізично суміжних осередках пам'яті. Послідовне уявлення неважко поширити і масиви вищої розмірності, розташовуючи у послідовних осередках пам'яті елементи масиву в лексикографічному порядку індексів (i1,i2, . ik). Наприклад, якщо у випадку двовимірного масиву через i1 позначимо номер рядка, а через i2-номер стовпця, масив виявиться розташованим у пам'яті по рядках.
Можна утворити кільце, використовуючи для цього одновимірний масив постійної довжини, при зверненні до елементів якого як тільки буде досягнутий один кінець масиву, відразу ж переходити до іншого кінця. На основі кільця дуже легко продати чергу або двосторонню чергу. Якщо підтримується баланс за кількістю операцій включення та виключення елементів черги, то осередки пам'яті, зайняті чергою, послідовно переміщаються у напрямку включення нових елементів. Для представлення стека можна скористатися одновимірним масивом, обмеживши доступ до елементів єдиним індексом, що вказує на вершину стека в даний момент. Нульове значення індексу означає, що стек порожній.
Якщо для подання стеків і черг використовувати масиви з малим числом елементів, то дуже велика ймовірність їхнього переповнення. Збільшення довжини масивів як погіршує використання пам'яті, а й гарантує від переповнення. Якщо використовувати масиви такої довжини, щоб унеможливити їх переповнення, то частина пам'яті, дійсно зайнята даними, виявиться зовсім невеликою. Ще більшимНедоліком є те, що обробка буде припинена, тільки-но переповниться хоча б один масив, відведений під стек, незважаючи на наявність достатнього обсягу вільної пам'яті в інших масивах. Звичайно, виникають питання: чи не можна всю незайняту пам'ять, відведену для представлення масивів змінної довжини, використовувати як загальну; як це позначиться ефективності використання пам'яті?
Мал. 2.3. Подання кільця та черги з використанням покажчиків (подання у зв'язаній пам'яті):
а -кільце; б - виключення з кільця (включення в кільце). За винятком суцільна стрілка замінюється на пунктирну, а при включенні - пунктирна на суцільну;в -двостороння черга
Цю проблему можна вирішити шляхом надання пам'яті певної структури, зв'язавши між собою окремі блоки пам'яті за допомогою покажчиків. Мал. 2.3а ілюструє ідею пов'язаного уявлення з прикладу кільця. Прямокутники на малюнку показані вузли пам'яті. Кожен вузол складається із двох полів. Одне поле містить елемент або складнішу структуру даних, а інше — покажчик на наступний вузол. Стрілки малюнку відповідають значенням покажчиків. Якщо послідовність представлена у зв'язаної пам'яті, то операції включення та виключення елементів у послідовність виконуються так, як показано на рис. 2.3.б. Обидві операції використовують список вільної пам'яті - при включенні пам'ять займається, а при виключенні повертається до цього списку. У будь-якому випадку відбувається зміна трьох покажчиків. При цьому із схеми на рис. 2.3.б випливає, що при заданому покажчику на вузол, що містить дане S, операції включення та виключення можливі лише «праворуч від S» і неможливі «зліва від S». Операція "виключити S" також неможлива. Одним із способів,що дозволяють подолати ці обмеження є використання в кожному вузлі двох покажчиків, що буде розглянуто нижче. У цьому випадку стане можливим проводити включення та виключення праворуч і ліворуч від S. Можливий і інший технічно простий прийом. При необхідності «виключити вузол S» перепишемо в нього дані вузла, що знаходиться праворуч від S (данеТ),а потім виключимо вузол справа (фактично буде виключено вузол, що йде заS, —вузол, що спочатку містив данеТ).Аналогічно може бути виконана і операція «включити зліва відS».Для цього спочатку включимо новий вузол праворуч від S і перепишемо в нього данеS,потім запишемо нове дане у вузол, який раніше займало данеS,і, нарешті, пересунемо покажчик доступу до структури на вузол, який тепер містить дане S.
Подання у пам'яті двосторонніх черг має забезпечити можливість доступу з обох кінців черги. Це може бути досягнуто використанням у кожному вузлі двох покажчиків, як показано на рис. 2.3.в. У цьому випадку операції включення та виключення вимагатимуть зміни п'яти покажчиків.
Вважається, що списки забезпечують ефективне використання пам'яті. Потрібно пам'ятати, що для зберігання покажчиків потрібна додаткова пам'ять, а для роботи з покажчиками - додаткові операції.
Основний сенс застосування покажчиків не стільки підвищення ефективності обробки, скільки у можливості уявлення складніших структур. Використання покажчиків дозволяє пов'язувати між собою найрізноманітніші дані, що є основою представлення різних складних структур, механізмів, явищ. Серед них особливе місце посідаютьпорівняно прості, але дуже важливі деревоподібні структури. Наприклад, якщо для представлення вузлів бінарного дерева використовувати записи з двома покажчиками, як показано на рис. 2.4, то можна робити обхід дерева починаючи від кореня у напрямку кінцевих вузлів. Операції виключення чи включення аркуша (кінцевого вузла) виконуються дуже просто-зміною всього трьох покажчиків.
У математиці однією з базових понять ємножина.У сфері обробки даних операції над множинами часто також дуже бажані. Проте уявлення у пам'яті безлічі, що має структури, представляє значну проблему, і зазвичай намагаються обходитися без них. Нехай, наприклад, у тривимірному просторі задано кінцеву множину, що складається з n точок. Як уявити цю множину в пам'яті, щоб мати можливість виконувати відповідні операції? Якщо число елементів множини постійно і всі елементи заздалегідь відомі - перенумеруємо їх числами від 1 до n. , .п)—будемо зберігати в матриці з (nхЗ) елементів. Тоді для представлення будь-якої підмножини цієї множини можна скористатися одновимірним масивом з бітів (p1, р2, .рn), присвоюючи Pi(i-му біту) значення 1, якщо точка з номеромiналежить підмножиною, і 0, якщо не належить. Такий логічний масив зазвичай називають бітовою картою. Операції над множинами в такому випадку зводяться до логічних операцій над відповідними логічними масивами.
Мал. 2.4. Подання бінарного дерева з використанням покажчиків.
Чи не знайшли те, що шукали? Скористайтеся пошуком: