Лінійні структури даних
Лінійні структури даних, їх подання та реалізація.
Лінійна структура даних - це С.Д. сукупність елементів якої є лінійно впорядкованою. Лінійними С.Д. є: 1) Послідовність 2) Еластична стрічка 3) Лінійні списки а) стек б) грудня в) чергу г) пріоритетна чергу 4) Рядки. Можна дати більш повне визначення лінійної структурі даних. Це безліч складається ізn> = 0 узловx1. x2. x3. xn структурні (топологічні) властивості якого по суті обмежуються лише лінійним (одномірним) відносним становищем вузлів. Тобто есліn> 0, тоx1 - перший вузол; якщо 1
Лінійні структури даних.
1) Інтуїтивне поняття про реалізованої структурі даних.
2) Функціональне опис структури даних.
(Специфікація): РОР (PUSH (S, X)) = S-аксіома.
3) Логічне опис.
Описуємо в певних раніше поняттях.
Нове поняття визначаємо через набір операцій:
а) логічне опис структури;
б) логічне опис операцій над цією структурою;
(Логічне опис на абстрактному рівні).
4) Фізичне представлення.
(Реалізація операцій над представником).
Об'єднання, з'єднання, поділ варіантів.
Операції над лінійною структурою даних
CREATE -для динамічних структур;
INIT - для статичних структур;
2) отримати доступ до k-му елементу структури з метою дослідження або зміни цього елемента (селектор);
3) включити новий елемент безпосередньо перед заданим (після);
4) виключити заданий елемент
Якщо 3) і 4) існують, то структуру даних будемо називатьдінаміческой;
5) об'єднати дві структури даних в одну (конкатенація рядків)
6) розбити структуру на дві;
7) зробити копію структури даних;
8) визначити кількість елементів в структурі (операції спостерігача);
9) сортувати елементи структуриданних в деякому порядку;
11) знищити структуру даних (деструкція);
Види лінійних структур даних.
Черга типу LIFO - lost-in-first-out.
Черга - така лінійна структура, де доступ, додавання - з одного кінця, а вибірка з іншого.
Черга-кільцевої буфер, циклічна пам'ять або чергу типу (FIFO).
Грудня -двухвходовая чергу (Double-Ended-Quene).
дек з обмеженим входом - архів;
дек з обмеженим виходом -Перелік або реєстр.
Пріоритетна чергу-вибірка проводиться з одного кінця (голови), а включення в будь-яке місце-в залежності від пріоритету.