шпоры1 (1079641)

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

Текст из файла

1. Классы и объекты.

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

Объявление класса начинается с ключевого слова class.

class inf

{int a;

double b;

public:

void num();

int sum();};

void num(), int sum()- методы класса inf

int a, double b поля данных класса inf

По умолчанию члены класса являются закрытыми(private). Чтобы сделать части класса открытыми(т.е. доступными для других частей программы), необходимо объявить их после ключевого слова public. /////для 5

Для создания объекта классового типа используется имя класса.

inf i1,i2;

Для доступа к полям данных класса используется оператор “точка” (.) .

i1.a=2;

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

void inf ::num()

{a=a+2;

cout<<a;

}

“::”-оператор разрешения области видимости(квалифицирует имя члена вместе именем его класса)

Вызов функции для классового элемента.

i1.num();

объекты

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

Объект нового типа определяется точно так же, как и любая целочисленная переменная:

Class Cat{

Int GrossWeight;

Cat Frisky;}

В том коде определяется переменная GrossWeight, которая имеет тип int, а также определяется объект Frisky класса (или типа) Cat.

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

1. Особенности сортировки файлов

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

Для сортировки файлов используют методы.

-метод слияния

-метод осциллирующей сортировки

-метод многофазной сортировки

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

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

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

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

Мы изучаем три метода сортировки:

1. Сортировка файлов слиянием

2. Осциллирующая сортировка

3. Многофазная сортировка

1. Члены класса – методы и поля.

См.4 вопрос

Поле класса (переменная-член, data member, class field, instance variable) в объектно-ориентированном программировании — переменная, связанная с классом или объектом. Все данные объекта хранятся в его полях. Доступ к полям осуществляется по их имени. Обычно тип данных каждого поля задаётся в описании класса, членом которого является поле.

Поля структур

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

Статические поля

Обычно каждому объекту соответствуют собственные значения всех его полей. Также к полям класса относят статические поля (static data members, static class fields, class variables) — поля, общие для всех объектов класса.

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

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

Битовые поля

Некоторые языки, такие как C++, позволяют определять битовые поля. Эти поля занимают менее одной единицы памяти (байт, слово); компилятор сам упаковывает несколько битовых полей в одну единицу памяти, позволяя при этом обращаться к битовым полям как к отдельным полям класса.

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

class foo

{ private:

int x; // Это поле — закрытое. Доступ к нему возможен только

// из методов класса ''foo''.

public:

int y; //Это поле — открытое. Доступ к нему возможен из любого места программы.

int get_x() {return x;};

void set_x(int x) {this->x = x; };

static int z; // Это статическое поле. Оно принадлежит классу foo целиком, а не его объектам.

char a:3; // Это битовые поля. В сумме они занимают

char b:3; // 8 бит, т.е. они будут размещены в одном

char c:1; // байте памяти. Таким образом возможно

char d:1: // обращаться к отдельным битам памяти.};

1. Сортировка файлов методом слияния

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

Одним из наиболее примечательных свойств сортировки методом слияния является то, что она сортирует n элементов, за время, пропорциональное nlogn, независимо от характера входных данных.

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

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй».Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Для решения задачи сортировки эти три этапа выглядят так: 1) Сортируемый массив разбивается на две половины меньшего размера; 2) Каждая из получившихся половин сортируется отдельно; 3) Два упорядоченных массива половинного размера соединяются в один.

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

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

Объединение 2х массивов в третий с использованием цикла for.

Template <class Item>

Void MergeAB (Item a[], Item b[], Item c[], int n, int m)

{ for (int i=0, j=0, k=0; k< n+m; k++)

{If (i==m) {c[k]= b[j++]; continue;}

If (j==n) {c[k] =a[i++]; continue; }

c[k] = (a[i]<b[j]) ? a[i++]:b[j++]; }}

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

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

1. Конструкторы классов.

Конструктор-это функция-член в классе, которая вызывается при создании объекта.

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

Определение класса.

class inf

{int a;

double b;

public:

inf(); конструктор

void num();

int sum();};

В объявлении конструктора отсутствует тип возвращаемого значения, так как конструкторы в C++ не возвращают значений.

Определение конструктора.

inf::inf()

{cout<<”!!!”;}

Параметризированные конструкторы.

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

class inf

{int a;

double b;

public:

inf(int i); параметризированный конструктор

void num();

int sum();};

Для передачи аргумента конструктору используется следующая запись при создании классового элемента.

inf a(10); (тип_класса имя_переменной(список_аргументов))

32. Осциллирующая сортировка файлов.

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

Здесь мы используем А_r и D_{r для} обозначения соответственно возрастающих и убывающих отрезков относительной длины r. Рассматриваемый метод начинает с записи по одному начальному отрезку на каждую из 4-х лент и сливает их, читая в обратном направлении, на пятую. Опять возобновляется рсчпределение, на этот раз циклически сдвинутое на 1 вправо по отношению к лентам, и второе слияние дает еще один отрезок D_4. Когда этим способом сформированы 4 отрезка D₄, дополнительное слияние создает А₁₆. Процесс можно продолжать, создавая еще три А₁₆, сливая их в D₆₄ и т.д. до тех пор, пока не исчерпаются все исходные данные. Не нужно знать заранее длину исходных данных.

Если число начальных отрезков S есть 4^m, то нетрудно видеть, что этот метод обрабатывает каждую запись ровно m+1 раз (один раз во время распределения и m раз во время слияния). Если S лежит между 4^m-1 и 4^m, то можно с помощью фиктивных отрезков увеличить S до 4^m, следовательно, общее время сортировки будет определяться [log ₄S] +1 проходами по всем данным. В общем случае, осциллирующая сортировка с Т рабочими лентами эквивалентна сбалансированному слиянию с 2(Т-1) лентами, т.к. она делает [log_T-1 S] +1 проходов по данным. Если S оказывается степенью Т-1, то это самое лучшее, что можно получить при любом методе с Т лентами. С другой стороны, если S равно (Т-1)^m-1 +1, т.е. ровно на единицу больше степени Т-1, то этот метод теряет целый проход.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов лабораторной работы