Методические указания по выполнению лабораторных и практических работ по мдк
 Скачать 3.25 Mb.
|
|
Задание 3. Создание объекта класса Dictionary Пустой словарь: var dict = new Dictionary Словарь с набором элементов: var prodPrice = new Dictionary { ["bread"] = 23.3, ["apple"] = 45.2 }; Console.WriteLine($"bread price: {prodPrice["bread"]}"); Задание 4. Работа с объектами Dictionary Рассмотрим некоторые из свойств и методов класса Dictionary Свойства класса Dictionary Свойство Описание Count Количество объектов в словаре 79 Keys Ключи словаря Values Значения элементов словаря Console.WriteLine("Свойства"); Console.WriteLine($"Словарь prodPrice: {DictToString(prodPrice)}"); Console.WriteLine($"Count: {prodPrice.Count}"); Console.WriteLine($"Keys: {ListToString(prodPrice.Keys.ToList Console.WriteLine($"Values: {ListToString(prodPrice.Values.ToList Методы класса Dictionary Метод Описание Add(TKey, TValue) Добавляет в словарь элемент с заданным ключом и значением Clear() Удаляет из словаря все ключи и значения ContainsValue(TValue) Проверяет наличие в словаре указанного значения ContainsKey(TKey) Проверяет наличие в словаре указанного ключа GetEnumerator() Возвращает перечислитель для перебора элементов словаря Remove(TKey) Удаляет элемент с указанным ключом TryAdd(TKey, TValue) Метод, реализующий попытку добавить в словарь элемент с заданным ключом и значением TryGetValue(TKey, TValue) Метод, реализующий попытку получить значение по заданному ключу prodPrice.Add("tomate", 11.2); Console.WriteLine($"Словарь prodPrice: {DictToString(prodPrice)}"); var isExistValue = prodPrice.ContainsValue(11.2); Console.WriteLine($"isExistValue = {isExistValue}"); var isExistKey = prodPrice.ContainsKey("tomate"); Console.WriteLine($"isExistKey = {isExistKey}"); prodPrice.Remove("bread"); Console.WriteLine($"Словарь prodPrice: {DictToString(prodPrice)}"); var isOrangeAdded = prodPrice.TryAdd("orange", 20.1); Console.WriteLine($"isOrangeAdded = {isOrangeAdded}"); double orangePrice; var isPriceGetted = prodPrice.TryGetValue("orange", out orangePrice); Console.WriteLine($"isPriceGetted = {isPriceGetted}"); Console.WriteLine($"orangePrice = {orangePrice}"); prodPrice.Clear(); Console.WriteLine($"Словарь prodPrice: {DictToString(prodPrice)}"); Кортежи Tuple и ValueTuple Относительно недавним нововведением в языке C# (начиная с C# 7) являются кортежи. Кортежем называют структуру данных типа Tuple или ValueTuple (чуть ниже мы рассмотрим различия между ними), которые позволяют группировать объекты разных типов друг с другом. С практической точки зрения они являются удобным способом возврата из метода нескольких значений – это наиболее частый вариант использования кортежей. Различия между Tuple и ValueTuple приведены в таблице ниже. Tuple ValueTuple Ссылочный тип Тип значение Неизменяемый тип Изменяемый тип Элементы данных – это свойства Элементы данных – это поля Создание кортежей Рассмотрим несколько вариантов создания кортежей. Создание кортежа без явного и с явным указанием имен полей: (string, int) p1 = ("John", 21); (string Name, int Age) p2 = ("Mary", 23); При этом для доступа к элементам кортежа в первом варианте используются свойства Item с числом, указывающем на порядок элемента, во втором – заданные пользователем имена: Console.WriteLine($"p1: Name: {p1.Item1}, Age: {p1.Item2}"); 80 Console.WriteLine($"p1: Name: {p2.Name}, Age: {p2.Age}"); Возможны следующие способы создания кортежей с явным заданием имен: var p3 = (Name: "Alex", Age: 24); var Name = "Lynda"; var Age = 25; var p4 = (Name, Age); Console.WriteLine($"p3: Name: {p3.Name}, Age: {p3.Age}"); Console.WriteLine($"p4: Name: {p4.Name}, Age: {p4.Age}"); При этом возможность обращаться через свойства Item1 и Item2 для созданных выше переменных остается: Console.WriteLine($"p3: Name: {p3.Item1}, Age: {p3.Item2}"); Console.WriteLine($"p4: Name: {p4.Item1}, Age: {p4.Item2}"); Работа с кортежами Как было сказано в начале раздела, кортежи можно возвращать в качестве результата работы метода. Пример метода, который сравнивает длину переданной строки с некоторым порогом и возвращает соответствующее bool-значение и целое число – длину строки: static (bool isLonger, int count) LongerThenLimit(string str, int limit) => str.Length > limit ? (true, str.Length) : (false, str.Length); Кортежи можно присваивать друг другу, при этом необходимо, чтобы соблюдались следующие условия: количество элементов в обоих кортежах одинаковое; типы соответствующих элементов совпадают, либо могут быть приведены друг к другу. var p5 = ("Jane", 26); (string, int) p6 = p5; Console.WriteLine($"p6: Name: {p6.Item1}, Age: {p6.Item2}"); Операцию присваивания можно использовать для деструкции кортежа. (string name, int age) = p5; Console.WriteLine($"Name: {name}, Age: {age}"); Исходный код примеров из этой статьи можете скачать из нашего github-репозитория. Практическая работа № 1.19. Параметризованные классы Цель работы: изучить механизм параметрического полиморфизма на основе создания и использования параметризованных классов. Ход работы Задание. Ввести код программы, проанализировать результат. Пример программы //класс вещество, содержащий температуру и массу class Substance { double Mass; double Temperature; public: //требуется перегрузка оператора сложения для класса Substance, так как данная операция совершается в классе Matrix. Без данной перегрузки компилятор выдаст ошибку Substance operator + (Substance c) { Substance res; res.Mass = this->Mass + c.Mass; res.Temperature = (this->Temperature*this->Mass + c.Temperature*c.Mass) / (this->Mass + c.Mass); return res; } //так как метод rand_val вызывается из класса Matrix, то данный метод должен обязательно присутствовать в классе Substance static Substance rand_val() { Substance res; res.Mass = (rand() % 2000) / 100.0 + 5; 81 res.Temperature = (rand() % 2000) / 100.0 + 10; return res; } //так как метод to_str вызывается из класса Matrix, то данный метод должен обязательно присутствовать в классе Substance void to_str(char* bufer) { sprintf(bufer, "M=%.2lf;T=%.2lf", Mass, Temperature); } }; //определение шаблонного класса Matrix, который позволяет хранить матрицу из объектов, которые имеются тип T template <class T> class Matrix{ //определение массива элементов типа T T m[4][4]; public: Matrix() { for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) m[i][j] = T::rand_val(); } //запись T::rand_val() в шаблонном классе предполагает наличие у класса T публичного статического метода rand_val. Программа не может быть собрана, если у класса T нет данного метода. void print() { char *bufer = new char[100]; printf("Matrix\n"); for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { m[i][j].to_str(bufer); printf("%s\t", bufer); } printf("\n"); } printf("\n"); delete bufer; } //запись m[i][j].to_str(bufer) для элемента (он имеет тип T) массива m предполагает наличие метода to_str у класса T. Программа не может быть собрана, если у класса T нет данного метода. Matrix operator + (Matrix &b) { Matrix<T> res; for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) res.m[i][j] = this->m[i][j] + b.m[i][j]; return res; } //операция сложения между экземплярами класса T (это - this->m[i][j] и b.m[i][j]) предполагает наличие у класса T перегруженного оператора сложения. Программа не может быть собрана, если у класса T нет данного перегруженного оператора. }; 82 //класс Substance имеет статический метод rand_val(), метод to_str() и перегруженный оператор сложения, поэтому он может быть использован в качестве параметра шаблонного класса Matrix. void main() { Matrix<Substance> m1; m1.print(); Matrix<Substance> m2; m2.print(); Matrix<Substance> m3 = m1 + m2; m3.print(); } Практическая работа № 1.20. Использование регулярных выражений Цель работы: изучить регулярные выражения Теоретический материал Регулярные выражения представляют собой язык описания текстовых шаблонов. Регулярные выражения содержат образцы символов, входящих в искомое текстовое выражение, и конструкции, определяемые специальными символами (метасимволами). Метасимволы, используемые в регулярных выражениях ^ начало строки $ конец строки [] любой символ, заключенный в квадратные скобки; чтобы задать диапазон символов, в квадратных скобках указываются через дефис первый и последний символы диапазона [^] любой символ, кроме символов, заданных в квадратных скобках любой отдельный символ \ отменяет специальное значение следующего за ним метасимвола * указывает, что предыдущий шаблон встречается 0 или более раз \{n\} указывает, что предыдущий шаблон встречается ровно n раз \{n,\} указывает, что предыдущий шаблон встречается не менее n раз \{,n\} указывает, что предыдущий шаблон встречается не более n раз \{n,m\} указывает, что предыдущий шаблон встречается не менее n и не более m раз Примеры регулярных выражений ^the ищутся строки, начинающиеся с буквосочетания "the" be$ ищутся строки, заканчивающиеся буквосочетанием "be" [Ss]igna[lL] ищутся строки, содержащие буквосочетания: "signal", "Signal", "signaL" или "SignaL" \. ищутся строки, содержащие точку ^...th ищутся строки, содержащие символы "th" в 4-й и 5-й позициях ^.*\{53\}th ищутся строки, содержащие символы "th" в 54-й и 55-й позициях ^.*\{10,30\}th ищутся строки, содержащие символы "th" в любых позициях между 11-й и 31-й ^.....$ ищутся строки, состоящие из 5 любых символов ^t.*e$ ищутся строки, начинающиеся с буквы "t" и заканчивающиеся буквой "e" [0-9][a-z] ищутся строки, содержащие комбинацию: цифра-прописная буква [^123] ищутся строки, не содержащие цифр "1" или "2" или "3" Функции для работы с регулярными выражениями: 1) boolereg(stringpattern, stringstring [, arrayregs]) – ищет в строке string соответствие регулярному выражению, заданному в шаблоне pattern. 2) stringereg_replace(stringpattern, stringreplacement, stringstring) – заменяет найденный в строке string шаблон pattern на строку replacement и, если соответствие было найдено, возвращает модифицированную строку. 83 3) booleregi (stringpattern, stringstring[, arrayregs]) – идентична функции ereg, за исключением того, что она игнорирует регистр. 4) arraysplit (stringpattern, stringstring [, intlimit]) – возвращает массив строк, которые представляют собой подстроки строки string, образованные в результате разделения строки string на подстроки в соответствии с регулярным выражением pattern. 5) arrayspliti (stringpattern, stringstring [, intlimit]) - аналогична функции split, за исключением того, что является нечувствительной к регистру. 6) stringeregi_replace (stringpattern, stringreplacement, stringstring) – аналогична функции ereg_replace, за исключением того, что она является нечувствительной к регистру. Ход работы 1. Составьте регулярное выражение для проверки корректности заполнения адреса электронной почты. 2. Создайте web-страницу, содержащую четыре поля (имя, адрес электронной почты, пароль и подтверждение пароля) и кнопку отправки данных. Ход работы (решение сохраните в отдельную папку): 1. В первом задании нужно только составить выражение без его проверки на компьютере. В регулярном выражении для проверки адреса электронной почты необходимо учесть то, что: а) в имени пользователя могут присутствовать буквы нижнего и верхнего регистров, цифры, знаки подчеркивания, минуса и точки; б) для проверки разделителя между именем пользователя и именем домена в выражение требуется добавить +@; в) доменное имя может содержать две или три латинские буквы. Все три шага нужно объединить в одно выражение при помощи плюса. 2. К выполнению второго задания предъявляется следующие требования: a. Поля и кнопка должны располагаться сверху вниз; b. В имени могут содержаться только латинские буквы и цифры; c. Адрес электронной почты проверяется в соответствие с регулярным выражением, составленным в предыдущем задании; d. Пароль и подтверждение пароля должно отображаться знаками «*». Для этого указывается type=password. Конечно, значения обоих полей должны совпадать; e. Вся форма и каждое поле в отдельности проверяется на пустоту при помощи функции empty или isset. Для каждого пустого поля выводится соответствующее сообщение красным цветом, например, «не введён адрес»; f. Из первых двух полей удалите обратные слеши и тэги; Как только форма заполнена абсолютно корректно на той же web-странице (где находится форма) выводится сообщение «всё в порядке». Практическая работа № 1.21. Операции со списками Цель работы: изучение операций со списками Теоретический материал Основные операции Список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL. Для нас односвязный список полезен тем, что Он очень просто устроен и все алгоритмы интуитивно понятны Односвязный список – хорошее упражнение для работы с указателями Его очень просто визаулизировать, это позволяет "в картинках" объяснить алгоритм Несмотря на свою простоту, односвязные списки часто используются в программировании, так что это не пустое упражнение. Эта структуру данных можно определить рекурсивно, и она часто используется в рекурсивных алгоритмах. Для простоты рассмотрим односвязный список, который хранит целочисленное значение. Односвязный список Односвязный список состоит из узлов. Каждый узел содержит значение и указатель на следующий узел, поэтому представим его в качестве структуры ? 84 typedef struct Node { int value; struct Node *next; } Node; Чтобы не писать каждый раз struct мы определили новый тип. Теперь наша задача написать функцию, которая бы собирала список из значений, которые мы ей передаём. Стандартное имя функции – push, она должна получать в качестве аргумента значение, которое вставит в список. Новое значение будет вставляться в начало списка. Каждый новый элемент списка мы должны создавать на куче. Следовательно, нам будет удобно иметь один указатель на первый элемент списка. ? Node *head = NULL; Вначале списка нет и указатель ссылается на NULL. Для добавления нового узла необходимо Выделить под него память. Задать ему значение Сделать так, чтобы он ссылался на предыдущий элемент (или на NULL, если его не было) Перекинуть указатель head на новый узел. 1) Создаём новый узел Создали новый узел, на который ссылается локальная переменная tmp 2) Присваиваем ему значение Присвоили ему значение 3) Присваиваем указателю tmp адрес предыдущего узла Перекинули указатель tmp на предыдущий узел 4) Присваиваем указателю head адрес нового узла Перекинули указатель head на вновь созданный узел tmp 5) После выхода из функции переменная tmp будет уничтожена. Получим список, в который будет вставлен новый элемент. Новый узел добавлен ? void push(Node **head, int data) { Node *tmp = (Node*) malloc(sizeof(Node)); tmp->value = data; tmp->next = (*head); (*head) = tmp; } Так как указатель head изменяется, то необходимо передавать указатель на указатель. Теперь напишем функцию pop: она удаляет элемент, на который указывает head и возвращает его значение. Если мы перекинем указатель head на следующий элемент, то мы потеряем адрес первого и не сможем его удалить и тем более вернуть его значения. Для этого необходимо сначала создать локальную переменную, которая будет хранить адрес первого элемента Локальная переменная хранит адрес первого узла Уже после этого можно удалить первый элемент и вернуть его значение Перекинули указатель head на следующий элемент и удалили узел ? int pop(Node **head) { Node* prev = NULL; int val; if (head == NULL) { exit(-1); } prev = (*head); val = prev->value; (*head) = (*head)->next; free(prev); 85 return val; } Не забываем, что необходимо проверить на NULL голову. Таким образом, мы реализовали две операции push и pop, которые позволяют теперь использовать односвязный список как стек. Теперь добавим ещё две операции - pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение. Ход работы Необходимо реализовать функции getLast, которая возвращает указатель на последний элемент списка, и nth, которая возвращает указатель на n-й элемент списка. Так как мы знаем адрес только первого элемента, то единственным способом добраться до n-го будет последовательный перебор всех элементов списка. Для того, чтобы получить следующий элемент, нужно перейти к нему через указатель next текущего узла ? Node* getNth(Node* head, int n) { int counter = 0; while (counter < n && head) { head = head->next; counter++; } return head; } Переходя на следующий элемент не забываем проверять, существует ли он. Вполне возможно, что был указан номер, который больше размера списка. Функция вернёт в таком случае NULL. Сложность операции O(n), и это одна из проблем односвязного списка. Для нахождение последнего элемента будем передирать друг за другом элементы до тех пор, пока указатель next одного из элементов не станет равным NULL ? Node* getLast(Node *head) { if (head == NULL) { return NULL; } while (head->next) { head = head->next; } return head; } Теперь добавим ещё две операции - pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение. Для вставки нового элемента в конец сначала получаем указатель на последний элемент, затем создаём новый элемент, присваиваем ему значение и перекидываем указатель next старого элемента на новый ? void pushBack(Node *head, int value) { Node *last = getLast(head); Node *tmp = (Node*) malloc(sizeof(Node)); tmp->value = value; tmp->next = NULL; last->next = tmp; } Односвязный список хранит адрес только следующего элемента. Если мы хотим удалить последний элемент, то необходимо изменить указатель next предпоследнего элемента. Для этого нам понадобится функция getLastButOne, возвращающая указатель на предпоследний элемент. ? 86 Node* getLastButOne(Node* head) { if (head == NULL) { exit(-2); } if (head->next == NULL) { return NULL; } while (head->next->next) { head = head->next; } return head; } Функция должна работать и тогда, когда список состоит всего из одного элемента. Вот теперь есть возможность удалить последний элемент. ? void popBack(Node **head) { Node *lastbn = NULL; //Получили NULL if (!head) { exit(-1); } //Список пуст if (!(*head)) { exit(-1); } lastbn = getLastButOne(*head); //Если в списке один элемент if (lastbn == NULL) { free(*head); *head = NULL; } else { free(lastbn->next); lastbn->next = NULL; } } Удаление последнего элемента и вставка в конец имеют сложность O(n). Можно написать алгоритм проще. Будем использовать два указателя. Один – текущий узел, второй – предыдущий. Тогда можно обойтись без вызова функции getLastButOne: ? int popBack(Node **head) { Node *pFwd = NULL; //текущий узел Node *pBwd = NULL; //предыдущий узел //Получили NULL if (!head) { exit(-1); } //Список пуст if (!(*head)) { exit(-1); } pFwd = *head; while (pFwd->next) { pBwd = pFwd; pFwd = pFwd->next; } 87 if (pBwd == NULL) { free(*head); *head = NULL; } else { free(pFwd->next); pBwd->next = NULL; } } Теперь напишем функцию insert, которая вставляет на n-е место новое значение. Для вставки, сначала нужно будет пройти до нужного узла, потом создать новый элемент и поменять указатели. Если мы вставляем в конец, то указатель next нового узла будет указывать на NULL, иначе на следующий элемент ? void insert(Node *head, unsigned n, int val) { unsigned i = 0; Node *tmp = NULL; //Находим нужный элемент. Если вышли за пределы списка, то выходим из цикла, //ошибка выбрасываться не будет, произойдёт вставка в конец while (i < n && head->next) { head = head->next; i++; } tmp = (Node*) malloc(sizeof(Node)); tmp->value = val; //Если это не последний элемент, то next перекидываем на следующий узел if (head->next) { tmp->next = head->next; //иначе на NULL } else { tmp->next = NULL; } head->next = tmp; } Покажем на рисунке последовательность действий Создали новый узел и присвоили ему значение После этого делаем так, чтобы новый элемент ссылался на следующий после n-го Теперь значение next нового узла хранит адрес того же узла, что и элемент, на который ссылается head Перекидываем указатель next n-го элемента на вновь созданный узел Теперь узел, адрес которого хранит head, указывает на новый узел tmp Функция удаления элемента списка похожа на вставку. Сначала получаем указатель на элемент, стоящий до удаляемого, потом перекидываем ссылку на следующий элемент за удаляемым, потом удаляем элемент. ? int deleteNth(Node **head, int n) { if (n == 0) { return pop(head); } else { Node *prev = getNth(*head, n-1); Node *elm = prev->next; int val = elm->value; prev->next = elm->next; free(elm); return val; 88 } } Рассмотрим то же самое в картинках. Сначала находим адреса удаляемого элемента и того, который стоит перед ним Для удаления узла, на который ссылается elm необходим предыдущий узел, адрес которого хранит prev После чего прокидываем указатель next дальше, а сам элемент удаляем. Прекидываем указатель на следующий за удалённым узел и освобождаем память Кроме создания списка необходимо его удаление. Так как самая быстрая функция у нас этот pop, то для удаления будем последовательно выталкивать элементы из списка. ? void deleteList(Node **head) { while ((*head)->next) { pop(head); *head = (*head)->next; } free(*head); } Вызов pop можно заменить на тело функции и убрать ненужные проверки и возврат значения ? void deleteList(Node **head) { Node* prev = NULL; while ((*head)->next) { prev = (*head); (*head) = (*head)->next; free(prev); } free(*head); } Осталось написать несколько вспомогательных функций, которые упростят и ускорят работу. Первая - создать список из массива. Так как операция push имеет минимальную сложность, то вставлять будем именно с её помощью. Так как вставка произойдёт задом наперёд, то массив будем обходить с конца к началу: ? void fromArray(Node **head, int *arr, size_t size) { size_t i = size - 1; if (arr == NULL || size == 0) { return; } do { push(head, arr[i]); } while(i--!=0); } И обратная функция, которая возвратит массив элементов, хранящихся в списке. Так как мы будем создавать массив динамически, то сначала определим его размер, а только потом запихнём туда значения. ? int* toArray(const Node *head) { int leng = length(head); int *values = (int*) malloc(leng*sizeof(int)); while (head) { values[--leng] = head->value; head = head->next; } return values; 89 } И ещё одна функция, которая будет печатать содержимое списка ? void printLinkedList(const Node *head) { while (head) { printf("%d ", head->value); head = head->next; } printf("\n"); } Теперь можно провести проверку и посмотреть, как работает односвязный список ? void main() { Node* head = NULL; int arr[] = {1,2,3,4,5,6,7,8,9,10}; //Создаём список из массива fromArray(&head, arr, 10); printLinkedList(head); //Вставляем узел со значением 333 после 4-го элемента (станет пятым) insert(head, 4, 333); printLinkedList(head); pushBack(head, 11); pushBack(head, 12); pushBack(head, 13); pushBack(head, 14); printLinkedList(head); printf("%d\n", pop(&head)); printf("%d\n", popBack(&head)); printLinkedList(head); //Удаляем пятый элемент (индексация с нуля) deleteNth(&head, 4); printLinkedList(head); deleteList(&head); getch(); } |