Struktura_danikh_Ch1

УДК 004.422.63 Г - 56

Рецензенти:

Л.П.Шевченко, канд.фіз.-мат.наук, професор, зав.кафедри економічної кібернетики (ХДТУБА) С.Ю.Запорожцев, канд.техн.наук, доцент кафедри

автоматизації та комп’ютерно-інтегрованих технологій (ХНАДУ)

Рекомендовано кафедрою комп’ютерного моделювання та інформаційних технологій, протокол № 4 від 21.11.2005

Затверджено методичною радою університету, протокол № 3 від 22.12.2005

Автори: Л.А.Гнучих, Є.М.Литвиненко, О.В.Мерлак

Г – 56 Гнучих Л.А., Литвиненко Є.М., Мерлак О.В. Моделі та структури даних. Частина І Структури даних: Навчально-методичний посібник. – Х.:ХДТУБА, 2006. – 78 с.

Розглянуто основні види структур даних, що використовуються у ЕОМ. Наведена достатньо велика кількість алгоритмів виконання особливо важливих операцій та їх реалізації у вигляді процедур та функцій написаних мовою Паскаль, які можуть бути використані в самостійних розробках студентів та програмістів.

Призначено для використання під час вивчення дисципліни «Моделі та структури даних» студентами спеціальності 6.050102 «Економічна кібернетика».

Іл. 42; Бібліогр. 34 назв

©Л.А.Гнучих, Є.М.Литвиненко, О.В.Мерлак

2006

4

Метою курсу «Моделі та структури даних» є ознайомлення студентів з існуючими моделями та структурами даних, а також опанування студентами навичок роботи з ними.

В результаті вивчення цього курсу студент повен:

1знати:

−основні принципи роботи з існуючими моделями та структурами даних;

−різноманітні типи моделей даних;

−сучасні методи розробки структур даних;

−існуючі типи баз даних;

2вміти:

−використовувати існуючі моделі даних;

−розробляти нові структури даних;

−розробляти взаємодіючі моделі даних;

3мати уяву:

−про сучасні моделі та структури даних;

−про призначення та способи використання різноманітних моделей даних;

−про сучасні системи управління базами даних.

Навчально-методичний посібник розроблений у відповідності з навчальною програмою курсу «Моделі та структури даних» спеціальності 6.050102 «Економічна кібернетика», який викладається у третьому та четвертому семестрах. На цьому курсі засновано подальше вивчення таких курсів як «Проектування баз даних», «Розподілені бази даних» та інших. Відповідно до освітньо-кваліфікаційної характеристики спеціальності 6.050102 «Економічна кібернетика» курс «Моделі та структури даних» виноситься на державний іспит зі спеціальності.

Програми зазвичай оперують інформацією, яка міститься у таблицях. У більшості випадків ці таблиці уявляють собою не просто масу числових даних,

аелементи даних з важливими структурними взаємозв’язками.

Унайпростішому виді таблиця може виглядати як простий лінійний список, а відомості про її структурні властивості можна отримати, якщо дати відповіді на наступні питання. Який елемент розташований у списку першим? Який останнім? Які елементи передують поточному елементу, а які йдуть за ним? Скільки елементів зберігається у списку?

Убільш складних випадках таблиця може мати структуру двовимірного масиву або навіть n-вимірного масиву для n більше 2, деревовидну структуру, яка має ієрархічні або розгалужені зв’язки, або таку складну багатозв’язну структуру з великою кількістю з’єднань як людський мозок.

Для правильного використання комп’ютера необхідно добре знати структурні взаємозв’язки між даними, основні методи подання структур всередині комп’ютера, а також методи роботи з ними.

5

РОЗДІЛ 1 ТЕРМІНИ ТА ВИЗНАЧЕННЯ

Інформація у таблиці складається з набору вузлів (nodes); також використовуються такі визначення як: записи (records), об’єкти (entities) або ланцюжки (beads). Іноді замість терміну „вузол” можуть використовуватися терміни „предмет” та „елемент”. Кожний вузол складається з одного або декількох послідовних слів у пам’яті комп’ютера, які можуть бути розділені на іменовані частини – поля. У найпростішому випадку вузол уявляє собою тільки одне слово і містить тільки одне поле, що цілком охоплює слово. Кожний вузол має власну адресу (address), яка також називається зв’язком (link), вказівником (pointer) або посиланням (reference) на цей вузол, і є адресою його першого слова. Адреса часто вказується відносно деякої базової комірки пам’яті.

1.1. Статична та динамічна пам’ять

Пам’ять комп’ютера, яку системи програмування виділяють для роботи програм, можна поділити на 4 частини:

1Програмний код.

2Дані.

3Програмний стек.

4Купа.

Пам’ять, виділена під програмний код, призначена для збереження програм у внутрішньому поданні системи програмування або у машинних кодах.

Пам’ять, виділена під дані, призначена для збереження статичних даних програм (глобальних змінних та констант).

Програмний стек призначений для тимчасового збереження локальних змінних, параметрів підпрограм, організації виклику підпрограм та обчислення виразів.

