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

Размещено на http://www.allbest.ru/

Федеральное агентство морского и речного транспорта

Воронежский филиал

Федерального государственного бюджетного образовательного

учреждения высшего образования

«Государственный университет морского и речного флота имени адмирала С.О. Макарова»

КУРСОВАЯ РАБОТА

по дисциплине: Алгоритмы и структуры данных

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

Выполнил: студент группы ИТ-3-2

Гладких Надежда Викторовна

Воронеж 2022 г

Содержание

Введение

1. Язык С#

1.1. Алфавит языка С#

1.2 Операторы языка С#

1.3 Понятие классов и объектов

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

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

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

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

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

Заключение

Введение

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

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

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

Объектами исследования настоящей курсовой работы являются методы и технологии разработки программных продуктов.

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

Информационной базой исследования является учебная литература по информатике и программированию, техническая документация по языку С# инструментальной среды MS Visual Studio 2010.

1. Язык С#

1.1 Алфавит языка С#

Все тексты на языке пишутся с помощью его алфавита. В C# используется кодировка символов Unicode. Кодировкой, или кодовой таблицей (character set), называется соответствие между символами и кодирующими их числами. Кодировка Unicode позволяет представить символы всех существующих алфавитов одновременно. Каждому символу соответствует свой уникальный код.

Алфавит C# включает:

- буквы (латинские и национальных алфавитов) и символ подчеркивания (_), который употребляется наряду с буквами;

- цифры;

