Сборка и анализ программного продукта

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

Ход работы Очередь FIFO (акроним First In, First Out — «первым пришёл — первым ушёл») — способ организации и манипулирования данными относительно времени и приоритетов. Это выражение описывает принцип технической обработки очереди или обслуживания конфликтных требований путём упорядочения процесса по принципу: «первым пришёл — первым обслужен» (ПППО). Тот, кто приходит первым, тот и обслуживается первым, пришедший следующим ждёт, пока обслуживание первого не будет закончено, и так далее.

Этот принцип аналогичен поведению лиц, стоящих в очереди, когда люди получают обслуживание в том порядке, в котором они занимали очередь. То же самое происходит, например, на нерегулируемом перекрёстке, когда водители ожидают своей очереди на продолжение движения (в американских ПДД нет правила «помеха справа», приоритет определяется по принципу FIFO). ПППО также используется как сокращённое название для алгоритма FIFO планирования работы операционной системы, по которому процессорное время выделяется каждому процессу в порядке их поступления на обслуживание. В более широком смысле, абстракция LIFO или Last-In-First-Out («последним пришёл — первым ушёл») является противоположностью абстракции FIFO. Разница, возможно, станет яснее, если принять во внимание реже используемый синоним FILO, означающий First-In-Last-Out («первым пришёл — последним ушёл»). В сущности, обе абстракции являются конкретными случаями более общего понятия работы со списком. Разница не в списке (данных), а в правиле доступа к содержимому. В первом случае добавление делается к одному концу списка, а снятие с другого, во втором случае добавление и снятие делается на одном конце.

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

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде, отсюда и название алгоритма).

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

Сортировка слиянием — стабильный алгоритм сортировки. Это означает, что порядок «равных» элементов не изменяется в результате работы алгоритма. В некоторых задачах это свойство достаточно важно.

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

• 1. прост в реализации;
• 2. эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
• 3. эффективен на наборах данных, которые уже частично отсортированы;
• 4. это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
• 5. может сортировать массив по мере его получения;
• 6. не требует временной памяти, даже под стек.

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

Рисунок 7. Запуск программы.

Перейдем к работе с данными.

Рисунок 8. Работа с данными.

Удалим пару элементов:

Рисунок 9. Удаление элементов.

Добавим элемент:

Рисунок 10.

Отсортируем по фамилии:

Рисунок 11.

По типу операции:

Рисунок 12. Сортировка по типу операции.

По типу украшения:

Рисунок 13. Сортировка по типу украшения.

Вывод числа совершенных операций:

Рисунок 14. Вывод числа совершенных операций.

Листинг программы:

Класс Dataданные, состоящие из трех строковых параметров (фамилия сотрудника, район и тип преступления).

using System;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

namespaceProgEng.

{.

classData.

{.

string name { get; set; }//Фамилия.

string type { get; set; }//Тип операции.

string vid { get; set; }//Продукция.

stringsostav { get; set; }//Состав.

public Data (string name, string type, string vid, stringsost)//конструктор

{.

this.name = name;

this.type = type;

this.sostav = sost;

this.vid = vid;

}.

publicstringReturnData ()//Возвращает всю информацию в виде одной строки.

{.

return name + «» + type + «» + vid + «» + sostav;

}.

publicstaticintNameCompare (Data d1, Data d2)//Сравнивает 2 объекта по полю фамилия.

{.

returnString.Compare (d1.name, d2.name);

}.

publicstaticintTypeCompare (Data d1, Data d2)//Сравнивает 2 объекта по полю тип сделки.

{.

returnString.Compare (d1.type, d2. type);

}.

publicstaticintVidCompare (Data d1, Data d2)//Сравнивает 2 объекта по полю вид продукции.

{.

returnString.Compare (d1.vid, d2. vid);

}.

publicstaticintSostavCompare (Data d1, Data d2)//Сравнивает 2 объекта пополю состав изделия.

{.

returnString.Compare (d1.sostav, d2. sostav);

}}}.

Класс List — реализует экземпляр односвязного списка с указателемна следующий и полем с данными. (Приложение 2).

Класс FIFO — хранит ссылку на первый элемент очереди и позволяет работать с ней, осуществляя операции добавления (в конец), удаления (из начала) и сортировки. (Приложение 3).

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