Купа призначена для динамічного розподілу пам’яті під структури даних. Пам’ять, виділена під програмний код та дані, є статичною, а програмний стек та купа – динамічною пам’яттю. Програмним стеком керує система

програмування без втручання програміста в той час, як купа спеціально призначена для використання програмістом.

Визначають дві базові операції над динамічною пам’яттю (купою): „виділити блок пам’яті” та „звільнити блок пам’яті”. Блоком називають неперервну ділянку пам’яті визначеного розміру. У деякий момент роботи програми купу можна представити у вигляді двох списків (рис. 1.1): список зайнятих блоків (L1) та список вільних блоків (L2).

Після отримання команди на виділення блоку пам’яті (рис. 1.1 а) ) програма, що керує купою, шукає у списку вільних блоків блок пам’яті потрібного розміру (або більший) та заносить його у список зайнятих блоків, повертаючи посилання на цей блок (рис. 1.1 б) ). Якщо блок потрібного розміру не знайдено, виникає помилка.

6

Після отримання команди на звільнення блоку пам’яті (рис. 1.2 а) ) програма, що керує купою, звільняє цей блок, можливо об’єднавши його з сусідніми вільними блоками, якщо такі є (рис. 1.2 б) ).

Рисунок 1.1 - Виділення блоку пам’яті

Рисунок 1.2 - Звільнення блоку пам’яті m

1.2 Вказівники

Вказівником називають змінну, значенням якої є адреса пам’яті. Вказівники використовують для роботи з динамічною пам’яттю та організації рекурсивних структур даних.

7

Можна вважати, що вказівник вказує на початок деякого блоку пам’яті або на деяку змінну (рис. 1.3).

Рисунок 1.3 - Графічне зображення вказівників

Мовою Паскаль опис типу вказівника та змінної цього типу виглядає так:

type t = ^type; var p: t;

де type - тип вказівника, t – тип змінної, на яку вказує вказівник. Наприклад:

type pint = ^integer; pchar = ^char;

Для вказівників у Паскалі визначено такі операції, відношення та

2 Відношення - для вказівників визначені відношення = та <>. 3 Інструкції.

3.1 Виділення пам’яті new(_); new(p) виділяє у динамічній пам’яті блок пам’яті, який має розмір, достатній для розміщення змінної типу t. Вказівник p буде вказувати на початок цього блоку пам’яті (рис. 1.4 а) ). Треба відмітити, що пам’ять виділяється не під сам вказівник, а під змінну, на яку цей вказівник буде вказувати.

3.2 Звільнення пам’яті dispose(_); dispose(p) звільняє блок пам’яті, на який вказував вказівник p (рис. 1.4 б) ). Після цього значення змінної, на яку вказує вказівник p, стає недосяжним.

8

РОЗДІЛ 2 МАСИВИ

2.1 Масиви та їх використання

