Internal.

Наконец, элементы классов и структур, в частности, поля, методы, свойства и вложенные

типы являются по умолчанию доступными из описаний соответствующих классов или

структур и описываются с помощью зарезервированного слова private.

Проиллюстрируем обсуждение использования модификаторов областей видимости

объектов (public и private) следующим содержательным примером фрагмента

программы на языке C#:

public class Stack

{

private int[] val;

// private используется и по умолчанию

private int top;

// private используется и по умолчанию

public Stack() {...}

public void Push(int x) {...}

public int Pop() {...}

}

Как видно из приведенного примера, фрагмент программы на языке C# содержит

описание класса стека Stack, реализованного на основе массива целочисленных

элементов (поле val). Голова стека представляет собой целочисленное значение (поле

top). Над стеком определены операции инициализации (метод Stack), а также вставки

(метод Push) и удаления (метод Pop) элемента.

Как явствует из примера, класс Stack и все манипулирующие его объектами методы

(Stack, Push и Pop) являются общедоступными (public), тогда как поля являются

доступными локально (private), т.е. только из описания данного класса.

Наследование

Наследование — это свойство системы, позволяющее описать новый класс на основе уже существующего с частично или полностью заимствующейся функциональностью. Класс, от которого производится наследование, называется базовым, родительским или суперклассом. Новый класс — потомком, наследником или производным классом.[1]

Полиморфизм

Полиморфизм — это свойство системы использовать объекты с одинаковым интерфейсом без информации о типе и внутренней структуре объекта.[1]

Класс

Класс является описываемой на языке терминологии (пространства имён) исходного кода моделью ещё не существующей сущности (объекта). Фактически он описывает устройство объекта, являясь своего рода чертежом. Говорят, что объект — это экземпляр класса. При этом в некоторых исполняющих системах класс также может представляться некоторым объектом при выполнении программы посредством динамической идентификации типа данных. Обычно классы разрабатывают таким образом, чтобы их объекты соответствовали объектам предметной области.

Формы полиморфизма:

Полиморфной называется такая переменная, которая может хранить в себе значения различных типов данных

Полиморфной функцией является такая функция, которая может вызываться с аргументами различного типа, а фактический выполняемый код зависит от типа аргументов

Преимущества использования полиморфизма:

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

Полиморфизм сужает концептуальное пространство, т.е. уменьшает количество информации, которое необходимо помнить программисту.

Пример обобщенного алгоритма:

Пусть имеется класс Enumerable, в котором объявлены операции отношения >, <, >=, <=, == и !=, и имеется свободная функция sort(), которая упорядочивает элементы массива типа Enumerable по возрастанию

Тогда всем классам, производным от класса Enumerable, будет доступна операция упорядочивания массива по возрастанию

Пример обобщенного алгоритма:

// Упорядочивание массива методом пузырька

void sort(Enumerable *mass, int count)

{

for(int i = 0; i < count-1; i++)

{

for(int j = i+1; j < count; j++)

{

if(mass[i] > mass[j])

{

swap(mass[i], mass[j]);

}

}

}

}

Понятие наследования. Иерархия классов. Способы создания иерархии в языке.

Наследование

Наследование - это способность брать существующий - базовый класс и порождать из него новый класс - потомок, с наследованием всех его атрибутов и поведения. Это пожалуй самая впечатляющая возможность объектно-ориентированного программирования и, возможно, единственное коренное отличие С++ от Си.

Рассмотрим отвлеченный пример из реальной жизни - классификационную схему живых организмов. По этой схеме растительные и живые царства делятся на группы, так называемые типы. Каждый тип, в свою очередь, делится на классы, отряды, семейства и далее. Группы более низкого уровня наследуют характеристики групп более высоких уровней. Так, из утверждения о том, что волк относится к семейству псовых, вытекает сразу несколько положений. Из него следует, что у волков хорошо развиты слух и обоняние, поскольку таковы характеристики псовых. Так как псовые входят в отряд хищных, это утверждение говорит еще о том, что волки питаются мясом. Поскольку хищные относятся к млекопитающим, это утверждение говорит и о том, что волки имеют волосяной покров и регулируемую температуру тела. Наконец, так как млекопитающие являются позвоночными, мы узнаем и то, что у волков есть позвоночник.

