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

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

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

· количество присваиваний;

· количество сравнений.

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

· прямые методы сортировки;

· улучшенные методы сортировки.

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

1) сортировка вставкой (включением);

2) сортировка выбором (выделением);

3) сортировка обменом (метод «пузырька»).

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

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

Абстрактный тип данных (АТД) – это “новый” тип, реализованный набором процедур и функций и не поддерживаемый ни аппаратурой, ни системой программирования.

Но АТД, введённым внутри программы нельзя воспользоваться вне программы (в других программах), т.к. то, что создано внутри программы есть неотъемлемые части программой единицы.

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

Для реализации этого в С предусмотрены внешние отдельно компилируемые процедуры (функции).

{т.е. функция может быть описана отдельно от самой программы (объектный/заготовочный файл)}.

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

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

В Си поддержка модульной архитектуры реализуется просто: каждый.c файл компилируется независимо, но при этом они могут связываться с помощью подключения заголовочных.h-файлов. В сущности,.c-файл - это реализация модуля, а.h-файл - его интерфейс, то есть доступная клиентскому коду часть функциональности. При этом разные реализации могут использовать один интерфейс: пусть есть заголовочный файл list.h, описывающий интерфейс списочной структуры данных, и файлы реализации list_array.c, list_dynamic.c, его подключающие. Тогда управляющий модуль main.c может быть скомпилирован и как gcclist_array.cmain.c, и как list_dynamic.c, и при этом в коде не придётся менять абсолютно ничего.

48 Модули в расширениях языка Паскаль. Модуль имеет следующую структуру:

UNIT <имя модуля>

INTERFACE

<раздел интерфейсный>

IMPLEMENTATION

<раздел реализации>

BEGIN

<раздел инициализации>

END.

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

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

Раздел инициализации – заключается в словесные скобки BEGIN END.

и содержит операторы, которые будут выполнены до передачи управления основной программе. Это м.б. операторы инициализации данных (переменных) Например операторы присваивания, ввода а также процедуры связывания и открытия файлов. Раздел операторов м.б. пустымBEGIN END или отсутствовать простоEND.

В конце модуля ставится точка.

 

49 Абстракции в языках программирования. Был осуществлен переход к более высокому уровню абстракции, связанному с понятием абстрактного типа данных. АТД — это, по существу, определение некоторого понятия в виде класса (одного или более) объектов с некоторыми свойствами и операциями.

В самой развитой форме в определение АТД входят следующие четыре части:

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

2. абстрактное описание операций и объектов, с которыми они работают, средства- ми некоторого языка спецификаций, допускающего, в частности, формулирование свойств;

3. конкретное (логическое) описание этих операций на обычном распространенном языке программирования предыдущего поколения;

4. описание связи между 2 и 3, объясняющее, в каком смысле часть 3 корректно представляет часть 2.

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

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

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

50 Абстрактные типы данных. Пример модуля ЛТД ОЧЕРЕДЬ.

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

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

Модуль АТД ОЧЕРЕДЬ:

#ifndef __functions_h_

#define __functions_h_

#include <stdio.h>

typedef struct elem elem;

struct elem{

int val;

elem *next;

};

typedef struct{

elem *top;

elem *bottom;

} stack;

void stack_init(stack *s); // создание

bool empty(stack *s); // “пусто?”

voidpop(stack *s); // удалить первый элемент

inttop(stack *s); // значение первого элемента

voidpush(stack *s, intval); // добавить элемент в конец

voidprint_list(stack *s); // распечатать содержимое

intcount(stack *s); // “сколько элементов?”

#endif

#include "functions.h"

void stack_init(stack *s){

s->top = 0;

}

bool empty(stack *s){

return s->top == 0;

}

…