Тема: Реалізація абстрактного типу даних «Сортування масивів»




Скачати 38.07 Kb.
НазваТема: Реалізація абстрактного типу даних «Сортування масивів»
Дата25.12.2013
Розмір38.07 Kb.
ТипДокументы
nauch.com.ua > Информатика > Документы

http://antibotan.com/ - Всеукраїнський студентський архів

Лабораторна робота №8 (2 год)

модуль 1


Тема: Реалізація абстрактного типу даних «Сортування масивів».

Мета: формування навичок роботи з абстрактними типами даних

Література:


  1. Архангельский А.Я. Язык Pascal и основы программирования в Delphi

  2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.

  3. Культин Н.Б. Turbo Pascal в задачах и примерах

  4. М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування.

  5. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0

  6. Меженный О.А. Turbo Pascal

  7. Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal

  8. Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с.

  9. Павловская Т.А. Паскаль. Программирование на языке высокого уровня

  10. Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с.
^

Короткі теоретичні відомості


Концептуально важливими теоретичними поня­ттями, сформованими у рамках структурного програмування, стали поняття структури даних і абстрактного типу даних (АТД).

Структура даних складається з трьох основних компонент:

  • Набір предметно-орієнтованих операцій для обробки специфічних типів абстрактних об’єктів предметної області, що описується.

  • Структура пам’яті, у якій зберігаються дані, що описують абстрактні об’єкти.

  • Інтерпретація (реалізація) кожної з операцій у термінах структури пам’яті.

Перша компонента визначення – набір операцій над абстрактними об’єктами – нази­ва­ється абстрактним типом даних. Друга і третя компоненти разом складають реалізацію структури даних.

АТД визначає, що робить структура даних – які операції вона підтримує, але не розкриває, як вони виконуються.

Постановка задачі сортування послідовності

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

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

Крім того, послідовності можна представити різними струк­ту­рами даних. Як і слідує очікувати, ефективність алгорит­мів виявляється дуже залежить від реалізації послідовності.

Нехай дано послідовність елементів a1, a2, ... , an. Елементи цієї послідо­вності – дані довільного типу, на якому визначено відношення порядка “<<” (менше) таке, що будьякі два різних елемента можна порівняти. Сортування означає перестановку елементів послідовності ak1, ak2, ... , akn таку, що ak1 << ak2 << ... << akn.

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

Сортування масивів


Якщо послідовність a1, a2, ... , an реалізована як масив a[1..n], вся вона розташована в адресній пам’яті. Тому поряд з вимогою ефектив­ності за часом основна вимога – економне використання пам’яті. Це означає, що алгоритм не повинен використовувати додаткових масивів і пере­си­лань з масива a у ці масиви.

Постановка задачі сортування у загальному вигляді пердбачає, що існують тільки два типа дій з даними типа, що сортуємо: порівняння двох елементів (x << y) і пересилання елемента (x := y). Тому зручна міра складності алгоритма сортування масива a[1..n] за часом – кількість порівнянь C(n) і кількість пересилань M(n).

Відомі алгоритми сортування масивів діляться на прості і швидкі (ефективні). Незалежно від належності тому чи іншому класу, алгоритми, що розглядаються, використовують на практиці.

^

Задачі для самостійного розв’язування


  1. Складіть програму сортування за спаданням лінійного масиву методом обміну, так щоб в результаті одного лінійного перегляду масива максимальний елемент спливав на початок.

  2. Складіть програму сортування за зростанням лінійного масиву методом обміну, так щоб в результаті одного лінійного перегляду масива мінімальний елемент спливав на початок.

  3. Складіть програму сортування за спаданням лінійного масиву методом обміну, так щоб в результаті одного лінійного перегляду масива мінімальний елемент спливав у кінець.

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

  5. Складіть програму сортування за зростанням лінійного масиву методом вибору з пошуком максимального елемента.

  6. Складіть програму сортування за спаданням лінійного масиву методом вибору з пошуком мінімального елемента.

  7. Складіть програму сортування за спаданням лінійного масиву методом вставок.

  8. Дано дійсна матриця розміру nm; впорядкувати (переставити) рядки матриці за неспаданням значень перших елементів рядків.

  9. Дано дійсна матриця розміру nm; впорядкувати (переставити) стовбці матриці за незростанням значень мінімальних елементів цих стовбців.

  10. Дано дійсна матриця розміру nm; впорядкувати (переставити) рядки матриці за незростанням суми елементів рядків.





Схожі:

Тема: Реалізація абстрактного типу даних «Сортування масивів» iconТема уроку: Сортування І фільтрація даних у таблицях. Мета
Мета: Сформувати поняття сортування, фільтрація, автофільтр; пояснити правила впорядкування І пошуку даних; сформувати вміння створювати...
Тема: Реалізація абстрактного типу даних «Сортування масивів» iconТема: Алгоритми впорядкування табличних величин. Впорядкування обміном
Мета: Познайомити учнів з принципами впорядкування табличних величин методом обміном. Засвоїти відомості з основ програмування а...
Тема: Реалізація абстрактного типу даних «Сортування масивів» iconТема: Швидкі алгоритми сортування. Сортування Хоара
Мета: Закріпити поняття складності алгоритма. Сформувати вміння застосовувати швидкі алгоритми сортування
Тема: Реалізація абстрактного типу даних «Сортування масивів» iconОсновні алгоритми сортування масивів
На і-му кроці значення і-го елемента масиву тимчасово запам'ятовується в змінній
Тема: Реалізація абстрактного типу даних «Сортування масивів» iconЛекція №3 Тема: Цілий та дійний типи даних
Значеннями типу integer є елементи підмножини цілих чи­сел. Цю підмножину визначає конкретна реалізація мови. Для кожної реалізації...
Тема: Реалізація абстрактного типу даних «Сортування масивів» iconМіністерство освіти І науки, молоді та спорту України Національний...
Програмування співпроцесора з використанням команд обчислення трансцендентних функцій та реалізація розгалужень при порівнянні даних...
Тема: Реалізація абстрактного типу даних «Сортування масивів» icon1. 1Введення даних
Як І в програмі Microsoft Word в програмі Excel можна створювати звичні текстові документи, бланки, прайс-листи, проводити сортування,...
Тема: Реалізація абстрактного типу даних «Сортування масивів» iconПрограмування масивів. Поняття масиву
До цих під для опрацювання даних використовувались скалярні типи. Однак при обробці великих наборів даних використання скалярних...
Тема: Реалізація абстрактного типу даних «Сортування масивів» iconРеферат з курсу
Середовище Delphi широко використовується для програмування баз даних. Найчастіше, бази даних як певний підбір даних, організовані...
Тема: Реалізація абстрактного типу даних «Сортування масивів» iconМета роботи
...
Додайте кнопку на своєму сайті:
Школьные материалы


При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
nauch.com.ua
Головна сторінка