Волк -> Псовые -> Хищники -> Млекопитающие -> Позвоночные

Подобные схемы наследования можно проследить в классификации языков программирования, классификации типов компьютеров и других. Рассмотрим существующие в объектно-ориентированных языках иерархии порождаемых объектов.

Иерархия классов

Наследование может использоваться множество раз при порождении объектов. Порожденные классы могут наследовать готовые функции элементы своих классов-предков, набирая при каждом порождении все больше и больше функций элементов.

Окно

^

Наследование Панель Порождение

классов

v

Меню

Вы можете также порождать несколько классов из базового класса:

^ Меню

Насле- Порождение

дование > < классов

v

Вертикальное Горизонтальное

Вертикальное и Горизонтальное меню имеют одного предка - Меню. Общее свойство, унаследованное от Меню - это список элементов, расположение. Порождение нескольких классов из одного корня позволяет использовать текст программ для многих классов.

Используя наследование, можно наращивать иерархию классов, создавая как-бы древовидные формы. Еще более сложные иерархии образуются через множественное наследование.

Пример наследования

Чтобы задать отношения наследования между классами, надо при описании нового класса после имени класса поставить двоеточие и далее перечислить через запятую имена потомков.

В этом примере из базового класса shape порождается класс circle:

class shape { < Объявление класса

public:

double xo, yo; < Данные (координаты)

shape(double x, double y); < Конструктор

virtual double area(void); < Виртуальная функция элемент

};

Связывание порожденного класса с базовым

v

class circle : public shape { < Объявление порожденного класса

public:

double radius; < Дополнительные данные

double area(void); < Заимствованная функция элемент

circle(double x, double y, double r); < Конструктор

};

Абстрактные классы, виртуальные методы. Наследование и замещение методов.

Виртуальные функции

Что же делать, если мы хотим, чтобы "наследник" вел себя отлично от "предка", сохраняя при этом свойство совместимости с ним? На этот случай существуют виртуальные методы.

Виртуальный метод – это метод, который, будучи описан в потомках, замещает собой соответствующий метод везде, даже в методах, описанных для предка, если он вызывается для потомка.

Адрес виртуального метода известен только в момент выполнения программы. Когда происходит вызов виртуального метода, его адрес берется из таблицы виртуальных методов своего класса. Таким образом, вызывается то, что нужно.

В чем же преимущество виртуальных методов? Самое главное в том, что они допускают обработку объектов, тип которых неизвестен во время компиляции.

Это новый способ мышления для С.

Предположим, вы написали пакет графических средств, который поддерживает различные типы фигур: точки, окружности, квадраты и т.п. может возникнуть необходимость написать в качестве части этого пакета подпрограмму, которая будет изображать графическую фигуру с помощью "мыши".

Старый способ заключается в написании отдельных процедур для изображения графических фигур всех типов. Написать единую процедуру для рисования всех этих фигур будет затруднительно: окружность не имеет сторон, квадрат имеет только одну длину стороны и др.

Наиболее искусные программисты будут передавать признак фигуры, а затем, например, с помощью оператора switch выбирать нужную подпрограмму.

А что делать, если вы вдруг решите включить новую фигуру, например, восьмиугольник (для рисования дорожных знаков).

В вашем switch 'е нет такого case, и даже если вы напишите необходимую для рисования функцию, вы не сможете ее вызвать (разве что добавите еще один case). Явный недостаток вашего пакета – без дополнительных затрат на модифицирование уже отлаженных подпрограмм он может работать только с типами данных, которые он знает, то есть которые были определены разработчиками.

А вот полиморфные методы, определенные только сейчас, могут быть объединены совместно с программой, которая была откомпилирована год назад. Виртуальные методы – ключ к решению этой проблемы.

