Курсовая работа: Классификация структур данных языка программирования С#

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

[атрибуты] [спецификаторы ] class имя_класса [: предки ] тело_класса.

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

class Demo {}.

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

Таблица 1 - Спецификаторы класса

Программист создает экземпляр класса с помощью операции new, например:

Demo a = new Demo(); // создание экземпляра класса Demob = new Demo(); // создание другого экземпляра класса Demo.

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

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

Ниже приведено краткое описание всех элементов класса:

- Константы класса хранят неизменяемые значения, связанные с классом.

- Поля содержат данные класса;

- Методы реализуют вычисления или другие действия, выполняемые классом или экземпляром;

- Свойства определяют характеристики класса в совокупности со способами их задания и получения, то есть методами записи и чтения;

- Конструкторы реализуют действия по инициализации экземпляров или класса в целом;

- Деструкторы определяют действия, которые необходимо выполнить до того, как объект будет уничтожен;

- Индексаторы обеспечивают возможность доступа к элементам класса по их порядковому номеру;

- Операции задают действия с объектами с помощью знаков операций;

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

1.4 Структура программного модуля на С#

Программа на C# состоит из классов, внутри которых описывают методы и данные. Переменные, описанные непосредственно внутри класса, называются полями класса. Им автоматически присваивается так называемое «значение по умолчанию» - как правило, это 0 соответствующего типа. Переменные, описанные внутри метода класса, называются локальными переменными. Их инициализация возлагается на программиста.

Так называемая область действия переменной, то есть область программы, где можно использовать переменную, начинается в точке ее описания и длится до конца блока, внутри которого она описана. Блок - это код, заключенный в фигурные скобки. Основное назначение блока - группировка операторов. В C# любая переменная описана внутри какого-либо блока: класса, метода или блока внутри метода. Имя переменной должно быть уникальным в области ее действия. Область действия распространяется на вложенные в метод блоки.

1.5 Алгоритм пузырьковой сортировки

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

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

1.6 Сортировка Шелла

Сортировка Шелла -- алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами -- это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

Принцип работы:

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

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

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

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

Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

Отсутствие потребности в памяти под стек;

Отсутствие деградации при неудачных наборах данных -- быстрая сортировка легко деградирует до O(nІ), что хуже, чем худшее гарантированное время для сортировки Шелла.

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

Рис. 1 - Пример сортировки Шелла

2. Практическая часть

2.1 Выполнение задания курсовой работы

Алгоритмы пузырьковой сортировки

int[] a = new int[10];

int[] b = new int[10];

Random rnd = new Random();

for (int i = 0; i < a.Length; i++)

{

a[i] = rnd.Next(1, 50);

b[i] = a[i];

Console.Write("{0} ", a[i]);

}

Console.WriteLine();

Console.WriteLine("сортировка пузырьком");

for (int i = 0; i < a.Length; i++)

{

for (int j = 0; j < (a.Length - 1); j++)

{

if (b[j] > b[j + 1])

{

int tmp = b[j];

b[j] = b[j + 1];

b[j + 1] = tmp;

}

}

}

Рис. 2 - Написание кода

Рис. 3 - Консоль отладки

Алгоритм сортировки методом Шелла.

#include <stdio.h>

#include <malloc.h>

#include <conio.h>

//сортировка методом Шелла

void ShellSort(int n, int mass[])

{

int i, j, step;

int tmp;

for (step = n / 2; step > 0; step /= 2)

for (i = step; i < n; i++)

{

tmp = mass[i];

for (j = i; j >= step; j -= step)

{

if (tmp < mass[j - step])

mass[j] = mass[j - step];

else

break;

}

mass[j] = tmp;

}

}

int main()

{

//ввод N

int N;

printf("Input N: ");

scanf_s("%d", &N);

//выделение памяти под массив

int* mass;

mass = (int*)malloc(N * sizeof(int));

//ввод элементов массива

printf("Input the array elements:\n");

for (int i = 0; i < N; i++)

scanf_s("%d", &mass[i]);

//сортировка методом Шелла

ShellSort(N, mass);

//вывод отсортированного массива на экран

printf("Sorted array:\n");

for (int i = 0; i < N; i++)

printf("%d ", mass[i]);

printf("\n");

//освобождение памяти

free(mass);

_getch();

return 0;

}

#include <stdio.h>

#include <malloc.h>

#include <conio.h>

//сортировка методом Шелла

void ShellSort(int n, int mass[])

{

int i, j, step;

int tmp;

for (step = n / 2; step > 0; step /= 2)

for (i = step; i < n; i++)

{

tmp = mass[i];

for (j = i; j >= step; j -= step)

{

if (tmp < mass[j - step])

mass[j] = mass[j - step];

else

break;

}

mass[j] = tmp;

}

}

int main()

{

//ввод N

int N;

printf("Input N: ");

scanf_s("%d", &N);

//выделение памяти под массив

int* mass;

mass = (int*)malloc(N * sizeof(int));

//ввод элементов массива

printf("Input the array elements:\n");

for (int i = 0; i < N; i++)

scanf_s("%d", &mass[i]);

//сортировка методом Шелла

ShellSort(N, mass);

//вывод отсортированного массива на экран

printf("Sorted array:\n");

for (int i = 0; i < N; i++)

printf("%d ", mass[i]);

printf("\n");

//освобождение памяти

free(mass);

_getch();

return 0;

}

Рис. 4 - Написание кода

Рис. 5 - Консоль отладки

оператор сортировка алгоритм спецификатор

Заключение

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

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

Инструментальной средой разработки программ стала MS Visual Studio 2022.

Ввиду очень удобного объектно-ориентированного дизайна, C# является хорошим выбором для быстрого конструирования различных компонентов - от высокоуровневой бизнес логики до системных приложений, использующих низкоуровневый код. Также следует отметить, что C# является и Web ориентированным - используя простые встроенные конструкции языка ваши компоненты могут быть легко превращены в Web сервисы, к которым можно будет обращаться из Internet посредством любого языка на любой операционной системе. Дополнительные возможности и преимущества перед другими языками приносит в C# использование передовых Web технологий, таких как: XML (Extensible Markup Language) и SOAP (Simple Object Access Protocol). Среда разработки Web сервисов позволяет программисту смотреть на существующие сегодня Web приложения, как на родные C# объекты, что дает возможность разработчикам соотнести имеющиеся Web сервисы с их познаниями в объектно-ориентированном программировании.

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

Список использованной литературы

Павловская Т.А. C#. Программирование на языке высокого уровня: Учебник для вузов. - СПб.: БХВ-Петербург. 2019.

Попов И.И., Партыка Т.Л. Языки программирования: Учебное пособие. - М.: ФОРУМ: ИНФРА-М, 2018.

Голицина О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие. - М.: ФОРУМ: ИНФРА-М, 2021.