Лабораторная работа асд. Лабораторные работы_по_АСД. Дисциплина Алгоритмы и структуры данных Отчёт по лабораторной работе
 Скачать 3.09 Mb.
|
|
Блок схема алгоритма решения задачи представлена на рисунке 31:  Рисунок 30- Блок схема алгоритма решения задачи 2 Программа на C#: using System; using System.Collections.Generic; using System.Windows.Forms; namespace lr5_z2 { struct Book { public string Name; public string Autor; public decimal ID; public string Category; public string Genre; public string[] Additionally; public Book(string n, string au, decimal id, string c, string g, string[] a) { Name = n; Autor = au; ID = id; Category = c; Genre = g; Additionally = a; } } public partial class Form1 : Form { List Book book = new Book(); public Form1() { InitializeComponent(); initForm(); } private void initForm() { textBox1.Text = ""; textBox2.Text = ""; numericUpDown1.Value = 1; comboBox1.SelectedIndex = 0; domainUpDown1.SelectedIndex = 0; for (int i = 0; i < checkedListBox1.Items.Count; i++) { checkedListBox1.SetItemChecked(i, false); } listView1.Items .Clear(); treeView1.Nodes.Clear(); for (int i = 0; i < domainUpDown1.Items.Count; i++) { treeView1.Nodes.Add(new TreeNode(domainUpDown1.Items[i].ToString())); } for (int i = 0; i < books.Count; i++) { for (int j = 0; j < domainUpDown1.Items.Count; j++) { if (books[i].Category == domainUpDown1.Items[j].ToString()) { treeView1.Nodes[j].Nodes.Add(new TreeNode(books[i].Name)); } } } } private void button1_Click(object sender, EventArgs e) { book.Name = textBox1.Text; book.Autor = textBox2.Text; book.ID = numericUpDown1.Value; book.Genre = comboBox1.Text; book.Category = domainUpDown1.Text; List for (int i = 0; i < checkedListBox1.Items.Count; i++) { if (checkedListBox1.GetItemChecked(i)) { selected.Add(checkedListBox1.Items[i].ToString()); } } book.Additionally = selected.ToArray(); books.Add(book); initForm(); for (int i = 0; i < books.Count; i++) { string аdditionally = ""; for (int j = 0; j < books[i].Additionally.Length; j++) { аdditionally += books[i].Additionally[j] + ", "; } ListViewItem listViewItem = new ListViewItem(new string[] { books[i].Name, books[i].Autor, books[i].ID.ToString(), books[i].Genre, books[i].Category, аdditionally }); listView1.Items.Add(listViewItem); } } } } Скриншот результата работы программы представлен на рисунке 32.  Рисунок 31 - Скриншот результата работы программы задачи 2. Задача 3. 1. Cформировать линейный список методом вставки элемента в начало списка. Вывести список на экран. Описать функцию или процедуру, которая: а) определяет, является ли список L пустым; б) находит среднее арифметическое элементов непустого списка L (ТЭ=real); в) заменяет в списке L все вхождения E1 на E2; г) меняет местами первый и последний элементы непустого списка L; д) проверяет, упорядочены ли элементы списка L е) находит сумму последнего и предпоследнего элементов списка L, содержащего не менее двух элементов (ТЭ=integer). 2. Описать процедуру, которая формирует список L, включив в него по одному разу элементы, которые (Делаем используя цикл foreach): а) входят хотя бы в один из списков L1 и L2; б) входят одновременно в оба списка L1 и L2; в) входят в список L1, но не входят в список L2; г) входят в один из списков L1 и L2, но в то же время не входят в другой из них. 3. Описать процедуру, которая объединяет два упорядоченных по неубыванию списка L1 и L2 (ТЭ=геа1) в один упорядоченный по неубыванию список построив новый список L. Все используемые идентификаторы представлены в таблице 17 Таблица 17 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 33:     Рисунок 32- Блок схема алгоритма решения задачи 3 Программа на C#: using System; using System.Collections.Generic; namespace lr5_z3 { class Program { public static void Main() { int n; Console.WriteLine("1. Cформировать линейный список методом вставки элемента в начало списка"); Console.Write("Количество чисел в списке L: "); n = int.Parse(Console.ReadLine()); LinkedList list = new LinkedList(); if (n > 0) { Console.WriteLine("Введите элементы списка:"); for (int i = 1; i <= n; ++i) list.AddFront(int.Parse(Console.ReadLine())); } list.Print(); Console.WriteLine("а) определение, является ли список L пустым: "); if (list.isEmpty) Console.WriteLine("Список L пустой"); else { Console.WriteLine("Список L содержит " + list.Count + " элементов"); Console.WriteLine(); Console.WriteLine("б) среднее арифметическое элементов: " + list.Average()); Console.WriteLine(); Console.WriteLine("в) замена в списке L все вхождения E1 на E2: "); Console.Write("Введите значение E1: "); int E1 = int.Parse(Console.ReadLine()); Console.Write("Введите значение E2: "); int E2 = int.Parse(Console.ReadLine()); LinkedList list2 = list.Copy(); list2.Replace(E1, E2); list2.Print(); Console.WriteLine(); Console.WriteLine("г) замена местами первого и последнего элементов списка L"); LinkedList list3 = list.Copy(); list3.ReplaceFirstAndLast(); list3.Print(); Console.WriteLine(); Console.WriteLine("д) проверка на упорядоченность списка L"); if (list.isOrderAsc) Console.Write("Cписок L упорядочен по возрастанию"); else { if (list.isOrderDesc) Console.Write("Cписок L упорядочен по убыванию"); else Console.Write("Cписок L не упорядочен"); } Console.WriteLine(); if (list.Count > 1) { Console.WriteLine("е) сумма последнего и предпоследнего элементов списка L: " + list.SumLastAndPenultimate()); } Console.WriteLine(); } Console.WriteLine("2. Сформировать список L, включив в него по одному разу элементы. "); Console.Write("Количество чисел в списке L1: "); n = int.Parse(Console.ReadLine()); List Console.WriteLine("Введите элементы списка L1:"); for (int i = 0; i < n; ++i) list_z2_1.Add(int.Parse(Console.ReadLine())); Console.WriteLine("Список L1: " + string.Join(" ", list_z2_1)); Console.Write("Количество чисел в списке L2: "); n = int.Parse(Console.ReadLine()); List Console.WriteLine("Введите элементы списка L2:"); for (int i = 0; i < n; ++i) list_z2_2.Add(int.Parse(Console.ReadLine())); Console.WriteLine("Список L2: " + string.Join(" ", list_z2_2)); Console.Write("а) Список L из элементов, которые входят хотя бы в один из списков L1 и L2: " + string.Join(" ", Utils.Union(list_z2_1, list_z2_2))); Console.WriteLine(); Console.Write("б) Список L из элементов, которые входят одновременно в оба списка L1 и L2: " + string.Join(" ", Utils.Intersect(list_z2_1, list_z2_2))); Console.WriteLine(); Console.Write("в) Список L из элементов, которые входят в список L1, но не входят в список L2: " + string.Join(" ", Utils.IncludeL1NotIncludeL2(list_z2_1, list_z2_2))); Console.WriteLine(); Console.Write("г) Список L из элементов, входят в один из списков L1 и L2, но в то же время не входят в другой из них: " + string.Join(" ", Utils.SymmetricDifference(list_z2_1, list_z2_2))); Console.WriteLine(); Console.WriteLine("3. Объединение двух упорядоченных по неубыванию списка L1 и L2."); Console.Write("Количество чисел в списке L1: "); n = int.Parse(Console.ReadLine()); List Console.WriteLine("Введите элементы списка L1:"); for (int i = 0; i < n; ++i) list_z3_1.Add(double.Parse(Console.ReadLine())); list_z3_1.Sort(Utils.Compare); Console.WriteLine("Упорядоченный по неубыванию список L1 : " + string.Join(" ", list_z3_1)); Console.Write("Количество чисел в списке L2: "); n = int.Parse(Console.ReadLine()); List Console.WriteLine("Введите элементы списка L2:"); for (int i = 0; i < n; ++i) list_z3_2.Add(double.Parse(Console.ReadLine())); list_z3_2.Sort(Utils.Compare); Console.WriteLine("Упорядоченный по неубыванию список L2: " + string.Join(" ", list_z3_2)); Console.WriteLine("Объединенный упорядоченный по неубыванию список L: " + string.Join(" ", Utils.UnionSort(list_z3_1, list_z3_2))); Console.ReadKey(); } } } using System; namespace lr5_z3 { class LinkedList { private class Node { public int data; public Node next; public Node(int data, Node next) { this.data = data; this.next = next; } } private int count = 0; private Node head = null; private Node tail = null; //добавление элемента в начало списка public void AddFront(int data) { if (head == null) { head = new Node(data, null); tail = head; } else { Node new_node = new Node(data, head); head = new_node; } ++count; } //количество элементов списка public int Count { get { return count; } } //проверка списка на пустоту public bool isEmpty { get { return count == 0; } } //проверка на упорядоченность списка по возрастанию public bool isOrderAsc { get { bool isOrder = true; for (Node r = head; r != null; r = r.next) { if (r.next != null && r.data > r.next.data) { isOrder = false; break; } } return isOrder; } } //проверка на упорядоченность списка по убыванию public bool isOrderDesc { get { bool isOrder = true; for (Node r = head; r != null; r = r.next) { if (r.next != null && r.data < r.next.data) { isOrder = false; break; } } return isOrder; } } //среднее арифметическое элементов public double Average() { double sum = 0; for (Node r = head; r != null; r = r.next) sum += r.data; return sum / count; } // замена элемента другим значением public void Replace(int a, int b) { for (Node r = head; r != null; r = r.next) { if (r.data == a) { r.data = b; break; } } } //замена местами первого и последнего элементов списка public void ReplaceFirstAndLast() { int t = head.data; head.data = tail.data; tail.data = t; } //сумма последнего и предпоследнего элементов списка public int SumLastAndPenultimate() { int i = 0; int penultimate = 0; for (Node r = head; r != null; r = r.next) { if (i == count - 2) { penultimate = r.data; break; } i++; } return penultimate + tail.data; } //печать списка на экран public void Print() { Console.Write("Полученный список: "); for (Node r = head; r != null; r = r.next) Console.Write("{0} ", r.data); Console.WriteLine(); } //копирование списка public LinkedList Copy() { LinkedList copyList = new LinkedList(); for (Node r = head; r != null; r = r.next) { copyList.Add(r.data); } return copyList; } private void Add(int data) { if (head == null) { head = new Node(data, null); tail = head; } else { tail.next = new Node(data, null); tail = tail.next; } ++count; } } } using System.Collections.Generic; namespace lr5_z3 { class Utils { public static List { List list1.ForEach(delegate (int item) { if (!list.Contains(item)) { list.Add(item); } }); list2.ForEach(delegate (int item) { if (!list.Contains(item)) { list.Add(item); } }); return list; } public static List { List list1.ForEach(delegate (int item) { if (!list.Contains(item) && list2.Contains(item)) { list.Add(item); } }); return list; } public static List { List list1.ForEach(delegate (int item) { if (!list.Contains(item) && !list2.Contains(item)) { list.Add(item); } }); return list; } public static List { List list1.ForEach(delegate (int item) { if (!list.Contains(item) && !list2.Contains(item)) { list.Add(item); } }); list2.ForEach(delegate (int item) { if (!list.Contains(item) && !list1.Contains(item)) { list.Add(item); } }); return list; } public static int Compare(double x, double y) { if (x > y) { return 1; } else { if (x < y) { return -1; } } return 0; } public static List { List int k = 0; for (int i = 0; i < list1.Count; i++) { for (int j = k; j < list2.Count; j++) { if (list1[i] < list2[j]) { list.Add(list1[i]); break; } else { list.Add(list2[j]); k = j + 1; } } } for (int j = k; j < list2.Count; j++) { list.Add(list2[j]); } return list; } } } Скриншот результата работы программы представлен на рисунке 34.    Рисунок 33 - Скриншот результата работы программы задачи 3. Задача 4. Реализовать стек, очередь, дек. Проверить работоспособность. Все используемые идентификаторы представлены в таблице 18 Таблица 18 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 35:   Рисунок 34 - Блок схема алгоритма решения задачи 4 Программа на C#: using System; namespace lr5_z4 { class Program { static void Main(string[] args) { Console.WriteLine("Стек"); NodeStack //заполняем стек stack.Push("первый"); stack.Push("второй"); stack.Push("третий"); stack.Push("четвертый"); Console.WriteLine("Первоначальный стек:"); foreach (var item in stack) Console.WriteLine(item); Console.WriteLine(); string header = stack.Peek(); Console.WriteLine($"Верхушка стека: {header}"); //извлекаем элемент стека stack.Pop(); Console.WriteLine("Стек после извлечения элемента:"); foreach (var item in stack) Console.WriteLine(item); Console.WriteLine(); Console.WriteLine("Очередь"); Queue //заполняем очередь queue.Enqueue("первый"); queue.Enqueue("второй"); queue.Enqueue("третий"); queue.Enqueue("четвертый"); Console.WriteLine("Первоначальная очередь:"); foreach (string item in queue) Console.WriteLine(item); Console.WriteLine(); string firstItem = queue.Dequeue(); Console.WriteLine($"Извлеченный элемент: {firstItem}"); Console.WriteLine("Очередь после извлечения элемента:"); foreach (string item in queue) Console.WriteLine(item); Console.WriteLine(); Console.WriteLine("Дек"); Deque //заполняем дек deque.AddFirst("первый"); deque.AddLast("второй"); Console.WriteLine("Первоначальный дек:"); foreach (string s in deque) Console.WriteLine(s); Console.WriteLine(); deque.AddFirst("перед первым"); //добавляем в начало Console.WriteLine("Дек после добавления в начало:"); foreach (string s in deque) Console.WriteLine(s); Console.WriteLine(); deque.AddLast("третий"); //добавляем в конец Console.WriteLine("Дек после добавления в конец:"); foreach (string s in deque) Console.WriteLine(s); Console.WriteLine(); string removedItemFirst = deque.RemoveFirst(); Console.WriteLine("Удален первый элемент: {0}", removedItemFirst); string removedItemLast = deque.RemoveLast(); Console.WriteLine("Удален последний элемент: {0}", removedItemLast); Console.WriteLine(); Console.WriteLine("Дек после удаления из начала и конца:"); foreach (string s in deque) Console.WriteLine(s); Console.ReadKey(); } } } Класс Node: namespace lr5_z4 { public class Node { public Node(T data) { Data = data; } public T Data { get; set; } public Node } } Класс NodeStack: using System; using System.Collections.Generic; using System.Collections; namespace lr5_z4 { public class NodeStack { Node int count; public bool IsEmpty { get { return count == 0; } } public int Count { get { return count; } } public void Push(T item) { // увеличиваем стек Node node.Next = head; // переустанавливаем верхушку стека на новый элемент head = node; count++; } public T Pop() { // если стек пуст, выбрасываем исключение if (IsEmpty) throw new InvalidOperationException("Стек пуст"); Node head = head.Next; // переустанавливаем верхушку стека на следующий элемент count--; return temp.Data; } public T Peek() { if (IsEmpty) throw new InvalidOperationException("Стек пуст"); return head.Data; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator { Node while (current != null) { yield return current.Data; current = current.Next; } } } } Класс Queue: using System; using System.Collections; using System.Collections.Generic; namespace lr5_z4 { public class Queue { Node Node int count; // добавление в очередь public void Enqueue(T data) { Node Node tail = node; if (count == 0) head = tail; else tempNode.Next = tail; count++; } // удаление из очереди public T Dequeue() { if (count == 0) throw new InvalidOperationException(); T output = head.Data; head = head.Next; count--; return output; } // получаем первый элемент public T First { get { if (IsEmpty) throw new InvalidOperationException(); return head.Data; } } // получаем последний элемент public T Last { get { if (IsEmpty) throw new InvalidOperationException(); return tail.Data; } } public int Count { get { return count; } } public bool IsEmpty { get { return count == 0; } } public void Clear() { head = null; tail = null; count = 0; } public bool Contains(T data) { Node while (current != null) { if (current.Data.Equals(data)) return true; current = current.Next; } return false; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator { Node while (current != null) { yield return current.Data; current = current.Next; } } } } Класс DoublyNode: namespace lr5_z4 { public class DoublyNode { public DoublyNode(T data) { Data = data; } public T Data { get; set; } public DoublyNode public DoublyNode } } Класс Deque: using System; using System.Collections.Generic; using System.Collections; namespace lr5_z4 { public class Deque { DoublyNode DoublyNode int count; // количество элементов в списке // добавление элемента в конец public void AddLast(T data) { DoublyNode if (head == null) head = node; else { tail.Next = node; node.Previous = tail; } tail = node; count++; } // добавление элемента в начало public void AddFirst(T data) { DoublyNode DoublyNode node.Next = temp; head = node; if (count == 0) tail = head; else temp.Previous = node; count++; } // удаление элемента с начала public T RemoveFirst() { if (count == 0) throw new InvalidOperationException(); T output = head.Data; if (count == 1) { head = tail = null; } else { head = head.Next; head.Previous = null; } count--; return output; } // удаление элемента с конца public T RemoveLast() { if (count == 0) throw new InvalidOperationException(); T output = tail.Data; if (count == 1) { head = tail = null; } else { tail = tail.Previous; tail.Next = null; } count--; return output; } // получение первого элемента public T First { get { if (IsEmpty) throw new InvalidOperationException(); return head.Data; } } // получение последнего элемента public T Last { get { if (IsEmpty) throw new InvalidOperationException(); return tail.Data; } } public int Count { get { return count; } } public bool IsEmpty { get { return count == 0; } } public void Clear() { head = null; tail = null; count = 0; } public bool Contains(T data) { DoublyNode while (current != null) { if (current.Data.Equals(data)) return true; current = current.Next; } return false; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator { DoublyNode while (current != null) { yield return current.Data; current = current.Next; } } } } Скриншот результата работы программы представлен на рисунке 36.    Рисунок 35 - Скриншот результата работы программы задачи 3. Задача 5. В поле ListBox вывести в виде списка элементы массива строк. Реализовать ввод массива в listbox. Все используемые идентификаторы представлены в таблице 19 Таблица 19 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 37:  Рисунок 36- Блок схема алгоритма решения задачи 5 Программа на C#: using System; using System.Windows.Forms; namespace lr5_var1_z5 { public partial class Form1 : Form { string[] strings = { }; public Form1() { InitializeComponent(); listBox1.Items.AddRange(strings); } private void button1_Click(object sender, EventArgs e) { listBox1.Items.Add(textBox1.Text); textBox1.Text = ""; } } } Скриншот результата работы программы представлен на рисунке 38.  Рисунок 37 - Скриншот результата работы программы задачи 5. Задача 6. Считать список из файла1. Изменить его (любым образом). Вывести в файл2. А из файла2 вывести данные в ListBox. Все используемые идентификаторы представлены в таблице 20 Таблица 20 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 39:  Рисунок 38- Блок схема алгоритма решения задачи 6 Программа на C#: using System; using System.Text; using System.Windows.Forms; using System.IO; namespace lr5_var1_z6 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { listBox1.Items.AddRange(File.ReadAllLines("файл1.txt", Encoding.UTF8)); string[] strings = new string[listBox1.Items.Count + 1]; for (int i = 0; i < listBox1.Items.Count; i++) strings[i] = listBox1.Items[i].ToString(); strings[listBox1.Items.Count] = "12. Остров в море."; System.IO.StreamWriter SaveFile = new System.IO.StreamWriter("файл2.txt"); foreach (var item in strings) { SaveFile.WriteLine(item); } SaveFile.Close(); listBox2.Items.AddRange(File.ReadAllLines("файл2.txt", Encoding.UTF8)); } private void button2_Click(object sender, EventArgs e) { listBox1.Items.Clear(); listBox2.Items.Clear(); } } } Скриншот результата работы программы представлен на рисунке 40.  Рисунок 39 - Скриншот результата работы программы задачи 6. Задача 7. Считать из ListBox1 информацию в файл. В файле, между первой и второй строкой, вставить строку «Привет!». Считать из файла в список List. Отсортировать строки списка. Используя метод BinarySearch() определить, есть ли строка «Привет!» в списке. Если есть, добавить в этой строке «, Коля», чтобы получилось «Привет, Коля!» и вывести сообщение в окно сообщений «Ура, добавили!». Получившийся список вывести в ListView добавив каждой строке изображения. Все используемые идентификаторы представлены в таблице 21 Таблица 21 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 41:  Рисунок 40- Блок схема алгоритма решения задачи 7 Программа на C#: using System; using System.Collections.Generic; using System.Text; using System.Windows.Forms; using System.IO; namespace lr5_z7 { public partial class Form1 : Form { string[] strings = { "первый", "второй", "третий", "четвертый", "пятый" }; public Form1() { InitializeComponent(); listBox1.Items.AddRange(strings); } private void button1_Click(object sender, EventArgs e) { Form2 Form2 = new Form2(); //записываем в файл из listBox1 System.IO.StreamWriter SaveFile = new System.IO.StreamWriter("файл.txt"); foreach (var item in listBox1.Items) { SaveFile.WriteLine(item); } SaveFile.Close(); // считываем из файла и добавляем строку между первой и второй string[] text = System.IO.File.ReadAllLines("файл.txt", Encoding.UTF8); text[0] = text[0] + Environment.NewLine + "Привет!"; System.IO.StreamWriter SaveFile2 = new System.IO.StreamWriter("файл.txt"); foreach (var item in text) { SaveFile2.WriteLine(item); } SaveFile2.Close(); List listBox2.Items.AddRange(File.ReadAllLines("файл.txt", Encoding.UTF8)); list.Sort();//сортировка int index = list.BinarySearch("Привет!"); // BinarySearch if (index >= 0) { list[index] = list[index].Insert(list[index].IndexOf("!"), ", Коля"); Form2.label1.Text = "Ура, добавили!"; } else { Form2.label1.Text = "Не добавили :("; } Form2.ShowDialog(); for (int i = 0; i < list.Count; i++) { ListViewItem listViewItem = new ListViewItem(new string[] { "", list[i]}); listViewItem.ImageIndex = 0; listView1.Items.Add(listViewItem); } } private void button2_Click(object sender, EventArgs e) { listBox1.Items.Clear(); listBox2.Items.Clear(); listView1.Items.Clear(); listBox1.Items.AddRange(strings); } } } Скриншот результата работы программы представлен на рисунке 42.  Рисунок 41 - Скриншот результата работы программы задачи 7. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||