Виртуальные методы описываются с помощью ключевого слова virtual в базовом классе. Это означает, что в производном классе этот метод может быть замещен методом, более подходящим для этого производного класса. Объявленный виртуальным в базовом классе, метод останется виртуальным для всех производных классов. Если в производном классе виртуальный метод не будет переопределен, то при вызове будет найден метод с таким именем вверх по иерархии классов (т.е. в базовом классе).

Перепишем нашу иерархию классов.

class Point

{

...

public:

...

virtual void Show ();

virtual void Hide ();

void MoveTo (int newX, int newY);

};

...

реализация методов класса Point

...

class Circle: public Point

{

...

public:

... // без метода MoveTo()

virtual void Show ();

virtual void Hide ();

};

...

реализация методов класса Circle

...

Прежде всего, заметим, что в классе Circle нет метода MoveTo(), он наследуется из класса Point.

При этом все вызовы отложенных в MoveTo() методов будут методами класса Circle, так как они являются виртуальными методами.

Область применения виртуальных функций не ограничивается случаями, аналогичными представленному выше. Другая сфера приложения виртуальных функций связана с использованием указателей на объекты. Особенность указателей в С++ состоит в том, что указатель, объявленный в качестве указателя на базовый класс, также может использоваться, как указатель на любой класс, производный от этого базового. Так что, в это смысле, возможно

Point pointObj (100,20); // объект базового класса

Circle circleObj (20,30,10); // объект производного класса

Point *pointPtr; // указатель базового класса

pointPtr = & pointObj; // указывает на объект базового класса

pointPtr = & circleObj; // указывает на объект производного класса

Абстрактный класс

Иногда, когда виртуальная функция объявляется в базовом классе, она не выполняет никаких значимых действий. Это вполне обычная ситуация, поскольку часто базовый класс не определяет законченный тип, или, если рассматривать наш пример, объект базового типа не представляет особой ценности. Речь здесь идет о том, что хотя базовый класс (Point) и содержит базовый набор методов и состояний, который производный класс дополняет всем недостающим, полезность точки, как графического объекта, не велика и, программируя, например, некоторый графический интерфейс, без точки, как объекта, можно вполне обойтись. Однако мы выяснили, что именно Point, как нельзя лучше подходит для роли базового класса, поскольку Point содержит в себе главные атрибуты любых графических объектов. Т.е. мы пришли к пониманию того, что класс Point ценен не своими объектами, а своей способностью выступать в качестве базового класса.

Возвращаясь к виртуальным методам, заметим, что теперь, когда отпала необходимость создавать объекты класса Point, методы виртуальные Show() и Hide() стали нужны только для того, чтобы их обязательно переопределили в производных классах. Для реализации этого положения С++ поддерживает чисто виртуальные методы.

Чисто виртуальные методы не определяются в базовом классе. У них нет тела, а есть только декларации об их существовании.

Для чисто виртуальной функции используется общая форма

virtual тип имя_функции (список параметров) = 0;

Ключевой частью этого объявления является приравнивание функции к нулю.

Класс, содержащий хотя бы один виртуальный метод, называется абстрактным классом. Абстрактные классы не бывают изолированными, т.е. всегда абстрактный класс должен быть наследуемым. Поскольку у чисто виртуального метода нет тела, то создать объект абстрактного класса невозможно.

Абстрактным классом можно назвать класс, специально определенный для обеспечения наследования характеристик порожденными классами.

Вот как теперь станет выглядеть наш новый Point.

class Point

{

protected:

int X;

int Y;

Boolean Visible;

public:

int GetX(void) { return X; }

int GetY(void) { return Y; }

Boolean isVisible (){ return Visible;}

Point (int newX =0, int new Y =0);

virtual void Show() = 0; // чисто виртуальная функция

virtual void Hide() = 0; // чисто виртуальная функция

void MoveTo (int newX, int newY)

{

Hide();

X = newX; Y = newY;

Show();

}

};