Масив - це упорядкована кінцева сукупність однорідних за структурою і характеристиками даних, позначена одним ідентифікатором (ім'ям), яка розглядається як єдине ціле.

До всіх елементів масивів можуть бути застосовані одні й ті ж операції. Для використання елементів масивів (для посилання на окремі елементи масивів) вводиться поняття змінної з індексом, що записується в вигляді імені (ідентифікатору) масиву, до якого дописуються індекси. Наприклад, a1,1, ai,j, b1, xj, b5, xn. Тут b1 означає, що мається на увазі елемент масиву B, що стоїть в цьому масиві на першому місці (самий лівий або самий верхній, якщо перейти до вектора-стовпчика), xn - це n-й елемент масиву Х, a1,1 - елемент масиву А, який знаходиться в першому рядку і першому стовпчику масиву, аіj - в i-му рядку та j-му стовпчику.

В мовах програмування прийнято індекси записувати в круглих або квадратних дужках. Наприклад: A (1.1), A (i, j), B (1), C (k, 1, 1) і т.п. Або A [1,1], A [i, j], B [1], C [k, 1, 1] і т.п.

Одні і ті ж дані в програмі можуть використовуватися багаторазово, отже, вони повинні зберігатися, тобто бути доступними в декількох місцях алгоритму (програми). Для цієї мети в ЕОМ є спеціальне обладнання, що називається оперативною пам'яттю. В пам'яті кожне дане займає деяке місце - певну ділянку пам'яті. Величина цієї ділянки залежить як від організації пам'яті, так і від характеристик даного. Прийнято вимірювати пам'ять в байтах (8 двійкових розрядів - бітів). Якщо дане скалярне, то воно буде займати деяку ділянку пам'яті, наприклад, 4 байти. А якщо дане є масивом таких елементів розмірності n, то ділянка пам'яті, необхідна для розміщення такого даного, буде вже дорівнювати 4*n байтів. Якщо це двомірний масив розмірності [m х n], то – 4*m*n байтів. Ділянки пам'яті, що відводяться під масиви даних, завжди суцільні - без розривів. Знаючи початок (адресу) першого елементу, завжди легко обчислити початок (адресу) в пам'яті будь-якого елементу масиву. Наприклад, якщо К - це адреса першого елементу масиву В, а l – його довжина (число байтів, що резервуються для одного елементу), то адреса 2-го елементу буде К+1, 3-го - К+2*1, а деякого i-го - K+(i-1)*l. Легко перевірити, що для двомірного масиву А елемент, що зберігається в i-му рядку і j-му стовпчикові, буде мати адресу K+((i-1)*n+(j-1))*l, тут n - число елементів в рядку матриці. При цьому припускається, що рядки масиву в пам'яті розташуються один за одним. Аналогічні формули можуть бути отримані і для масивів будь-якої розмірності.

Завдяки однорідності елементів масиву (ця властивість забезпечує однакову довжину елементів масиву) легко обчислюється положення кожного його елементу в пам'яті, як тільки стають відомими індекси цього елементу. Ця

10

властивість дозволяє використовувати змінні з індексом для посилань на елементи масиву. При цьому з кожною змінною, що є ім'ям масиву, в програмі зв'язується адреса в оперативній пам'яті ЕОМ першого елементу цього масиву. Правила визначення місцеположення елементу використовуються тільки в програмах для ЕОМ спеціальними обслуговуючими програмами (програміст про їхню роботу може нічого не знати).

2.2 Зсув масиву даних

У багатьох задачах виникає необхідність використати масиви, в яких в процесі розв’язання задачі змінюється кількість елементів. В деякі моменти роботи алгоритму в масив додаються елементи, а в деякі інші - виключаються. При цьому додавання елементів може здійснюватися як на вільне місце в кінці масиву, так і серед існуючих елементів, наприклад, щоб не порушити упорядкованість елементів масиву. Вилучення елементів з масиву здійснюється зазвичай шляхом вилучення першого елементу масиву, вірніше, його заміщення другим елементом, другого елементу – третім, тощо. Наприклад, нехай даний масив X = (2, 4, 5, 6, 3). Після зсуву на один елемент в початок масиву отримаємо перетворений масив X = (4, 5, 6, 3, 0). При цьому число корисних елементів в масиві зменшиться на одиницю і звільнюється місце останнього елементу, яке можна очистити нулем. Сюди, можливо, і буде поміщений новий елемент масиву. Фактично на місці останнього елементу залишається непотрібна копія останнього елементу, що знищується, якщо новий елемент вставляється на це місце. Тобто, після зсуву масив Х має вигляд Х = (4, 5, 6, 3, 3).

До операції “зсуву масиву” призводять більшість практичних задач. Наприклад, якщо моделюється зміна черги до деякого обслуговуючого “пристрою” (верстат, що обробляє деякі деталі, перукар, візок-робот, що доставляє деталі до різноманітних верстатів і т.п.), та в масив В вставляються відомості про об'єкти, що очікують обслуговування. Якщо перший елемент “піде” на обслуговування, то черга зсувається вперед на один елемент, і число елементів в черзі зменшується на одиницю.

Для того, щоб зсунути чергу на 1, в масиві необхідно здійснити зсув всіх елементів в початок масиву і зменшити число корисних елементів в масиві на одиницю.

Іншим прикладом може бути автоматизація системи зарахування у ВНЗ за результатами конкурсних іспитів. Кожний абітурієнт отримав деякий бал. Якщо припустити, що частина абітурієнтів упорядкована за зменшенням величини конкурсного балу, то додавання в цей список прізвища нового абітурієнта, можливо, вимагатиме зміни місця розташування всіх елементів списку (масиву) або якоїсь її частини.

11

2.2.1 Зсув елементів в початок масиву

Дано масив А [N]. Потрібно скласти алгоритм зсуву в початок масиву всіх елементів масиву, тобто, алгоритм, в якому б кожний елемент заміщався елементом, що йде за ним. При цьому перший елемент масиву буде втрачений, місце останнього елементу в масиві звільниться, і число елементів в масиві зменшиться на одиницю. Алгоритм розв’язання цієї задачі наведений на рис. 2.1.

Рисунок 2.1 - Блок-схема зсуву елементів в початок масиву

2.2.2 Зсув елементів в кінець масиву

У разі зсуву елементів в кінець масиву можливі два випадки:

1 масив А заповнений повністю, тобто всі N елементів масиву визначені

(M=N);

2 масив А заповнений частково, тобто з загального числа N елементів масиву визначені і розміщені в А тільки М (М<N) елементів. Крім того, ці М елементів можуть по-різному розташуватися в масиві А, наприклад, або від початку масиву (тобто всі вільні (N-M) елементів масиву розміщені в кінці масиву А), або не від початку масиву, і в цьому випадку вільні (незайняті) елементи розташуються в початку і, можливо, в кінці масиву. Але така деталізація нічого істотно нового в алгоритм не вносить. Новим може бути тільки вимога збереження або втрати першого (за напрямком зсуву) елементу. В зв'язки з цим потрібно розглянути тільки один можливий варіант зсуву елементів в кінець масиву.

12