СДлб3
.docxМинистерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем (БИС)
АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ
Отчет по практической работе №3 по дисциплине «Структуры данных»
Студент гр. 731-2
А.С. Батаев
Принял:
преподаватель КИБЭВС
Д.Р. Уразаев
Томск 2022
СОДЕРЖАНИЕ
Y
1 Введение 3
2 Ход работы 4
2.1 Удаление четных чисел из списка 7
2.2 Удаление повторяющихся чисел из списка 9
Заключение 13
1 Введение
Данная работа посвящена реализации динамического списка при помощи двух классов. Во время работы будет реализован односвязный список на языке программирования С#
В качестве ТЗ было получено задание:
Реализуемый список должен быть циклическим. Дополнительно реализовать методы: удалить из списка четные элементы. Удалить из списка повторяющиеся элементы.
2 Ход работы
Весь код программы представлен в приложении А.
По заданию был реализован класс Node, который отвечает за инициализацию и переопределение списков. Класс Node представлен на Рисунке 2.1.
Рисунок 2.1- Класс Node
Далее по заданию был реализован публичный класс List (Рисунок 2.2).
Рисунок 2.2- Класс List
Далее для работы методов класса были созданы различные переменные (Рисунок 2.3)
Рисунок 2.3- Переменные
Remove - метод для удаления данных. На вход поcтупает элемент, который требуется найти и удалить. Пока есть элементы для проверки цикл while будет работать, если находится элемент, который требуется удалить, то идёт проверка является ли этот элемент началом списка. Если элемент является началом списка, то происходит переопределение значения first на след. элемент, если нет, то текущий элемент перед удалённым будет ссылаться на следующий элемент после удалённого, если элемент был последним, то конец списка будет обозначен идущим за удалённым элементом.
Рисунок 2.5- Класс Remove
Очистка списка осуществляется обнулением элемента first и last. Когда у списка не остаётся обозначения начала и конца, его длина сокращается до 0, далее сборщик мусора сам удаляет все остальные элементы списка (Рисунок 2.7).
Рисунок 2.7- Clear
Поиск элемента осуществляется по принципу кода для удаления. Список проверяется до конца, если находится элемент, то возвращается значение true, если к концу списка элемент не находится, то возвращается значение false (Рисунок 2.8).
Рисунок 2.8- Поиск элемента
2.1 Удаление четных чисел из списка
Метод проверяет значение каждого элемента на четность и удаляет в случае когда число без остатка делится на два (Рисунок 2.9).
Рисунок 2.9- Метод Delchet
Результат работы программы представлен на рисунке 2.11
Рисунок 2.10-Результат работы программы
Блок-схема алгоритма изображена на рисунке 2.11.
Рисунок 2.11-Блок схема алгоритма
2.2 Удаление повторяющихся чисел из списка
Метод проверяет каждое число с каждым и если числа повторяются удаляются оба числа на рисунке (Рисунок 2.12).
Рисунок 2.12-Метод Delclon
Результат работы программы представлен на рисунке 2.13
Рисунок 2.13-Результат работы программы
Блок-схема изображена на рисунке 2.1
Рисунок 2.14-Блок схема алгоритма
Блок-схема вспомогательного алгоритма изображена на рисунке 2.15
Рисунок 2.15-Блок схема алгоритма
Заключение
Во время лабораторной работы была проведена реализация динамического списка при помощи двух классов. Были получены навыки работы с динамическими списками на базе языка программирования c#.
Приложение А (обязательное)
using System.Collections;
using System;
using System.Collections.Generic;
namespace sd3
{
public class Node<T>
{
public Node(T data)
{
Data = data;
}
public T Data { get; set; }
public Node<T> Next { get; set; }
}
public class List<T> : IEnumerable<T>
{
Node<T> first;
Node<T> last;
int count;
public void Add(T data)
{
Node<T> node = new Node<T>(data);
// если список пуст if (first == null)
if (first == null)
{
first = node;
last = node;
last.Next = first;
}
else
{
node.Next = first;
last.Next = node;
last = node;
}
count++;
}
public bool Remove(T data)
{
Node<T> current = first;
Node<T> previous = null;
if (IsEmpty) return false;
do
{
if (current.Data.Equals(data))
{
if (previous != null)
{
previous.Next = current.Next;
if (current == last)
last = previous;
}
else
{
if (count == 1)
{
first = last = null;
}
else
{
first = current.Next;
last.Next = current.Next;
}
}
count--;
return true;
}
previous = current;
current = current.Next;
} while (current != first);
return false;
}
public bool IsEmpty { get { return count == 0; } }
public void Clear()
{
first = null;
last = null;
count = 0;
}
public int Count { get { return count; } }
public bool Contains(T data)
{
Node<T> current = first;
if (current == null) return false;
do
{
if (current.Data.Equals(data)) return true;
current = current.Next;
}
while (current != first);
return false;
}
IEnumerator IEnumerable.GetEnumerator()
{
return ((IEnumerable)this).GetEnumerator();
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
Node<T> current = first;
do
{
if (current != null)
{
yield return current.Data;
current = current.Next;
}
}
while (current != first);
}
}
}
class Program
{
static void Main(string[] args)
{
var list = new List<int>();
var rand = new Random();
int[] spisok = new int[10];
for (int i = 0; i < spisok.Length; i++)
{
spisok[i] = rand.Next(1, 9);
}
foreach (var item in spisok)
{
list.Add(item);
}
foreach (var item in list)
{
Console.WriteLine(item);
}
Console.WriteLine("\nЧто вы хотите сделать с этим списком?");
Console.WriteLine("Удалить четные элементы - 1, удалить повторяющиеся элементы - 2 ");
switch (int.Parse(Console.ReadLine()))
{
case 1:
delchet(list);
break;
case 2:
delclon(list);
break;
}
}
static void delchet(List<int> list)
{
int[] f = new int[list.Count];
int k = 0;
foreach (var item in list)
{
f[k] = item;
k++;
}
for (int i = 0; i < f.Length; i++)
{
if (f[i] % 2 == 0)
{
list.Remove(f[i]);
}
}
Enter(list);
}
static void delclon(List<int> list)
{
int[] f = new int[list.Count];
int k = 0;
foreach (var item in list)
{
f[k] = item;
k++;
}
for (int i = 0; i < f.Length; i++)
{
for (int j = 1; j < f.Length; j++)
{
if (i != j)
{
if (f[i] == f[j])
{
list.Remove(f[i]);
list.Remove(f[j]);
}
}
}
}
Enter(list);
}
static void Enter(List<int> list)
{
Console.WriteLine("\n После операций: \n");
foreach (var t in list)
{
Console.WriteLine(t);
}
}
}