Класс Point теперь действует как заготовка, из которого все порожденные классы могут взять элементы, общие для всех типов в иерархии, но теперь, при попытке создать объект типа Point, компилятор выдаст сообщение об ошибке.

Заметьте, что необходимость конструктора при этом не отпала, поскольку по-прежнему нужно будет инициализировать X, Y и Visible для производных классов.

Приведенное выше логическое обоснование или разумное объяснение демонстрирует важный принцип ООП: определяя иерархию классов, соберите все общие атрибуты в один абстрактный класс, и определите иерархию классов так, чтобы все общие элементы использовались из этого класса.

Параметризация типов данных в классах и функциях.

Вероятно, самой важной из новых возможностей C++ является шаблон (template). Причина этого заключается в том, что шаблоны фундаментально изменяют внешнюю сторону программирования. Используя шаблон, вы можете создавать обобщенные спецификации для функций и для классов, которые часто называются параметризованными функциями (generic functions) и параметризованными классами (generic classes). Параметризованная функция определяет общую процедуру, которая может быть применена к данным различных типов. Параметризованный класс определяет общий класс, который может применяться к изменяющимся типам данных. В обоих случаях конкретный тип данных, над которыми выполняется операция, передается в качестве параметра. Как вы можете себе представить, именно это и делает шаблоны чрезвычайно ценным средством. В C++ шаблон функции или класса декларируется с помощью ключевого слова template. Возможно, вы уже знакомы с основными принципами использования ключевого слова template. В этой главе будут рассмотрены некоторые приемы, позволяющие в полной мере использовать преимущества, предоставляемые шаблонами.

Как уже говорилось, ключевое слово template используется для построения параметризованных функций и классов. В этой главе исследуются параметризованные функции, а параметризованные классы будут изучаться в следующей главе. Мы исследуем причины, вследствие которых были изобретены шаблоны, выясним, почему использование шаблонов представляет собой более эффективный метод по сравнению с другими средствами создания параметризованных функций, а затем на ряде примеров проиллюстрируем их применение.

Для демонстрации возможностей шаблонов мы используем поиск и сортировку - две наиболее широко распространенных в компьютерном мире операции. Алгоритмы поиска и сортировки выбраны нами по трем причинам. Во-первых, они легко преобразуются в форму шаблонов, и, как вы увидите далее, это преобразование существенно повышает их эффективность. Во-вторых, поиск и сортировка используются практически в любой программе, и поэтому чтение этой главы принесет практическую пользу всем программистам, которые в результате этого получат в свое распоряжение разнообразные параметризованные функции поиска и сортировки. Наконец, алгоритмы сортировки представляют собой одну из самых интересных и захватывающих областей науки программирования. Кроме того, эту тему многие не разрабатывают, а принимают на веру. Так, многие программисты используют в своих разработках стандартные библиотечные функции сортировки. Однако, как вы вскоре убедитесь, благодаря использованию шаблонов, на эту важную тему стоит посмотреть свежим взглядом.

Почему следует использовать параметризованные функции

С первых же дней существования программирования программисты понимали необходимость в параметризованных подпрограммах, которые можно использовать повторно. Как вы знаете, многие алгоритмы не зависят от типа данных, которыми они манипулируют. Например, рассмотрим следующую последовательность обмена значениями между двумя переменными:

DataType temp, x, у;

//…

temp=x;

х=у;

y=temp;

Построение параметризованных функций сортировки

Сортировка (sorting) - это процесс, позволяющий упорядочить множество подобных данных в возрастающем или убывающем порядке. Сортировка представляет собой один из наиболее приятных с интеллектуальной точки зрения алгоритмов, поскольку процесс хорошо определен. Алгоритмы сортировки хорошо исследованы и изучены. К сожалению, по этой причине сортировку иногда принимают как некую данность. Фактически, когда возникает необходимость в сортировке данных, большинство программистов просто используют стандартную функцию сортировки, имеющуюся в библиотеке, которая поставляется с их компилятором, и больше об этом не задумываются. Однако, как вы увидите далее, различные подходы к сортировке обладают различными характеристиками. Хотя некоторые методы в среднем могут быть лучше других, ни один из методов не будет идеальным для всех ситуаций. Поэтому каждый программист должен иметь в своем распоряжении несколько различных типов сортировки. То, что теперь эти методы могут быть реализованы в виде параметризованных функций, еще более усиливает их значимость.

