Контроль правильності запису даних | Передача інформації | Модуляція і демодуляція сигналу | Ущільнення сигналу і виділення ущільненого сигналу | Комп'ютерні мережі | топологія мереж | Методи передачі даних в мережах | Організація обміну інформацією в мережі | Обробка інформації | Операції над даними |

загрузка...
загрузка...
На головну

Способи доступу по первинному ключу

  1. II-2.5.3. Способи завдання цільової функції
  2. V. Способи упаковки шприців, голок, інструментів для стерилізації
  3. Алгоритм доступу до середовища CSMA / CD
  4. Алгоритм видалення елемента в списку по ключу
  5. Аналітичні способи вираження концентрації розчинів.
  6. Банківська гарантія і поручительство як способи забезпечення виконання зобов'язань.

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

послідовне сканування

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

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

· Для невпорядкованого списку порівняння повторюється до досягнення кінця списку. У цьому випадку, якщо збігу ключів так і не було, робиться висновок про відсутність потрібного елемента в списку;

· Для впорядкованого списку перевіряється умова, наприклад, перевищення значення ключа доступу Кдоступ значення ключа Ке: якщо список впорядкований по зростанню, пошук триває; якщо по спадаючій - пошук припиняється через відсутність потрібного елемента.

Приклад 1. Для списку з таблиці 1 потрібно переглянути адресу студента на прізвище Скворцов, тобто qпросмотр = (Прізвище = Скворцов, Домашня адреса), а Кдоступ = Скворцов (тут і далі значення ключа доступу виділяється курсивом).

Доступ здійснюється послідовним виконанням кроків:

1. вибирається перший елемент списку;

2. ключове поле елемента Ке = Строков порівнюється з ключем доступу: Строков = Скворцов;

3. оскільки поля не рівні, вибирається наступний - другий - елемент списку;

4. ключове поле елемента порівнюється з ключем доступу: Скворцов = Скворцов;

5. оскільки поля рівні, виводиться адреса: пр. Миру, 45 - 3; алгоритм закінчує роботу.

Приклад 2. Нехай потрібно переглянути домашню адресу студента, якого немає у списку, наприклад, на прізвище Сидоров, тобто qпросмотр = (Прізвище = Сидоров, Домашня адреса), де Кдоступ = Сидоров.

Робота алгоритму для невпорядкованого списку (таблиця 1):

1. вибирається перший елемент списку;

2. ключове поле елемента порівнюється з ключем доступу: Строков = Сидоров;

3. оскільки поля не рівні, вибирається наступний - другий - елемент списку;

4. ключове поле елемента порівнюється з ключем доступу: Скворцов = Сидоров;

5. внаслідок того, що поля не рівні, вибирається наступний - третій - елемент списку;

6. ключове поле елемента порівнюється з ключем доступу: Соколов = Сидоров;

7. через те, що поля не рівні, робиться спроба звернутися до іншого збігу;

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

Робота алгоритму для впорядкованого списку з таблиці 2 (список впорядкований по зростанню первинного ключа - прізвища):

1. вибирається перший елемент списку;

2. ключове поле елемента порівнюється з ключем доступу: Скворцов = Сидоров;

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

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

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

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

· Для невпорядкованого списку порівняння повторюється до досягнення кінця списку. У цьому випадку, якщо збігу ключів так і не було, новий елемент з ключем Кдоступ розміщується в списку;

· Для впорядкованого списку перевіряється умова, наприклад, перевищення значення ключа доступу Кдоступ значення ключа Ке: якщо список впорядкований по зростанню, перебір елементів триває; якщо за спаданням, що розміщується елемент з ключем Кдоступ розміщується перед елементом з ключем Ке. Слід зазначити, що названа процедура розміщення елемента в упорядкованому списку проблематична і розглядається як окреме завдання в розділі Розміщення елементів в упорядкованому списку.



лінійні списки | блоковий спосіб
загрузка...
© um.co.ua - учбові матеріали та реферати