Всего на сайте:
119 тыс. 927 статей

Главная | Информатика

Комбінаторні алгоритми обробки структур даних. Задачі пошуку та сортування.  Просмотрен 67

ТЕОРЕТИЧНІ ОСНОВИ ПРОГРАМУВАННЯ

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

У прямих методах за 1 етап 1 елемент переміщається на своє місце у структурі, інші елементи практично не перегруповуються(складність порядку ).

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

Однією з найпоширеніших задач обробки структур даних є пошук. Найчастіше таку задачу застосовують до однорідних структур. Це, в першу чергу, масиви, рядки символів, файли як типізовані, так і текстові. Під пошуком розуміється встановлення факту входження деякого елементу, або послідовності елементів у структуру даних та визначення індексного номеру початку входження у структуру. Якщо ж шуканого елемента немає, то алгоритм повинен дати негативну відповідь.

Серед задач пошуку виділяють 2 підзадачі:

- пошук першого входження елемента чи послідовності;

- пошук всіх входжень елемента чи послідовності.

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


Предыдущая статья:Дополнительные примечания. Спонсируя нового партнера, очень важно научить его побуждать тебя рабо.. Следующая статья:Прямий пошук рядка.
page speed (0.0082 sec, direct)