Пузырьковая сортировка

Самым известным (и самым скверным) методом сортировки является пузырьковый метод. Его популярность является следствием запоминающегося названия и простоты. Однако, в общем случае это -- самый худший из всех когда-либо изобретенных методов.

Простейшая реализация пузырьковой сортировки для символов

#include <iostream.h>

ttinclude <string.h>

void bubble(char *item, int count);

main()

{

char str[] = "dcab";

bubble(str, (int) strlen(str));

cout « "Отсортированная строка: " « str « endl;

return 0;

}

Простая версия пузырьковой сортировки void bubble(char *item, int count)

{

register int a, b;

char t;

for(a=l; a<count; ++a)

for(b=count-l; b>=a; --b) {

if(item[b-l] > item[b]) {

Перестановка значений

t=item[b-l];

item[b-l] = item[b];

item[b] = t;

}

//Параметризованная версия пузырьковой сортировки

template <class Stype> void bubble(Stype *item, int count) {

register int a, b;

Stype t;

for(a=l; a<count; ++a)

for(b=count-l; b>=a; --b) {

if(item[b-l] > item[b]) {

//Перестановка значений t=item[b-l];

item[b-l] = item[b];

item[b] = t;

}

Общие вопросы программирования и алгоритмов

Алгоритм - точное предписание исполнителю совеpшить определенную последовательность действий для достижения поставленной цели за конечное число шагов.

Поэтому обычно формулируют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций.

Такими свойствами являются:

• Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

• Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

• Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

• Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

Основные этапы построения алгоритмов.

Каждый раз при решении конкретной задачи такая схема может подвергаться некоторым изменениям: какой-то блок будет исключен или усовершенствован, какой-то — добавлен. Все этапы определяются поставленной задачей и целями моделирования.

Постановка задачи

Жизнь постоянно ставит перед человеком проблемы, требующие разрешения. Эти проблемы по своей сложности нельзя сравнить ни с одной, даже самой трудной задачей из школьных учебников. В школьных задачах вам четко указано, что дано и что требуется получить, а в разделе, где приводится задача, рекомендованы возможные методы ее решения. Как правило, в реальной жизни человек имеет дело с задачами (проблемами), где этого в явной форме нет. Поэтому важнейшим признаком грамотного специалиста является умение поставитъ задачу, то есть сформулировать ее таким образом и на таком языке, чтобы ее однозначно понял любой, кто будет участвовать в ее решении.

Этап постановки задачи характеризуется тремя основными моментами: описание задачи, определение целей моделирования, формализация задачи.

Описание задачи

Постановка задачи, как правило, начинается с ее описания. Делается это на обычном языке, самыми общими фразами. При этом подробно описывается исходный объект, условия, в которых он находится, и желаемый результат, иначе говоря, отправной и конечный пункты моделирования.

Некоторые задачи формулируются несколько шире. Что будет, если изменять характеристики объекта в заданном диапазоне с некоторым шагом? Такое исследование помогает проследить зависимость параметров объекта от исходных данных.

Вторая группа задач имеет такую обобщенную формулировку: какое надо произвести воздействие на объект, чтобы его параметры удовлетворяли некоторому заданному условию? Такая постановка задачи часто называется «как сделать, чтобы?..». Например, какого объема должен быть воздушный шар, наполненный гелием, чтобы он мог подняться вверх с грузом 100 кг?

Рассмотрим простую задачу, на примере которой в дальнейшем проследим этапы моделирования.

Задача. Движение автомобиля.

Как изменяется скорость автомобиля при движении?

В данной задаче предполагается проследить, как будет изменяться скорость автомобиля в некотором диапазоне времени. Это расширенная постановка задачи «что будет, если?..».

Цель моделирования

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

Рассмотрим возможные цели моделирования.

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

Нередко целью моделирования является эффективность управления объектом (или процессом). Поскольку критерии управления бывают весьма противоречивыми, то эффективным оно окажется только при условии, что будут «и волки сыты, и овцы целы»

Вернемся к ранее описанной задаче и определим цель моделирования.

Задача. Движение автомобиля.

Цель: исследовать процесс движения.

Формализация задачи

В повседневной жизни мы постоянно сталкиваемся с проявлением формализма, означающего строгий порядок. И хотя мы часто говорим о формализме с отрицательной оценкой, в некоторых случаях без него не обойтись. Возможно ли организовать учет и хранение лекарств в больнице или диспетчерское управление авиации, если не подчинить эти процессы строгой формализации? В таких случаях она означает четкие правила и их одинаковое понимание всеми, строгий учет, единые формы отчетности и т.д.

Обычно о формализации говорят и тогда, когда собранные данные предполагают обрабатывать математическими средствами.

Задача. Движение автомобиля.

Что моделируется?

Процесс движения объекта «автомобиль»

Вид движения

Равноускоренное

Что известно о движении?

Начальная скорость (V0), ускорение (а), максимально развиваемая скорость (Vmax)

Что надо найти?

Скорость (Vi) в заданные моменты времени (ti).

Как задаются моменты времени?

От нуля через равные интервалы (∆t)?

Что ограничивает расчеты?

Vi < Vmax

Такие характеристики объекта, как цвет, тип кузова, год выпуска и общий пробег, степень изношенности шин и многие другие, в данной постановке учитывать не будем.

Разработка модели

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

Информационная модель

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

Если отбросить существенные факторы, то модель будет неверно отражать оригинал (прототип). Если оставить их слишком много, модель окажется сложна для построения и исследования. Во многих исследованиях создают несколько моделей одного объекта, начиная от простейших, с минимальным набором определяющих параметров. Затем постепенно уточняют модель, добавляя некоторые из отброшенных характеристик.

Задача. Движение автомобиля

Объект моделирования

Параметры

Процесс движения автомобиля

V0 – начальная скорость

∆t – интервал изменения времени

а – ускорение

Vмакс – максимально развиваемая автомобилем скорость

ti – время движения

Vi – значения скорости

Информационная модель, как правило, представляется в той или иной знаковой форме. Таблица – один из примеров знаковых моделей.

Компьютерная модель

Теперь, когда сформирована информационная знаковая модель можно приступать собственно к компьютерному моделированию - созданию компьютерной модели. Сразу возникает вопрос о средствах, которые необходимы для этого, то есть об инструментах моделирования.

Компьютерная модель - это модель, реализованная средствами программной среды.

Компьютерный эксперимент

Чтобы дать жизнь новым конструкторским разработкам, внедрить новые технические решения в производство или проверить новые идеи, нужен эксперимент. Эксперимент — это опыт, который производится с объектом или моделью. Он заключается в выполнении некоторых действий и определении, как реагирует экспериментальный образец на эти действия.

В школе вы проводите опыты на уроках биологии, химии, физики, географии.

План эксперимента

План эксперимента должен четко отражать последовательность работы с моделью. Первым пунктом такого плана всегда является тестирование модели.

Проведение исследования

После тестирования, когда у вас появилась уверенность в правильности построенной модели, можно переходить непосредственно к проведению исследования.

В плане должен быть предусмотрен эксперимент или серия экспериментов, удовлетворяющих целям моделирования. Каждый эксперимент должен сопровождаться осмыслением итогов, что служит основой анализа результатов моделирования и принятия решений.

Анализ результатов моделирования

Конечная цель моделирования - принятие решения, которое должно быть выработано на основе всестороннего анализа результатов моделирования. Этот этап решающий - либо вы продолжаете исследование, либо заканчиваете. Полученные выводы

часто способствуют проведению дополнительной серии экспериментов, а подчас и изменению задачи.

Главное, надо всегда помнить: выявленная ошибка — тоже результат. Как гласит народная мудрость, на ошибках учатся.

Алгоритмы внутренней сортировки. Критерии выбора.

Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в каком-либо строго определенном порядке (обычно в алфавитном или числовом).

Пусть на дана последовательность элементов: a1, a2, ..., an сортировка означает - перестановку этих элементов в таком порядке: ak1,ak2, .. ,akn, что при заданной функции упорядочивания f(x), справедливо отношение :

f(ak1) <= f(ak2)<= .. <= f(akn) - функция упорядочивания не вычисляется, а содержится в каждом элементе в виде явной компоненты и ее значение называют ключом элемента. Следовательно, для представления i-ого элемента последовательности наилучшим образом подходит структура записи. Определим тип элемента, который будем использовать в алгоритмах сортировки следующим образом :

type elem = Record

key: integer;

описание др. компонентов

end;

Поле key - служит только для идентификации элемента.

Если сортируемый файл целиком помещается в память (или целиком помещается в массив), то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой.

Главное отличие между ними состоит в том, что при внутренней сортировке любая запись - легко доступна, в то время как при внешней сортировке мы можем пользоваться записями только последовательно, или большими блоками.

Обычно, главное, что будет нас интересовать в алгоритме - это время его работы. Время работы алгоритма характеризуется числом необходимых сравнений обозначаемых через С и число м необходимых пересылок элемента - M.

Простые алгоритмы, которые мы рассмотрим, для сортировки N элементов имеют время работы пропорциональное N2, в то время как более сложные алгоритмы используют время пропорциональное NlogN. (Можно доказать, что никакой алгоритм сортировки не может использовать менее, чем N logN сравнений между ключами.)

Количество используемой дополнительной памяти алгоритма сортировки - это еще один важный фактор, который мы будем принимать во внимание.

Сортировка Выбором

Один из самых простых методов сортировки работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте, потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементом и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором поскольку он работает циклически выбирая наименьший из оставшихся элементов.

Сортировка выбором

procedure selection;

var

i, j, min, t : integer;

begin

for i:=1 to N-1 do

begin

min := i;

for j:=i+1 to N do

if a[j]<a[min] then

min := j;

t := a[min];

a[min] :=a[i];

a[i] := t;

end;

end;

Сортировка Вставкой

Сортировка вставкой - это метод который почти настолько же прост, что и сортировка выбором, но гораздо более гибкий. Этот метод часто используют при сортировке карт: берем один элемент и вставляем его в нужное место среди тех, что мы уже обработали (тем самым оставляя их отсортированными).

type

Index = 0..n;

var

a: array[1..n] of elem;

procedure Insert;

var i,j: index;

x: elem;

begin

for i:= 1 to n do

begin

x:= a[i]; a[0]:= x; j:= i-1;

while x.key < a[j].key do

begin

a[j+1]:= a[j]; j:= j-1;

end;

a[j+1]:= x;

end;

end;

Пузырьковая Сортировка

Следующий метод - это пузырьковая сортировка. Проходить через массив, обменивая если нужно элементы; когда на каком-то шаге обменов не потребуется - сортировка окончена. Реализация этого метода дана ниже.

procedure bubble;

var i, j, t : byte;

begin

for i :=2 to N do

for j:=N down to i do

if x[i-1]>x[j] then

begin t:=x[j-1];x[j-1]:=x[j];x[j]:=t; end;

end;

end;

Динамические типы данных – линейные списки. Виды, структура, основные свойства. Применение.

Линейные однонаправленные списки являются динамической структурой данных, каждый элемент которой состоит из информативной и ссылочной части. Ниже представлено описание динамической строки символов.

type

TypeOfElem= Char;

Assoc= ^DynElem;

DynElem= record

Elem: TypeOfElem;

NextElem: Pointer

end;

DynStr= Assoc;

На практике, для обработки динамических строк вводят два указателя: на начало и конец (текущий элемент) цепочки.