68973

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

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-09-28

30.5 KB

3 чел.

Лекція № 18

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

План

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

Специфікація класів для сортування масивів

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

Перше питання, на яке слід отримати відповідь, це визначити, чи може і |чи повинна програма бути об'єктно-орієнтованою чи ні? В даному випадку відповідь "Так" очевидна. Чому? Об'єктом є масив, який доцільно розмістити в динамічній пам'яті. Стан об'єкту цілком і повністю визначається станом елементів масиву. Для роботи з об'єктом можна використовувати інтерфейс, що містить наступний набір операцій: розміщення масиву динамічної пам'яті, ініціалізація масиву, проглядання (вивід) значень елементів масиву, сортування масиву різними способами (прості і складні сортування вибором, обміном або вставками), звільнення зайнятої пам'яті. Отже, сортування масиву зручно реалізувати з використанням класу або ієрархії класів, до проектування яких ми і перейдемо зараз.

Специфікація класу для сортування масиву

При проектуванні специфікації класу необхідно вирішити наступні питання:

-  вибрати доцільну ієрархію класів;

- визначити, чи достатнім є використання звичайних класів або слід застосувати шаблони класів;

- спроектувати структуру кожного з класів ієрархії (визначити склад членів класу, їх функціональне призначення і доступність);

- спроектувати файлову структуру класу (чи розміщувати цілком визначення класів в заголовних файлах або оголошення класів поміщати в заголовні файли, а реалізацію методів класів — у файли з розширенням срр).

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

розміщення масиву в динамічній пам'яті (конструктор);

ініціалізація масиву значеннями, що читаються, наприклад, з файлу на магнітному диску;

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

звільнення зайнятої масивом динамічної пам'яті (деструкція).

 

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

Таким чином, отримуємо наступну ієрархію класів, яку можна використовувати для сортування масивів.

// Базовий клас: конструктор, деструкція, ініціалізація і виведення масиву

class SArTJB

{

};

// Похідний клас: різні методи сортування масивів

class SArTJD : public SArT_B

{

}

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

шаблон похідних класів повинні розміщуватися в різних заголовних файлах.


 

А также другие работы, которые могут Вас заинтересовать

20433. Сетевые операционные системы, файловые серверы 174 KB
  Сетевые операционные системы В противоположность распределенным операционным системам сетевые операционные системы не нуждаются в том чтобы аппаратное обеспечение на котором они функционируют было гомогенно и управлялось как единая система. Машины и их операционные системы могут быть разными но все они соединены в сеть. Сетевые операционные системы также имеют в своем составе команду удаленного копирования для копирования файлов с одной машины на другую...
20434. Программное обеспечение промежуточного уровня 110.5 KB
  Программное обеспечение промежуточного уровня Ни распределенные ни сетевые операционные системы не соответствуют нашему определению распределенных систем данному в разделе 1. На ум приходит вопрос: а возможно ли вообще разработать распределенную систему которая объединяла бы в себе преимущества двух миров масштабируемость и открытость сетевых операционных систем и прозрачность и относительную простоту в использовании распределенных операционных систем Решение было найдено в виде дополнительного уровня программного обеспечения который...
20435. Систе́ма управле́ния ба́зами да́нных 159 KB
  Основные функции СУБД управление данными во внешней памяти на дисках; управление данными в оперативной памяти с использованием дискового кэша; журнализация изменений резервное копирование и восстановление базы данных после сбоев; поддержка языков БД язык определения данных язык манипулирования данными. Обычно современная СУБД содержит следующие компоненты: ядро которое отвечает за управление данными во внешней и оперативной памяти и журнализацию процессор языка базы данных обеспечивающий оптимизацию запросов на извлечение и...
20436. Модель клиент-сервер 39 KB
  Модель клиентсервер До этого момента мы вряд ли сказали чтото о действительной организации распределенных систем более интересуясь тем как в этих системах организованы процессы. Они пришли к выводу о том что мышление в понятиях клиентов запрашивающих службы с серверов помогает понять сложность распределенных систем и управляться с ней. В этом разделе мы кратко рассмотрим модель клиентсервер. Клиенты и серверы В базовой модели клиентсервер все процессы в распределенных системах делятся на две возможно перекрывающиеся группы.
20437. Разделение приложений по уровням 76 KB
  Например сервер распределенной базы данных может постоянно выступать клиентом передающим запросы на различные файловые серверы отвечающие за реализацию таблиц этой базы данных. В этом случае сервер баз данных сам по себе не делает ничего кроме обработки запросов. Однако рассматривая множество приложений типа клиентсервер предназначенных для организации доступа пользователей к базам данных многие рекомендовали разделять их на три уровня: уровень пользовательского интерфейса; уровень обработки; уровень данных. Уровень обработки обычно...
20438. CASE-средства 1.81 MB
  В предыдущей лекции было рассказано о видах диаграмм UML и даны некоторые рекомендации относительно последовательности их построения. Мы уже знаем что нотация UML специально разрабатывалась в расчете на то чтобы диаграммы можно было легко рисовать от руки. В этой лекции мы познакомимся с некоторыми подобными пакетами а именно: IBM Rational Rose; Borland Together; Microsoft Visio; Sparx Systems Enterprise Architect; Gentleware Poseidon; SmartDraw; Dia; Telelogic TAU G2; StarUML; другие программы UML отличное средство моделирования но как...
20439. Rational Rose DataModeler 29.5 KB
  Унифицированный язык объектноориентированного моделирования Unified Modeling Language UML явился средством достижения компромисса между этими подходами. Существует достаточное количество инструментальных средств поддерживающих с помощью UML жизненный цикл информационных систем и одновременно UML является достаточно гибким для настройки и поддержки специфики деятельности различных команд разработчиков. Таким языком оказался UML. Создание UML началось в октябре 1994 г.
20440. CASE-средства 39.5 KB
  Microsoft Visio Visio решение для построения диаграмм от Microsoft. По словам разработчиков Visio помогает преобразовать технические и бизнесконцепции в визуальную форму. Visio имеет некоторые дополнительные возможности но все же повторим по большей мере это только средство для иллюстрирования документов MS Office не дотягивающее до уровня пакетов которые мы описывали ранее. Изобразительные же возможности Visio действительно весьма широки: Используя предопределенные фигуры Visio Professional draganddrop и мастера вы можете...
20441. Эволюция CASE-средств 99.5 KB
  Таким образом CASEтехнологии не могут считаться самостоятельными методологиями они только делают более эффективными пути их применения. CASE ≈ не революция в программо технике: современные CASEсредства являются естественным продолжением эволюции всей отрасли средств разработки ПО. Традиционно выделяют шесть периодов качественно отличающихся применяемой техникой и методами разработки ПО которые характеризуются использованием в качестве инструментальных следующих средств: ассемблеров дампов памяти анализаторов компиляторов...