Добавлен: 09.11.2023
Просмотров: 24
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
ЧЕБОКСАРСКИЙ ИНСТИТУТ (ФИЛИАЛ)
МОСКОВСКОГО ПОЛИТЕХНИЧЕСКОГО УНИВЕРСИТЕТА
Кафедра Информационных технологий, электроэнергетики и систем
управления
КУРСОВАЯ РАБОТА
по дисциплине: Структуры и алгоритмы обработки данных
на тему: «Исследование кольцевых структур»
Выполнил:
студент группы: 203-Ч091-3з
Кольцов Никита Вячеславович
учебный шифр: 18051
Проверил(а):
доцент Скипина Л. Н.
Чебоксары 2023
Содержание
Введение 3
1.Описание предметной области 4
2.Технология разработки приложения 9
3.Результаты работы программы 12
4.Руководство пользователя 13
Заключение 14
Список использованной литературы 15
Приложение 16
Введение
Необходимым условием обучения предмету алгоритмы и структуры данных является наличие наглядного материала демонстрирующего основные принципы работы с данными различной структуры.
Целью данной работы были изучение принципов и реализация алгоритмов создания и обработки кольцевых структур.
В соответствии с целью работы были сформулированы следующие задачи:
-
Изучить методы сортировки циклических списков. -
Провести исследование методов сортировки. -
Разработать алгоритм создания и работы со структурой данных циклического типа. -
Спроектировать структуру программного изделия. -
Создать программный продукт. -
Отладить и протестировать готовую программу.
В первой главе обосновывается актуальность задачи, формируется объект исследования, кратко обосновывается причина выбора в качестве средства программирования языка C#.
Во второй главе рассматриваются общие принципы кольцевой структуры, описывается алгоритм работы программы, используемые классы, функции. Рассматриваются наборы входных и выходных данных.
В третьей главе подробно описывается технология работы с программным продуктом, возможные ошибки и способы их устранения.
Данная программа позволяет дать наглядное представление внутреннего размещения в памяти циклической структуры данных.
Заключение содержит выводы по результатам работы, в нём описываются возможные способы использования программы.
алгоритм кольцевой структура программа
-
Описание предметной области
В настоящее время есть несколько видов различных структур данных: массивы, списки, очереди, деревья, стеки. Каждая из них имеет свои особенности, например, стеки имеют возможность обращения только к верхнему элементу, массивы позволяют обращаться к любому элементу по индексу, деревья представляют собой динамическую структуру данных, в которой заранее невозможно представить как она будет выглядеть, ясно лишь, что они имеют один узел, на который не ведёт ни одной ссылки - корень. Списки и очереди – близкие типы данных, однако если в списке последовательно проходя по элементам можно дойти до любого элемента и произвести над ним операции: чтения, удаления, вставить новый элемент, то в очереди возможно чтение и удаление только с головы, а добавление – в хвост.
Алгоритм циклической структуры – это алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз.
Многократное повторение последовательности действий называется циклом, а многократно повторяющиеся действия –телом цикла.
Изучение циклов демонстрирует учащимся главное преимущество компьютера перед человеком – выполнение большого числа действий за короткое время. Ведь даже весьма короткий циклический алгоритм, составить который не так уж долго, при исполнении может потребовать выполнения нескольких сотен действий, с которыми компьютер справится намного быстрее, чем человек.
Кольцевой буфер, или циклический буфер — это структура данных, использующая единственный буфер фиксированного размера, как будто бы после последнего элемента сразу же снова идет первый. Такая структура легко предоставляет возможность буферизации потоков данных.
Кольцевой буфер находит очень широкое применение в том числе при программировании МК. Кольцевые буферы часто используют для организации различных очередей сообщений и буферов приёма-передачи различных коммуникационных интерфейсов. Популярность КБ обусловлена тем, что это один из самых простых и эффективных способов организовать FIFO(англ. first in — first out, «первым пришёл — первым вышел») без использования динамической памяти. Существует множество разновидностей КБ.
Кольцевой буфер создается пустым, с некоторой заранее определенной длиной. Например, это семиэлементный буфер:
Рисунок 1
Предположим, что в середину буфера записывается 1 (в кольцевом буфере точная начальная ячейка не имеет значения):
Рисунок 2
Затем предположим, что после единицы были добавлены ещё два элемента — 2 и 3:
Рисунок 3
Если после этого два элемента должны быть удалены из буфера, то выбираются два наиболее старых элемента. В нашем случае удаляются элементы 1 и 2, в буфере остается только 3:
Рисунок 4
Если в буфере находится 7 элементов, то он заполнен:
Рисунок 5
Если продолжить запись в буфер, не принимая во внимание его заполненность, то новые данные начнут перезаписывать старые данные. В нашем случае, добавляя элементы A и B мы перезапишем 3 и 4:
Рисунок 6
В другом варианте реализации процедуры, обслуживающие буфер могут предотвратить перезапись данных и вернуть ошибку или выбросить исключение. Перезапись или её отсутствие оставляется на усмотрение обслуживающих процедур буфера или приложения, использующего кольцевой буфер.
Наконец, если теперь удалить из буфера два элемента, то удалены будут не 3 и 4, а 5 и 6, потому что A и B перезаписали элементы 3 и 4; буфер придет в состояние:
Рисунок 7
Кольцевой односвязный список получается из обычного односвязного списка путем присваивания указателю последнего элемента списка значения указателя начала списка (рис. 8).
Рисунок 8
Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности. Дело в том, что по однонаправленному списку можно двигаться только в одном направлении, от заглавного звена к последнему звену списка. Между тем нередко возникает необходимость произвести какую-либо обработку элементов, предшествующих элементу с заданным свойством. Однако после нахождения элемента с этим свойством в односвязном списке у нас нет возможности получить достаточно удобный и быстрый доступ к предыдущим элементам. Для достижения этой цели придется усложнить алгоритм, что неудобно и нерационально.
Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено списка. Динамическая структура, состоящая из элементов такого типа, называется двунаправленным или двусвязным списком.
Двусвязный список характеризуется тем, что у любого элемента есть два указателя.
Один указывает на предыдущий (левый) элемент (L), другой указывает на последующий (правый) элемент (R).
Фактически двусвязный список это два односвязных списка с одинаковыми элементами, записанные в противоположной последовательности (рис 9).
Рисунок 9
Кольцевые двусвязные списки получают следующим образом: в качестве значения поля R последнего элемента принимают ссылку на первый элемент, а в качестве значения поля L первого элемента - ссылку на последний элемент (рис. 10).
Рисунок 10
-
Технология разработки приложения
-
Алгоритм работы программы
Алгоритм работы программы наглядно представлен в виде блок схемы (рис. 11)
Блок схема операции добавление элемента в кольцевой список. (рис. 12)
-
Описание библиотечных функций
Класс создания кольцевого списка: public partial class Form1: Form
questionList = new List
private void Check(); - сортировка по возрастанию
private void Print(); - проверка на отсутствие ячеек
private void button1_Click_1(object sender, EventArgs e); - навигация по ячейкам
private void button3_Click_1(object sender, EventArgs e); - замена содержимого ячейки
private void button2_Click(object sender, EventArgs e); - удаление ячейки
private void button3_Click(object sender, EventArgs e); - добавление ячейки
-
Результаты работы программы
Режим создания кольцевого списка
На рисунке 13 и рисунке 14, изображен результат работы программы создания кольцевого списка.
Рисунок 13 вид программы
Рисунок 14 замена данных первого элемента
-
Руководство пользователя
1. Ввести значение и нажать «Изменить данные»
2. Далее вводить значения добавляемых элементов и выбрать «Добавить элемент»
3. Навигация по всем существующим и добавленным ячейкам происходит с помощью кнопки «Следующая ячейка»
4. При необходимости можем удалить ячейку памяти.
Заключение
В результате проделанной работы:
-
изучены разделы дисциплины «Алгоритмы и структуры данных» в объёме, необходимом для написания программного продукта; -
исследованы свойства циклических структур; -
разработан алгоритм задачи; -
спроектирована структура программного изделия; -
разработан алгоритм отображения кольцевого списка; -
на языке C# разработана программа отображения списка;
При изучении темы были сделаны выводы о структуре кольцевого списка.
Циклические (кольцевые) списки проще в реализации, имеют более высокую скорость работы.
Задачи, сформулированные в данном курсовом проекте, были выполнены в полном объеме.
Список использованной литературы
1. Лойко В.И. Структуры и алгоритмы обработки данных: учебное пособие. Краснодар: КубГАУ, 2000. 261 с.
2. Лойко В.И. Алгоритмы и структуры данных: Курс лекций. Краснодар: КубГАУ, 2006. 120 с.
3. Ахо А. и др. Структуры данных и алгоритмы /А. Ахо, Дж. Хопкрофт, Дж. Ульман: Пер. с англ. М.: Вильямс, 2000. 384 с.
4. Хусаинов Б.С. Структуры и алгоритмы обработки данных, Примеры на языке Си (CD): Учебное пособие. М.: Финансы и статистика, 2004. 464 с.
Приложение
Листинг программы кольцевой структуры данных
using System;
using System.Collections.Generic;
using System.Windows.Forms;
namespace WindowsFormsApplication1
{
public partial class Form1: Form
{
List
int currentQuestionIndex = 0;
public Form1()
{
InitializeComponent();
questionList = new List
{
new Question(0, "Первый элемент"),
new Question(1, "Второй элемент"),
new Question(2, "Третий элемент"),
new Question(3, "Четвертый элемент"),
new Question(4, "Пятый элемент")
};
textBox1.Text = questionList[currentQuestionIndex].Text;
}
private void Check()
{
if (currentQuestionIndex >= questionList.Count)
currentQuestionIndex = 0;
}
private void Print()
{
if (questionList.Count > 0)
textBox1.Text = questionList[currentQuestionIndex].Text;
else
textBox1.Text = "<Список пуст>";
}
private void button1_Click_1(object sender, EventArgs e)
{
currentQuestionIndex++;
Check();
Print();
}
private void button2_Click_1(object sender, EventArgs e)
{
if (questionList.Count > 0)
questionList.RemoveAt(currentQuestionIndex);
Check();
Print();
}
private void button3_Click(object sender, EventArgs e)
{
questionList.Insert(currentQuestionIndex, new Question(currentQuestionIndex,textBox2.Text));
if (questionList.Count > 0)
questionList.RemoveAt(currentQuestionIndex+1);
}
private void button4_Click(object sender, EventArgs e)
{
questionList.Insert(currentQuestionIndex, new Question(currentQuestionIndex, textBox3.Text));
}
}
public struct Question
{
private int index;
private string text;
public Question(int index, string text)
{
this.index = index;
this.text = text;
}
public int Index { get { return this.index; } }
public string Text { get { return this.text; } }
}
}