- специальные символы, например +, *, { и &;

- пробельные символы (пробел и символы табуляции);

- символы перевода строки.

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

Лексема (token) - это минимальная единица языка, имеющая самостоятельный смысл. Существуют следующие виды лексем:

- имена (идентификаторы);

- ключевые слова;

- знаки операций;

- разделители;

- литералы (константы).

Лексемы языка программирования аналогичны словам естественного языка. Например, лексемами являются число 128 (но не его часть 12), имя Vasia, ключевое слово goto и знак операции сложения +. Далее мы рассмотрим лексемы подробнее.

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

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

Из лексем составляются выражения и операторы. Выражение задает правило вычисления некоторого значения. Например, выражение a + b задает правило вычисления суммы двух величин.

1.2 Операторы языка С#

Любое выражение, завершающееся точкой с запятой, рассматривается как оператор, выполнение которого заключается в вычислении выражения. Частным случаем выражения является пустой оператор; (он используется, когда по синтаксису оператор требуется, а по смыслу - нет). Примеры: i++; // выполняется операция инкремента*= b + c; // выполняется умножение с присваиванием( i, k ); // выполняется вызов функции( true ); // цикл из пустого оператора (бесконечный)

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

Условный оператор if используется для разветвления процесса вычислений на два направления.

Формат оператора:

if ( логическое_выражение ) оператор_1; [ else оператор_2; ]

Сначала вычисляется логическое выражение. Если оно имеет значение true, выполняется первый оператор, иначе - второй. После этого управление передается на оператор, следующий за условным. Ветвь else может отсутствовать.

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

Примеры условных операторов:

( a < 0 ) b = 1; // 1( a < b && ( a > d || a == 0 ) ) b++; else { b *= a; a = 0; } // 2( a < b ) if ( a < c ) m = a; else m = c;if ( b < c ) m = b; else m = c; // 3( b > a ) max = b; else max = a; // 4

Если требуется проверить несколько условий, их объединяют знаками логических условных операций. Например, выражение в примере 2 будет истинно в том случае, если выполнится одновременно условие a < b и одно из условий в скобках. Оператор в примере 3 вычисляет наибольшее значение из трех переменных.

Оператор switch (переключатель) предназначен для разветвления процесса вычислений на несколько направлений

Формат оператора:

switch ( выражение ){константное_выражение_1: [ список_операторов_1 ]константное_выражение_2: [ список_операторов_2 ]

...константное_выражение_n: [ список_операторов_n ]

[ default: операторы ]

}

Выполнение оператора начинается с вычисления выражения. Тип выражения чаще всего целочисленный (включая char) или строковый. Затем управление передается первому оператору из списка, помеченному константным выражением, значение которого совпало с вычисленным. Если совпадения не произошло, выполняются операторы, расположенные после слова default, а при его отсутствии управление передается следующему за switch оператору.

Каждая ветвь переключателя должна заканчиваться явным оператором перехода, а именно одним из операторов break, goto или return:

оператор break выполняет выход из самого внутреннего из объемлющих его операторов switch, for, while и do;

оператор goto выполняет переход на указанную после него метку, обычно это метка case одной из нижележащих ветвей оператора switch;

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

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

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

Проверка условия продолжения цикла выполняется на каждой итерации либо до тела цикла (тогда говорят о цикле с предусловием), либо после тела цикла (цикл с постусловием).

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

Цикл завершается, если условие его продолжения не выполняется. Возможно принудительное завершение как текущей итерации, так и цикла в целом. Для этого служат операторы break, continue, return и goto. Передавать управление извне внутрь цикла запрещается.

Формат оператора:

while ( выражение ) оператор.

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

Выражение вычисляется перед каждой итерацией цикла. Если при первой проверке выражение равно false, цикл не выполнится ни разу.

Цикл с постусловием и имеет вид:

do оператор while выражение.

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

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

Цикл с параметром имеет следующий формат:

for ( инициализация; выражение; модификации ) оператор.

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

for ( int i = 0, j = 20; ...k, m;

for ( k = 1, m = 0; ...

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

Выражение типа bool определяет условие выполнения цикла: если его результат равен true, цикл выполняется.

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

( int i = 0, j = 20; i < 5 && j > 10; i++, j-- )

Простой или составной оператор представляет собой тело цикла. Любая из частей оператора for может быть опущена (но точки с запятой надо оставить на своих местах!).

Для примера вычислим сумму чисел от 1 до 100:

s = 0;( int i = 1; i <= 100; i++ ) s += i.

Цикл foreach используется для просмотра всех объектов из некоторой группы данных, например, массива, списка или другого контейнера. Он будет рассмотрен в разделе «Оператор foreach».

В С# есть пять операторов, изменяющих естественный порядок выполнения вычислений:

- оператор безусловного перехода goto;

- оператор выхода из цикла break;

- оператор перехода к следующей итерации цикла continue;

- оператор возврата из функции return;

- оператор генерации исключения throw.

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

Оператор безусловного перехода goto используется в одной из трех форм:

goto метка;case константное_выражение;default.

В теле той же функции должна присутствовать ровно одна конструкция вида: метка: оператор.

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

Вторая и третья формы оператора goto используются в теле оператора выбора switch. Оператор goto case константное_выражение передает управление на соответствующую константному выражению ветвь, а оператор goto default - на ветвь default.

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

Оператор перехода к следующей итерации текущего цикла continue пропускает все операторы, оставшиеся до конца тела цикла, и передает управление на начало следующей итерации.

Оператор возврата из функции return завершает выполнение функции и передает управление в точку ее вызова. Синтаксис оператора:

return [ выражение ].

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

1.3 Понятие классов и объектов

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

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

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

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

class Demo {}.

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

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

№	Спецификатор	Описание
1	new	Используется для вложенных классов. Задает новое описание класса взамен унаследованного от предка. Применяется в иерархиях объектов
2	public	Доступ не ограничен
3	protected	Используется для вложенных классов. Доступ только из элементов данного и производных классов
4	internal	Доступ только из данной программы (сборки)
5	protected internal	Доступ только из данного и производных классов или из данной программы (сборки)
6	private	Используется для вложенных классов. Доступ только из элементов класса, внутри которого описан данный класс
7	abstract	Абстрактный класс. Применяется в иерархиях объектов, рассматривается в главе 8
8	sealed	Бесплодный класс. Применяется в иерархиях объектов, рассматривается в главе 8
9	static	Статический класс. Введен в версию языка 2.0. Рассматривается в разделе «Конструкторы»

Программист создает экземпляр класса с помощью операции 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.

Фаронов В.В., Создание приложений с помощью C#: Руководство программиста. - М.: Эксмо, 2018.

Свердлов С.З. Языки программирования и методы трансляции. Учебное пособие. - СПб.: Питер, 2020.

Павловская Т.А. С/С++ Программирование на языке высокого уровня. - СПб.: Питер, 2022.

Нортроп Тони, Уилдермьюс Шон, Райан Билл. Основы разработки приложений на платформе Microsoft .Net Framework. Учебный курс Microsoft / Пер. с англ. - М.: «Русская редакция», СПб.: «Питер», 2019

Размещено на Allbest.ru

...