Головна

структури даних

  1. I Реалізація простих і складних запитів до бази даних
  2. I. ВАРІАЦІЇ забарвлення і СТРУКТУРИ ШЕРСТІ
  3. III. Аналіз результатів психологічного аналізу 1 і 2 періодів діяльності привів до наступного розуміння узагальненої структури стану психологічної готовності.
  4. III. Робота з функціями Бази даних
  5. III. Етап кількісного та якісного аналізу даних
  6. Iquest; Використання панелі інструментів Бази даних та Запиту в режимі таблиці
  7. Iquest; Створення таблиць шляхом введення даних в таблицю

структура даних відноситься, по суті, до "просторовим" поняттями: її можна звести до схеми організації інформації в пам'яті комп'ютера. Алгоритм же є відповідним процедурним елементом в структурі програми - він служить рецептом розрахунку.

Перші алгоритми були придумані для вирішення численних завдань типу множення чисел, знаходження найбільшого спільного дільника, обчислення тригонометричних функцій і інших. Сьогодні в рівній мірі важливі і нечисельні алгоритми; вони розроблені для таких завдань, як, наприклад, пошук в тексті заданого слова, планування подій, сортування даних в зазначеному порядку і т.п. Нечисельні алгоритми оперують з даними, які не обов'язково є числами; більш того, не потрібні ніякі глибокі математичні поняття, щоб їх конструювати або розуміти. З цього, однак, зовсім не випливає, що у вивченні таких алгоритмів в математиці немає місця; навпаки, точні, математичні методи необхідні при пошуку найкращих рішень нечисельних завдань при доказі правильності цих рішень.

Структури даних, що застосовуються в алгоритмах, можуть бути надзвичайно складними. В результаті вибір правильного уявлення даних часто служить ключем до успішного програмування і може більшою мірою позначатися на продуктивності програми, ніж деталі використовуваного алгоритму. Навряд чи коли-небудь з'явиться загальна теорія вибору структур даних. Найкраще, що можна зробити, - це розібратися в усіх базових "цеглинки" і в зібраних з них структурах. Здатність докласти ці знання до конструювання великих систем - це перш за все справа інженерного майстерності і практики.

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

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

поняття "фізична структура даних"Відображає спосіб фізичного представлення даних в пам'яті машини і називається ще структурою зберігання, Внутрішньою структурою або структурою пам'яті.

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

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

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

Вельми важлива ознака структури даних - її мінливість - Зміна числа елементів і (або) зв'язків між елементами структури. У визначенні мінливості структури не відображений факт зміни значень елементів даних, оскільки в цьому випадку все структури даних мали б властивість мінливості. За ознакою мінливості розрізняють структури статичні, полустатіческіе, динамічні. Класифікація структур даних за ознакою мінливості приведена на рис. 5.2. Базові структури даних, статичні, полустатіческіе і динамічні характерні для оперативної пам'яті і часто називаються оперативними структурами. Файлові структури відповідають структурам даних для зовнішньої пам'яті.


Мал. 5.2. Класифікація структур даних

Важлива ознака структури даних - характер впорядкованості її елементів. За цією ознакою структури можна ділити на лінійні і нелінійні структури.

Залежно від характеру взаємного розташування елементів в пам'яті лінійні структури можна розділити на структури з послідовним розподілом елементів в пам'яті (вектори, рядки, масиви, стеки, черги) і структури з довільним зв'язковим розподілом елементів в пам'яті (одинзв'язні, двусвязного списки). Приклад нелінійних структур - багатозв'язкові списки, дерева, графи.

У мовах програмування поняття "структури даних" тісно пов'язане з поняттям "типи даних". Будь-які дані, тобто константи, змінні, значення функцій або виразу, характеризуються своїми типами.

Інформація по кожному типу однозначно визначає:

1) структуру зберігання даних зазначеного типу, тобто виділення пам'яті і уявлення даних в ній, з одного боку, і інтерпретування двійкового представлення, з іншого;

2) безліч допустимих значень, які може мати той чи інший об'єкт описуваного типу;

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

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

Тип - Відносно стійка, незалежна сукупність елементів, яку можна виділити в усьому розглянутому безлічі (предметної області} типи даних бувають такі:




При наборі змінних (0, 1, 1) буде брехня, а при наборі (1, 0, 1) - істина. | організація машини | Принцип двійкового кодування. Згідно з цим принципом, вся інформація, яка надходить в ЕОМ, кодується за допомогою двійкових сигналів. | Структурна схема базової моделі МП фірми Intel представлена ??на малюнку 4.15. | ОЗУ призначена для зберігання змінної інформації, працює в режимах запису, читання і зберігання. | Ці два різновиди пам'яті розрізняються швидкодією і питомоющільністю (ємністю зберігається). | Накопичувачі на магнітних дисках. | Накопичувачі на оптичних дисках | Флеш-пам'ять | Стратегія вирішення завдань. |

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