Головна

Розміщення елементів в упорядкованому списку

  1. Алгоритм видалення елемента в списку по ключу
  2. Аналіз елементів договору к-п.
  3. Атрибути маркерів у ненумерований списку
  4. Залежно від методу стерилізації повинна правильно проводитися розміщення хімічних, а індикатори не стерилізуються об'єктах.
  5. Імовірність безвідмовної роботи елементів
  6. Імовірність нормального функціонування елементів КСНО
  7. ВИБІР МАТЕРІАЛІВ ТРІБОПАР З УРАХУВАННЯМ СУМІСНОСТІ ЇХ ЕЛЕМЕНТІВ

Для розміщення елемента з ключем Кдоступ в упорядкованому списку можливі два підходи:

1. включення елемента в список з переупорядочение списку;

2. використання областей переповнення.

Перший підхід показаний нижче:

1. нехай вихідний список відповідає таблиці 8:

 Таблиця 8

 № п / п  Прізвище  ім'я  По батькові  Номер залікової книжки  Домашня адреса
 Скворцов  Олег  Іванович  пр. Миру, 45 - 3
 Соколов  Юрій  Кузьмич  вул. Леонова, 23 - 98
 Строков  Іван  Іванович  вул. Червона, 9 - 2
 Супруненко  Віктор  Єгорович  Каштанова алея, 23 - 5

2. додається елемент зі структурою таблиці 9, тобто qдодавання = (Прізвище= Стручков, ім'я = Петро, По батькові= Кузьмич, Номер залікової книжки = 18345, Домашня адреса= Вул. Леонова, 14-16):

Таблиця 9

 Прізвище  ім'я  По батькові  Номер залікової книжки  Домашня адреса
 Стручков  Петро  Кузьмич  вул. Леонова, 14 - 16

3) результуючий список відповідає таблиці 10 (доданий елемент представлений заливкою):

 Таблиця 10

 № п / п  Прізвище  ім'я  По батькові  Номер залікової книжки  Домашня адреса
 Скворцов  Олег  Іванович  пр. Миру, 45 - 3
 Соколов  Юрій  Кузьмич  вул. Леонова, 23 - 98
 Строков  Іван  Іванович  вул. Червона, 9 - 2
 Стручков  Петро  Кузьмич  вул. Леонова, 14 - 16
 Супруненко  Віктор  Єгорович  Каштанова алея, 23 - 5

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

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

Ілюстрація цього підходу показана нижче:

1. вихідний список представлений таблицею 11:

 Таблиця 11

 № п / п  Прізвище  ім'я  По батькові  Номер залікової книжки  Домашня адреса  Посилання на область переповнення
 Скворцов  Олег  Іванович  пр. Миру, 45 - 3  
 Соколов  Юрій  Кузьмич  вул. Леонова, 23 - 98  
 Строков  Іван  Іванович  вул. Червона, 9 - 2  
 Супруненко  Віктор  Єгорович  Каштанова алея, 23 - 5  

2. додається елемент зі структурою таблиці 12, тобто qдодавання = (Прізвище= Стручков, ім'я = Петро, По батькові= Кузьмич, Номер залікової книжки = 18345, Домашня адреса= Вул. Леонова, 14-16):

 Таблиця 12

 Прізвище  ім'я  По батькові  Номер залікової книжки  Домашня адреса
 Стручков  Петро  Кузьмич  вул. Леонова, 14 - 16

3. він розміщується в області переповнення - таблиця 13 (спочатку вона порожня):

Таблиця 13

 № п / п  Прізвище  ім'я  По батькові  Номер залікової книжки  Домашня адреса
 Стручков  Петро  Кузьмич  вул. Леонова, 14 - 16

4) модифікується вихідний список - таблиця 14 (нове дане виділено заливкою):

Таблиця 14

 № п / п  Прізвище  ім'я  По батькові  Номер залікової книжки  Домашня адреса  Посилання на область переповнення
 Скворцов  Олег  Іванович  пр. Миру, 45 - 3  
 Соколов  Юрій  Кузьмич  вул. Леонова, 23 - 98  
 Строков  Іван  Іванович  вул. Червона, 9 - 2
 Супруненко  Віктор  Єгорович  Каштанова алея, 23 - 5  

Як видно, модифікація основного списку полягає в зміні одного з полів того елемента, за яким має слідувати знову надійшов елемент: в поле Посилання на область переповненняпоміщається порядковий номер додається елемента з області переповнення. Таким чином, новий список складається з двох частин: основного модифікованого списку (таблиця 14) і списку - області переповнення (таблиця 13). Коли другий список стає занадто великим, він «включається» в основний і його елементи займають належні їм позиції в основному списку. Така процедура називається веденням списку.



Індексного-довільний спосіб | рандомизация

топологія мереж | Методи передачі даних в мережах | Організація обміну інформацією в мережі | Обробка інформації | Операції над даними | лінійні списки | Способи доступу по первинному ключу | блоковий спосіб | двійковий спосіб | Індексного-послідовний спосіб |

© um.co.ua - учбові матеріали та реферати